Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 6380373fc6a1a7651f2c4ce9159ee05093810394
https://github.com/WebKit/WebKit/commit/6380373fc6a1a7651f2c4ce9159ee05093810394
Author: Sosuke Suzuki <[email protected]>
Date: 2026-08-06 (Thu, 06 Aug 2026)
Changed paths:
A JSTests/microbenchmarks/array-prototype-sort-string-keys.js
A JSTests/microbenchmarks/json-parse-short-string-ids.js
A JSTests/stress/array-default-sort-radix-edge-cases.js
A JSTests/stress/json-parse-short-value-then-key.js
M Source/JavaScriptCore/runtime/ArrayPrototype.cpp
Log Message:
-----------
[JSC] Use counting sort for `Array#sort`
https://bugs.webkit.org/show_bug.cgi?id=317103
Reviewed by Yusuke Suzuki.
Sorting an array of strings without a comparator is common, e.g.
`Object.keys(obj).sort()`.
The current implementation partitions entries into a StdMap<char16_t, Vector>
per character,
which allocates map nodes and grows bucket vectors at every depth.
This patch replaces it with an in-place counting sort over the UTF-16 byte
stream, allocating
only a single scratch buffer for the whole sort. Buckets below
radixSortThreshold are finished
with std::ranges::sort, breaking ties on equal strings by their original index,
so the result
stays stable [1] without stable_sort's temporary buffer.
[1]: https://tc39.es/ecma262/#sec-array.prototype.sort
baseline
pr1
sort-custom-comparator 118.8305+-0.4189 ^
91.7292+-2.2847 ^ definitely 1.2954x faster
array-prototype-sort-large-array 30.0766+-0.5206 ^
7.7445+-0.1864 ^ definitely 3.8836x faster
array-prototype-sort-string-keys 58.1619+-0.8397 ^
29.2567+-0.2513 ^ definitely 1.9880x faster
array-prototype-sort-small-array-comparator
9.8417+-0.2049
9.7472+-0.2406
array-prototype-sort-large-array-comparator
5.5050+-0.1057 ?
5.6815+-0.3862 ? might be 1.0321x slower
array-prototype-sort-large-array-comparator-double
9.3065+-0.1118
9.0973+-0.2528 might be 1.0230x faster
array-prototype-sort-medium-array-comparator
30.2638+-0.2000 ?
30.3275+-0.5047 ?
array-prototype-sort-medium-array 45.2888+-0.4573 ^
30.9154+-0.4568 ^ definitely 1.4649x faster
array-prototype-sort-small-array 15.3942+-0.3811 ^
12.7713+-0.2441 ^ definitely 1.2054x faster
Tests: JSTests/microbenchmarks/array-prototype-sort-string-keys.js
JSTests/stress/array-default-sort-radix-edge-cases.js
* JSTests/microbenchmarks/array-prototype-sort-string-keys.js: Added.
* JSTests/stress/array-default-sort-radix-edge-cases.js: Added.
(ser):
(refCmp):
(rnd):
(trial.i.else):
(o.toString):
(checkStability):
* Source/JavaScriptCore/runtime/ArrayPrototype.cpp:
(JSC::sortBucketSort):
(JSC::sortImpl):
Canonical link: https://commits.webkit.org/318743@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
