Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 6b13bfa7ba4341e5041b6f02566d2dd89fd2b855
https://github.com/WebKit/WebKit/commit/6b13bfa7ba4341e5041b6f02566d2dd89fd2b855
Author: Yusuke Suzuki <[email protected]>
Date: 2026-08-17 (Mon, 17 Aug 2026)
Changed paths:
A JSTests/microbenchmarks/float32array-sort-large-array.js
A JSTests/microbenchmarks/float64array-sort-large-array.js
A JSTests/microbenchmarks/float64array-sort-low-entropy.js
A JSTests/microbenchmarks/float64array-sort-medium-array.js
A JSTests/microbenchmarks/float64array-sort-presorted.js
A JSTests/microbenchmarks/float64array-sort-small-array.js
A JSTests/microbenchmarks/int16array-sort-large-array.js
A JSTests/microbenchmarks/int16array-sort-low-entropy.js
A JSTests/microbenchmarks/int32array-sort-large-array.js
A JSTests/microbenchmarks/int32array-sort-low-entropy.js
A JSTests/microbenchmarks/int32array-sort-medium-array.js
A JSTests/microbenchmarks/int32array-sort-presorted.js
A JSTests/microbenchmarks/int32array-sort-small-array.js
A JSTests/microbenchmarks/uint16array-sort-large-array.js
A JSTests/microbenchmarks/uint32array-sort-large-array.js
A JSTests/stress/typed-array-sort-radix-sort.js
M JSTests/stress/typedarray-sort-out-of-memory.js
M Source/JavaScriptCore/runtime/JSGenericTypedArrayView.h
M Source/JavaScriptCore/runtime/JSGenericTypedArrayViewInlines.h
M Source/WTF/wtf/SIMDHelpers.h
M Tools/TestWebKitAPI/CMakeLists.txt
M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
A Tools/TestWebKitAPI/Tests/WTF/SIMDHelpers.cpp
Log Message:
-----------
[JSC] Implement radix-sort for TypedArrays
https://bugs.webkit.org/show_bug.cgi?id=321877
rdar://185056908
Reviewed by Sosuke Suzuki.
Since TypedArrays' element size are fixed, we can apply radix-sort. For
1-byte sized elements, we already introduced counting-sort. And for the
rest of the element types, we use radix-sort: uint16_t becomes two
uint8_t digits. Performing the counting-sort onto the lower uint8_t
side, and then doing the counting-sort onto the upper uint8_t.
ToT Patched
uint8array-sort-large-array 49.7578+-1.6459
49.7540+-0.8851
uint32array-sort-large-array 132.7664+-5.3124 ^
53.1423+-0.6340 ^ definitely 2.4983x faster
float64array-sort-large-array 97.6190+-4.4608 ^
37.8412+-0.1655 ^ definitely 2.5797x faster
int32array-sort-large-array 130.4901+-5.7267 ^
56.2865+-0.5195 ^ definitely 2.3183x faster
float64array-sort-medium-array 69.3409+-4.0941 ^
63.3630+-0.8433 ^ definitely 1.0943x faster
uint32array-sort-custom 9.6304+-0.1055 ?
9.6732+-0.1015 ?
uint16array-sort-large-array 127.9445+-0.7055 ^
28.0103+-1.0780 ^ definitely 4.5678x faster
int8array-sort-large-array 51.9604+-0.7734 ?
53.1044+-1.9928 ? might be 1.0220x slower
uint8array-sort-medium-array 114.3740+-2.3787
113.5297+-3.5727
int16array-sort-large-array 128.7244+-0.4794 ^
29.1688+-0.5807 ^ definitely 4.4131x faster
float64array-sort-small-array 133.8621+-2.3568 ?
134.3342+-3.1311 ?
int32array-sort-small-array 124.7704+-0.5951 ?
124.9305+-0.6441 ?
float64array-sort-presorted 129.4033+-2.1667 ^
70.1832+-0.1949 ^ definitely 1.8438x faster
uint8array-sort-small-array 88.8232+-6.2246
88.5175+-2.4005
float32array-sort-large-array 115.9230+-0.9632 ^
62.4550+-0.3878 ^ definitely 1.8561x faster
uint8array-sort-presorted 8.3450+-0.2152
8.2700+-0.2215
uint8array-sort-low-entropy 50.0322+-0.2387
49.9000+-0.3350
float64array-sort-low-entropy 117.3185+-1.2640 ?
119.8619+-1.7623 ? might be 1.0217x slower
int32array-sort-low-entropy 115.2864+-3.2295
114.4655+-2.0151
uint8array-sort-tiny-array 97.7407+-0.9797 ?
97.9517+-1.0774 ?
int32array-sort-medium-array 130.4366+-1.6415 ^
91.3443+-0.2602 ^ definitely 1.4280x faster
int32array-sort-presorted 115.2502+-1.0671 ^
17.0865+-0.9215 ^ definitely 6.7451x faster
int16array-sort-low-entropy 121.2838+-0.7962 ?
121.5654+-2.7104 ?
<geometric> 82.5904+-0.3588 ^
55.2056+-0.1905 ^ definitely 1.4961x faster
Tests: JSTests/microbenchmarks/float32array-sort-large-array.js
JSTests/microbenchmarks/float64array-sort-large-array.js
JSTests/microbenchmarks/float64array-sort-low-entropy.js
JSTests/microbenchmarks/float64array-sort-medium-array.js
JSTests/microbenchmarks/float64array-sort-presorted.js
JSTests/microbenchmarks/float64array-sort-small-array.js
JSTests/microbenchmarks/int16array-sort-large-array.js
JSTests/microbenchmarks/int16array-sort-low-entropy.js
JSTests/microbenchmarks/int32array-sort-large-array.js
JSTests/microbenchmarks/int32array-sort-low-entropy.js
JSTests/microbenchmarks/int32array-sort-medium-array.js
JSTests/microbenchmarks/int32array-sort-presorted.js
JSTests/microbenchmarks/int32array-sort-small-array.js
JSTests/microbenchmarks/uint16array-sort-large-array.js
JSTests/microbenchmarks/uint32array-sort-large-array.js
JSTests/stress/typed-array-sort-radix-sort.js
Tools/TestWebKitAPI/Tests/WTF/SIMDHelpers.cpp
* JSTests/microbenchmarks/float32array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/float64array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/float64array-sort-low-entropy.js: Added.
(nextRandom):
* JSTests/microbenchmarks/float64array-sort-medium-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/float64array-sort-presorted.js: Added.
* JSTests/microbenchmarks/float64array-sort-small-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/int16array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/int16array-sort-low-entropy.js: Added.
(nextRandom):
* JSTests/microbenchmarks/int32array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/int32array-sort-low-entropy.js: Added.
(nextRandom):
* JSTests/microbenchmarks/int32array-sort-medium-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/int32array-sort-presorted.js: Added.
* JSTests/microbenchmarks/int32array-sort-small-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint16array-sort-large-array.js: Added.
(nextRandom):
* JSTests/microbenchmarks/uint32array-sort-large-array.js: Added.
(nextRandom):
* JSTests/stress/typed-array-sort-radix-sort.js: Added.
(shouldBe):
(nextRandom):
(isBigIntArray):
(compareNumbers):
(compareBigInts):
(sortedReference):
(coerce):
(integerPatterns.random):
(integerPatterns.identical):
(integerPatterns.ascending):
(integerPatterns.descending):
(integerPatterns.lowDigitOnly):
(integerPatterns.secondDigitOnly):
(integerPatterns.twoValues):
(integerPatterns.alternatingSign):
(inversionPositions):
(storageView):
(sweepInversions):
(compareFloats):
(shouldMatchFloatReference):
(floatPatterns.random):
(floatPatterns.identical):
(floatPatterns.ascending):
(floatPatterns.descending):
(floatPatterns.subnormalAndTiny):
(floatPatterns.largeMagnitude):
(floatPatterns.withZeros):
(floatPatterns.withInfinities):
(floatPatterns.withNaN):
(floatPatterns.allNaN):
(floatPatterns.negativeNaN):
(ascendingWideBase):
(shouldRestoreBase):
* JSTests/stress/typedarray-sort-out-of-memory.js:
(catch):
* Source/JavaScriptCore/runtime/JSGenericTypedArrayView.h:
* Source/JavaScriptCore/runtime/JSGenericTypedArrayViewInlines.h:
(JSC::JSGenericTypedArrayView<Adaptor>::sort):
(JSC::JSGenericTypedArrayView<Adaptor>::sortKey):
(JSC::JSGenericTypedArrayView<Adaptor>::sortKeyDigit):
(JSC::JSGenericTypedArrayView<Adaptor>::isNonDescending):
(JSC::JSGenericTypedArrayView<Adaptor>::countingSort):
(JSC::JSGenericTypedArrayView<Adaptor>::hasFewDistinctValues):
(JSC::JSGenericTypedArrayView<Adaptor>::radixSort):
(JSC::JSGenericTypedArrayView<Adaptor>::radixSortWithCounters):
* Source/WTF/wtf/SIMDHelpers.h:
(WTF::SIMD::bitXor2):
(WTF::SIMD::bitXor):
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WTF/SIMDHelpers.cpp: Added.
(TestWebKitAPI::extractLanes):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, LessThanUnsigned8)):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, LessThanUnsigned16)):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, LessThanUnsigned32)):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, LessThanUnsigned64)):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, Bitwise32)):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, Bitwise64)):
(TestWebKitAPI::TEST(WTF_SIMDHelpers, LessThanFeedsIsNonZero)):
Canonical link: https://commits.webkit.org/319339@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
