`list.sort` enhancement proposal: Adaptivity for `binarysort`

[dg-pb]

Feature or enhancement

Proposal:

Note:

1. This is POC that this has a observable impact.
2. This is subject to further calibration and optimizations, but high level concept is dicusable.
3. Will issue PR shortly.

Rationale

Galloping provides adaptivity when merging runs.
However, underlying binarysort always does O(nlogn).

Concept

The concept is simple:

1. binarysort optionally does adaptive routine.
   1. It has a mechanism to switch it off during the run and go to simple binarysort
   2. It returns 1 if it has completed full data with binary routine and 0 otherwise
2. timsort calls binarysort
   1. If it returns 1, then use it again next time
   2. If it returns 0, then use binarysort without adaptivity next time
   3. increase number of simple binarysort runs before next attempt of adaptive run with every 0 returned

High level results

• A0 is current
• A1 is with adaptivity
• P means performance / runtime
• C means comparison count
• Aggregate numbers for all datasets combined are in the title

1. Plain integers and floats

2. Integers and floats wrapped in list, so comparisons are __lt__ calls, thus more expensive

So the benefit is higher when comparisons cost more.
But there is some benefit for optimized comparisons as well.

Worst case

• Adaptive binarysort does ~20% more comparisons than simple binarysort for random data.
• However, it detects that it is not paying off after about 30 iterations.

Thus the worst case would be random data up to size 30, which would be 20% slower.
Size 60 would only be 10% slower.
Size 120 would only be 5% slower.
And so on...

Has this already been discussed elsewhere?

I have already discussed this feature proposal on Discourse

Links to previous discussion of this feature:

https://discuss.python.org/t/sorting-adaptivity-improvement/103700

Linked PRs

• gh-138946: list.sort enhancement proposal: Adaptivity for binarysort #138947

[terryjreedy]

@tim-one

[dg-pb]

So final / semi-final version is pushed. See high level benchmarks in PR description. I took length 1000 as it is small enough to make small run sorting do reasonable fraction of total work. Also, note that effect on comparisons for datasets where adaptivity is not optimal has been minimised (no differences of 1-5% that are exist in benchmarks in the title of this issue).

Some explanation on what has been done. There are 2 parts - Adaptive Binary Sort and the way it is incorporated into Tim Sort.

1. Adaptive Binary Sort

For previous 2 insort positions $pos_{j-1}$ and $pos_{j}$, the prediction (2 layers of binary search midpoints) $\mu_{j+1}$ is as follows:

$\mu_{j+1} = pos_{j} + \left( pos_{j} - pos_{j-1} \right)$
$\sigma_{j+1} = \left| pos_{j} - \mu_{j} \right|$

In simple words. If last position was 2 indices higher than the current one, then we expect the next one to be 2 indices higher than the current one. And "error" of it is how good the last prediction was.

Once these 2 are available, 2 layers of search are performed before going into simple binary insertion sort, where search points are as follows:

$\left[\mu-2\sigma, \mu-\sigma, \mu, \mu+\sigma, \mu+2\sigma\right]$

Firstly, checking if new value is higher or lower than value at $\mu$, then taking either $\mu+\sigma$ or $\mu-\sigma$ and doing the same, ...

So there is a new routine Py_ssize_t abinarysort(..., int adapt), which can either run in adaptive mode or just do simple binary search. However, in both cases it returns "badness measure", which indicates how fitted the data is to enable adaptivity. 1000 is the maximum value, meaning that it mis-predicted all positions by maximum indices possible and 0 indicating that it predicted all positions precisely.

2. Incorporation

The logic can be clearly seen in the code.
First of all, there is a global decision whether to run Tim Sort with or without Adaptive Binary sort.

Currently, it enables it for all inputs higher or equal than 100. This number can be adjusted further based on benefit / cost ration for different lengths, where amortisation did not have time to take effect and costs can be visible for adversarial data.

Furthermore, this number can be different based on comparison type.

However, 100 is a good number as first run never does adaptivity, only calculates the goodness of fit. Then, if it does not fit, then next 3 runs are done by the old binarysort without any additional costs. While if it does fit, mild benefits can already be observed - especially for object_compare.

So the logic is as follows:

if size >= 100:
    adapt = 0   # do not run adaptive on 1st run (but calculate measure)
    cs = 0     # time off counter
    cd = 1     # number of time off runs to take after fail
    while nremaining:
        n = count_run(..., nremaining);
        minrun = minrun_next(...);
        if n < minrun:
            force = nremaining if nremaining <= minrun else minrun
            if cs:
                # time off (no extra calculations)
                binarysort(..., force, n)
                cd -= 1
            else:
                # always calculates measure (but might not do adaptivity)
                adapt = abinarysort(..., force, n, adapt) < 250
                if adapt:
                    # cs == 0 here, keep it that way
                    # reset time-off counter
                    cd = 1
                elif cd >= 9:
                    # 11 is maximum time-off
                    # Amortizes well: max penalty < 20%
                    # This makes it < 2%
                    # Can be amended
                else:
                    # increase time-off and set counter to it
                    # minimum time-off is 3
                    cs = cd = cd + 2
                ...
        else:
            # after large monotonic, start adapting aggressively
            adapt = 1
            cs = 0
            cd = 1
        ...
