1239710 - Specialize %TypedArray%.prototype.sort for Uint8Array and Int8Array

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[Morgan Phillips [:mrrrgn]]

We should make use of type information to boost the performance of sorting. In the case of int8/uint8 Counting Sort is the obvious algorithm to switch to: https://en.wikipedia.org/wiki/Counting_sort

I'm happy to mentor this bug.

Comment 1

[Daniel Näslund [:dannas]]

Hi Morgan! I'd like to work on this bug, could you assign me please?

I haven't looked at the firefox code base before, and have very little Javascript experience (I'm an embedded C++ programmer - looking to widen my views). But I'd like to take a stab at it.

So far I've followed the instructions on https://wiki.mozilla.org/JavaScript:New_to_SpiderMonkey: checked out the source code; ran the test suite; downloaded and ran the Sunspider benchmarks. I've also played around with the js interactive shell to get a feel for what a TypedArray is.

Bug 8704014 describes how the existing sort for TypedArray is self-hosting. Didn't know what that meant but found https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Internals/self-hosting.

I guess I need to answer these questions (not expecting answers, just trying to outline my unknows):

1. How can I specify that my sort() function should only be called for arrays of type Uint8Array/Int8Array? Is the dispatch done in JavaScript code or C++ code? Skimmed builtin/TypedArray.js, vm/TypedArrayObject.cpp and vm/SelfHosting.cpp but didn't understand how the code gets called.

2. Can the implementation for such a function be self-hosting?

3. Brush up on my JavaScript enough to be able write a correct, efficient counting sort for Uint8/Int8 (with accompanying tests and benchmarks) .

My next step: Figure out how to set a breakpoint on TypedArray.sort(); get a full backtrace of the JavaScript and C++ stack in order to understand where I can add my dispatch code.

Am I heading in the right direction? Do you have any suggestion on some resource I should read to get a better feel for how the code is organized? I still have a couple of wiki-pages linked from the "New to SpiderMonkey" web page I mentioned earlier, to plough through.

Comment 2

[Morgan Phillips [:mrrrgn]]

1. How can I specify that my sort() function should only be called for arrays of type Uint8Array/Int8Array? 

We'll want to dispatch from javascript (builtin/TypedArray.js) in TypedArraySort above where it currently calls a QuickSort. 

2. Can the implementation for such a function be self-hosting?

I believe at least a portion of the type testing function will need to be written in C++. We'll be able to call any such function from javascript by adding it to intrinsic_functions[] in vm/SelfHosting.cpp.

Here are the helpers I've found so far: http://mxr.mozilla.org/mozilla-central/source/js/src/jsfriendapi.h#1737

3. Brush up on my JavaScript enough to be able write a correct, efficient counting sort for Uint8/Int8 (with accompanying tests and benchmarks) .

See what we currently have in builtin/Sorting.js and tests/ecma_6/TypedArray/sort* to get a feel for previous work. We'll definitely want to verify that CountingSort is indeed faster than QuickSort. 

This is going to be awesome. :) \o/

Comment 3

[Morgan Phillips [:mrrrgn]]

Okay, regarding testing for the array type, I believe we'll want to add new methods: intrinsic_IsInt8TypedArray and intrinsic_IsUint8TypedArray 

then add them here https://dxr.mozilla.org/mozilla-central/source/js/src/vm/SelfHosting.cpp#1595 with names like: IsInt8TypedArray and IsUint8TypedArray

inside the methods you'll want to make use of JS_GetArrayBufferViewType (https://dxr.mozilla.org/mozilla-central/source/js/src/jsfriendapi.h#1870) which will return a Scalar::Type, so that you can do something like

return JS_GetArrayBufferViewType(v) == Scalar::Int8;

For an example of how to implement an intrinsic function check out https://dxr.mozilla.org/mozilla-central/source/js/src/vm/SelfHosting.cpp#783.

Comment 4

[Daniel Näslund [:dannas]]

Attachment: WIP patch for scratch countingsort

Comment 5

[Daniel Näslund [:dannas]]

Attachment: Simple benchmark script with output in comment

