Skip to content

Commit 73a3669

Browse files
committed
Update Array.prototype.sort to be consistent with tightened spec
https://bugs.webkit.org/show_bug.cgi?id=202582 Reviewed by Yusuke Suzuki and Keith Miller. JSTests: Provided microbenchmarks test receivers that are half-sorted: 50% of their items and item pairs (to accomodate merge sort) are at the right place. Arrays of multiple sizes (8/24/64 items) are tested with both userland and default comparator (to cover bucket sort). * ChakraCore/test/Array/array_sort.baseline-jsc: Fix typo in error message. * microbenchmarks/array-prototype-sort-large-array-comparator.js: Added. * microbenchmarks/array-prototype-sort-large-array.js: Added. * microbenchmarks/array-prototype-sort-medium-array-comparator.js: Added. * microbenchmarks/array-prototype-sort-medium-array.js: Added. * microbenchmarks/array-prototype-sort-small-array-comparator.js: Added. * microbenchmarks/array-prototype-sort-small-array.js: Added. * mozilla/js1_5/Array/regress-157652.js: Skip sorting sparse array of UINT_MAX size. * stress/regress-188577.js: Replace sort() with unshift() and refactor. Source/JavaScriptCore: This patch implements the spec change [1] that reduces amount of cases resulting in an implementation-defined sort order, aligning JSC with V8 and SpiderMonkey. To achieve this, we collect all existing non-undefined receiver elements to a temporary array, sort it, and write back sorted items, followed by `undefined` values and holes. This change is proven to be web-compatible (shipping since Chrome 76) and neutral on peak memory consumption in the wild. Although we can unobservably detect sparse receivers, we can't avoid creating a temporary array for common case since userland comparators may throw; string sorting won't measurably benefit from this, only increasing code complexity. This change uses @putByValDirect unless the spec requires [[Set]], avoids using closure variables, and adds a few drive-by optimizations, resulting in ~22% faster string sorting and 13% speed-up for userland comparators. Dromaeo/jslib is neutral. [1]: tc39/ecma262#1585 * builtins/ArrayPrototype.js: (sort.stringComparator): Optimization #1: replace char-by-char comparison loop with > operator, aligning JSC with V8 and SpiderMonkey. This semantically equivalent change alone is a ~15% progression for string sort. (sort.compact): (sort.commit): Optimization #2: copy large non-numeric arrays in a loop rather than @appendMemcpy. Using the latter unconditionally regresses provided microbenchmarks. (sort.merge): Optimization #3: replace `typeof` check and negation with strict equality. (sort.mergeSort): Optimization #4: always return sorted array instead of copying, even if it's the buffer. Tweak: create the buffer with correct length. (sort.bucketSort): Optimization #5: avoid emitting 2 extra get_by_val ops by saving bucket lookup to a variable. Tweak: create new bucket via array literal. (sort): Fix typo in error message. (sort.compactSparse): Deleted. (sort.compactSlow): Deleted. (sort.comparatorSort): Deleted. (sort.stringSort): Deleted. * runtime/ObjectConstructor.cpp: (JSC::ObjectConstructor::finishCreation): Remove @object.@getPrototypeOf as it's now unused and we have @getPrototypeOf intrinsic anyway. LayoutTests: While adding new LayoutTests for JS-only features is undesirable, it's a quick-and-dirty way to import the tests [1] and fix the call count/order of observable operations via debug() and text expectations. The tests are imported into LayoutTests/js/dom instead of LayoutTests/js for run-javascriptcore-tests to ignore them as they require array-sort-harness.js. These files will be removed shortly in favor of thorough test262 coverage, which is required for the proposal [2] to be merged. [1]: https://gist.github.com/szuend/05ae15b4e1329b264ab4c9a1cda09242 [2]: tc39/ecma262#1585 * TestExpectations: Mark a test as slow. * js/dom/array-sort-*-expected.txt: Added. * js/dom/array-sort-*.html: Added. * js/dom/script-tests/array-sort-*.js: Added. * js/resources/array-sort-harness.js: Added. Canonical link: https://commits.webkit.org/229696@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@267514 268f45cc-cd09-0410-ab3c-d52691b4dbfc
1 parent be51d8a commit 73a3669

67 files changed

