1491813 - TypedArray.from is 15x too slow

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P3)

Description

[Maarten Breddels]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/69.0.3497.81 Safari/537.36

Steps to reproduce:

I created this benchmark:
https://jsperf.com/comparing-typed-array-casting



Actual results:

Float32Array.from seems 15x slower than a manual loop.


Expected results:

it should have been at least as fast, if not faster.

Comment 1

[Maarten Breddels]

Chrome seems worse (100x slower), reported here:
https://bugs.chromium.org/p/chromium/issues/detail?id=884671
Safari seems only a factor of 2 slower (acceptable)

Comment 2

[Sylvestre Ledru [:Sylvestre]]

In case jsperf goes down, examples are:
With:

var N = 1000 * 1000;
var ar = new Float64Array(N);
  

---
Float32Array.from(ar);
---
vs
---
const N = ar.length;
var ar32 = new Float32Array(N);
for(var i = 0; i < N; i++) {
  ar32[i] = ar[i];
}
---

Comment 3

[Kannan Vijayan [:djvj]]

The cause of this issue is most likely due to the fact that `<TypedArrayType>.from()` is implemented in C++, and the accesses of the properties of the source array are being done blindly from C++ code, instead of optimized JS code.

The relevant code (generic, across different typed array types), is here: https://searchfox.org/mozilla-central/source/js/src/vm/TypedArrayObject.cpp#1090

In the second case, the JS jits quickly recognize that `ar` is a normal array object and will optimize the elements accesses.  The C++ implementation in that function only special cases constructing typed arrays from other Typed Arrays (potentially wrapped).

The simple fix for this is to add another optimization path in the linked function that fast-paths the "initialize from plain array" case.

This is a good contributor bug - bite-sized, well-defined, and (relatively) straightforward.

Comment 4

[William Strode]

Hi,

I'm currently looking for a first bug to start contributing and would like to work on this bug if that's possible.

Thanks!

Comment 5

[Kannan Vijayan [:djvj]]

William: that's awesome!  Of course you are welcome to take a stab.

To give a synopsis on what needs to be done: we need to add another conditional to the linked function, of the form:

```
if (other->is<ArrayObject>()) { ... }
```

Within the conditional, we want to convert the JSObject into an ArrayObject, then check if the array is a _dense_, _packed_ array (array->initializedLength == array->length && array->length < array->denseCapacity), and if that's the case, we can quickly pull the `length` off of the array, and then iterate from 0 to length-1, pulling values directly out of the ObjectElements structure that hangs off of every JSObject.

If you want more context, I'll be happy to provide.  Feel free to ping me (:djvj on #jsapi on IRC) or generally ask questions in #jsapi if you run into issues.  Commenting on the bug also works.

Thanks for taking a stab at it!

Comment 6

[William Strode]

Great, thanks!

I have some stuff to do today so I'll start working on the bug over the weekend - I'll hop on the irc if I run into any questions.

Comment 7

[André Bargull [:anba]]

