~/blog/cpython-powersort/ko.mdx

CPython 3.11의 powersort: list.sort가 바꾼 병합 순서

Python 3.11에서 list.sort의 run 병합 규칙이 timsort의 스택 불변식에서 powersort의 경계 power로 바뀌었습니다. 무엇이 달라졌는지 코드로 따라가고, 3.10과 3.11에서 비교 횟수와 시간을 직접 재 봤습니다. 무작위 입력에서는 차이가 없고, 길이가 고르지 않은 run에서만 차이가 납니다.

Python의 list.sort는 2002년부터 timsort였습니다. 이미 정렬된 구간(run)을 찾아 스택에 쌓고, 스택 크기 규칙에 따라 이웃한 run을 병합하는 방식입니다. Python 3.11에서 이 중 병합 순서를 정하는 규칙 하나만 powersort로 바뀌었습니다.1 run을 찾는 방법, 짧은 run을 삽입 정렬로 늘리는 방법, galloping은 그대로입니다.

릴리스 노트에서는 한 줄이라 지나치기 쉬운 변경입니다. 이 글의 수치는 모두 Docker의 python:3.10.22, python:3.11.17 이미지(linux/arm64, Apple Silicon 노트북)에서 직접 잰 것입니다.

두 병합 규칙

timsort (3.10): 스택 크기 불변식 powersort (3.11): 경계의 power 예 아니오 예 아니오 스택 위 세 run A, B, C A > B + C 이고B > C 인가? 다음 run을 쌓음 A와 C 중 작은 쪽을 B와 병합 새 run과 이전 run 사이경계의 power p 계산 스택 위 경계의power > p 인가? 그 경계를 병합 p를 기록하고 run을 쌓음

timsort는 스택에 쌓인 run 길이만 봅니다. 위에서부터 세 run을 A, B, C라 할 때 A > B + C, B > C가 성립하도록 유지하고, 깨지면 병합합니다. 이 규칙 덕분에 스택 길이는 피보나치처럼 늘어나 깊이가 로그로 제한됩니다. 다만 이 불변식은 원래 위쪽 세 개만 검사해서 깊은 곳에서 깨질 수 있었고, 2015년 de Gouw 등이 정형 검증 중에 이를 찾아내 네 번째 run까지 보는 검사가 추가됐습니다.2

powersort는 배열 안에서 이웃한 run의 중점이 놓인 위치로 경계의 power를 계산합니다. 중점을 구할 때 run의 시작 위치와 길이를 모두 씁니다. 스택의 run 길이 불변식 대신 이 power로 병합 순서를 정하고, power가 큰 경계부터 병합합니다. power가 작을수록 병합 트리의 뿌리 쪽에 가깝습니다.

경계의 power

배열 길이를 nn이라 하고, 이웃한 두 run이 위치 s1s_1에서 시작해 길이 n1n_1, n2n_2라고 합시다. 각 run의 중점을 [0,1)[0, 1)로 정규화합니다.

a=s1+n1/2n,b=s1+n1+n2/2na = \frac{s_1 + n_1/2}{n}, \qquad b = \frac{s_1 + n_1 + n_2/2}{n}

경계의 power는 aa와 bb를 이진 소수로 썼을 때 처음으로 다른 자리의 번호입니다. [0,1)[0,1)을 반, 사분의 일, 팔분의 일로 계속 나눌 때 두 중점이 처음 갈라지는 깊이라고 봐도 됩니다. 배열 한가운데를 걸치는 경계는 power 1이 되고, 끝 쪽의 작은 run 사이는 power가 큽니다. CPython은 이 값을 부동소수점 없이 정수 연산으로 구합니다. 그 루프를 Python으로 옮기면 이렇습니다.

power.py
def power(s1, n1, n2, n):
a = 2 * s1 + n1
b = a + n1 + n2
p = 0
while True:
p += 1
if a >= n:
a -= n; b -= n
elif b >= n:
break
a <<= 1; b <<= 1
return p

