Optimize in-operator for typed arrays

RESOLVED FIXED in Firefox 59

Status

()

P3
normal
RESOLVED FIXED
a year ago
a year ago

People

(Reporter: anba, Assigned: mgaudet)

Tracking

(Blocks: 1 bug)

Trunk
mozilla59
Points:
---

Firefox Tracking Flags

(firefox59 fixed)

Details

Attachments

(1 attachment, 3 obsolete attachments)

(Reporter)

Description

a year ago
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());
---
Priority: -- → P3
(Assignee)

Updated

a year ago
Assignee: nobody → mgaudet
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.
(Assignee)

Updated

a year ago
Attachment #8933355 - Attachment is obsolete: true
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.
(Assignee)

Updated

a year ago
Attachment #8933359 - Attachment description: Optimize in Operator for typed arrays jandem → Optimize in Operator for typed arrays
Attachment #8933359 - Attachment is obsolete: true
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
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.
(Assignee)

Updated

a year ago
Attachment #8933428 - Flags: review?(jdemooij)
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 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);
Attachment #8933428 - Flags: review?(jdemooij) → feedback+
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.
(Assignee)

Updated

a year ago
Attachment #8933428 - Attachment is obsolete: true
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
Attachment #8933694 - Flags: review?(jdemooij)
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
Attachment #8933694 - Flags: review?(jdemooij) → review+
Thanks! I opened the follow up Bug 1422851. Setting the flag, as the build looks good to me (though, there were two aborted jobs)
Keywords: checkin-needed

Comment 11

a year ago
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/87fdf9ff3843
Optimize in Operator for typed arrays. r=jandem
Keywords: checkin-needed

Comment 12

a year ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/87fdf9ff3843
Status: NEW → RESOLVED
Last Resolved: a year ago
status-firefox59: affected → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla59

Comment 13

a year ago
> +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.
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

a year ago
Sounds like a good fix to me!
Opened Bug 1423586 to land test enhancement. Thanks so much for the catch and minireview!
You need to log in before you can comment on or make changes to this bug.