Haven't made that much progress yet, but I'm posting a simple benchmark script with some numbers and the WIP patch in the previous comment to keep the conversation alive.

Made a rough benchmark where I replaced the call to QuickSort in builtin/TypedArray.js. See the attachment for numbers, but countingsort is substantially faster on my testcase.

(I had expected that the JIT-compiler would optimize away the sort-call in my script, since the result is never used, but looks like that didn't happen (and I'm glad it didn't, since it would have complicated my testing). But out of curiosity: If I would have coded the same in C++, I would have had to add some asm volatile("" : "+r" (variable)) statement or similar to fool the optimizer. Why didn't SpiderMonkey optimize away my sort calls?

Comment 6

[Jan de Mooij [:jandem]]

(In reply to Daniel Näslund from comment #5)
> (I had expected that the JIT-compiler would optimize away the sort-call in
> my script, since the result is never used, but looks like that didn't happen
> (and I'm glad it didn't, since it would have complicated my testing). But
> out of curiosity: If I would have coded the same in C++, I would have had to
> add some asm volatile("" : "+r" (variable)) statement or similar to fool the
> optimizer. Why didn't SpiderMonkey optimize away my sort calls?

The JIT can eliminate dead code or move code out of loops, but for that to work, we have to prove the code has no side-effects (including infinite loops, exceptions, etc) etc. I don't think any (other) JS JIT can completely optimize away your sort function.

> // ### TODO(dannas): What's a List? AFAIK, that's not a Javascript type?
> // The wiki [1] says that List and Record are defined in EcmaScript spec to be similar to Array and Object.
> // ### Where is it defined? I can that List is mentioned in builtin/Utilities.js, but where is the full definition?

The "function List()" in that file is the full definition :)

>    // ### Can constructor expressions be used in self-hosted code?  The line below says yes.
>    // ### I got the impression they couldn't? Why so, in that case? What are the restrictions on self-hosted code?

Calling constructors is fine, but you have to be careful in self-hosted code: if you'd use Array instead of List, someone could do:

  Object.defineProperty(Array.prototype, "0", {set: () => { throw 1; }});

And then your self-hosted code would behave incorrectly:

  var arr = new Array();
  arr[0] = 3; // This will call the setter...

List is safe because it has a null prototype, so there's no way non-self-hosted code can affect its behavior.

Comment 7

[Daniel Näslund [:dannas]]

(In reply to Jan de Mooij [:jandem] from comment #6)

> The JIT can eliminate dead code or move code out of loops, but for that to
> work, we have to prove the code has no side-effects (including infinite
> loops, exceptions, etc) etc. I don't think any (other) JS JIT can completely
> optimize away your sort function.

Ok. I read http://mrale.ph/blog/2012/12/15/microbenchmarks-fairy-tale.html and got under the impression that JIT's would be very aggressive at dead code elimination. I'll have to read up/experiment with JIT optimizer to understand that part of the engine better. Will be fun! 
> 
> > // ### TODO(dannas): What's a List? AFAIK, that's not a Javascript type?
> > // The wiki [1] says that List and Record are defined in EcmaScript spec to be similar to Array and Object.
> > // ### Where is it defined? I can that List is mentioned in builtin/Utilities.js, but where is the full definition?
> 
> The "function List()" in that file is the full definition :)
Ah, I got tripped by the "new List()" expression. Calling functions with new?. I'm starting to suspect that learning JavaScript by hacking on a JavaScript Engine is not the proper thing to do. I'm slowly beginning to see how prototype thing works. /me reaches for his Douglas Crockford  and Eloquent Javascript book.
> 
> >    // ### Can constructor expressions be used in self-hosted code?  The line below says yes.
> >    // ### I got the impression they couldn't? Why so, in that case? What are the restrictions on self-hosted code?
> 
> Calling constructors is fine, but you have to be careful in self-hosted
> code: if you'd use Array instead of List, someone could do:
> 
>   Object.defineProperty(Array.prototype, "0", {set: () => { throw 1; }});
> 
> And then your self-hosted code would behave incorrectly:
> 
>   var arr = new Array();
>   arr[0] = 3; // This will call the setter...
> 
> List is safe because it has a null prototype, so there's no way
> non-self-hosted code can affect its behavior.

Ah. Thank you for taking the time to explain these things to me. Very much appreciated!

Comment 8

[Daniel Näslund [:dannas]]

Attachment: wip-v2.diff

One more WIP patch with lots of inline questions, mostly directed to myself but I'd very much appreciate if anyone has pointers to where I can find answers. 

I can sort Uint8Array's and Int8Array's by now. Yay! Will tidy up the patch and publish another one for review later today or - more likely - tomorrow.

Comment 9

[Daniel Näslund [:dannas]]

Attachment: 1239710.diff

I haven't added any more tests since the tests in tests/ecma_6/TypedArray already checks  custom comparators, edge values and generates random data to be sorted for both Uint8 and Int8.

I'll run the sunspider benchmarks to verify that the performance improves with this patch (my attached benchmark script suggests that it may do, but it's just an isolated micro-benchmark).

Testing done:

$ ./tests/jstests.py -d -j 4 build_OPT.OBJ/dist/bin/js
[6460|   0|   0| 493] 100% ==========================================>| 220.8s
PASS

$ ./jit-test/jit_test.py --no-slow build_OPT.OBJ/dist/bin/js 
[4981|   0|   0|   0] 100% ==========================================>| 139.5s
PASSED ALL

I haven't made wip-v2.diff obsolute yet. It contains a couple of questions that maybe someone can give hint at solutions to (they're not strictly related to the patch, and a few of them are phrased in a rather vague form, but anyway, they're there).

Comment 10

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8712816 [details] [diff] [review]
1239710.diff

Review of attachment 8712816 [details] [diff] [review]:
-----------------------------------------------------------------

I'm really impressed with how fast you've done this. Here are some things I noticed in my first pass.

::: js/src/builtin/TypedArray.js
@@ +1006,5 @@
>              return v;
>          }
>      }
>  
> +    // CountingSort doesn't invoke the comparefn

