Skip to content

Commit 7726722

Browse files
ConstellationConstellation
committed
[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
1 parent 4fb7829 commit 7726722

18 files changed

Lines changed: 539 additions & 296 deletions

‎JSTests/microbenchmarks/array-prototype-sort-large-array-comparator-double.js‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
var comparator = (a, b) => a - b;
2+
3+
for (var i = 0; i < 1e4; ++i) {
4+
[
5+
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,31,30,29,28,27,26,25,24,23,22,21,20,19,
6+
18,17,16,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,63,62,61,60,59,58,57,
7+
56,55,54,53,52,51,50,49,48.9
8+
].sort(comparator);
9+
}

‎LayoutTests/js/dom/array-prototype-properties-expected.txt‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ PASS Array.prototype.push.call(undefined, {}) threw exception TypeError: undefin
1212
PASS Array.prototype.reverse.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.reverse.call(undefined)').
1313
PASS Array.prototype.shift.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.shift.call(undefined)').
1414
PASS Array.prototype.slice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.slice.call(undefined, 0, 1)').
15-
PASS Array.prototype.sort.call(undefined) threw exception TypeError: Array.prototype.sort requires that |this| not be null or undefined.
15+
PASS Array.prototype.sort.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.sort.call(undefined)').
1616
PASS Array.prototype.splice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.splice.call(undefined, 0, 1)').
1717
PASS Array.prototype.unshift.call(undefined, {}) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.unshift.call(undefined, {})').
1818
PASS Array.prototype.every.call(undefined, toString) threw exception TypeError: Array.prototype.every requires that |this| not be null or undefined.

‎Source/JavaScriptCore/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1206,6 +1206,7 @@ set(JavaScriptCore_PRIVATE_FRAMEWORK_HEADERS
12061206
runtime/SmallStrings.h
12071207
runtime/SourceOrigin.h
12081208
runtime/SparseArrayValueMap.h
1209+
runtime/StableSort.h
12091210
runtime/StackAlignment.h
12101211
runtime/StackFrame.h
12111212
runtime/StringObject.h

‎Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1932,6 +1932,7 @@
19321932
E32D4DE926DAFD4300D4533A /* TemporalCalendar.h in Headers */ = {isa = PBXBuildFile; fileRef = E32D4DE326DAFD4300D4533A /* TemporalCalendar.h */; };
19331933
E32D4DEA26DAFD4300D4533A /* TemporalCalendarConstructor.h in Headers */ = {isa = PBXBuildFile; fileRef = E32D4DE426DAFD4300D4533A /* TemporalCalendarConstructor.h */; };
19341934
E32E1B3128DA8C7A00FCB571 /* IntlDurationFormat.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E319A3E628DA84E900DF18C7 /* IntlDurationFormat.cpp */; };
1935+
E32EF01E2BD72AEF001675BA /* StableSort.h in Headers */ = {isa = PBXBuildFile; fileRef = E32EF01D2BD72AEF001675BA /* StableSort.h */; settings = {ATTRIBUTES = (Private, ); }; };
19351936
E32F713D281B3C6600AFD21D /* UnifiedSource5-c.c in Sources */ = {isa = PBXBuildFile; fileRef = E32F7138281B3C6600AFD21D /* UnifiedSource5-c.c */; };
19361937
E32F713E281B3C6600AFD21D /* UnifiedSource4-c.c in Sources */ = {isa = PBXBuildFile; fileRef = E32F7139281B3C6600AFD21D /* UnifiedSource4-c.c */; };
19371938
E32F713F281B3C6600AFD21D /* UnifiedSource1-c.c in Sources */ = {isa = PBXBuildFile; fileRef = E32F713A281B3C6600AFD21D /* UnifiedSource1-c.c */; };
@@ -5504,6 +5505,7 @@
55045505
E32D4DE326DAFD4300D4533A /* TemporalCalendar.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TemporalCalendar.h; sourceTree = "<group>"; };
55055506
E32D4DE426DAFD4300D4533A /* TemporalCalendarConstructor.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TemporalCalendarConstructor.h; sourceTree = "<group>"; };
55065507
E32D4DE526DAFD4300D4533A /* TemporalCalendarConstructor.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TemporalCalendarConstructor.cpp; sourceTree = "<group>"; };
5508+
E32EF01D2BD72AEF001675BA /* StableSort.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = StableSort.h; sourceTree = "<group>"; };
55075509
E32F7138281B3C6600AFD21D /* UnifiedSource5-c.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; name = "UnifiedSource5-c.c"; path = "DerivedSources/JavaScriptCore/unified-sources/UnifiedSource5-c.c"; sourceTree = BUILT_PRODUCTS_DIR; };
55085510
E32F7139281B3C6600AFD21D /* UnifiedSource4-c.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; name = "UnifiedSource4-c.c"; path = "DerivedSources/JavaScriptCore/unified-sources/UnifiedSource4-c.c"; sourceTree = BUILT_PRODUCTS_DIR; };
55095511
E32F713A281B3C6600AFD21D /* UnifiedSource1-c.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; name = "UnifiedSource1-c.c"; path = "DerivedSources/JavaScriptCore/unified-sources/UnifiedSource1-c.c"; sourceTree = BUILT_PRODUCTS_DIR; };
@@ -8676,6 +8678,7 @@
86768678
425BA1337E4344E1B269A671 /* SourceOrigin.h */,
86778679
0F0CD4C315F6B6B50032F1C0 /* SparseArrayValueMap.cpp */,
86788680
0FB7F39215ED8E3800F167B2 /* SparseArrayValueMap.h */,
8681+
E32EF01D2BD72AEF001675BA /* StableSort.h */,
86798682
0F3AC751183EA1040032029F /* StackAlignment.h */,
86808683
0F6DB7E71D6124B200CDBF8E /* StackFrame.cpp */,
86818684
0F6DB7E81D6124B200CDBF8E /* StackFrame.h */,
@@ -11660,6 +11663,7 @@
1166011663
A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */,
1166111664
0FD82E54141DAEEE00179C94 /* SpeculatedType.h in Headers */,
1166211665
A785F6BC18C553FE00F10626 /* SpillRegistersMode.h in Headers */,
11666+
E32EF01E2BD72AEF001675BA /* StableSort.h in Headers */,
1166311667
0F3AC752183EA1040032029F /* StackAlignment.h in Headers */,
1166411668
0F6DB7E91D6124B500CDBF8E /* StackFrame.h in Headers */,
1166511669
A7C1EAF217987AB600299DB2 /* StackVisitor.h in Headers */,

‎Source/JavaScriptCore/builtins/ArrayPrototype.js‎

Lines changed: 0 additions & 194 deletions
Original file line numberDiff line numberDiff line change
@@ -344,200 +344,6 @@ function includes(searchElement /*, fromIndex*/)
344344
return false;
345345
}
346346

