1419372 - Optimize in-operator for typed arrays

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect, P3)

Description

[André Bargull [:anba]]

Follow-up from bug 1290543.

Expected: Similar performance for |inArray| and |inTypedArray|.
Actual: |inTypedArray| is ~40 times slower.

Test case:
---
function inArray() {
    var a = new Array(1000).fill(1);

    var q = 0;
    var t = dateNow();
    for (var i = 0; i < 100000; ++i) {
        for (var j = 0, len = a.length; j < len; ++j) {
            if (j in a) ++q;
        }
    }
    return [dateNow() - t, q];
}

function inTypedArray() {
    var a = new Int32Array(1000).fill(1);

    var q = 0;
    var t = dateNow();
    for (var i = 0; i < 100000; ++i) {
        for (var j = 0, len = a.length; j < len; ++j) {
            if (j in a) ++q;
        }
    }
    return [dateNow() - t, q];
}

print(inArray());
print(inTypedArray());
---

Comment 1

[Matthew Gaudet (he/him) [:mgaudet]]

Attachment: Optimize in Operator for typed arrays

Add inline cache entry for TypedArray exists checks. Requires adding
a new CacheIR opcode LoadTypedElementExistsResult, as well as a macro
assembler implementation for that opcode.

Comment 2

[Matthew Gaudet (he/him) [:mgaudet]]

Attachment: Optimize in Operator for typed arrays

Add inline cache entry for TypedArray exists checks. Requires adding
a new CacheIR opcode LoadTypedElementExistsResult, as well as a macro
assembler implementation for that opcode.

Comment 3

[Tom S [:evilpie]]

Great work so far!
Just for reference: There is actually something quite special about typed arrays. Out of bounds "in" or "hasOwnProperty" should always return false, and not consider the prototype chain at all. See https://tc39.github.io/ecma262/#sec-integer-indexed-exotic-objects-getownproperty-p Step 3.b.v (hasOwnProperty works by calling [[GetOwnProperty]]) and https://tc39.github.io/ecma262/#sec-integer-indexed-exotic-objects-hasproperty-p

Comment 4

[Matthew Gaudet (he/him) [:mgaudet]]

Attachment: Optimize in Operator for typed arrays

Add inline cache entry for TypedArray exists checks. Requires adding
a new CacheIR opcode LoadTypedElementExistsResult, as well as a macro
assembler implementation for that opcode.

Comment 5

[Matthew Gaudet (he/him) [:mgaudet]]

For reference, this takes the ~30x regression i see on my machine, and drops it to ~10x 

# Before
mgaudet39262:src mgaudet$ ~/gecko/js/src/build_dir/dist/bin/js ~/bugs/1419372/BothArray.js 
108.638916015625,100000000   
3451.239013671875,100000000

# After
mgaudet39262:src mgaudet$ build_DBG.OBJ/dist/bin/js ~/bugs/1419372/BothArray.js
112.716064453125,100000000
381.537109375,100000000

Comment 6

[Jan de Mooij [:jandem]]

Comment on attachment 8933428 [details] [diff] [review]
Optimize in Operator for typed arrays

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

Looks great! Just some nits/suggestions below.

::: js/src/jit-test/tests/typedarray/typed-array-inline-cache.js
@@ +1,3 @@
> +// ECMA262 9.4.5.2 [[HasProperty]] 
> +
> +libdir="/Users/mgaudet/mozilla-unified/js/src/jit-test/lib/"

Should remove this line

@@ +1,4 @@
> +// ECMA262 9.4.5.2 [[HasProperty]] 
> +
> +libdir="/Users/mgaudet/mozilla-unified/js/src/jit-test/lib/"
> +load(libdir + "asserts.js");

I think the test will work without this line? assertEq is a shell builtin and I don't think the test uses any of the functions defined in asserts.js