Lines changed: 943 additions & 147 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎JSTests/ChakraCore/test/Array/array_sort.baseline-jsc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,5 +7,5 @@ for,sample,some,strings,testing - Output different in cscript due to NaN
77
1,2,3
88
10
99
1,1.2,4,4.8,12
10-
TypeError: Array.prototype.sort requires the comparsion function be a function or undefined
10+
TypeError: Array.prototype.sort requires the comparator argument to be a function or undefined
1111
1,2,3

‎JSTests/ChangeLog‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,26 @@
1+
2020-09-23 Alexey Shvayka <[email protected]>
2+
3+
Update Array.prototype.sort to be consistent with tightened spec
4+
https://bugs.webkit.org/show_bug.cgi?id=202582
5+
6+
Reviewed by Yusuke Suzuki and Keith Miller.
7+
8+
Provided microbenchmarks test receivers that are half-sorted: 50% of their
9+
items and item pairs (to accomodate merge sort) are at the right place.
10+
11+
Arrays of multiple sizes (8/24/64 items) are tested with both userland
12+
and default comparator (to cover bucket sort).
13+
14+
* ChakraCore/test/Array/array_sort.baseline-jsc: Fix typo in error message.
15+
* microbenchmarks/array-prototype-sort-large-array-comparator.js: Added.
16+
* microbenchmarks/array-prototype-sort-large-array.js: Added.
17+
* microbenchmarks/array-prototype-sort-medium-array-comparator.js: Added.
18+
* microbenchmarks/array-prototype-sort-medium-array.js: Added.
19+
* microbenchmarks/array-prototype-sort-small-array-comparator.js: Added.
20+
* microbenchmarks/array-prototype-sort-small-array.js: Added.
21+
* mozilla/js1_5/Array/regress-157652.js: Skip sorting sparse array of UINT_MAX size.
22+
* stress/regress-188577.js: Replace sort() with unshift() and refactor.
23+
124
2020-09-23 Yusuke Suzuki <[email protected]>
225

326
[JSC] Intl spec update: handle awkward rounding behavior
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
8+
].sort(comparator);
9+
}
Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
for (var i = 0; i < 1e4; ++i) {
2+
[
3+
"0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","O","N","M","L","K","J","I",
4+
"H","G","F","E","D","C","B","A","@","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]",
5+
"^","_","o","n","m","l","k","j","i","h","g","f","e","d","c","b","a","`"
6+
].sort();
7+
}
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
var comparator = (a, b) => a - b;
2+
3+
for (var i = 0; i < 1e5; ++i) {
4+
[0,1,2,3,4,5,11,10,9,8,7,6,12,13,14,15,16,17,23,22,21,20,19,18].sort(comparator);
5+
}
Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
for (var i = 0; i < 1e5; ++i) {
2+
["A","B","C","D","E","F","L","K","J","I","H","G","M","N","O","P","Q","R","X","W","V","U","T","S"].sort();
3+
}
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
var comparator = (a, b) => a - b;
2+
3+
for (var i = 0; i < 1e5; ++i) {
4+
[0,1,2,3,7,6,5,4].sort(comparator);
5+
}
Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
for (var i = 0; i < 1e5; ++i) {
2+
["A","B","C","D","H","G","F","E"].sort();
3+
}

‎JSTests/mozilla/js1_5/Array/regress-157652.js‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -117,9 +117,12 @@ printBugNumber(bug);
117117
printStatus(summary);
118118

119119
// JSC doesn't run out of memory, so we don't expect an abnormal exit code
120-
//expectExitCode(3);
121-
var IN_RHINO = inRhino();
120+
// expectExitCode(3);
122121

122+
// As of https://webkit.org/b/202582, JSC copies internal spare array to a
123+
// temporary buffer like Rhino, SpiderMonkey, and V8.
124+
// var IN_RHINO = inRhino();
125+
var IN_RHINO = true;
123126
if (!IN_RHINO)
124127
{
125128
var a1=Array(0xFFFFFFFF);

‎JSTests/stress/regress-188577.js‎

Lines changed: 5 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,16 +2,11 @@
22

33
var exception;
44
try {
5-
var i = 25000;
6-
var args = [];
7-
var v3;
8-
while (i--)
9-
args[i] = "a";
10-
var argsList = args.join();
11-
setter = Function(argsList, "");
12-
Object.defineProperty(args, '0', {set: setter});
13-
args.sort();
14-
5+
var args = new Array(25000).fill("a");
6+
Object.defineProperty(args, "0", {
7+
set: new Function(args.join(), ""),
8+
});
9+
args.unshift(1);
1510
} catch (e) {
1611
exception = e;
1712
}

0 commit comments

Comments
 (0)