두 중점에 2n2n을 곱해 정수로 만듭니다. a/2na/2n과 b/2nb/2n이 원래 중점입니다. 나눗셈을 하지 않으니 반올림 오차가 없습니다.

a≥na \ge n이면 a/2n≥1/2a/2n \ge 1/2이고, b>ab > a이므로 bb도 마찬가지입니다. 두 수의 현재 자리가 모두 1이니 1을 빼고 다음 자리로 넘어갑니다.

a<n≤ba < n \le b이면 현재 자리에서 aa는 0, bb는 1입니다. 처음 갈라진 자리를 찾았으니 그 번호 p를 돌려줍니다.

둘 다 0이면 두 배로 늘려 다음 자리를 봅니다. 이진 소수를 한 자리씩 왼쪽으로 미는 것과 같습니다.

CPython의 실제 구현(Objects/listobject.c의 powerloop)도 같은 루프입니다. 이 루프는 run 하나를 찾을 때마다 한 번 돌고 반복 횟수는 log⁡2n\log_2 n을 넘지 않으므로, 정렬 전체 비용에 비하면 무시할 만합니다.

퀴즈경계의 power를 확인합니다

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 두 run 중점의 정규화된 이진 표현이 첫 자리에서 갈라집니다. 그 경계의 power와 병합 트리에서의 위치는 어떻게 봅니까?

같은 run, 다른 병합 순서

병합 순서가 얼마나 달라지는지 보려고 run 길이 열두 개짜리 예를 하나 골랐습니다. 아래에서 설명할 시뮬레이션에서 두 규칙의 차이가 가장 컸던 입력입니다.

run5768913391361656110101365
오른쪽 경계 power14532434678

맨 앞의 576짜리 run과 나머지 사이 경계가 power 1입니다. powersort는 이 경계를 맨 마지막에 한 번만 병합합니다. 576개 원소는 병합에 딱 한 번 참여합니다.

timsort는 같은 입력에서 이렇게 병합합니다.

단계timsort (3.10)powersort (3.11)
113 + 3913 + 39
289 + 5289 + 52
3141 + 136141 + 136
46 + 110165 + 6
5165 + 1166 + 5
6277 + 28113 + 11
710 + 1310 + 24
8558 + 23110 + 34
9576 + 581171 + 144
106 + 5277 + 315
111157 + 11576 + 592

timsort는 뒤쪽 작은 run이 스택에 늦게 도착하는 바람에 558짜리 덩어리에 23개를, 1157짜리 덩어리에 11개를 따로 붙입니다. 큰 덩어리가 작은 run 때문에 병합에 또 들어가는 것입니다. 병합 비용을 “병합하는 두 run 길이의 합”으로 세면 timsort는 4,365, powersort는 2,929입니다.

엔트로피로 본 하한

run 길이가 r1,…,rkr_1, \dots, r_k일 때 run 분포의 엔트로피는 다음과 같습니다.

H=−∑i=1krinlog⁡2rin\mathcal{H} = -\sum_{i=1}^{k} \frac{r_i}{n} \log_2 \frac{r_i}{n}

비교 기반 병합으로 이 run들을 합치려면 대략 nHn\mathcal{H} 정도의 비용은 피할 수 없습니다. 길이가 고른 run이 많으면 H\mathcal{H}가 크고, 큰 run 하나가 대부분이면 작습니다. Munro와 Wild는 powersort의 병합 비용이 nH+O(n)n\mathcal{H} + O(n) 이하임을 보였고,3 Buss와 Knop은 timsort가 1.5 nH1.5\,n\mathcal{H} 근처까지 갈 수 있음을 보였습니다.4

이걸 직접 확인하려고 두 병합 규칙을 Python으로 옮기고(timsort는 3.10의 merge_collapse, powersort는 3.11의 found_new_run), 무작위 run 길이 목록 20,000개에서 병합 비용을 nHn\mathcal{H}로 나눠 봤습니다.

