Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: fedbb7bdc250525145431ecbc2243004bc754fef
https://github.com/WebKit/WebKit/commit/fedbb7bdc250525145431ecbc2243004bc754fef
Author: Yusuke Suzuki <[email protected]>
Date: 2026-08-10 (Mon, 10 Aug 2026)
Changed paths:
A JSTests/microbenchmarks/int8array-sort-large-array.js
A JSTests/microbenchmarks/uint8array-sort-large-array.js
A JSTests/microbenchmarks/uint8array-sort-low-entropy.js
A JSTests/microbenchmarks/uint8array-sort-medium-array.js
A JSTests/microbenchmarks/uint8array-sort-presorted.js
A JSTests/microbenchmarks/uint8array-sort-small-array.js
A JSTests/microbenchmarks/uint8array-sort-tiny-array.js
A JSTests/stress/typed-array-sort-counting-sort.js
M Source/JavaScriptCore/runtime/JSGenericTypedArrayView.h
M Source/JavaScriptCore/runtime/JSGenericTypedArrayViewInlines.h
Log Message:
-----------
[JSC] Add counting-sort to 1-byte element TypedArrays
https://bugs.webkit.org/show_bug.cgi?id=321263
rdar://184313545
Reviewed by Sosuke Suzuki.
Since 1-byte element is only having 256 patterns, we can apply
counting-sort easily. This patch applies counting-sort to 1-byte element
TypedArrays.
1. We use 128-size threshold, this is picked based on empirical
measurement.
2. Before starting counting-sort, we scan elements via SIMD to detect
"no sorting is necessary" case. This is relatively frequently
happening in the wild, and cost is cheap.
3. Then we do counting-sort.
3.1. We have 4-way histogram to avoid repeated read-update-write in
various places to the same places to make pipeline smoother. We do
not need to wait for the previous element's update and we can do
pipeline with 4-way histogram.
3.2. Then we scan this and construct the pattern (1) which element
exists (2) how many counts. This requires additional one time scan
of histogram, but in fact this makes filling faster due to removal
of branch prediction miss (typically more than 30% faster).
3.3. Then we fill the destination array with the accumulated sequence
data from 3.2.
ToT Patched
uint8array-sort-large-array 611.3374+-0.7106 ^
51.1908+-0.4178 ^ definitely 11.9423x faster
int8array-sort-large-array 611.3211+-0.5981 ^
52.4664+-0.3827 ^ definitely 11.6517x faster
uint8array-sort-medium-array 435.9760+-0.7050 ^
120.1770+-1.1086 ^ definitely 3.6278x faster
uint8array-sort-small-array 233.2745+-0.4947 ^
92.9591+-1.1352 ^ definitely 2.5094x faster
uint8array-sort-presorted 323.2663+-0.5266 ^
8.4205+-0.0350 ^ definitely 38.3902x faster
uint8array-sort-low-entropy 170.4761+-0.8698 ^
51.0791+-0.0686 ^ definitely 3.3375x faster
uint8array-sort-tiny-array 103.8720+-0.2649 ^
103.2340+-0.3650 ^ definitely 1.0062x faster
Tests: JSTests/microbenchmarks/int8array-sort-large-array.js
JSTests/microbenchmarks/uint8array-sort-large-array.js
JSTests/microbenchmarks/uint8array-sort-low-entropy.js
JSTests/microbenchmarks/uint8array-sort-medium-array.js
JSTests/microbenchmarks/uint8array-sort-presorted.js
JSTests/microbenchmarks/uint8array-sort-small-array.js
JSTests/microbenchmarks/uint8array-sort-tiny-array.js
JSTests/stress/typed-array-sort-counting-sort.js
* JSTests/microbenchmarks/int8array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint8array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint8array-sort-low-entropy.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint8array-sort-medium-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint8array-sort-presorted.js: Added.
* JSTests/microbenchmarks/uint8array-sort-small-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint8array-sort-tiny-array.js: Added.
(nextRandom):
* JSTests/stress/typed-array-sort-counting-sort.js: Added.
(shouldBe):
(nextRandom):
(sortedReference):
(shouldMatchReference):
(patterns.random):
(patterns.identical):
(patterns.ascending):
(patterns.descending):
(patterns.extremes):
(patterns.twoValues):
* Source/JavaScriptCore/runtime/JSGenericTypedArrayView.h:
* Source/JavaScriptCore/runtime/JSGenericTypedArrayViewInlines.h:
(JSC::JSGenericTypedArrayView<Adaptor>::sort):
(JSC::JSGenericTypedArrayView<Adaptor>::countingSort):
(JSC::JSGenericTypedArrayView<Adaptor>::countingSortWithCounters):
Canonical link: https://commits.webkit.org/318927@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
