Repository navigation
Commit 73a3669
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-d52691b4dbfc1 parent be51d8a commit 73a3669
67 files changed
Lines changed: 943 additions & 147 deletions
File tree
- JSTests
- ChakraCore/test/Array
- microbenchmarks
- mozilla/js1_5/Array
- stress
- LayoutTests
- js
- dom
- script-tests
- resources
- Source/JavaScriptCore
- builtins
- runtime
Some content is hidden
Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
7 | 7 | | |
8 | 8 | | |
9 | 9 | | |
10 | | - | |
| 10 | + | |
11 | 11 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
1 | 24 | | |
2 | 25 | | |
3 | 26 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
117 | 117 | | |
118 | 118 | | |
119 | 119 | | |
120 | | - | |
121 | | - | |
| 120 | + | |
122 | 121 | | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
123 | 126 | | |
124 | 127 | | |
125 | 128 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
2 | 2 | | |
3 | 3 | | |
4 | 4 | | |
5 | | - | |
6 | | - | |
7 | | - | |
8 | | - | |
9 | | - | |
10 | | - | |
11 | | - | |
12 | | - | |
13 | | - | |
14 | | - | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
15 | 10 | | |
16 | 11 | | |
17 | 12 | | |
| |||
0 commit comments