입력timsort / nHn\mathcal{H}powersort / nHn\mathcal{H}
길이 64 run 1,024개1.0001.000
길이가 두 배씩 줄어드는 run1.0001.000
위의 12개 run (H\mathcal{H} = 2.346)1.5931.069

고른 run이나 규칙적으로 줄어드는 run에서는 둘 다 최적입니다. 차이는 길이가 들쭉날쭉할 때만 생기고, 20,000개 중 가장 나쁜 경우가 1.49배였습니다.

실제 CPython에서

시뮬레이션의 병합 비용은 원소 이동 횟수에 가깝지만, 실제 list.sort에는 galloping이 있어서 큰 run에 작은 run을 붙일 때 이진 탐색으로 대부분을 건너뜁니다. 그래서 __lt__가 불릴 때마다 횟수를 세는 클래스로 3.10과 3.11의 실제 비교 횟수를 쟀습니다. 먼저 흔한 패턴입니다(nn = 131,072).

입력3.103.11
무작위2,057,6402,057,640
정렬됨 / 역순131,071131,071
길이 32 run 반복1,697,0991,697,099
길이가 두 배씩 줄어드는 run393,333393,333
길이 1,000 run 반복1,065,8021,053,757
길이 10,000 run 반복629,970619,977
파레토 분포 run 길이1,079,1271,075,868

무작위, 정렬, 고른 run에서는 한 번도 다르지 않습니다. 이런 입력에서는 두 규칙이 같은 병합 트리를 만들기 때문입니다. 차이는 run 길이가 nn을 깔끔하게 나누지 못할 때만 1% 안팎으로 생깁니다.

위의 12개 run 패턴을 64배, 256배로 늘리고 각 run을 정렬된 무작위 실수로 채우면 이렇습니다.

배율nn3.10 비교3.11 비교
×6474,752262,295255,202 (−2.7%)
×256299,0081,049,5391,020,365 (−2.8%)

시뮬레이션에서 1.49배였던 차이가 비교 횟수로는 3% 남짓입니다. 큰 run과 작은 run을 병합할 때 galloping이 큰 쪽을 거의 건너뛰기 때문입니다. 시간은 비교 횟수보다 조금 더 차이가 납니다. 비교를 건너뛰어도 원소 복사(memcpy)는 남는데, powersort는 큰 덩어리를 다시 병합하지 않으니 복사 자체가 줄어듭니다.

"3.10 들쭉날쭉" "3.11 들쭉날쭉" "3.10 무작위" "3.11 무작위" 0 5 10 15 20 25 30 ms sorted() 시간, n = 299,008 (ms, 낮을수록 좋음)

×256 입력에서 3.10은 6.05 ms, 3.11은 5.25 ms로 13% 빨랐습니다. 같은 크기의 무작위 입력은 28.15 ms와 28.04 ms로 차이가 없습니다. 모두 7번씩 5회 반복한 값 중 최솟값입니다.

정리

  • 3.11의 변경은 list.sort의 병합 순서를 정하는 규칙 하나입니다. run 탐색, 삽입 정렬, galloping은 그대로입니다.
  • timsort는 스택 위 run 길이로, powersort는 배열 안에서 경계의 위치(power)로 병합 순서를 정합니다. power는 두 run 중점의 이진 표현이 처음 갈라지는 자리입니다.
  • 무작위, 정렬, 고른 run 입력에서는 비교 횟수가 3.10과 한 번도 다르지 않았습니다. 일상적인 정렬에서 빨라진 것을 느끼기는 어렵습니다.
  • 길이가 들쭉날쭉한 run에서는 병합 비용이 이론상 최대 1.5배까지 차이 나고, galloping이 대부분을 흡수해 실측으로는 비교 3%, 시간 13% 정도였습니다.

