blqsort: A C++ Quicksort Optimized via Branchless Partitioning and Sorting Networks

In benchmarks conducted on an Apple M1 system, the blqsort algorithm sorted 50 million random doubles in 0.68 seconds, outperforming the standard C++ library's std::sort, which took 1.33 seconds. This performance gain is driven by a series of optimizations designed to minimize CPU pipeline stalls and handle specific data distributions more efficiently than general-purpose sorting implementations.

This table provides the empirical evidence for the performance gains mentioned in the introduction.

This visual supports the discussion on how blqsort handles different data distributions and sizes.

Eliminating Branch Mispredictions

Standard quicksort implementations often rely on 'if' conditions to partition data. On modern CPUs, if the data is randomly distributed, these conditions become unpredictable for the branch predictor, forcing the processor to flush its pipeline and restart execution.

blqsort addresses this by using a branchless approach. Instead of a conditional jump, it uses a conditional increment instruction to move elements. While this introduces an unconditional memory write for every element, the author notes that the overhead of the write is significantly lower than the performance loss caused by frequent branch mispredictions.

This code snippet illustrates the transition from standard conditional logic to the optimized blqsort structure.

“The key concepts of blqsort are branchless partitioning, sorting networks for small partitions, and good pivot selection.”

— A Fast Quicksort

Sorting Networks for Small Partitions

For very small partitions, such as those with fewer than 20 elements, traditional quicksort is less efficient than simpler methods. blqsort replaces these with sorting networks, which use a fixed sequence of comparisons and swaps to order elements.

The implementation includes specific logic for partition sizes up to 16. By using these networks, the algorithm avoids the overhead of recursive calls and provides a highly optimized path for the 'base cases' of the sorting process.

Pivot Selection and Edge Case Handling

To maintain high performance across different data types, blqsort employs a multi-step pivot selection process. It determines several medians from the partition to calculate a final median, ensuring a more even distribution of data during the partitioning step.

The algorithm also includes safeguards for difficult inputs. If the data distribution remains uneven—often due to many identical elements—the system switches to heap sort. Additionally, it identifies and groups duplicate keys to maintain efficiency.

Performance Trade-offs and Limitations

The primary trade-off for blqsort's speed is the use of branchless logic, which requires the compiler to perform writes to memory even when the condition is not met. The compiler cannot automatically optimize this into a conditional write because it cannot guarantee that such a write is safe for the allocated buffer.

While blqsort outperforms std::sort on random data, its relative advantage varies by architecture. For example, on x86 systems, the performance gap between blqsort and std::sort was observed to be approximately 10%.

This table illustrates the performance trade-offs and architectural variations discussed in the final section.

Chart drawn by HN Digest from figures reported by tiki.li; values are shown as written in the source.