Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
11193032:
Use JavaScript's Array.sort. (Closed)
|
Created:
8 years, 2 months ago by ahe Modified:
5 years, 10 months ago CC:
reviews_dartlang.org, ngeoffray, floitsch Visibility:
Public. |
DescriptionUse JavaScript's Array.sort.
Patch Set 1 #
Total comments: 13
Patch Set 2 : Address Lasse's concers #Patch Set 3 : Minor tweak to sort$0 #
Total comments: 16
Messages
Total messages: 18 (0 generated)
Nice. How is performance? I'm interested in comparing three configurations, they can be tested on d8. 1. The plain dual pivot quicksort as generated by dart2js today 2. Your change 3. dual pivot quicksort, but with a really smart array bounds check remover that removes all bounds checks (I believe it is possible with specialization against a set of constraints on the args or arg.length to eliminate all bound checks. i.e with the precondition to _doSort that 0 <= left <= right < a.length, you can prove the same on the recursive calls with a sufficiently strong solver). You can generate an approximation to this version from 1. by deleting bounds checks. I'm suspicious that DART_CLOSURE_TO_JS is too slow - e.g. it generates code that passes through a path using 'arguments[0]'. That is fine for handling mouse events at 100Hz, but not in this kind of inner loop. This example (and others I can think of, like calling JSON.stringify) have many fewer constraints than callpacks passed to addEventListener. The callback is called synchronously from within the same isolte context. A much cheaper conversion would be desirable and might be necessary.
https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:373: var jsCompare = JS('var', '(function (compareHelper, compare) {' A few linebreaks might improve the indentation, e.g. jsCompare = JS('var', '(funct.... https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:374: ' return function (a, b) { return compareHelper(compare, a, b); } })(#, #)', sort calls function (a, b), which calls the function returned by DART_CLOSURE_TO_JS, which pulls in the isolate library # unnecessary in this context calls some isolate code # unnecessary in this context calls compareHelper.call$3 which # probably could be eliminated calls compare.call$2(a, b) Without some more work here, this could be noticeably slower than the equivalent JavaScript program.
LGTM! https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:367: JS('var', '#.sort(#)', receiver, DART_CLOSURE_TO_JS(Comparable.compare)); 'var' -> 'void'? https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:374: ' return function (a, b) { return compareHelper(compare, a, b); } })(#, #)', Fix long line with a bit more adjacent string concat? https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:376: JS('var', '#.sort(#)', receiver, jsCompare); 'var' -> 'void'? https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... File dart/lib/compiler/implementation/lib/js_helper.dart (right): https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/js_helper.dart:1416: compareHelper(compare, a, b) => compare(a, b); Add a comment that explains what this is used for and why it's needed.
Stephen, I don't understand your comments about "arguments[0]" and "bringing in
the isolate library".
The relevant snippets of generated code are:
$.compareHelper = function(compare, a, b) {
return compare.call$2(a, b);
};
...
$.sort$1 = function(receiver, compare) {
if (!$.isJsArray(receiver))
return receiver.sort$1(compare);
$.checkMutable(receiver, 'sort');
receiver.sort((function (compareHelper, compare) { return function (a, b) {
return compareHelper(compare, a, b); } })($.compareHelper.call$3, compare));
};
...
$.compareHelper.call$3 = $.compareHelper;
On 2012/10/18 07:47:47, ahe wrote:
> Stephen, I don't understand your comments about "arguments[0]" and "bringing
in
> the isolate library".
>
> The relevant snippets of generated code are:
>
> $.compareHelper = function(compare, a, b) {
> return compare.call$2(a, b);
> };
>
> ...
>
> $.sort$1 = function(receiver, compare) {
> if (!$.isJsArray(receiver))
> return receiver.sort$1(compare);
> $.checkMutable(receiver, 'sort');
> receiver.sort((function (compareHelper, compare) { return function (a, b) {
> return compareHelper(compare, a, b); } })($.compareHelper.call$3, compare));
> };
>
> ...
>
> $.compareHelper.call$3 = $.compareHelper;
Good!
Clearly I don't understand DART_CLOSURE_TO_JS.
The code generated / used for calling a native method that takes a function has
the elements I mention.
lgtm
https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:376: JS('var', '#.sort(#)', receiver, jsCompare); JavaScript's sort is hard-coded to sort null/undefined after all non-null/undefined elements, *without calling the compare function*. That might not be compatible with the compare function if one is provided. It's also slightly iffy that it doesn't throw on "[null,null,1].sort()" when null doesn't implement compareTo and 1.compareTo(null) throws.
PTAL https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:367: JS('var', '#.sort(#)', receiver, DART_CLOSURE_TO_JS(Comparable.compare)); On 2012/10/18 07:46:36, kasperl wrote: > 'var' -> 'void'? Done. https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:373: var jsCompare = JS('var', '(function (compareHelper, compare) {' On 2012/10/18 07:44:39, sra1 wrote: > A few linebreaks might improve the indentation, e.g. > > jsCompare = > JS('var', > '(funct.... > Using bind instead. https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:374: ' return function (a, b) { return compareHelper(compare, a, b); } })(#, #)', On 2012/10/18 07:44:39, sra1 wrote: > sort > calls function (a, b), which > calls the function returned by DART_CLOSURE_TO_JS, which > pulls in the isolate library # unnecessary in this context > calls some isolate code # unnecessary in this context > calls compareHelper.call$3 which # probably could be eliminated > calls compare.call$2(a, b) > > Without some more work here, this could be noticeably slower than the equivalent > JavaScript program. You are correct. I have used tests/co19/src/LibTest/core/List/sort_A01_t06.dart to benchmark this. Original DualPivotQuickSort is pretty fast: 228ms This is what I'm using now: jsCompare = DART_CLOSURE_TO_JS(compareHelper); jsCompare = JS('var', '#.bind(#, #)', jsCompare, null, compare); More than twice as slow: 550ms It improves if I cheat (in a fairly general way): jsCompare = JS('var', r'#.call$2.bind(#)', compare, compare); to: 467ms But if I cheat even further and does: jsCompare = JS('var', r'#.call$2', compare); It becomes really fast: 164ms (which is significantly better than 228ms). In those numbers I also included a fix for what Lasse pointed out. This means that I have to run through the array to see if it has nulls. If I remove that check, the test runs in about the same time. Kasper and I concluded that we need a smarter way to extract a JS closure from a Dart closure, but that we should land this change. https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:374: ' return function (a, b) { return compareHelper(compare, a, b); } })(#, #)', On 2012/10/18 07:46:36, kasperl wrote: > Fix long line with a bit more adjacent string concat? Using bind which is shorter. https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:376: JS('var', '#.sort(#)', receiver, jsCompare); On 2012/10/18 07:46:36, kasperl wrote: > 'var' -> 'void'? Done. https://codereview.chromium.org/11193032/diff/1/dart/lib/compiler/implementat... dart/lib/compiler/implementation/lib/interceptors.dart:376: JS('var', '#.sort(#)', receiver, jsCompare); On 2012/10/18 08:23:28, Lasse Reichstein Nielsen wrote: > JavaScript's sort is hard-coded to sort null/undefined after all > non-null/undefined elements, *without calling the compare function*. That might > not be compatible with the compare function if one is provided. It's also > slightly iffy that it doesn't throw on "[null,null,1].sort()" when null doesn't > implement compareTo and 1.compareTo(null) throws. Done.
LGTM. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:417: jsCompare = JS('var', '#.bind(#, #)', jsCompare, null, compare); Is 'bind' fast now? That would be great :) Try replacing it with this and see which is faster: JS("var", "(function(compare, jsCompare) { return function(a,b) { return jsCompare(compare, a, b); }; })(#,#)", compare, jsCompare); https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/js_helper.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/js_helper.dart:1423: compare(a, b); return result? (I.e., is this tested? :)
LGTM. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:365: if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort()); After this if I would call sort$1(receiver, Comparable.compare). It will reevaluate the isJsArray test, but make things much simpler. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:391: int length = JS('int', '#.length', receiver); Just tell dart2js that receiver is a JavaScript-array, instead of having all these JS here. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:395: for (int i = 0; i < length; i++) { Given that you already run through the array, you could also see if every element is a number (but not NaN, Infinity, -Infinity). If the compare function === Compare.compareTo (the common case) we could probably be even faster by avoiding the expensive compareTo function and creating a three phase sorting: - count the -0s and replace them with 0s. - sort using function(x, y) { return x - y; } - search for the first 0 and replace the first ones with as many -0s as there were in the beginning. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:396: // JavaScript's Array.prototype.sort has wierd semantics for null. weird https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:401: array = JS('var', '#.slice(0)', array); Why do we need a copy? To avoid the try/finally? https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:408: if (hasNull) { I would special case for the Compare.compare: if (compare === Compare.compare && hasNull) jsCompare = ...; In that case you don't even need to bind.
https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:365: if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort()); The trick is that this is simpler because we know the compare function - it will not work on nulls. So instead of copying the array contents if it contains a null, we just make it throw immediately. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:369: if (length == 0 || length == 1) return; <= 1 should be fine, a JS Array's length can't be negative.
https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:365: if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort()); On 2012/10/18 13:04:00, Lasse Reichstein Nielsen wrote: > The trick is that this is simpler because we know the compare function - it will > not work on nulls. So instead of copying the array contents if it contains a > null, we just make it throw immediately. Since the shortcut only applies when it is going to throw, I wouldn't make the special case. If we really want to abort early I would rather special case in sort$1 (testing if compare === Compare.compareTo).
https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:401: array = JS('var', '#.slice(0)', array); Because any NullSentinel in the original array would be visible during the call to the compare function.
I forgot to mail this out. There has been a lot of changes to this code recently, but I would like to revive this CL. https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:391: int length = JS('int', '#.length', receiver); On 2012/10/18 12:27:22, floitsch wrote: > Just tell dart2js that receiver is a JavaScript-array, instead of having all > these JS here. How do I do that?
https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:391: int length = JS('int', '#.length', receiver); On 2012/11/23 08:43:42, ahe wrote: > On 2012/10/18 12:27:22, floitsch wrote: > > Just tell dart2js that receiver is a JavaScript-array, instead of having all > > these JS here. > > How do I do that? This code is dominated by isJsArray(receiver). Why is that not sufficient? https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:395: for (int i = 0; i < length; i++) { On 2012/10/18 12:27:22, floitsch wrote: > Given that you already run through the array, you could also see if every > element is a number (but not NaN, Infinity, -Infinity). If the compare function > === Compare.compareTo (the common case) we could probably be even faster by > avoiding the expensive compareTo function and creating a three phase sorting: > - count the -0s and replace them with 0s. > - sort using function(x, y) { return x - y; } > - search for the first 0 and replace the first ones with as many -0s as there > were in the beginning. This assumes compareTo returns num, not int. I'm not convinced that is a wise choice. You would need to weed out values within 2x of the max magnitude since otherwise the subtraction could overflow and return Infinity.
https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... File dart/lib/compiler/implementation/lib/interceptors.dart (right): https://codereview.chromium.org/11193032/diff/7003/dart/lib/compiler/implemen... dart/lib/compiler/implementation/lib/interceptors.dart:391: int length = JS('int', '#.length', receiver); On 2012/11/23 10:57:33, sra1 wrote: > On 2012/11/23 08:43:42, ahe wrote: > > On 2012/10/18 12:27:22, floitsch wrote: > > > Just tell dart2js that receiver is a JavaScript-array, instead of having all > > > these JS here. > > > > How do I do that? > > This code is dominated by isJsArray(receiver). > Why is that not sufficient? It should be, and now with the new interceptor approach this should work even better. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