이 변경의 가치는 평균 속도보다 보장에 있습니다. timsort의 병합 비용은 1.5 nH1.5\,n\mathcal{H}까지 갈 수 있다는 것이 알려져 있었고, powersort는 nH+O(n)n\mathcal{H} + O(n) 이하를 보장합니다. 게다가 규칙이 스택 불변식보다 단순해서, 2015년처럼 불변식이 깊은 곳에서 깨지는 종류의 버그가 생길 여지가 없습니다.

퀴즈병합 비용과 비교 횟수를 구분한다면

답을 고르면 해설이 나옵니다.

3문제 중 0개 맞힘

  1. CPython 3.11로 올렸으니 run 탐색과 galloping도 새 알고리즘으로 바뀌었다고 설명합니다. 본문에서 확인한 변경 범위는 무엇입니까?

  2. 시뮬레이션에서 병합 비용 차이가 컸는데 실제 비교 횟수 차이는 작습니다. 두 측정이 다른 이유는 무엇입니까?

  3. 본문의 무작위 입력에서 두 Python 버전의 비교 횟수가 같습니다. 이 결과로 powersort의 변경이 쓸모없다고 결론 내릴 수 있습니까?

각주

  1. CPython 3.11의 Objects/listsort.txt에 powersort로 바꾼 이유와 power 계산 방법이 정리되어 있습니다. 변경은 Tim Peters가 직접 했습니다. ↩

  2. Stijn de Gouw 외, “OpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst case”, CAV 2015. 같은 버그가 CPython에도 있었습니다. ↩

  3. J. Ian Munro, Sebastian Wild, “Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs”, ESA 2018. ↩

  4. Sam Buss, Alexander Knop, “Strategies for Stable Merge Sorting”, SODA 2019. ↩

~/blog/cpython-powersort/en.mdx

Powersort in CPython 3.11: the merge order list.sort changed

In Python 3.11 the rule that decides which runs list.sort merges switched from timsort's stack invariants to powersort's boundary powers. This post walks through what changed in code and measures comparison counts and time on 3.10 and 3.11. Random input does not move at all; only runs of uneven length do.

Python’s list.sort has been timsort since 2002. It finds already-sorted stretches (runs), pushes them on a stack, and merges neighbouring runs according to rules about stack sizes. In Python 3.11 only the rule that decides merge order was replaced with powersort.1 Run detection, extending short runs with insertion sort, and galloping are unchanged.

It is one line in the release notes and easy to miss. Every number in this post was measured on the Docker images python:3.10.22 and python:3.11.17 (linux/arm64, on an Apple Silicon laptop).

Two merge rules

timsort (3.10): stack size invariants powersort (3.11): boundary power yes no yes no Top three runs A, B, C A > B + C andB > C ? Push the next run Merge B with the smaller of A and C Compute power p of the boundarybetween new run and previous run Power of the boundaryon top of stack > p ? Merge across that boundary Record p and push the run

Timsort looks only at the lengths of the runs on the stack. Calling the top three A, B, C, it maintains A > B + C and B > C, merging whenever they break. This makes stack lengths grow like Fibonacci numbers, so the depth stays logarithmic. The invariant used to be checked only on the top three entries and could break deeper down; in 2015 de Gouw et al. found this during formal verification, and a check reaching the fourth run was added.2

Powersort computes each boundary’s power from where the adjacent runs’ midpoints sit in the array. Computing those midpoints uses both run starts and run lengths. This power replaces the stack’s run-length invariants as the merge-order rule, with larger-power boundaries merged first. The smaller the power, the closer the boundary is to the root of the merge tree.

The power of a boundary

Let the array have length nn, and let two adjacent runs start at s1s_1 with lengths n1n_1 and n2n_2. Normalize each run’s midpoint into [0,1)[0, 1):

a=s1+n1/2n,b=s1+n1+n2/2na = \frac{s_1 + n_1/2}{n}, \qquad b = \frac{s_1 + n_1 + n_2/2}{n}