@@ +2,5 @@
> +
> +libdir="/Users/mgaudet/mozilla-unified/js/src/jit-test/lib/"
> +load(libdir + "asserts.js");
> +
> +function check_in(x, a) { 

There's some trailing whitespace here and elsewhere in this file. The review tool shows this - personally I also use Mercurial's color extension, it shows trailing whitespace in the shell. Git probably has something similar.

@@ +3,5 @@
> +libdir="/Users/mgaudet/mozilla-unified/js/src/jit-test/lib/"
> +load(libdir + "asserts.js");
> +
> +function check_in(x, a) { 
> +    return (x in a); 

Maybe add something like check_in but for hasOwnProperty? HasPropIRGenerator is used for both.

::: js/src/jit/CacheIR.cpp
@@ +2568,5 @@
> +HasPropIRGenerator::tryAttachTypedArray(HandleObject obj, ObjOperandId objId,
> +                                        uint32_t index, Int32OperandId indexId)
> +{
> +    // Cobbled together from GetPropIRGenerator::tryAttachTypedElement
> +    // -- Surely these could share checks somehow.

Nit: can remove this comment.

@@ +2573,5 @@
> +
> +    if (!obj->is<TypedArrayObject>() && !IsPrimitiveArrayTypedObject(obj))
> +        return false;
> +
> +    if (!cx_->runtime()->jitSupportsFloatingPoint && TypedThingRequiresFloatingPoint(obj))

Nit: we can remove this check. We don't actually load (floating point) values from the array so this stub will work fine on platforms without floating point support.

@@ +2577,5 @@
> +    if (!cx_->runtime()->jitSupportsFloatingPoint && TypedThingRequiresFloatingPoint(obj))
> +        return false;
> +
> +    // Ensure the index is in-bounds
> +    if (obj->is<TypedArrayObject>() && index >= obj->as<TypedArrayObject>().length())

Nit: we can remove this check if the stub handles out-of-bounds cases (see other comment).

::: js/src/jit/CacheIRCompiler.cpp
@@ +1969,5 @@
> +        return false;
> +
> +    // Bound check.
> +    LoadTypedThingLength(masm, layout, obj, scratch);
> +    masm.branch32(Assembler::BelowOrEqual, scratch, index, failure->label());

So if we don't have to check the prototype chain, we could easily handle this case by returning false. That way we also don't need the FailurePath. Something like:

Label outOfBounds, done;
masm.branch32(Assembler::BelowOrEqual, scratch, index, &outOfBounds);
EmitStoreBoolean(masm, true, output);
masm.jump(&done);

masm.bind(&outOfBounds);
EmitStoreBoolean(masm, false, output);

masm.bind(&done);

Comment 7

[Matthew Gaudet (he/him) [:mgaudet]]

Attachment: Optimize in Operator for typed arrays

Add inline cache entry for TypedArray exists checks. Requires adding
a new CacheIR opcode LoadTypedElementExistsResult, as well as a macro
assembler implementation for that opcode.

Comment 8

[Matthew Gaudet (he/him) [:mgaudet]]

Comment on attachment 8933694 [details] [diff] [review]
Optimize in Operator for typed arrays

Addressed feedback, increased test coverage. 

Try build is currently chugging along here: https://treeherder.mozilla.org/#/jobs?repo=try&revision=649c870545c6e1a30f1d1f215a0b234f49faeb7f

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 8933694 [details] [diff] [review]
Optimize in Operator for typed arrays

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

Looks great, thanks! One follow-up suggestion below.

::: js/src/jit/CacheIR.cpp
@@ +2576,5 @@
> +    if (IsPrimitiveArrayTypedObject(obj) && cx_->compartment()->detachedTypedObjects)
> +        return false;
> +
> +    TypedThingLayout layout = GetTypedThingLayout(obj->getClass());
> +    writer.guardShape(objId, obj->as<ShapedObject>().shape());

This is fine, but for typed arrays we could consider adding a GuardIsTypedArray CacheIR instruction (that does something like [0]) and emitting it instead of GuardShape.

The idea is this: typed array objects with different element types (say Int32Array and Int8Array) have a different js::Class* and therefore get a different Shape, but this IC stub works exactly the same for each TypedArrayObject. So GuardIsTypedArray would be a more generic guard that would accept all typed arrays.

Follow-up bug blocking the CacheIR meta bug is fine :)

[0] https://searchfox.org/mozilla-central/rev/477ac066b565ae0eb3519875581a62dfb1430e98/js/src/jit/CodeGenerator.cpp#12029-12034

Comment 10

[Matthew Gaudet (he/him) [:mgaudet]]

Thanks! I opened the follow up Bug 1422851. Setting the flag, as the build looks good to me (though, there were two aborted jobs)

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/87fdf9ff3843
Optimize in Operator for typed arrays. r=jandem

Comment 12

[Bogdan Tara[:bogdan_tara | bogdant]]

https://hg.mozilla.org/mozilla-central/rev/87fdf9ff3843

Comment 13

[Simon Lindholm]

> +function test_with_protochain(a) {
> +    var a = new Int32Array(1000).fill(1);
> +    // try to force the behaviour of 9.4.5.2
> +    a[1012] = "1012";
> +    a["-0"]   = "-0";
> +    a[-10]  = "-10";

Should this perhaps modify a.__proto__? Seems like the sets will be ignored otherwise, by 9.4.5.9.

Comment 14

[Matthew Gaudet (he/him) [:mgaudet]]

That's a great catch. I really appreciate it. 

What's your thought on tweaking the test case like this: 

    diff --git a/js/src/jit-test/tests/typedarray/typed-array-inline-cache.js b/js/src/jit-test/tests/typedarray/typed-array-inline-cache.js
    index cfb6892a9c13..67a1bca020b4 100644
    --- a/js/src/jit-test/tests/typedarray/typed-array-inline-cache.js
    +++ b/js/src/jit-test/tests/typedarray/typed-array-inline-cache.js
    @@ -42,9 +42,10 @@ function test_with_no_protochain(a) {
     function test_with_protochain(a) {
         var a = new Int32Array(1000).fill(1);
         // try to force the behaviour of 9.4.5.2
    -    a[1012] = "1012";
    -    a["-0"]   = "-0";
    -    a[-10]  = "-10";
    +    Object.prototype["-0"] = "value";
    +    Object.prototype[-1]   = "value";
    +    Object.prototype[-10]  = "value";
    +    Object.prototype[1012] = "value";
         warmup(a);
         check_assertions(a);
     }

Comment 15

[Simon Lindholm]

Sounds like a good fix to me!

Comment 16

[Matthew Gaudet (he/him) [:mgaudet]]

Opened Bug 1423586 to land test enhancement. Thanks so much for the catch and minireview!