Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 7726722f8ddd89a6c25ab071961cb059eab63d14
https://github.com/WebKit/WebKit/commit/7726722f8ddd89a6c25ab071961cb059eab63d14
Author: Yusuke Suzuki <[email protected]>
Date: 2024-04-23 (Tue, 23 Apr 2024)
Changed paths:
A
JSTests/microbenchmarks/array-prototype-sort-large-array-comparator-double.js
M LayoutTests/js/dom/array-prototype-properties-expected.txt
M Source/JavaScriptCore/CMakeLists.txt
M Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
M Source/JavaScriptCore/builtins/ArrayPrototype.js
M Source/JavaScriptCore/heap/GCMemoryOperations.h
M Source/JavaScriptCore/interpreter/CachedCall.h
M Source/JavaScriptCore/runtime/ArgList.cpp
M Source/JavaScriptCore/runtime/ArgList.h
M Source/JavaScriptCore/runtime/ArrayPrototype.cpp
M Source/JavaScriptCore/runtime/CommonIdentifiers.h
M Source/JavaScriptCore/runtime/JSArray.cpp
M Source/JavaScriptCore/runtime/JSArray.h
M Source/JavaScriptCore/runtime/JSGenericTypedArrayViewPrototypeFunctions.h
M Source/JavaScriptCore/runtime/JSGlobalObject.cpp
M Source/JavaScriptCore/runtime/JSTypedArrayViewPrototype.cpp
A Source/JavaScriptCore/runtime/StableSort.h
M Source/JavaScriptCore/runtime/VM.h
Log Message:
-----------
[JSC] Rewrite Array#sort
https://bugs.webkit.org/show_bug.cgi?id=273051
rdar://126833827
Reviewed by Keith Miller.
The world found that JS-implemented Array#sort is too slow, in particular in
Baseline JIT.
As a result, all other engines rewrote Array#sort in C++ (V8 and SpiderMonkey).
We also found that our Array#sort is too slow in Speedometer 3.0,
so we need to rewrite to follow to the other engines.
But now, the implementation is significantly simpler than before since
Array#sort is now well defined in the spec and we first copy content to
non user-observable array for sorting. This avoids any changes to this array
via function calls, so we can make sorting much simpler and
safer (even than JS implemented one).
1. VMTraps is moved to make access close to the other fields in VM.
2. Unify TypedArray / Array sort.
3. Add insertion sort path for smaller arrays.
4. Add a fast path skipping many comparisons by checking whether two subarrays
are already sorted. This is aligned to V8 and SpiderMonkey behavior.
ToT
Patched
uint32array-sort-custom 73.4050+-0.6354 ^
48.5713+-0.3494 ^ definitely 1.5113x faster
array-prototype-sort-large-array 25.9099+-0.0528 ^
22.4718+-0.1368 ^ definitely 1.1530x faster
array-prototype-sort-small-array-comparator
12.6596+-0.2183 ^
9.7617+-0.2233 ^ definitely 1.2969x faster
array-prototype-sort-large-array-comparator
13.8265+-0.1290 ^
6.7050+-0.2796 ^ definitely 2.0621x faster
sorting-benchmark 10.0377+-0.1360 ^
8.3962+-0.2557 ^ definitely 1.1955x faster
array-prototype-sort-medium-array-comparator
42.4683+-0.4189 ^
28.7110+-0.2369 ^ definitely 1.4792x faster
array-prototype-sort-medium-array 70.2655+-0.6955 ^
29.8648+-0.3713 ^ definitely 2.3528x faster
array-prototype-sort-small-array 20.3562+-0.1621 ^
9.7814+-0.0692 ^ definitely 2.0811x faster
* Source/JavaScriptCore/CMakeLists.txt:
* Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:
* Source/JavaScriptCore/builtins/ArrayPrototype.js:
(linkTimeConstant.sortStringComparator): Deleted.
(linkTimeConstant.sortCompact): Deleted.
(linkTimeConstant.sortCommit): Deleted.
(linkTimeConstant.sortMerge): Deleted.
(linkTimeConstant.sortMergeSort): Deleted.
(linkTimeConstant.sortBucketSort): Deleted.
(sort): Deleted.
* Source/JavaScriptCore/heap/GCMemoryOperations.h:
(JSC::gcSafeMemcpy):
(JSC::gcSafeMemmove):
* Source/JavaScriptCore/interpreter/CachedCall.h:
(JSC::CachedCall::callWithArguments):
* Source/JavaScriptCore/runtime/ArgList.cpp:
(JSC::ArgList::getSlice const):
(JSC::MarkedVectorBase::markLists):
(JSC::MarkedVectorBase::expandCapacity):
* Source/JavaScriptCore/runtime/ArgList.h:
(JSC::MarkedVector::at const):
(JSC::MarkedVector::set):
(JSC::ArgList::ArgList):
(JSC::ArgList::at const):
* Source/JavaScriptCore/runtime/ArrayPrototype.cpp:
(JSC::ArrayPrototype::finishCreation):
(JSC::sortCompact):
(JSC::sortBucketSort):
(JSC::sortStableSort):
(JSC::sortCommit):
(JSC::JSC_DEFINE_HOST_FUNCTION):
* Source/JavaScriptCore/runtime/CommonIdentifiers.h:
* Source/JavaScriptCore/runtime/JSArray.cpp:
(JSC::JSArray::appendMemcpy):
* Source/JavaScriptCore/runtime/JSArray.h:
* Source/JavaScriptCore/runtime/JSGenericTypedArrayViewPrototypeFunctions.h:
(JSC::genericTypedArrayViewProtoFuncSortImpl):
(JSC::typedArrayMerge): Deleted.
(JSC::typedArrayMergeSort): Deleted.
(JSC::coerceComparatorResultToBoolean): Deleted.
* Source/JavaScriptCore/runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::init):
* Source/JavaScriptCore/runtime/JSTypedArrayViewPrototype.cpp:
(JSC::JSTypedArrayViewPrototype::finishCreation):
* Source/JavaScriptCore/runtime/StableSort.h: Added.
(JSC::coerceComparatorResultToBoolean):
(JSC::arrayInsertionSort):
(JSC::arrayMerge):
(JSC::arrayStableSort):
* Source/JavaScriptCore/runtime/VM.h:
Canonical link: https://commits.webkit.org/277878@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