(In reply to Kannan Vijayan [:djvj] from comment #3)
> The cause of this issue is most likely due to the fact that
> `<TypedArrayType>.from()` is implemented in C++, and the accesses of the
> properties of the source array are being done blindly from C++ code, instead
> of optimized JS code.

The method is implemented in JS code -> https://searchfox.org/mozilla-central/rev/3564dfde3b125878dc5a04fe92629fc5195942df/js/src/builtin/TypedArray.js#1443

> In the second case, the JS jits quickly recognize that `ar` is a normal
> array object and will optimize the elements accesses.  The C++
> implementation in that function only special cases constructing typed arrays
> from other Typed Arrays (potentially wrapped).

`ar` is a TypedArray object in the test case.

> 
> The simple fix for this is to add another optimization path in the linked
> function that fast-paths the "initialize from plain array" case.

TypedArrayObjectTemplate<T>::fromArray(...) calls TypedArrayObjectTemplate<T>::fromObject(...), which in turn already optimises plain array initialisation: <https://searchfox.org/mozilla-central/rev/3564dfde3b125878dc5a04fe92629fc5195942df/js/src/vm/TypedArrayObject.cpp#1226-1257>. But as written above, this code isn't actually invoked for the test case. 



(In reply to Kannan Vijayan [:djvj] from comment #5)
> William: that's awesome!  Of course you are welcome to take a stab.
> 
> To give a synopsis on what needs to be done: we need to add another
> conditional to the linked function, of the form:
> 
> ```
> if (other->is<ArrayObject>()) { ... }
> ```
> 

So what actually needs to be done here, is to modify TypedArrayStaticFrom to include something like this after <https://searchfox.org/mozilla-central/rev/3564dfde3b125878dc5a04fe92629fc5195942df/js/src/builtin/TypedArray.js#1476-1477>:
---
if (!mapping && IsTypedArray(source) && IsTypedArrayConstructor(C) &&
    usingIterator === TypedArrayValues && IsArrayIteratorNextSane())
{
    // TODO: Fast path for step 7 of %TypedArray%.from.
    // Spec: https://tc39.github.io/ecma262/#sec-%typedarray%.from
    ...
}
---

where "IsTypedArrayConstructor" is a new function to test if the variable `C` is a built-in TypedArray constructor and "IsArrayIteratorNextSane" is a new function to test if the %ArrayIterator%.next method is still the built-in %ArrayIteratorPrototype%.next <https://tc39.github.io/ecma262/#sec-%arrayiteratorprototype%.next> function.

Comment 8

[William Strode]

Right, gonna start taking a look at this today - just getting my VM up to date.

So to clarify - I need to write new functions for "IsTypedArrayConstructor" and "IsArrayIteratorNextSane" which will help to identify if C is a TypedArrayConstructor (I might be unclear on this?) and that the correct method is being used for %ArrayIterator%.next, and then implement step 7 of %TypeArray%.from to be used when those conditions are met? 

Thanks in advance for your help and patience!

Comment 9

[shivambalikondwar]

William if you are busy , i can work ? are you ?
I'll look for 5 days , if you aren't working i'll start solving it 
is it fine , cause i don't want to take this work from you 
:) have a good day .

Comment 10

[William Strode]

I'm working on it this evening :)

Got what should be a working function for IsTypedArrayConstructor written - bit rusty on js so it took longer than it should have but I'm getting used to it again. Now looking into IsArrayIteratorNextSane.

Comment 11

[William Strode]

One question I did have - where is the jsapi channel on the irc? I took a look earlier but I wasn't able to find it... Probably missing something obvious but I thought it wise to ask :)

Comment 12

[William Strode]

Attachment: typedArrayFrom inclusion of isTypedArrayConstructor + isArrayIteratorNextSane

(hopefully I've submitted this correctly) This is what I've done so far - pretty rusty with js so it took a while to get up and running. I'm pretty unsure about the iteratorNextSane function - still not all that familiar with how js works in that area.

Sorry for the message spam this evening, I appreciate the help and guidance.

Thanks!

Comment 13

[Kannan Vijayan [:djvj]]

Thanks for catching my error Andre!

Comment 14

[William Strode]

Right, gonna try to get the rest of this done today. If I could get a response on the IRC thing so I can drop in if I need to ask about testing and submitting stuff that would be great!

I'll try and have a new patch ready in an hour or two.

Comment 15

[William Strode]

Attachment: typedArray.from_patch.diff

Right, this is (near as I can tell) a working implementation of the guidelines given by Andre in the earlier comment - I'm not 100% on the fast-path implementation but I built firefox and used the console to run the test-cases given by Sylvestre when the bug was reported and it was noticeably faster than a build without the changes.

If you could let me know if anything further needs to be done that would be fantastic.

Thank you for all your help!

Comment 16

[William Strode]

Realised I should probably be submitting these patches through phabricator but I've been having some trouble getting moz-phab working (not sure what I'm meant to add to the path exactly to get it to work) so a point in the right direction on that would be greatly appreciated too!

Comment 17

[Kannan Vijayan [:djvj]]

William: It's ok, if you want to use me as a reviewer I don't mind reviewing the patches as-is :)

The integration kinks with Phabricator are still being worked out.  Trust me I've chafed against it too.