Why not move these to just after:
 var hasCustomCompare = comparefn !== undefined;

Then we will only create the wrapped compare function when we need it.

@@ +1009,5 @@
>  
> +    // CountingSort doesn't invoke the comparefn
> +    if (IsUint8TypedArray(this) && !hasCustomCompare)
> +        return CountingSort(obj, len, false /* signed */);
> +    else if (IsInt8TypedArray(this) && !hasCustomCompare)

Tiny nit, let's use "obj" here instead of this.

::: js/src/vm/SelfHosting.cpp
@@ +788,5 @@
> +    bool isArray = false;
> +
> +    if (args[0].isObject()) {
> +
> +        JSObject* obj = CheckedUnwrap(&args[0].toObject());

I'm not sure we should be trying to unwrap the object here. This has to do with compartments. In short, I don't expect someone to use this method on a "wrapped"/proxy object.

In that case, something like this would do I think:

  static bool
  intrinsic_IsUint8TypedArray(JSContext* cx, unsigned argc, Value* vp)
  {
      CallArgs args = CallArgsFromVp(argc, vp);
      MOZ_ASSERT(args.length() == 1);
      MOZ_ASSERT(args[0].isObject());

      JSObject* obj = &args[0].toObject();

      bool isArray = JS_GetArrayBufferViewType(obj) == Scalar::Uint8;
      args.rval().setBoolean(isArray);

      return true;
  }

@@ +1814,5 @@
>      JS_FN("ArrayBufferByteLength",   intrinsic_ArrayBufferByteLength,   1,0),
>      JS_FN("ArrayBufferCopyData",     intrinsic_ArrayBufferCopyData,     4,0),
>  
> +    JS_FN("IsUint8TypedArray", intrinsic_IsUint8TypedArray,             1,0),
> +    JS_FN("IsInt8TypedArray", intrinsic_IsInt8TypedArray,               1,0),

Silly nit, can we line up the method names so that the 'i's from intrinsic match up.

Comment 11

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8712816 [details] [diff] [review]
1239710.diff

Review of attachment 8712816 [details] [diff] [review]:
-----------------------------------------------------------------

I'm really impressed with how fast you've done this. Here are some things I noticed in my first pass.

::: js/src/builtin/Sorting.js
@@ +28,5 @@
> +
> +    // Traverse the buffer in order and write back elements to array
> +    var val = 0;
> +    for (var i = 0; i < len; i++) {
> +        // Invariant: sum(buffer[val:]) == len-i

We should add an assertion for the invariant here. It will be useful in debug builds (optimized out in production).

::: js/src/builtin/TypedArray.js
@@ +1006,5 @@
>              return v;
>          }
>      }
>  
> +    // CountingSort doesn't invoke the comparefn

