Change how sorting picks minimum run length

[tim-one]

Bug report

Bug description:

On randomly ordered data, Python's sort ends up artificially forcing all initial runs to length minrun, whose value is a function of len(list), picked in a cheap way to avoid the very worst cases of imbalance in the final merge.

Stefan Pochmann has invented a much better way, which may vary minrun a little from one run to the next. Under his scheme, at all levels of the merge tree:

• The number of runs is a power of 2.
• At most two different values of run lengths are in play.
• The lengths of run pairs to be merged differ by no more than 1.

So, in all cases, in all ways it's as close to perfectly balanced as possible.

For randomly ordered inputs, this eliminates all cases of "bad imbalance", cuts the average number of compares a little, and cuts the amount of pointer copying due to unbalanced merges.

Following is a Python prototype verifying the claims. Variables starting with "mr_" will become part of the MergeState struct, and the loop body in the generator will become a brief inlined function.

from itertools import accumulate
try:
    from itertools import batched
except ImportError:
    from itertools import islice
    def batched(xs, k):
        it = iter(xs)
        while chunk := tuple(islice(it, k)):
            yield chunk

MAX_MINRUN = 64

def gen_minruns(n):
    # mr_int = minrun's integral part
    # mr_frac = minrun's fractional part with mr_e bits and
    # mask mr_mask
    mr_int = n
    mr_e = 0
    while mr_int >= MAX_MINRUN:
        mr_int >>= 1
        mr_e += 1
    mr_mask = (1 << mr_e) - 1
    mr_frac = n & mr_mask

    mr_current_frac = 0
    while True:
        mr_current_frac += mr_frac
        assert mr_current_frac >> mr_e <= 1
        yield mr_int + (mr_current_frac >> mr_e)
        mr_current_frac &= mr_mask

def chew(n, show=False):
    if n < 1:
        return

    sizes = []
    tot = 0
    for size in gen_minruns(n):
        sizes.append(size)
        tot += size
        if tot >= n:
            break
    assert tot == n
    print(n, len(sizes))

    small, large = 32, 64
    while len(sizes) > 1:
        assert not len(sizes) & 1
        assert len(sizes).bit_count() == 1 # i.e., power of 2
        assert sum(sizes) == n
        assert min(sizes) >= min(n, small)
        assert max(sizes) <= large

        d = set(sizes)
        assert len(d) <= 2
        if len(d) == 2:
            lo, hi = sorted(d)
            assert lo + 1 == hi

        mr = n / len(sizes)
        for i, s in enumerate(accumulate(sizes, initial=0)):
            assert int(mr * i) == s

        newsizes = []
        for a, b in batched(sizes, 2):
            assert abs(a - b) <= 1
            newsizes.append(a + b)
        sizes = newsizes
        smsll = large
        large *= 2

    assert sizes[0] == n

for n in range(2_000_001):
    chew(n)

CPython versions tested on:

3.14, CPython main branch

Operating systems tested on:

Windows

Linked PRs

• gh-135551: Change how sorting picks minimum run length #135553

[pochmann3]

Here's an explanation and a proposal for a simpler implementation.

For example with 315 random elements, the old scheme uses fixed minrun=40 and produces runs of length 40, except possibly for the last. The new scheme produces a mix of lengths 39 and 40:

old:  40 40 40 40 40 40 40 35
new:  39 39 40 39 39 40 39 40

Both schemes produce eight runs, a power of 2. That's good for a balanced merge tree. But the new scheme allows merges where left and right length never differ by more than 1:

39 39 40 39 39 40 39 40
  78   79     79   79
    157         158
          315

(This shows merges downward, e.g.,
 two runs of length 39 are merged
 and become a run of length 78.)

With larger lists, the old scheme gets even more unbalanced. For example with 32769 elements (that's 2¹⁵+1), it uses minrun=33 and produces 993 runs (of length 33). That's not even a power of 2. The new scheme instead produces 1024 runs, all with length 32 except for the last one with length 33.

How does it work? Ideally, all runs would be exactly equally long. For the above example, each run would have 315/8 = 39.375 elements. Which of course doesn't work. But we can get close:

• For the first run, we'd like 39.375 elements. Since that's impossible, we instead use 39 and remember the current leftover fraction 0.375.
• For the second run, we add 0.375 + 39.375 = 39.75. Again impossible, so we instead use 39 and remember 0.75.
• For the third run, we add 0.75 + 39.375 = 40.125. This time we get 40 and remember 0.125.
• And so on.

Here's a Python generator doing that:

def gen_minruns_with_floats(n):
    mr = n
    while mr >= MAX_MINRUN:
        mr /= 2

    mr_current = 0
    while True:
        mr_current += mr
        yield int(mr_current)
        mr_current %= 1

IEEE 754 doubles could handle "only" ~2⁵³ elements, and I'm not sure CPython always uses IEEE 754. So here's an integer version, where the internal numbers are scaled up by 2^e, or rather not divided by 2^e. Instead, only each yielded minrun gets divided (by right-shifting). For example instead of adding 39.375 and reducing modulo 1, it just adds 315 and reduces modulo 8. And always divides by 8 to get each actual minrun value:

def gen_minruns_simpler(n):
    e = 0
    while (n >> e) >= MAX_MINRUN:
        e += 1
    mask = (1 << e) - 1

    mr_current = 0
    while True:
        mr_current += n
        yield mr_current >> e
        mr_current &= mask

This is a simpler version of the proposal's current code in Tim's post above and the PR. That one splits 39.375 into the integer part 39 and the fractional part 0.375 and scales only the latter by 8 so it's the integer 3. I instinctively did that split to keep the integers small enough for C's fixed size ints. But I now think that's unnecessary, as all numbers in gen_minruns_simpler are smaller than 2n. If that's indeed safe (Tim will know better about C, CPython, and its lists), then I propose this simpler implementation.

[tim-one]

Thanks! I'll happily work in all suggestions. Yes, using a single int "is safe". On a 32-bit box, Py_ssize_t is a signed 32-bit int, but Python lists can have at most 2**30 elements (since each requires 4 bytes to store the pointer, and the total address space is limited to 32-bit byte addresses). So twice the largest list length still doesn't spill into the sign bit. On a 64-bit box, there's even more spare capacity.