else:
    # Run things as they are now

---

So this is pretty much it. I think what is needed now is for people to play with it to see if some of their important cases are not damaged too much. It should not be more than 5%, but this can be tuned further to minimise undesirable effects.

There are a lot of cases, and given we are dealing with small differences (0-5%) and benchmarks are not very stable, it is hard to report complete impact (heatmaps in PR should cover it to a good degree though). Thus, I will finish this with 2 specific case:

1. Data with worst possible impact that I can manage to make
2. Data best possible impact that I can manage to make

(1) So it kicks in for size>=100, performs worse on specialised comparisons and does minimum 3 runs of time-off.

(2) Best case is simply something that is very well sorted, but not monotonic run. Made with elements with very expensive comparisons.

Both relatively small data sizes (say 640) so that small run sorting is as big proportion of the whole as possible.

S="
import random

def worst_case_data(n):
    x = 0
    xs = [0]
    while len(xs) < n:
        # 1. well sorted, but not monotonic!
        for _ in range(64):
            x = x + random.randint(-2, 7)
            xs.append(x)
        # Good fit identified, now make unfavourable data
        # 4 runs of it
        for _ in range(64 + 192):
            xs.append(x + random.random())
        x = xs[-1]
    return xs[:n]


def best_case_data(n):
    x = 0
    xs = [[x, x, x, x, x]]
    for _ in range(n):
        x += random.randint(-3, 15)
        xs.append([x, x, x, x, x])
    return xs


WORST = worst_case_data(640)
BEST = best_case_data(640)
"

$PYMAIN -m timeit -s $S "sorted(WORST)" # 68 µs
$PYNEW -m timeit -s $S "sorted(WORST)"  # 72 µs
$PYMAIN -m timeit -s $S "sorted(BEST)"  # 80 µs
$PYNEW -m timeit -s $S "sorted(BEST)"   # 43 µs

So worst case is 6% worse.

While it delivers benefits up to 50%.

P.S. The worst cases I have seen are on very small sizes e.g. 10, where sometimes new logic is not run at all, but it screwed up binary layout or something similar and it runs 10-20ns slower, which turns out to be 5% difference.

[dg-pb]

Just one more note regarding large data sizes.

Say for data size 100K:

RWKW = [[random.randint(-1, 3)] for _ in range(100_000)]
$PYMAIN -m timeit -s $S "sorted(RWKW)"  #  14 ms
$PYNEW -m timeit -s $S "sorted(RWKW)"   #   8 ms

Thus, as galloping adapts aggressively and successfully, small run sorting remains significant part.

---

Impact is much smaller for specialised types though (for both small and large data similarly):

RWK = [random.randint(-1, 3) for _ in range(100_000)]
$PYMAIN -m timeit -s $S "sorted(RWK)"   #  2.4 ms
$PYNEW -m timeit -s $S "sorted(RWK)"    #  2.1 ms

[pochmann3]

I think the third column in your images has numerator and denominator swapped.

[dg-pb]

I think the third column in your images has numerator and denominator swapped.

Indeed. The ones in PR description.

---

$PYMAIN -m timeit -s $S "sorted(WORST)" # 68 µs
$PYNEW -m timeit -s $S "sorted(WORST)" # 72 µs

So this is a fluke, actual impact should be ~1%.
As this is the impact of extra calculations in abinarysort, when adaptivity is not done, but simple binarysort is done, but with fitness calculation. And in this case, these calculations will be done only 2 out of 5 runs. So 1% x 2 / 5 = 0.4% and 1 in 5 runs will be adaptive run, which is ~3%, thu 3/5 = 0.6%. Thus 0.4 + 0.6 = 1%.

So theoretically, very worst case should be ~2% worse. 1% due to computations above and some branches were added, so maybe additional 1%

---

On my new branch I commented out all the new code, recompiled and was still getting the same difference.

After a while I ran this again and now consistently getting these results:

$PYMAIN -m timeit -s $S "sorted(WORST)" #  68
$PYNEW -m timeit -s $S "sorted(WORST)"  #  68

So I am dealing with fluctuations which are most likely not due to changes made. It would be great if someone could run BEST / WORST cases above and report results.

[dg-pb]

Took a bit larger size to get a bit more stable results for WORST_CASE:

WORST6400 = worst_case_data(640 * 10)
$PYMAIN -m timeit -s $S "sorted(WORST6400)" #  700 µs
$PYNEW -m timeit -s $S "sorted(WORST6400)"  #  715 µs

In line with expected 2%.

---

But the very worst case after all will be of 2 runs - one simple binary search signalling to run adaptivity and the adaptivity failing badly on the next one. And no time-off runs taken to amortise.

WORST100 = worst_case_data(100)
$PYMAIN -m timeit -s $S "sorted(WORST100)"  # 5.4 µs
$PYNEW -m timeit -s $S "sorted(WORST100)"   # 5.6 µs

4% worse.

Thus, minimum size could be increased if to get the worst case closer to amortised 2%. 320 minimum size would be theoretical 2.5% worst case, 640 would be 2.3%, etc...

(n_amortized * 5 * 2% + 2 * 4%) / (n_amortized * 5 + 2)
, where one amortized run is ~320 size.