list.sort() minrun computation is incorrect for very large lists on some architectures

[neelsomani]

Bug report

list.sort()'s PowerSort implementation computes the mask used by the minrun generator as:

ms->mr_mask = (1 << ms->mr_e) - 1;

Here, mr_mask and mr_e are Py_ssize_t, but the literal 1 has type int. For sufficiently large lists, mr_e can exceed the width for which this shift is valid/behaves as intended. On affected architectures, the shifted value becomes zero, so subtracting one causes mr_mask to become -1.

This breaks the intended PowerSort minrun calculation for very large lists and can cause substantially worse sorting performance than the intended O(n log n) behavior.

The issue was discovered while formally verifying CPython's PowerSort implementation in Lean as part of the ATLAS project:

facebookresearch/atlas-lean#8

The formalization initially modeled the mask computation using the width of Py_ssize_t, which exposed the discrepancy with the C implementation: the C expression performs the shift starting from an int, even though the result is stored in a Py_ssize_t.

CPython's Objects/listsort.txt describes the intended computation as:

mr_mask = (1 << mr_e) - 1

which does not have the fixed-width behavior of the C expression.

A minimal fix should be to perform the shift at the appropriate width, for example by making the left operand a Py_ssize_t before shifting.

An ordinary regression test through list.sort() is impractical because reaching the problematic values of mr_e requires an extremely large list (hundreds of GiB of list storage). I therefore plan to submit the fix without an end-to-end regression test unless there is a preferred way to exercise this internal calculation directly without allocating such a list.

CPython versions tested on:

CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-158486: Fix PowerSort mask calculation for very large lists #158487