BlockQuicksort: How Branch Mispredictions don't affect Quicksort

Stefan Edelkamp, Armin WeißarXiv 2016 · OpenReview

TL;DR

This paper introduces BlockQuicksort, a novel in-place sorting algorithm that significantly reduces branch mispredictions, a major performance bottleneck in traditional Quicksort. By processing data in blocks and decoupling comparison from element rearrangement, BlockQuicksort achieves up to an 88% speedup over standard std::sort on random integer data, while maintaining competitive performance across various data types and input distributions.

What Problem Does This Paper Address?

Modern CPUs rely heavily on pipelining to achieve high performance. However, conditional branches in code (like if statements) can disrupt this pipeline if the processor mispredicts which path to take. Quicksort, despite its efficiency, is notorious for its heavy reliance on conditional branches during the partitioning phase. Each element is compared to a pivot, and the outcome dictates whether it moves left or right. On processors with deep pipelines, these branch mispredictions lead to significant performance degradation. While previous work has explored ways to mitigate this, such as using skewed pivots or switching to other algorithms, an efficient in-place sorting algorithm that fundamentally addresses branch mispredictions in Quicksort remained an open challenge.

Methods

The core innovation of BlockQuicksort lies in its "block partitioning" strategy. Instead of comparing an element to the pivot and immediately deciding where to move it (which involves a conditional branch), BlockQuicksort processes data in fixed-size blocks (e.g., 128 elements).

  1. Scanning Phase: For each block, elements are compared to the pivot. Instead of performing a swap or moving the element, the indices of elements that need to be moved (e.g., elements smaller than the pivot) are stored in temporary buffers. This phase avoids conditional branches based on comparison outcomes.
  2. Rearrangement Phase: Once a block (or multiple blocks) has been scanned, the elements are rearranged in a second pass using the stored indices. This phase also aims to minimize conditional branches.

By separating the comparison logic from the data movement logic, BlockQuicksort effectively eliminates most of the branch mispredictions that plague standard Quicksort. The authors also incorporate standard Quicksort optimizations like switching to Insertion Sort for small subarrays and using median-of-three for pivot selection.

Datasets

The paper does not describe specific datasets used for training. For evaluation, they used:

  • Random Permutations: Generated using std::mt19937 (Mersenne Twister).
  • Various Data Types:
    • int: Signed 32-bit integers.
  • Vector: 10-dimensional arrays of 64-bit floating-point numbers (doubles), ordered by Euclidean norm.
  • Record: 21-dimensional arrays of 32-bit integers, ordered by the first component.
  • Specific Input Structures:
    • Sorted arrays.
  • Reversed arrays.
  • Arrays with long sorted runs.
  • Arrays with many duplicates (constant, patterned, and random 0-1 values).
  • Arrays with a specific number of inversions.

No new benchmarks were introduced; they compared against standard library implementations and other well-known sorting algorithms.

Key Insights and Ideas

  • Decoupling Comparison and Movement is Key: The most significant insight is that by separating the "what to move" (comparison results stored in buffers) from the "how to move" (rearrangement using stored indices), Quicksort's primary source of branch mispredictions can be eliminated.
  • Block Processing for Predictability: Processing data in blocks allows for a more predictable execution flow. Even though the rearrangement phase still involves some logic, the bulk of the unpredictable branching is removed.
  • Trade-off between Block Size and Cache: While larger block sizes can reduce the number of branch mispredictions, they can also lead to cache misses if the blocks exceed cache capacity. The optimal block size is data-type dependent.
  • Skewed Pivots vs. Median Pivots: Classic Quicksort benefits from skewed pivots to make branches more predictable. BlockQuicksort, however, performs best with median pivots, suggesting that its branch-avoidance mechanism makes it less sensitive to pivot distribution.
  • Insertionsort's Role: While Insertionsort itself incurs some branch mispredictions, its use as a recursion stopper for small subarrays contributes significantly to the overall low branch misprediction count of BlockQuicksort.

Key Results

  • Speedup: BlockQuicksort achieved up to an 88% speed increase (or 45ns per element) compared to GCC's std::sort (85ns per element) when sorting random integer permutations.
  • Branch Mispredictions: The paper theoretically proves an upper bound of $\epsilon n \log n + O(n)$ branch mispredictions for a static branch predictor, where $\epsilon$ depends on the block size. Experimentally, BlockQuicksort showed an almost non-visible $n \log n$ term, with an approximation of $0.02n \log n + 1.75n$ branch mispredictions per element. This is significantly lower than std::sort and Yaroslavskiy's dual-pivot Quicksort, which incur $O(n \log n)$ branch mispredictions.
  • Performance Across Data Types: BlockQuicksort demonstrated competitive or superior performance across various data types (integers, vectors, records) and input distributions, including random, sorted, and duplicate-heavy data.
  • In-place Operation: It maintains the in-place nature of Quicksort, requiring only a constant or logarithmic amount of extra space.

Limitations and Future Work

  • Final Rearrangement Optimality: The paper acknowledges that the final rearrangement of elements after the main block loop is not strictly optimal and can have similar issues with duplicates as Lomuto's partitioner.
  • Pivot Selection: While median-of-three is used, the authors suggest that a fast pseudo-random generator might be beneficial for selecting samples for pivot selection, especially given the performance differences observed with different pivot strategies.
  • Buffer Usage: The buffers used for storing indices are, on average, not fully utilized. Future work could explore more efficient buffer management, such as cyclic addressing, to potentially fill both buffers in a single loop.
  • Recursion Stopper: The use of Insertionsort as a recursion stopper, while effective, still introduces a linear number of branch misses. Investigating alternative recursion stoppers that induce fewer branch mispredictions is suggested.
  • Parallelism: The block structure is noted as being well-suited for parallelism, suggesting this as a future research direction.

Summary updated

Abstract

Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort -- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an essential way from branch mispredictions. We present a novel approach to address this problem by partially decoupling control from data flow: in order to perform the partitioning, we split the input in blocks of constant size (we propose 128 data elements); then, all elements in one block are compared with the pivot and the outcomes of the comparisons are stored in a buffer. In a second pass, the respective elements are rearranged. By doing so, we avoid conditional branches based on outcomes of comparisons at all (except for the final Insertionsort). Moreover, we prove that for a static branch predictor the average total number of branch mispredictions is at most $\epsilon n \log n + O(n)$ for some small $\epsilon$ depending on the block size when sorting $n$ elements. Our experimental results are promising: when sorting random integer data, we achieve an increase in speed of 80% over the GCC implementation of C++ std::sort. Also for many other types of data and non-random inputs, there is still a significant speedup over std::sort. Only in few special cases like sorted or almost sorted inputs, std::sort can beat out implementation. Moreover, even on random input permutations, our implementation is even slightly faster than an implementation of the highly tuned Super Scalar Sample Sort, which uses a linear amount of additional space.
BibTeX
@misc{edelkamp2016blockquicksort,
  author = {Stefan Edelkamp and Armin Weiß},
  title = {{BlockQuicksort: How Branch Mispredictions don't affect Quicksort}},
  year = {2016},
  eprint = {1604.06697},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.06697},
}

Loading related content...

Figure