347-
@linkTimeConstant
348-
function sortStringComparator(a, b)
349-
{
350-
"use strict";
351-
352-
var aString = a.string;
353-
var bString = b.string;
354-
355-
if (aString === bString)
356-
return 0;
357-
358-
return aString > bString ? 1 : -1;
359-
}
360-
361-
@linkTimeConstant
362-
function sortCompact(receiver, receiverLength, compacted, isStringSort)
363-
{
364-
"use strict";
365-
366-
var undefinedCount = 0;
367-
var compactedIndex = 0;
368-
369-
for (var i = 0; i < receiverLength; ++i) {
370-
if (i in receiver) {
371-
var value = receiver[i];
372-
if (value === @undefined)
373-
++undefinedCount;
374-
else {
375-
@putByValDirect(compacted, compactedIndex,
376-
isStringSort ? {string: @toString(value), value} : value);
377-
++compactedIndex;
378-
}
379-
}
380-
}
381-
382-
return undefinedCount;
383-
}
384-
385-
@linkTimeConstant
386-
function sortCommit(receiver, receiverLength, sorted, undefinedCount)
387-
{
388-
"use strict";
389-
390-
// Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
391-
392-
@assert(@isJSArray(sorted));
393-
var sortedLength = sorted.length;
394-
@assert(sortedLength + undefinedCount <= receiverLength);
395-
396-
var i = 0;
397-
if (@isJSArray(receiver) && sortedLength >= 64 && typeof sorted[0] !== "number") { // heuristic
398-
@appendMemcpy(receiver, sorted, 0);
399-
i = sortedLength;
400-
} else {
401-
for (; i < sortedLength; ++i)
402-
receiver[i] = sorted[i];
403-
}
404-
405-
for (; i < sortedLength + undefinedCount; ++i)
406-
receiver[i] = @undefined;
407-
408-
for (; i < receiverLength; ++i)
409-
delete receiver[i];
410-
}
411-
412-
@linkTimeConstant
413-
function sortMerge(dst, src, srcIndex, srcEnd, width, comparator)
414-
{
415-
"use strict";
416-
417-
var left = srcIndex;
418-
var leftEnd = @min(left + width, srcEnd);
419-
var right = leftEnd;
420-
var rightEnd = @min(right + width, srcEnd);
421-
422-
for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
423-
if (right < rightEnd) {
424-
if (left >= leftEnd) {
425-
@putByValDirect(dst, dstIndex, src[right]);
426-
++right;
427-
continue;
428-
}
429-
430-
// See https://bugs.webkit.org/show_bug.cgi?id=47825 on boolean special-casing
431-
var comparisonResult = comparator(src[right], src[left]);
432-
if (comparisonResult === false || comparisonResult < 0) {
433-
@putByValDirect(dst, dstIndex, src[right]);
434-
++right;
435-
continue;
436-
}
437-
438-
}
439-
440-
@putByValDirect(dst, dstIndex, src[left]);
441-
++left;
442-
}
443-
}
444-
445-
@linkTimeConstant
446-
function sortMergeSort(array, comparator)
447-
{
448-
"use strict";
449-
450-
var valueCount = array.length;
451-
var buffer = @newArrayWithSize(valueCount);
452-
453-
var dst = buffer;
454-
var src = array;
455-
for (var width = 1; width < valueCount; width *= 2) {
456-
for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
457-
@sortMerge(dst, src, srcIndex, valueCount, width, comparator);
458-
459-
var tmp = src;
460-
src = dst;
461-
dst = tmp;
462-
}
463-
464-
return src;
465-
}
466-
467-
@linkTimeConstant
468-
function sortBucketSort(array, dst, bucket, depth)
469-
{
470-
"use strict";
471-
472-
if (bucket.length < 32 || depth > 32) {
473-
var sorted = @sortMergeSort(bucket, @sortStringComparator);
474-
for (var i = 0; i < sorted.length; ++i) {
475-
@putByValDirect(array, dst, sorted[i].value);
476-
++dst;
477-
}
478-
return dst;
479-
}
480-
481-
var buckets = [ ];
482-
@setPrototypeDirect.@call(buckets, null);
483-
for (var i = 0; i < bucket.length; ++i) {
484-
var entry = bucket[i];
485-
var string = entry.string;
486-
if (string.length == depth) {
487-
@putByValDirect(array, dst, entry.value);
488-
++dst;
489-
continue;
490-
}
491-
492-
var c = string.@charCodeAt(depth);
493-
var cBucket = buckets[c];
494-
if (cBucket)
495-
@arrayPush(cBucket, entry);
496-
else
497-
@putByValDirect(buckets, c, [ entry ]);
498-
}
499-
500-
for (var i = 0; i < buckets.length; ++i) {
501-
if (!buckets[i])
502-
continue;
503-
dst = @sortBucketSort(array, dst, buckets[i], depth + 1);
504-
}
505-
506-
return dst;
507-
}
508-
509-
function sort(comparator)
510-
{
511-
"use strict";
512-
513-
var isStringSort = false;
514-
if (comparator === @undefined)
515-
isStringSort = true;
516-
else if (!@isCallable(comparator))
517-
@throwTypeError("Array.prototype.sort requires the comparator argument to be a function or undefined");
518-
519-
var receiver = @toObject(this, "Array.prototype.sort requires that |this| not be null or undefined");
520-
var receiverLength = @toLength(receiver.length);
521-
522-
// For compatibility with Firefox and Chrome, do nothing observable
523-
// to the target array if it has 0 or 1 sortable properties.
524-
if (receiverLength < 2)
525-
return receiver;
526-
527-
var compacted = [ ];
528-
var sorted = null;
529-
var undefinedCount = @sortCompact(receiver, receiverLength, compacted, isStringSort);
530-
531-
if (isStringSort) {
532-
sorted = @newArrayWithSize(compacted.length);
533-
@sortBucketSort(sorted, 0, compacted, 0);
534-
} else
535-
sorted = @sortMergeSort(compacted, comparator);
536-
537-
@sortCommit(receiver, receiverLength, sorted, undefinedCount);
538-
return receiver;
539-
}
540-
541347
@linkTimeConstant
542348
function concatSlowPath()
543349
{

‎Source/JavaScriptCore/heap/GCMemoryOperations.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ constexpr size_t mediumCutoff = 4 * 1024;
4040

4141
// This is a forwards loop so gcSafeMemmove can rely on the direction.
4242
template <typename T>
43-
ALWAYS_INLINE void gcSafeMemcpy(T* dst, T* src, size_t bytes)
43+
ALWAYS_INLINE void gcSafeMemcpy(T* dst, const T* src, size_t bytes)
4444
{
4545
static_assert(sizeof(T) == sizeof(JSValue));
4646
RELEASE_ASSERT(bytes % 8 == 0);
@@ -143,7 +143,7 @@ ALWAYS_INLINE void gcSafeMemcpy(T* dst, T* src, size_t bytes)
143143
}
144144

145145
template <typename T>
146-
ALWAYS_INLINE void gcSafeMemmove(T* dst, T* src, size_t bytes)
146+
ALWAYS_INLINE void gcSafeMemmove(T* dst, const T* src, size_t bytes)
147147
{
148148
static_assert(sizeof(T) == sizeof(JSValue));
149149
RELEASE_ASSERT(bytes % 8 == 0);

‎Source/JavaScriptCore/interpreter/CachedCall.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -131,7 +131,7 @@ class CachedCall : public CallLinkInfoBase {
131131
}
132132

133133
template<typename... Args>
134-
JSValue callWithArguments(JSGlobalObject* globalObject, JSValue thisValue, Args... args)
134+
ALWAYS_INLINE JSValue callWithArguments(JSGlobalObject* globalObject, JSValue thisValue, Args... args)
135135
{
136136
VM& vm = m_vm;
137137
auto scope = DECLARE_THROW_SCOPE(vm);

‎Source/JavaScriptCore/runtime/ArgList.cpp‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ void MarkedVectorBase::addMarkSet(JSValue v)
4545

4646
void ArgList::getSlice(int startIndex, ArgList& result) const
4747
{
48-
if (startIndex <= 0 || startIndex >= m_argCount) {
48+
if (startIndex <= 0 || static_cast<unsigned>(startIndex) >= m_argCount) {
4949
result = ArgList();
5050
return;
5151
}
@@ -60,7 +60,7 @@ void MarkedVectorBase::markLists(Visitor& visitor, ListSet& markSet)
6060
ListSet::iterator end = markSet.end();
6161
for (ListSet::iterator it = markSet.begin(); it != end; ++it) {
6262
MarkedVectorBase* list = *it;
63-
for (int i = 0; i < list->m_size; ++i)
63+
for (unsigned i = 0; i < list->m_size; ++i)
6464
visitor.appendUnbarriered(JSValue::decode(list->slotFor(i)));
6565
}
6666
}
@@ -86,7 +86,7 @@ auto MarkedVectorBase::expandCapacity() -> Status
8686
return expandCapacity(checkedNewCapacity);
8787
}
8888

89-
auto MarkedVectorBase::expandCapacity(int newCapacity) -> Status
89+
auto MarkedVectorBase::expandCapacity(unsigned newCapacity) -> Status
9090
{
9191
setNeedsOverflowCheck();
9292
ASSERT(m_capacity < newCapacity);
@@ -96,7 +96,7 @@ auto MarkedVectorBase::expandCapacity(int newCapacity) -> Status
9696
EncodedJSValue* newBuffer = static_cast<EncodedJSValue*>(FastMalloc::tryMalloc(checkedSize));
9797
if (!newBuffer)
9898
return Status::Overflowed;
99-
for (int i = 0; i < m_size; ++i) {
99+
for (unsigned i = 0; i < m_size; ++i) {
100100
newBuffer[i] = m_buffer[i];
101101
addMarkSet(JSValue::decode(m_buffer[i]));
102102
}

0 commit comments

Comments
 (0)