Comment 18

[William Strode]

If you could do a review that would be fantastic! I was just conscious of making things inconvenient for you :)

Thanks!

Comment 19

[Kannan Vijayan [:djvj]]

Oh don't worry about that - if in some circumstance I (or anyone else) can't review the patch in a timely way then it's our onus to let you know and try to find a capable reviewer.

Additionally, if you submit a review request and you notice it's being ignored, please don't feel hesitant in reminding someone (things do slip our minds), or asking around in #jsapi for another reviewer.

This is an OSS project and your contributions are just as valid as mine or anyone elses.  The major difference is that Moz gets to tell me what to work on, and as a contributor you can work on what you want :)

So getting back to the review - if you want to request a review of me please do the following:

1. Click on the `details` link next to the patch attachment.
2. On the "review" pulldown box, select "?".  This will expose a textbox right under that.
3. In the textbox, type ":djvj" - it should suggest me as a reviewer in a pop-down.  Select that.
4. Click "submit" at the bottom.

Cheers!

Comment 20

[Kannan Vijayan [:djvj]]

Hmm, this is landing in the middle of self-hosted code, which I am less familiar with.  I'll take a quick overview of this to spot obvious issues, but there is enough slight finnickyness in the self-hosted environment that I'd want somebody with experience in the area to sign off.

Will likely forward review to :jorendorff after I take a look.

Comment 21

[William Strode]

Just wondering how the review is going? Let me know if / when it's been done if there's stuff for me to work on (I'm assuming I didn't get everything quite right first time)

Comment 22

[Kannan Vijayan [:djvj]]

Sorry, I have not taken a serious look at it yet.  Generally the post-all-hands, pre-holiday period is kind of hectic and somewhat unproductive.  I'll try to look at it soon, hopefully tonight.

Comment 23

[Kannan Vijayan [:djvj]]

Comment on attachment 9029828 [details] [diff] [review]
typedArray.from_patch.diff

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

Looks good overall, but a few places to change.  I'm adding jorendorff as a reviewer to see what he thinks.