Why not move these to just after:
 var hasCustomCompare = comparefn !== undefined;

Then we will only create the wrapped compare function when we need it.

@@ +1009,5 @@
>  
> +    // CountingSort doesn't invoke the comparefn
> +    if (IsUint8TypedArray(this) && !hasCustomCompare)
> +        return CountingSort(obj, len, false /* signed */);
> +    else if (IsInt8TypedArray(this) && !hasCustomCompare)

Tiny nit, let's use "obj" here instead of this.

::: js/src/vm/SelfHosting.cpp
@@ +788,5 @@
> +    bool isArray = false;
> +
> +    if (args[0].isObject()) {
> +
> +        JSObject* obj = CheckedUnwrap(&args[0].toObject());

I'm not sure we should be trying to unwrap the object here. This has to do with compartments. In short, I don't expect someone to use this method on a "wrapped"/proxy object.

In that case, something like this would do I think:

  static bool
  intrinsic_IsUint8TypedArray(JSContext* cx, unsigned argc, Value* vp)
  {
      CallArgs args = CallArgsFromVp(argc, vp);
      MOZ_ASSERT(args.length() == 1);
      MOZ_ASSERT(args[0].isObject());

      JSObject* obj = &args[0].toObject();

      bool isArray = JS_GetArrayBufferViewType(obj) == Scalar::Uint8;
      args.rval().setBoolean(isArray);

      return true;
  }

@@ +1814,5 @@
>      JS_FN("ArrayBufferByteLength",   intrinsic_ArrayBufferByteLength,   1,0),
>      JS_FN("ArrayBufferCopyData",     intrinsic_ArrayBufferCopyData,     4,0),
>  
> +    JS_FN("IsUint8TypedArray", intrinsic_IsUint8TypedArray,             1,0),
> +    JS_FN("IsInt8TypedArray", intrinsic_IsInt8TypedArray,               1,0),

Silly nit, can we line up the method names so that the 'i's from intrinsic match up.

Comment 12

[Morgan Phillips [:mrrrgn]]

I double reviewed the patch ! The difference from comment 11 is that I suggested adding an assertion to CountingSort which verifies the invariant condition.

Comment 13

[Morgan Phillips [:mrrrgn]]

The speed boost here is *very* nice, however, there seems to be a problem with detecting uint8 arrays. Morgans-MacBook-Pro:src mrrrgn$ _DBG.OBJ/dist/bin/js ../../../test-scripts/typedarraysort.js
SORTING i32 WITH 200000 ITEMS 0.301 s
SORTING u32 WITH 200000 ITEMS 0.631 s
SORTING i16 WITH 200000 ITEMS 0.491 s
SORTING u16 WITH 200000 ITEMS 0.415 s
SORTING i8 WITH 200000 ITEMS 0.016 s
SORTING u8 WITH 200000 ITEMS 0.523 s
SORTING f32 WITH 200000 ITEMS 0.404 s
SORTING f64 WITH 200000 ITEMS 0.406 s

Comment 14

[Morgan Phillips [:mrrrgn]]

I used this script for the above btw => https://pastebin.mozilla.org/8855922

My final comment for the review is that I would like to see a test verifying the correctness of the counting sort. 

We can do that relative to QuickSort by using the same array to create both an 

let a = Int8Array.from(someLargeArray) and let b = Int32Array.from(someLargeArray) then assertDeepEq(a.sort(), b.sort())

Comment 15

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8712556 [details] [diff] [review]
wip-v2.diff

Review of attachment 8712556 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/builtin/Sorting.js
@@ +16,5 @@
> +    // ### trying to communicate is that it's the lower limit on the range of
> +    // ### acceptable values. Need to find a better name.
> +    // Map int8 values onto the uint8 range when storing in buffer.
> +    if (signed)  {
> +        min = -128;

I think this name is alright, especially with the comment above.

@@ +19,5 @@
> +    if (signed)  {
> +        min = -128;
> +    }
> +
> +    // ### Is a List default initialized to zero? Can this be made more efficient?

I don't believe so. I had also hoped that it was possible while working on MergeSort. :(

::: js/src/vm/SelfHosting.cpp
@@ +778,5 @@
>      args.rval().setUndefined();
>      return true;
>  }
>  
> +// ### IsUint8TypedArray and IsInt8TypedArray duplicates ten lines of code. Extract a

Yes, that would be very nice I think. The helper should just take in a Type::{Int8, Int32, ...} as a template argument and return whether or not there was a match. See intrinsic_IsInstanceOfBuiltin for an example.

@@ +809,5 @@
> +    // ### Where is the API documented for intrinsic functions? What is an intrinsic function?
> +    //
> +    // ### How do these functions get translated into code that can be excuted by the interpreter?
> +
> +    // ### What is a CallArgs?

AFAIK it's a nice way of interacting with the JS stack. I'm still learning myself however, see https://dxr.mozilla.org/mozilla-central/source/js/public/CallArgs.h?case=true&from=CallArgs#334

@@ +810,5 @@
> +    //
> +    // ### How do these functions get translated into code that can be excuted by the interpreter?
> +
> +    // ### What is a CallArgs?
> +    // ### What is a JSContext?

https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/JSAPI_reference/JSRuntime

@@ +816,5 @@
> +    MOZ_ASSERT(args.length() == 1);
> +
> +    bool isArray = false;
> +
> +    // ### Is a TypedArray always an object? Is an array always an object?

Yes.

@@ +819,5 @@
> +
> +    // ### Is a TypedArray always an object? Is an array always an object?
> +    if (args[0].isObject()) {
> +
> +        // ### What is the purpose of wrappers and proxies? Where can I learn more?

All you want to know and more => https://air.mozilla.org/enter-the-compartment/

@@ +827,5 @@
> +            // ### What happens when this gets called; triggers a callback?
> +            JS_ReportError(cx, "Permission denied to access object");
> +            return false;
> +        }
> +        // ### How detect an Uint8TypedArray? Can I call obj->is<Uint8TypedArray>

There is only a TypedArrayObject the finer grained types are stored in the class. See the source of the JS_GetArrayBufferViewType method.

@@ +1866,5 @@
>  
> +    // ### Using JS_FN instead of JS_INLINABLE_FN. The later required changes
> +    // ### to the jit part of the code; adding an enum and a function.
> +    // ### What is the interaction between intrinsic functions and the jit?
> +    // ### How does inlining work?

See https://air.mozilla.org/kannan-vijayan-baseline-jit/

@@ +1868,5 @@
> +    // ### to the jit part of the code; adding an enum and a function.
> +    // ### What is the interaction between intrinsic functions and the jit?
> +    // ### How does inlining work?
> +    // ### How can one evaluate the performance implications of choosing to
> +    // ### expose a function as inlinable vs non-inlinable?

Benchmarking is your best bet.

@@ +1871,5 @@
> +    // ### How can one evaluate the performance implications of choosing to
> +    // ### expose a function as inlinable vs non-inlinable?
> +    //
> +    // ### mrrgn said that I need not worry about inlining at this stage. Will
> +    // ### I need to add it before the patch lands?

No, the check will only be called one time per sort so the code is highly unlikely to get hot enough for inlining to be important IMO.

Comment 16

[Morgan Phillips [:mrrrgn]]

Returning to intrisic_IsInt8TypedArray, etc... Yes, a templatized helper function would be awesome. See my comments from WIP-2 :)

