Bug 202582 – Update Array.prototype.sort to be consistent with tightened spec

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Keith Miller]

https://github.com/tc39/ecma262/pull/1585 Makes a couple of changes to the JS spec. We should figure of if these are compatible and if they have any negative perf impact.

[Keith Miller]

Created attachment 406610 [details]
WIP

[Alexey Shvayka]

Created attachment 408305 [details]
Patch

[Alexey Shvayka]

(In reply to Alexey Shvayka from comment #2)
> Created attachment 408305 [details]
> Patch

--outer 50:

                                                  r266703                    patch

array-prototype-sort-large-array-comparator    42.5801+-0.9797     ?     43.6993+-1.8978        ? might be 1.0263x slower
array-prototype-sort-medium-array-comparator  133.5314+-1.1700     ?    133.7426+-4.0513        ?
array-prototype-sort-small-array-comparator    52.4552+-0.8312     ^     45.2888+-0.8978        ^ definitely 1.1582x faster

array-prototype-sort-large-array               75.0851+-1.2930     ^     66.5084+-1.1930        ^ definitely 1.1290x faster
array-prototype-sort-medium-array             262.5951+-4.4579     ^    200.2939+-3.7561        ^ definitely 1.3110x faster
array-prototype-sort-small-array               86.0947+-1.4513     ^     70.4338+-1.3429        ^ definitely 1.2223x faster

[Alexey Shvayka]

Created attachment 408329 [details]
Patch

Adjust a stress test and expectations.

[Geoffrey Garen]

Can you try test patch against Dromaeo? My memory is that JQuery performance is very sensitive to sort order because JQuery sorts DOM nodes in every API that returns DOM nodes (e.g. the $ API).

[Alexey Shvayka]

(In reply to Geoffrey Garen from comment #5)
> Can you try test patch against Dromaeo? My memory is that JQuery performance
> is very sensitive to sort order because JQuery sorts DOM nodes in every API
> that returns DOM nodes (e.g. the $ API).

I appreciate your insight: even the latest jQuery, judging by its source code, performs sorting based on Node::compareDocumentPosition().


dromaeo-jslib, 10 samples, runs/s:

                            r266894       patch

DOM Modification (jQuery)     4794         4734
DOM Traversal (jQuery)         613          618
Total (jQuery + Prototype)    1702         1712

[Geoffrey Garen]

Great!

[Darin Adler]

Comment on attachment 408329 [details]
Patch

Test failing is:

regress-157652.js.mozilla-llint

[Darin Adler]

Since sorting based on compareDocumentPosition is so inefficient, I wonder if we could replace it with an efficient implementation. Something like: Find a common ancestor, put all the nodes to be sorted into a map, then do a single tree walk from the common ancestor, pulling the nodes out of the map in order. This could be implemented as a public DOM API for explicit use, and we could also do the additional work to detect cases where we can safely optimize by replacing with a call to that DOM API.

[Alexey Shvayka]

Created attachment 408753 [details]
Patch

Adjust Mozilla regress test.

[Darin Adler]

Comment on attachment 408753 [details]
Patch

I’m probably not the right reviewer for this; back when I did work on our sorting it was written in C++ and wrong in a lot of ways!

When testing a user land comparator, you chose the "numeric comparison" one, one that we may choose to do special optimizations for. I would want a test that used an unusual comparator that we’re highly unlikely to ever optimize with a special code path, like maybe one that reverses the characters in a string?

(Looking at these tests it makes me wonder if we will ever find we want to do constant folding on sort; just a random thought.)

[Yusuke Suzuki]

Comment on attachment 408753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=408753&action=review

r=me with comments.

> Source/JavaScriptCore/ChangeLog:33
> +        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.

Lol, nice.

> Source/JavaScriptCore/ChangeLog:46
> +        Optimization #4: always return sorted array instead of copying, even if it's the buffer.
> +        Also, create the buffer with correct length.

Nice.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:326
> +        return aString > bString ? 1 : -1;

Nice.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:358
> +            @appendMemcpy(receiver, sorted, 0);

Let's check the receiver is JSArray since @appendMemcpy only accepts JSArrays. So, receiver and sorted must be JSArray. While sorted is always JSArray, receiver is not (user can call Array#sort with non arrays). @isJSArray(receiver) is required.
And I think `@assert(@isJSArray(sorted))` here would be nice.
Can you add a test exercising this case?

> Source/JavaScriptCore/builtins/ArrayPrototype.js:383
> +                    right++;

Use `++right` for consistency since we are not using post-increment feature here.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:391
> +                    right++;

Ditto.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:397
> +            left++;

Ditto.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:426
> +                dst++;

Ditto.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:437
> +                dst++;

Ditto.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:446
> +                @putByValDirect(buckets, c, [entry]);

Let's use `[ entry ]` (adding spaces before and after [ ]).

[Yusuke Suzuki]

Comment on attachment 408753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=408753&action=review

> Source/JavaScriptCore/builtins/ArrayPrototype.js:338
> +                    undefinedCount++;

Ditto.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:342
> +                    compactedIndex++;

Ditto.

[Yusuke Suzuki]

Comment on attachment 408753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=408753&action=review

> Source/JavaScriptCore/builtins/ArrayPrototype.js:335
> +            if (i in receiver) {

One behavior change here is that `I in receiver` can return true when Array.prototype[I] etc. is defined while own property is not defined.
Is it aligned to the behavior of the other engines?

[Yusuke Suzuki]

Comment on attachment 408753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=408753&action=review

>> Source/JavaScriptCore/builtins/ArrayPrototype.js:335
>> +            if (i in receiver) {
> 
> One behavior change here is that `I in receiver` can return true when Array.prototype[I] etc. is defined while own property is not defined.
> Is it aligned to the behavior of the other engines?

V8 is checking own property, while SpiderMonkey is checking via `in`. Possibly either is OK.

[Keith Miller]

Comment on attachment 408753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=408753&action=review

r=me too with some more comments.

>> Source/JavaScriptCore/ChangeLog:33
>> +        progression for string sort.
> 
> Lol, nice.

Oof, lol

>>> Source/JavaScriptCore/builtins/ArrayPrototype.js:335
>>> +            if (i in receiver) {
>> 
>> One behavior change here is that `I in receiver` can return true when Array.prototype[I] etc. is defined while own property is not defined.
>> Is it aligned to the behavior of the other engines?
> 
> V8 is checking own property, while SpiderMonkey is checking via `in`. Possibly either is OK.

It seems that the new spec uses `HasProperty`, which is the same as `in`.

>> Source/JavaScriptCore/builtins/ArrayPrototype.js:358
>> +            @appendMemcpy(receiver, sorted, 0);
> 
> Let's check the receiver is JSArray since @appendMemcpy only accepts JSArrays. So, receiver and sorted must be JSArray. While sorted is always JSArray, receiver is not (user can call Array#sort with non arrays). @isJSArray(receiver) is required.
> And I think `@assert(@isJSArray(sorted))` here would be nice.
> Can you add a test exercising this case?

Ditto on the isJSArray check. Also, did you confirm that this is faster if the array contains non-numbers? @appendMemcpy should be fast in almost all cases (except if there are accessors but that's not worth worrying about). If it's not maybe we should see why?

[Alexey Shvayka]

Created attachment 409408 [details]
Patch

Use pre-increment, add @isJSArray check & assert, and add spaces to array literals.

[Alexey Shvayka]

(In reply to Keith Miller from comment #16)
> > Let's check the receiver is JSArray since @appendMemcpy only accepts JSArrays. So, receiver and sorted must be JSArray. While sorted is always JSArray, receiver is not (user can call Array#sort with non arrays). @isJSArray(receiver) is required.
> > And I think `@assert(@isJSArray(sorted))` here would be nice.
> > Can you add a test exercising this case?
> 
> Ditto on the isJSArray check.

I've added the check, but couldn't come up with a test that crashes the previous patch.
Although @appendMemcpy casts `receiver` to JSArray, moveElements() path is taken w/o an error.

This patch is adding LayoutTests/js/dom/script-tests/array-sort-proxy.js, which calls sort() on a Proxy.
Also, there are a few tests with JSFinalObject receiver:
  test262/test/built-ins/Array/prototype/sort/
    S15.4.4.11_A3_T1.js
    S15.4.4.11_A3_T2.js
    S15.4.4.11_A4_T3.js
    S15.4.4.11_A6_T2.js

> Also, did you confirm that this is faster if the array contains non-numbers?
> @appendMemcpy should be fast in almost all cases (except if there are accessors
> but that's not worth worrying about). If it's not maybe we should see why?

I can confirm it is faster if the array contains 1-char strings.
@appendMemcpy is indeed fast (unless ArrayWithUndecided gets converted).
It would be nice to drop this "heuristic". Maybe JS to C++ call is slowing things down?

> > V8 is checking own property, while SpiderMonkey is checking via `in`. Possibly either is OK.
> 
> It seems that the new spec uses `HasProperty`, which is the same as `in`.

I believe it is for consistency with other pre-harmony Array.prototype methods like forEach().
It is a nice find, I will check the tests and file test262 issue to make sure it's well-covered.

(In reply to Yusuke Suzuki from comment #12)
> Use `++right` for consistency since we are not using post-increment feature
> here.

> Let's use `[ entry ]` (adding spaces before and after [ ]).

We may consider using ESLint: it provides rules to enforce spacing and disallow `==` out-of-box, while being easily pluggable.
It's parser might need a small tweak to handle @intrinsics though.

[EWS]

Committed r267514: <https://trac.webkit.org/changeset/267514>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 409408 [details].

[Radar WebKit Bug Importer]

<rdar://problem/69475072>