Opensource internals

One XOR and One CLZ: How Rust's Stable Sort Decides Which Runs to Merge

4 min read Jay Hubbert

Rust's driftsort uses the powersort merge-tree heuristic, but computes each merge node's depth with a single XOR and a leading-zero count instead of rational comparisons.

TL;DR: Rust’s stable sort (driftsort) merges runs using the powersort heuristic: build a merge tree over the runs, where each merge happens at the depth that balances the tree. The clever part is computing that depth — instead of comparing rational numbers, it rescales the number line to [0, 2^62) and takes the leading zeros of an XOR.

The theory

rust 
// library/core/src/slice/sort/stable/drift.rs:122-171

// Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally
// Adapt to Existing Runs by J. Ian Munro and Sebastian Wild.
//
// This method forms a binary merge tree, where each internal node corresponds
// to a splitting point between the adjacent runs that have to be merged. ...
// As an optimization we rescale the number line from [0, 1) to [0, 2^62). Then
// finding the simplest dyadic fraction between midpoints corresponds to finding
// the most significant bit difference of the midpoints. We save scale_factor =
// ceil(2^62 / n) to perform this rescaling using a multiplication, avoiding
// having to repeatedly do integer divides. ...
// Thus for the splitting point between two adjacent slices [a, b) and [b, c)
// the desired depth of the corresponding merge node is CLZ((a+b)*f ^ (b+c)*f),

Read the last line again, because it is the whole trick:

the desired depth of the corresponding merge node is CLZ((a+b)*f ^ (b+c)*f)

where f is a scale factor.

The implementation

rust 
// library/core/src/slice/sort/stable/drift.rs:122-171

#[inline(always)]
fn merge_tree_scale_factor(n: usize) -> u64 {
    if usize::BITS > u64::BITS {
        panic!("Platform not supported");
    }
    (1u64 << 62).div_ceil(n as u64)
}

#[inline(always)]
fn merge_tree_depth(left: usize, mid: usize, right: usize, scale_factor: u64) -> u8 {
    let x = left as u64 + mid as u64;
    let y = mid as u64 + right as u64;
    ((scale_factor * x) ^ (scale_factor * y)).leading_zeros() as u8
}

The classic powersort formulation compares the rational numbers (a+b)/2 and (b+c)/2 to decide which merge tree is most balanced. Doing that with rational arithmetic means multiplications, comparisons and careful overflow handling.

The trick: rescale [0, 1) to [0, 2^62). After rescaling, “which dyadic fraction is simplest between these two numbers?” becomes “what is the most significant bit where they differ?” — which is exactly leading_zeros(x ^ y). The scale factor f = ceil(2^62 / n) is computed once, and the rescaling is a multiplication.

So each merge-tree depth query is: two additions, two multiplications, one XOR, one lzcnt. No division, no rational comparison, no branch.

The sqrt approximation

The same file avoids the FPU for another purpose:

rust 
// library/core/src/slice/sort/stable/drift.rs:173-187

sqrt_approx computes √n with an ilog2 and one Newton step rather than calling f64::sqrt. No floating point, no libm call, and — importantly — no floating point in the middle of a sorting algorithm, where the reproducibility of the output matters.

The scratch buffer sizing

rust 
// library/core/src/slice/sort/stable/mod.rs:94-135

fn driftsort_main<T, F: FnMut(&T, &T) -> bool, BufT: BufGuard<T>>(v: &mut [T], is_less: &mut F) {
    // By allocating n elements of memory we can ensure the entire input can
    // be sorted using stable quicksort, which allows better performance on
    // random and low-cardinality distributions. However, we still want to
    // reduce our memory usage to n - n / 2 for large inputs. We do this by scaling
    // our allocation as max(n - n / 2, min(n, 8MB)), ensuring we scale like n for
    // small inputs and n - n / 2 for large inputs, without a sudden drop off. ...
    const MAX_FULL_ALLOC_BYTES: usize = 8_000_000; // 8MB
    let max_full_alloc = MAX_FULL_ALLOC_BYTES / size_of::<T>();
    let len = v.len();
    let alloc_len = cmp::max(
        cmp::max(len - len / 2, cmp::min(len, max_full_alloc)),
        SMALL_SORT_GENERAL_SCRATCH_LEN,
    );

    // For small inputs 4KiB of stack storage suffices, which allows us to avoid
    // calling the (de-)allocator. Benchmarks showed this was quite beneficial.
    let mut stack_buf = AlignedStorage::<T, 4096>::new();
    let stack_scratch = stack_buf.as_uninit_slice_mut();
    let mut heap_buf;
    let scratch = if stack_scratch.len() >= alloc_len {
        stack_scratch
    } else {
        heap_buf = BufT::with_capacity(alloc_len);
        heap_buf.as_uninit_slice_mut()
    };

Three decisions:

  1. The scratch is n - n/2 for large inputs, not n — half the memory of a textbook mergesort.
  2. Sorts of ≤ 4 KiB of elements never touch the allocator — the scratch is on the stack.
  3. The BufGuard trait is what lets core (which has no allocator) contain the algorithm while std provides the buffer. That is a nice layering trick: the sorting algorithm lives in core, and the allocation policy is injected.

Where it lives

  • library/core/src/slice/sort/stable/drift.rs — merge_tree_depth, merge_tree_scale_factor, sqrt_approx.
  • library/core/src/slice/sort/stable/mod.rs — driftsort_main, the scratch sizing, BufGuard.
  • library/core/src/slice/sort/stable/merge.rs — the merge itself.

Takeaway

The “simplest dyadic fraction between two rationals” is a natural way to balance a merge tree, but computing it with rational arithmetic is expensive. Rescaling the number line so that the answer becomes a bit difference is a classic “change the representation, change the cost” move: the same mathematical quantity, computed with an XOR and a lzcnt instead of multiplications and comparisons. It is the kind of trick that you can only find if you actually look at what the algorithm needs rather than how the paper writes it down.

RustInternalsStdPerformanceSortingAlgorithms