::: js/src/builtin/TypedArray.js
@@ +1481,5 @@
> +            usingIterator === TypedArrayValues && IsArrayIteratorNextSane())
> +        {
> +            //Step 7 (Fast-path? unsure on implementation here)
> +            //Step 7.a.
> +            var values = IterableToList(source, usingIterator);

I'm pretty sure we can skip using the iterable in this case, and avoid the extra intermediate array.

Since we know that `source` is a TypedArray, we can guarantee that it is not a proxy.  Only proxies are able to override `[]` element accesses, so we can be assured that `[]` will operate naturally on `source`.

This means we can skip this part and simply do `source[i]` to retrieve the elements in the for loop below.

@@ +1484,5 @@
> +            //Step 7.a.
> +            var values = IterableToList(source, usingIterator);
> +
> +            //Step 7.b.
> +            var len = values.length;

This can be `TypedArrayLength(source)` assuming the comment above.

@@ +1495,5 @@
> +                //Step 7.e.ii.
> +                var kValue = values[k];
> +
> +                //Step 7.e.iii. can be skipped as no mapping function
> +                

Nit: whitespace on blank line.

@@ +1496,5 @@
> +                var kValue = values[k];
> +
> +                //Step 7.e.iii. can be skipped as no mapping function
> +                
> +                //Step 7.e.iv. skipped as presumably a waste of time to declare mappedValue = kValue 

Nit: whitespace at end of line.

@@ +1827,5 @@
>  }
> +
> +//New function to test if a single argument (C) is a TypedArrayConstructor
> +//could be more efficient potentially? not sure if this implementation is 'good'
> +function isTypedArrayConstructor(C) {

Nit: Capitalize IsTypedArrayConstructor.

@@ +1830,5 @@
> +//could be more efficient potentially? not sure if this implementation is 'good'
> +function isTypedArrayConstructor(C) {
> +    var types = {Int8Array,Int16Array,Int32Array,
> +        Uint8Array,Uint8ClampedArray,Uint16Array,
> +        Uint32Array,Float32Array,Float64Array};

Constructing an object and then iterating through it is going to cost quite a bit of time.
This method should simply be a large if/else if/ chain.

Alternatively, lifting it out into a global that is external to the function might be a valid approach.

I'd want to get Jorendorff's comment on this.

@@ +1841,5 @@
> +    return false;
> +}
> +
> +//New function to test if %ArrayIterator%.next method is still the built-in
> +//%ArrayIteratorPrototype%.next function. 

Nit: Whitespace at end of line.

@@ +1842,5 @@
> +}
> +
> +//New function to test if %ArrayIterator%.next method is still the built-in
> +//%ArrayIteratorPrototype%.next function. 
> +function isArrayIteratorNextSane() {

Nit: Capitalise IsArrayIteratorNextSane

@@ +1845,5 @@
> +//%ArrayIteratorPrototype%.next function. 
> +function isArrayIteratorNextSane() {
> +    var arrIt = %ArrayIterator%.next;
> +    var targetArrIt = %ArrayIteratorPrototype%.next
> +    if (arrIt === targetArrIt) {

I'd avoid the var declarations prior to this and simply put both expressions directly within the conditional.  Saves a few dispatches in interpreter before this function becomes hot.  Also would speed up baseline-jitcode for this function a bit.

Comment 24

[Kannan Vijayan [:djvj]]

Comment on attachment 9029828 [details] [diff] [review]
typedArray.from_patch.diff

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

Got some feedback from jorendorff on this.  The `%ArrayIterator%.next` syntax is apparently not valid.  I thought it might have been some special syntax that's parseable in self-hosted code, but it's not.  It shows up in comments and such, but only as a shorthand.

I'm cancelling the review for now so that you can address the review comments as well as fix up the above issue.  Also, generally the workflow on submitting patches is to test the patch with a small microbench, both to ensure that it works correctly and to ensure that the desired performance gain is showing up.

jorendorff is a bit busy on this front, so please send the review to me again once you have the next iteration of the patch.

Comment 25

[Jason Orendorff [:jorendorff]]

Comment on attachment 9029828 [details] [diff] [review]
typedArray.from_patch.diff

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

Clearing the review flag for now.

::: js/src/builtin/TypedArray.js
@@ +1477,5 @@
>              ThrowTypeError(JSMSG_NOT_ITERABLE, DecompileArg(0, source));
>  
> +        //catching cases where fast path for step 7 can be used
> +        if (!mapping && IsTypedArray(source) && IsTypedArrayConstructor(C) &&
> +            usingIterator === TypedArrayValues && IsArrayIteratorNextSane())

Cool patch! This general approach can work, but it's very tough to guard against all the bizarre possibilities. Bear with me, I'm afraid this is super nit-picky:

*   You might figure, once we've checked that `source` is really a TypedArray, `source.length` shouldn't be able to lie to us. That would be nice. But alas, scripts can do `Object.defineProperty(source, "length", {value: 100})` and define `source.length` to be whatever they want. It can even be an accessor property with a getter. It could do anything and return anything.

    I think we want to optimize the case where `source.length` has *not* been tampered with, which means checking for it in this if-statement.

*   In a similar vein, `source`'s prototype might have been changed, by doing something like `Object.setPrototypeOf(source, {})`.

*   Or `source`'s immediate prototype may have been tampered with, by changing its prototype or adding a .length property to it.

*   Or %TypedArrayPrototype%.length may have been changed or deleted.

*   The `next` method on the iterator object's prototype (what the spec calls %ArrayIteratorPrototype%.next) might have been changed or deleted.

All of this silliness is the standard's fault; we just have to live with it...

I think in the past, the way we've dealt with this is to build things like this: <https://searchfox.org/mozilla-central/rev/49e78df13e7a505827a3a86daae9efdf827133c6/js/src/builtin/RegExp.cpp#1591>

How's your C++? :-)

@@ +1481,5 @@
> +            usingIterator === TypedArrayValues && IsArrayIteratorNextSane())
> +        {
> +            //Step 7 (Fast-path? unsure on implementation here)
> +            //Step 7.a.
> +            var values = IterableToList(source, usingIterator);

Well, I want to agree with Kannan. What I would *like* the fast path to say is:

        // Step 7.a-e, optimizing away the iterator and the temporary List.
        var len = source.length;
        var targetObj = TypedArrayCreateWithLength(C, len);
        for (var k = 0; k < len; k++) {
            targetObj[k] = source[k];
        }

        // Step 7.f asserts that the temporary List is now empty;
        // nothing to do, since we optimized it away.

        // Step 7.g.
        return targetObj;

Of course, writing those few lines is easy; figuring out how to make sure it's safe and standard-compliant is the hard part.

@@ +1844,5 @@
> +//New function to test if %ArrayIterator%.next method is still the built-in
> +//%ArrayIteratorPrototype%.next function. 
> +function isArrayIteratorNextSane() {
> +    var arrIt = %ArrayIterator%.next;
> +    var targetArrIt = %ArrayIteratorPrototype%.next

The `%ArrayIterator%` syntax isn't something we can actually parse, though we do use it in comments (it's a convention we took from the spec).

Alas, actually getting %ArrayIteratorPrototype%.next is no good anyway, since that could trigger a getter (or other possibilities, if the method has been deleted); see previous comment.

If you need any help building and running the JS engine with your changes, just ask -- either here or on Mozilla's IRC server. djvj and I are usually there in the #jsapi channel. It'll be way easier to get through this once you can run tests locally!

Comment 26

[William Strode]

Hey, sorry I've not responded until just now, I've had a lot of deadlines and stuff going on. 

I appreciate all your feedback and I'd like to fix up the patch once I get the chance, but I might take some time with travel and holiday plans and such. Thanks for getting the review to me though and letting me know what needs to be fixed up.

If I take too long getting back to this I'm happy for it to be passed on to someone else to clear up, but I'll try and see if I can get some time to work on it. 

If I need to get in touch on the IRC, is there a password for #jsapi? I seem to vaguely remember trying to use it when I was working on the first patch and not being able to connect but that might have been my irc ineptitude...

Comment 27

[Kannan Vijayan [:djvj]]

No worries - things are slow in general during the holidays.  I think you just need to be registered with NickServ (are you familiar with registered IRC nicks?) to join #jsapi, but I could be wrong.

Comment 28

[Garvit Khatri [:garvitdelhi]]

Hey, I see no update on for past 2 months, I would like to take this up, I have applied the patch and also accommodated review comments in the patch. To test, I should just build using ./mach build and run the tests in the first comment in the console?

Comment 29

[André Bargull [:anba]]

I've just posted a patch to bug 1522157 to add the necessary helpers (IsTypedArrayConstructor and ArrayIteratorPrototypeOptimizable) needed to finish up this bug.

Comment 30

[Garvit Khatri [:garvitdelhi]]

Okay, sure no problem @Anre.

Comment 31

[Garvit Khatri [:garvitdelhi]]

(In reply to Garvit Khatri [:garvitdelhi] from comment #30)

Okay, sure no problem @Anre.
*@Andre

Comment 32

[André Bargull [:anba]]

Just to prevent any misunderstandings: I didn't want to discourage anyone to work on this bug. I only wanted to say that bug 1522157 adds some helpers which are also necessary here. So this bug is now even a better "good-first-bug". :-D

Comment 33

[Chris]

Is anyone actively working on this? Or is it up for grabs? I see that it is currently unassigned.

Comment 34

[Kannan Vijayan [:djvj]]

Chris: as far as I know no-one is. It should be fine if you want to take it on.

Comment 35

[André Bargull [:anba]]

Attachment: Bug 1491813: Add fast path when TypedArray.from is called with a TypedArray. r=jandem!

Comment 36

[Vaishnavi Kaulagi]

Can I work on this?

Comment 37

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=6d1b93f0792688a2ee8f68c13951ae53b4cff2a2

Comment 38

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/37fe2e02b32b
Add fast path when TypedArray.from is called with a TypedArray. r=jandem

Comment 39

[Cosmin Sabou [:CosminS]]

https://hg.mozilla.org/mozilla-central/rev/37fe2e02b32b