The power of the boundary is the index of the first binary digit where aa and bb differ. Equivalently, keep halving [0,1)[0,1) into halves, quarters, eighths, and the power is the depth at which the two midpoints first land in different pieces. A boundary straddling the middle of the array gets power 1; boundaries between small runs near one end get large powers. CPython computes this with integer arithmetic only. Ported to Python, the loop looks like this.

power.py
def power(s1, n1, n2, n):
a = 2 * s1 + n1
b = a + n1 + n2
p = 0
while True:
p += 1
if a >= n:
a -= n; b -= n
elif b >= n:
break
a <<= 1; b <<= 1
return p

Multiply both midpoints by 2n2n to make them integers; a/2na/2n and b/2nb/2n are the original midpoints. No division, so no rounding error.

If a≥na \ge n then a/2n≥1/2a/2n \ge 1/2, and since b>ab > a so is bb. Both have a 1 in the current digit, so subtract it and move on.

If a<n≤ba < n \le b, the current digit is 0 for aa and 1 for bb. That is the first digit where they differ, so return its index p.

If both are 0, double them to look at the next digit. This is shifting the binary fraction left by one place.

CPython’s actual implementation (powerloop in Objects/listobject.c) is the same loop. It runs once per run found and never iterates more than log⁡2n\log_2 n times, which is negligible next to the sort itself.

QuizCheckpoint: boundary power

Choose an answer to see the explanation.

0 of 1 right

  1. Two normalized run midpoints differ at their first binary digit. How should you interpret that boundary's power and tree position?

Same runs, different merge order

To see how far the merge order can diverge, I picked one example with twelve runs. It is the input on which the two rules differed most in the simulation described below.

run5768913391361656110101365
right boundary power14532434678

The boundary between the leading run of 576 and everything else has power 1. Powersort merges it exactly once, at the very end, so those 576 elements take part in a single merge.

Here is what each rule does with the same input:

Steptimsort (3.10)powersort (3.11)
113 + 3913 + 39
289 + 5289 + 52
3141 + 136141 + 136
46 + 110165 + 6
5165 + 1166 + 5
6277 + 28113 + 11
710 + 1310 + 24
8558 + 23110 + 34
9576 + 581171 + 144
106 + 5277 + 315
111157 + 11576 + 592

Because the small runs at the end reach the stack late, timsort attaches 23 elements to a block of 558 and then 11 elements to a block of 1157. Large blocks get merged again just to absorb small runs. Counting merge cost as the sum of both run lengths per merge, timsort pays 4,365 and powersort 2,929.

A lower bound from entropy

For run lengths r1,…,rkr_1, \dots, r_k, the entropy of the run distribution is

H=−∑i=1krinlog⁡2rin\mathcal{H} = -\sum_{i=1}^{k} \frac{r_i}{n} \log_2 \frac{r_i}{n}

Merging these runs by comparisons costs roughly nHn\mathcal{H} at minimum. Many runs of similar length mean a large H\mathcal{H}; one run dominating means a small one. Munro and Wild proved powersort’s merge cost is at most nH+O(n)n\mathcal{H} + O(n),3 and Buss and Knop showed timsort can get close to 1.5 nH1.5\,n\mathcal{H}.4

To check this I ported both merge rules to Python (timsort from 3.10’s merge_collapse, powersort from 3.11’s found_new_run) and divided the merge cost by nHn\mathcal{H} across 20,000 random lists of run lengths.

Inputtimsort / nHn\mathcal{H}powersort / nHn\mathcal{H}
1,024 runs of length 641.0001.000
Runs halving in length1.0001.000
The 12 runs above (H\mathcal{H} = 2.346)1.5931.069

Both rules are optimal on even runs and on regularly shrinking ones. The gap appears only with ragged lengths, and the worst of 20,000 cases was 1.49×.

