JSC PowerSort Galloping Merge

cd9b986

Source/JavaScriptCore/runtime/StableSort.h

PowerSort는 JSC의 Array.prototype.sort와 TypedArray sort 구현체로, 입력에서 미리 정렬된 구간("run")을 탐지하고 merge tree가 결정한 순서에 따라 병합하는 natural merge sort 변형입니다. 이번 commit은 세 가지 최적화를 도입했습니다.

먼저 초기의 불필요한 buffer copy가 제거되었습니다. 이제 src는 항상 출력 대상이고, dst는 작업용 scratch buffer로만 사용됩니다. 또한 run 탐지 범위가 확장되어 내림차순 run을 인식하고, in-place reversal을 통해 오름차순으로 정규화하도록 변경되었습니다. 마지막으로 Python의 TimSort에서 차용한 galloping merge가 도입되었습니다.

Galloping은 내부 merge loop 방식을 변경합니다. 한쪽 run이 반복적으로 지배적인 상황 — 즉 연속된 원소 다수가 다른 run의 현재 원소보다 작은 경우 — 에서는 하나씩 비교하는 대신, 지수적 탐색(1, 2, 4, 8... 위치)으로 경계를 먼저 찾고 지배 구간 전체를 한 번에 복사합니다. 일반 Array 경로(ArrayPrototype.cpp)와 TypedArray 경로(JSGenericTypedArrayViewPrototypeFunctions.h) 모두에 이 변경이 적용되었습니다.

Standard merge inner loop:       Galloping merge inner loop:
  compare A[i] vs B[j]              gallopRight: probe B at 1,2,4,8… positions
  copy winner, advance one           find k where B[k] >= A[i]
  compare A[i] vs B[j+1]            bulk-copy B[j..j+k] to output
  ...O(n) comparisons               resume element-by-element

Significance

magic-forest benchmark에서 약 1.34배의 성능 향상을 달성했으며, galloping은 사용자 제어 comparator 함수와 상호작용하는 새로운 bulk-copy code path를 도입합니다. JS 엔진에서 type confusion 및 OOB 버그가 역사적으로 빈번하게 발생한 영역입니다.

Audit directions