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.
Created attachment 406610 [details] WIP
Created attachment 408305 [details] Patch
(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
Created attachment 408329 [details] Patch Adjust a stress test and expectations.
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).
(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
Great!
Comment on attachment 408329 [details] Patch Test failing is: regress-157652.js.mozilla-llint
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.
Created attachment 408753 [details] Patch Adjust Mozilla regress test.
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.)
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 [ ]).
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.
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?
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.
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?
Created attachment 409408 [details] Patch Use pre-increment, add @isJSArray check & assert, and add spaces to array literals.
(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.
Committed r267514: <https://trac.webkit.org/changeset/267514> All reviewed patches have been landed. Closing bug and clearing flags on attachment 409408 [details].
<rdar://problem/69475072>