Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: cd9b9860484074e45f586e5f988f9273f16a8404
https://github.com/WebKit/WebKit/commit/cd9b9860484074e45f586e5f988f9273f16a8404
Author: Yusuke Suzuki <[email protected]>
Date: 2026-03-30 (Mon, 30 Mar 2026)
Changed paths:
A JSTests/slowMicrobenchmarks/magic-forest.js
A JSTests/stress/sort-galloping-merge-optimizations.js
M Source/JavaScriptCore/runtime/ArrayPrototype.cpp
M Source/JavaScriptCore/runtime/JSGenericTypedArrayViewPrototypeFunctions.h
M Source/JavaScriptCore/runtime/StableSort.h
Log Message:
-----------
[JSC] Implement galloping merge in PowerSort
https://bugs.webkit.org/show_bug.cgi?id=310948
rdar://17190833
Reviewed by Yijia Huang.
This patch enhances our existing PowerSort implementation with three
extensions.
1. We are always returning src as a result. And dst side is just a
working copy for the algorithm. We avoid unnecessary initial copy.
2. We extended `extendRunRight` to `extendAndNormalizeRun`, which can
also detect descending patterns and extend the run by reversing at
last.
3. We introduced galloping merge: this is originally introduced in
TimSort[1]. The idea of galloping merge is "it is quite common that
cluster of elements are lower / higher than the first / last element
of the other run. Then instead of comparing both first elements
one-by-one and merging them, we should find the lower / higher
elements than the other run's first / last element, and copy them in
a bulk manner". This can avoid calling comparison invocation frequently,
which is very costly in JS sort implementation. gallopLeft and
gallopRight is basically finding an insertion point in the run, but
instead of using binary search, it is using galloping.
ToT Patched
magic-forest 464.3367+-5.3030 ^ 346.2807+-1.6506 ^
definitely 1.3409x faster
Apple OSS approval: OSS-24108
[1]: https://github.com/python/cpython/blob/main/Objects/listsort.txt
Test: JSTests/stress/sort-galloping-merge-optimizations.js
* JSTests/slowMicrobenchmarks/magic-forest.js: Added.
(Forest):
(Forest.prototype.wolfDevoursGoat):
(Forest.prototype.lionDevoursGoat):
(Forest.prototype.lionDevoursWolf):
(Forest.prototype.meal):
(Forest.prototype.isStable):
(Forest.prototype.toString):
(Forest.compare):
(meal):
(stableForests):
(findStableForests):
(go):
(goUI):
* JSTests/stress/sort-galloping-merge-optimizations.js: Added.
(assertSorted):
(assertStable):
(assertArraysEqual):
(assertSameElements):
(makePRNG):
(throw.new.Error):
* Source/JavaScriptCore/runtime/ArrayPrototype.cpp:
(JSC::sortStableSort):
(JSC::sortImpl):
* Source/JavaScriptCore/runtime/JSGenericTypedArrayViewPrototypeFunctions.h:
(JSC::genericTypedArrayViewProtoFuncSortImpl):
* Source/JavaScriptCore/runtime/StableSort.h:
(JSC::extendAndNormalizeRun):
(JSC::gallopLeft):
(JSC::gallopRight):
(JSC::mergePowersortRuns):
(JSC::arrayStableSort):
Canonical link: https://commits.webkit.org/310282@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