In real CPython

The simulated merge cost is close to the number of element moves, but the real list.sort gallops: when merging a small run into a large one it skips most of the large one with a binary search. So I measured actual comparisons on 3.10 and 3.11 with a class whose __lt__ increments a counter. First, common patterns (nn = 131,072):

Input3.103.11
Random2,057,6402,057,640
Sorted / reversed131,071131,071
Repeated runs of 321,697,0991,697,099
Runs halving in length393,333393,333
Repeated runs of 1,0001,065,8021,053,757
Repeated runs of 10,000629,970619,977
Pareto-distributed run lengths1,079,1271,075,868

Random, sorted, and even-run inputs do not differ by a single comparison, because both rules build the same merge tree for them. A difference of around 1% shows up only when run lengths do not divide nn cleanly.

Scaling the twelve-run pattern by 64 and 256 and filling each run with sorted random floats:

Scalenn3.10 comparisons3.11 comparisons
×6474,752262,295255,202 (−2.7%)
×256299,0081,049,5391,020,365 (−2.8%)

The 1.49× gap from the simulation shrinks to under 3% in comparisons, because galloping skips nearly all of the large side when a big run meets a small one. Time differs more than comparisons do. Galloping saves comparisons, but the element copies (memcpy) remain, and powersort avoids re-merging large blocks, so it copies less.

"3.10 ragged" "3.11 ragged" "3.10 random" "3.11 random" 0 5 10 15 20 25 30 ms sorted() time, n = 299,008 (ms, lower is better)

On the ×256 input 3.10 took 6.05 ms and 3.11 took 5.25 ms, 13% faster. Random input of the same size took 28.15 ms and 28.04 ms, no difference. Each figure is the best of 5 repeats of 7 runs.

Summary

  • The 3.11 change is a single rule in list.sort: the one that decides merge order. Run detection, insertion sort, and galloping are unchanged.
  • Timsort orders merges by run lengths on the stack; powersort orders them by the position of each boundary in the array (its power). The power is the first binary digit where the two runs’ midpoints differ.
  • On random, sorted, and even-run input, comparison counts never differed from 3.10. Everyday sorting will not feel faster.
  • On runs of ragged length the merge cost can differ by up to 1.5× in theory; galloping absorbs most of that, and I measured about 3% fewer comparisons and 13% less time.

The value of the change is the guarantee more than the average speed. Timsort’s merge cost was known to reach 1.5 nH1.5\,n\mathcal{H}; powersort guarantees at most nH+O(n)n\mathcal{H} + O(n). The rule is also simpler than the stack invariants, leaving no room for the kind of bug found in 2015, where an invariant broke deep in the stack.

QuizSeparating merge cost from comparisons

Choose an answer to see the explanation.

0 of 3 right

  1. Someone says upgrading to CPython 3.11 also replaced run detection and galloping. What change does the post actually establish?

  2. The simulation shows a large merge-cost gap, but actual comparison counts barely differ. Why can these measurements diverge?

  3. The post's random input yields identical comparison counts on both Python versions. Does that make the powersort change useless?

Notes

  1. CPython 3.11’s Objects/listsort.txt explains why powersort was adopted and how power is computed. Tim Peters made the change himself. ↩

  2. Stijn de Gouw et al., “OpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst case”, CAV 2015. CPython had the same bug. ↩

  3. J. Ian Munro, Sebastian Wild, “Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs”, ESA 2018. ↩

  4. Sam Buss, Alexander Knop, “Strategies for Stable Merge Sorting”, SODA 2019. ↩

ko.mdx

단축키Keyboard

/ ⌘K
글 검색Search posts
t
밝은/어두운 테마Light or dark theme
l
한국어/영어, 읽던 자리 유지Korean or English, keeping your place
[ ]
이전/다음 절Previous or next section
?
이 목록This list

↑↓ 이동move↵ 열기openesc 닫기close