Comment 17

[Jeff Walden [:Waldo]]

Comment on attachment 8712556 [details] [diff] [review]
wip-v2.diff

Review of attachment 8712556 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/SelfHosting.cpp
@@ +1880,5 @@
> +    // ### permissiveness.
> +    //
> +    // ### I wonder what Waldo meant by 'narrower permissiveness'. Is he talking
> +    // ### about security or about tweaking how aggressive the inliner will be,
> +    // ### e.g. "add more narrow permissiveness to avoid too many inline decisions".

Take a look at IonBuilder::inlineIsTypedArrayHelper.  Using a different predicate in the forAllClasses call, that accepts both Scalar::Uint8 and Scalar::Uint8Clamped, will suffice for detecting the u8 case.  For the int8 case you can eliminate that switch and instead have an exact class check, using types->getKnownClass() and being careful to handle null-return, not-int8class return, and int8class-return, all appropriately.

As for "narrower permissiveness", I meant answering "yes" to slightly fewer classes, i.e. only the int8 or uint8 ones.

Comment 18

[Daniel Näslund [:dannas]]

Attachment: 1239710-v2.diff

Morgan: The new patch (but realized that I'd forgotten some small details), so not the final version (is it ever?).

With this applied, do you see the same strange timing phenomens as I do?

Comment 19

[Daniel Näslund [:dannas]]

(In reply to Morgan Phillips [:mrrrgn] from comment #11)
> ::: js/src/builtin/Sorting.js
> @@ +28,5 @@
> > +
> > +    // Traverse the buffer in order and write back elements to array
> > +    var val = 0;
> > +    for (var i = 0; i < len; i++) {
> > +        // Invariant: sum(buffer[val:]) == len-i
> 
> We should add an assertion for the invariant here. It will be useful in
> debug builds (optimized out in production).

But that would cause the sort to either need to do extra work each time to keep track of a sum (even in optimized builds); or have quadratic runtime if we calculate the sum in an assert statement; is that acceptable even in a debug build? 

You suggested in another comment that I'd add a  testcase that compares the output of CountingSort and QuickSort for a few cases. Can I add that in tests/ecma_6/TypedArray/sort_basics.js? 

I noticed that no function in builtin/Sorting.js is called directly from the tests. Are the tests supposed to just test the API boundary or look under the hood?

Comment 20

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8713759 [details] [diff] [review]
1239710-v2.diff

Review of attachment 8713759 [details] [diff] [review]:
-----------------------------------------------------------------

I'm super excited! I'm willing to r+ this, let's just do a patch with the proper format:

Bug # - commit title; r=mrrrgn

Comment 21

[Morgan Phillips [:mrrrgn]]

Looks like we should also detect Scalar::Uint8Clamped in the IsUint8TypedArray function, otherwise, great!

Comment 22

[Daniel Näslund [:dannas]]

Attachment: 1239710.diff

The final patch!

$ ./tests/jstests.py -d -j 4 build_OPT.OBJ/dist/bin/js
[6465|   0|   0| 493] 100% ==========================================>| 207.5s
PASS

$ ./jit-test/jit_test.py --no-slow build_OPT.OBJ/dist/bin/js
[4988|   0|   0|   0] 100% ==========================================>| 143.8s
PASSED ALL

Comment 23

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8713802 [details] [diff] [review]
1239710.diff

Review of attachment 8713802 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/SelfHosting.cpp
@@ +798,5 @@
> +static bool
> +intrinsic_IsUint8TypedArray(JSContext* cx, unsigned argc, Value* vp)
> +{
> +    return intrinsic_IsSpecificTypedArray(cx, argc, vp, Scalar::Uint8)
> +        || intrinsic_IsSpecificTypedArray(cx, argc, vp, Scalar::Uint8Clamped);

Silly nit on my end, but I *think* we'll want that || on the top line,
I'll check the style guide again. I can do that on my end before I land this though so no worries.

Comment 24

[Morgan Phillips [:mrrrgn]]

Great job on this, I'm excited about implementing Radix sorts next. We're going to be so fast! ^.^

Comment 25

[Daniel Näslund [:dannas]]

Attachment: 1239710.diff

Realized that the patch had my work email-address. This one hasn't. If you've already pushed the patch, no big deal.

Fixed that and changed the || operator to be on the end of the previous line.

Comment 26

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4e613ae24233

Comment 27

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/4e613ae24233