Optimize Object.hasOwnProperty

RESOLVED FIXED in Firefox 55

Status

()

Core
JavaScript Engine
P2
normal
RESOLVED FIXED
2 months ago
3 hours ago

People

(Reporter: jandem, Assigned: evilpie)

Tracking

(Blocks: 4 bugs)

unspecified
mozilla55
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox55 fixed)

Details

(Whiteboard: [qf:p1])

Attachments

(9 attachments, 5 obsolete attachments)

24.01 KB, patch
jandem
: review+
Details | Diff | Splinter Review
5.84 KB, patch
jandem
: review+
Details | Diff | Splinter Review
11.99 KB, patch
jandem
: review+
Details | Diff | Splinter Review
10.63 KB, patch
jandem
: review+
Details | Diff | Splinter Review
5.86 KB, patch
jandem
: review+
Details | Diff | Splinter Review
399 bytes, text/plain
Details
20.03 KB, patch
jandem
: review+
Details | Diff | Splinter Review
1.48 KB, patch
jandem
: review+
Details | Diff | Splinter Review
11.96 KB, patch
jandem
: review+
Details | Diff | Splinter Review
(Reporter)

Description

2 months ago
A few weeks ago I noticed Speedometer spends a bunch of time under hasOwnProperty. I also noticed JSC has a HasOwnPropertyCache.

It seems we could do much better than that if we do the following (inspired by bug 1344463):

(1) Self-host hasOwnProperty.

(2) Make it call an intrinsic that the bytecode emitter turns into an op like JSOP_IN (maybe JSOP_IN_OWN or JSOP_HAS_OWN_PROPERTY).

(3) The JITs could share most of their JSOP_IN optimizations with this new op.

That should make hasOwnProperty basically as fast as JSOP_IN or a JSOP_GETPROP.
(Reporter)

Updated

2 months ago
Blocks: 1307062
Priority: -- → P2
Whiteboard: [qf:p1]

Updated

27 days ago
Assignee: nobody → kvijayan
(Assignee)

Comment 1

20 days ago
I have some WIP patches for this.
Assignee: kvijayan → evilpies
Blocks: 1259927
(Assignee)

Comment 2

20 days ago
Created attachment 8854581 [details] [diff] [review]
Add JSOP_HASOWN

Add the JSOP_HASOWN opcode that is going to be called from the self-hosted Object_hasOwnProperty function. I thought about doing the ToObject and ToPropertyKey in the self-hosted function, but that is going to involve two extra calls when not inlining (baseline/interp)
(Assignee)

Comment 3

20 days ago
Created attachment 8854582 [details] [diff] [review]
Baseline fallback support for HasOwn
(Assignee)

Comment 4

20 days ago
Created attachment 8854583 [details] [diff] [review]
CacheIR for HasOwn with baseline support
(Assignee)

Comment 5

20 days ago
I am probably just going to wait for bug 1337773 before implementing Ion support independently.
(Assignee)

Comment 6

20 days ago
Judging from emberjs/react we will also need megamorphic support for this op.
(Assignee)

Comment 7

20 days ago
Created attachment 8854620 [details] [diff] [review]
Megamorphic stub
(Assignee)

Comment 8

16 days ago
Created attachment 8856175 [details] [diff] [review]
CacheIR HasOwn in Ion

This is definitely the part with the most open questions for me. Should be always box the both inputs? I tried using the same policy as GetPropertyCache, but that caused issues in other places.
(Assignee)

Comment 9

16 days ago
Created attachment 8856176 [details] [diff] [review]
Part 1 - Add JSOP_HASOWN

I replaced std_Object_hasOwnProperty everywhere with hasOwn, I am not sure if this actually useful. The parameter order is a bit weird, but matches 'in'. As well as order in Object#hasOwnProperty, where ToPropertyKey is called before ToObject.
Attachment #8854581 - Attachment is obsolete: true
(Assignee)

Comment 10

15 days ago
Created attachment 8856256 [details] [diff] [review]
Part 2 - Baseline fallback support for HasOwn
Attachment #8854582 - Attachment is obsolete: true
(Assignee)

Updated

15 days ago
Attachment #8856176 - Attachment description: Add JSOP_HASOWN → Part 1 - Add JSOP_HASOWN
(Assignee)

Updated

15 days ago
Attachment #8856256 - Attachment description: Baseline fallback support for HasOwn → Part 2 - Baseline fallback support for HasOwn
(Assignee)

Comment 11

15 days ago
Created attachment 8856257 [details] [diff] [review]
Part 3 - CacheIR for HasOwn with baseline support
Attachment #8854583 - Attachment is obsolete: true
(Assignee)

Comment 12

15 days ago
Created attachment 8856258 [details] [diff] [review]
Part 4 - Megamorphic stub
Attachment #8854620 - Attachment is obsolete: true
(Assignee)

Comment 13

15 days ago
I think everything, but the Ion patch can be reviewed. I also have to additional patches for porting the NotDefined analysis from Ion as well as definite property support, which is untested.
(Assignee)

Updated

15 days ago
Attachment #8856176 - Flags: review?(jdemooij)
(Assignee)

Updated

15 days ago
Attachment #8856256 - Flags: review?(jdemooij)
(Assignee)

Updated

15 days ago
Attachment #8856257 - Flags: review?(jdemooij)
(Assignee)

Updated

15 days ago
Attachment #8856258 - Flags: review?(jdemooij)
(Assignee)

Comment 14

15 days ago
Comment on attachment 8856175 [details] [diff] [review]
CacheIR HasOwn in Ion

There are various things marked with XX where I wasn't sure what to do.
Attachment #8856175 - Flags: feedback?(jdemooij)
(Reporter)

Comment 15

13 days ago
Comment on attachment 8856176 [details] [diff] [review]
Part 1 - Add JSOP_HASOWN

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

Sorry for the delay. Looks great, thanks for taking this on!

Using hasOwn directly makes sense to me as it eliminates the s-h function call.
Attachment #8856176 - Flags: review?(jdemooij) → review+
(Reporter)

Comment 16

13 days ago
Comment on attachment 8856256 [details] [diff] [review]
Part 2 - Baseline fallback support for HasOwn

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

::: js/src/jit/BaselineIC.cpp
@@ +1285,5 @@
> +    MOZ_ASSERT(engine_ == Engine::Baseline);
> +
> +    EmitRestoreTailCallReg(masm);
> +
> +    // Sync for the decompiler.

This reminds me, please double check you get the same error messages as before for things like ({}).hasOwnProperty.call(null)

::: js/src/jit/BaselineIC.h
@@ +503,1 @@
>  

Nit: could remove 2 of the 3 blank lines here.
Attachment #8856256 - Flags: review?(jdemooij) → review+
(Reporter)

Comment 17

12 days ago
Comment on attachment 8856257 [details] [diff] [review]
Part 3 - CacheIR for HasOwn with baseline support

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

Looks good. I was wondering if we could use InIRGenerator for this, but separating them may be less confusing.
Attachment #8856257 - Flags: review?(jdemooij) → review+
(Reporter)

Comment 18

12 days ago
Comment on attachment 8856258 [details] [diff] [review]
Part 4 - Megamorphic stub

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

Please add a test for this if our test suite doesn't hit this code (that reminds me I should fix bug 1348790..)

::: js/src/jit/CacheIR.h
@@ +184,5 @@
>                                            \
>      _(MegamorphicLoadSlotResult)          \
>      _(MegamorphicLoadSlotByValueResult)   \
>      _(MegamorphicStoreSlot)               \
> +    _(MegamorphicHasOwnResult)            \

Maybe we could later use this for In too if we rename to MegamorphicHasProperty and add an IsOwn template parameter to the VM function, or something? We can worry about that later though.

::: js/src/jit/VMFunctions.cpp
@@ +1757,5 @@
> +
> +    // Property not found. Watch out for Class hooks.
> +    if (MOZ_UNLIKELY(!nobj->is<PlainObject>())) {
> +        if (ClassMayResolveId(cx->names(), nobj->getClass(), id, nobj) ||
> +            nobj->getClass()->getGetProperty()) // XXX other hooks I think lookup/has

The fast path in obj_hasOwnProperty calls NativeLookupOwnProperty -> LookupOwnPropertyInline, and there we only check for resolve hooks as far as I can tell? So I think ClassMayResolveId will be sufficient here...
Attachment #8856258 - Flags: review?(jdemooij) → review+
(Reporter)

Comment 19

12 days ago
Comment on attachment 8856175 [details] [diff] [review]
CacheIR HasOwn in Ion

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

::: js/src/jit/IonIC.cpp
@@ +48,5 @@
>          return asGetNameIC()->temp();
>        case CacheKind::In:
>          MOZ_CRASH("Baseline-specific for now");
> +      case CacheKind::HasOwn:
> +        return asHasOwnIC()->maybeTemp(); // XXX can we use output() ?

Using the output register should work.

Adding a temp may be reasonable (I think the primitive CacheIR regalloc benefits more from the extra register than Ion's regalloc) but in this case we can use the output register as temp so it probably doesn't help much.

::: js/src/jit/MIR.h
@@ +12547,5 @@
>  };
>  
> +class MHasOwnCache
> +  : public MBinaryInstruction,
> +    public MixPolicy<BoxPolicy<0>, BoxPolicy<1>>::Data

We should match the GetProp cache for this to avoid unnecessary guards and (un)boxing. If the lowering code is the same I don't know why it would fail.

@@ +12557,5 @@
> +
> +        // The cache will invalidate if there are objects with e.g. lookup or
> +        // resolve hooks on the proto chain. setGuard ensures this check is not
> +        // eliminated.
> +        // setGuard();

We can remove this because the MIR instruction is effectful so it won't be (re)moved anyway.
Attachment #8856175 - Flags: feedback?(jdemooij) → feedback+
(Reporter)

Comment 20

12 days ago
I'm interested in performance numbers btw, also for the megamorphic case.

hasOwnProperty is used a lot so it's super cool to have ICs for it.
(Assignee)

Comment 21

12 days ago
(In reply to Jan de Mooij [:jandem] from comment #18)
> ::: js/src/jit/VMFunctions.cpp
> @@ +1757,5 @@
> > +
> > +    // Property not found. Watch out for Class hooks.
> > +    if (MOZ_UNLIKELY(!nobj->is<PlainObject>())) {
> > +        if (ClassMayResolveId(cx->names(), nobj->getClass(), id, nobj) ||
> > +            nobj->getClass()->getGetProperty()) // XXX other hooks I think lookup/has
> 
> The fast path in obj_hasOwnProperty calls NativeLookupOwnProperty ->
> LookupOwnPropertyInline, and there we only check for resolve hooks as far as
> I can tell? So I think ClassMayResolveId will be sufficient here...
I think in theory we should look out for getOpsGetOwnPropertyDescriptor, but no well behaved native object should have that. I will look into adding an assert that none of the important ObjectOps are defined on native classes. IIRC environment objects are the exception still.
(Assignee)

Comment 22

12 days ago
Created attachment 8857466 [details] [diff] [review]
Part 6 - Port JSOP_IN notDefined optimization to JSOP_HASOWN
Attachment #8857466 - Flags: review?(jdemooij)
(Assignee)

Comment 23

12 days ago
Created attachment 8857562 [details]
micro benchmark

This benchmark improves from around 58ms to 32ms. While benchmarking on a simpler test case I noticed that we don't attach this stub for unboxed objects. Same for |in|. That should be easy to fix in a followup.
(Assignee)

Comment 24

12 days ago
Created attachment 8857591 [details] [diff] [review]
Part 5 - CacheIR HasOwn in Ion

Turns out there was some mistake about assigning the CacheIR input and I was switching up obj and key. 

https://treeherder.mozilla.org/#/jobs?repo=try&revision=290044d8ce15160c36984e167db5e639ec82b886&selectedJob=91016619
Attachment #8856175 - Attachment is obsolete: true
Attachment #8857591 - Flags: review?(jdemooij)
(Assignee)

Comment 25

12 days ago
Created attachment 8857614 [details] [diff] [review]
Test
Attachment #8857614 - Flags: review?(jdemooij)
(Assignee)

Comment 26

12 days ago
Looks like speedometer actually runs into unboxed objects and array indexes, so probably need to fix that as well soon.
(Assignee)

Comment 27

12 days ago
Created attachment 8857692 [details] [diff] [review]
Implement more stuff for Speedometer
(Reporter)

Comment 28

11 days ago
evilpie++
(Reporter)

Comment 29

11 days ago
Comment on attachment 8857466 [details] [diff] [review]
Part 6 - Port JSOP_IN notDefined optimization to JSOP_HASOWN

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

Cool.
Attachment #8857466 - Flags: review?(jdemooij) → review+
(Reporter)

Updated

11 days ago
Attachment #8857591 - Flags: review?(jdemooij) → review+
(Reporter)

Comment 30

11 days ago
Comment on attachment 8857614 [details] [diff] [review]
Test

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

Thanks

::: js/src/jit-test/tests/cacheir/hasown.js
@@ +24,5 @@
> +
> +function key() {
> +    var sym = Symbol(), sym2 = Symbol();
> +    var keys = [[sym, true], [sym2, false],
> +                   ["a", true], ["b", false],

Nit: indentation looks wrong
Attachment #8857614 - Flags: review?(jdemooij) → review+
(Assignee)

Comment 31

11 days ago
Comment on attachment 8857692 [details] [diff] [review]
Implement more stuff for Speedometer

I think this actually ok to review. The naming with unboxed and native is a bit confusing, but I can fix that later.
Attachment #8857692 - Attachment description: WIP implement everything that is important for Speedometer → Implement more stuff for Speedometer
Attachment #8857692 - Flags: review?(jdemooij)
(Assignee)

Updated

11 days ago
Blocks: 1356315
(Assignee)

Comment 32

11 days ago
With this last patch should we remove convertUnboxedObjects from jsop_hasown in Ion? Not sure how that interacts with the not defined analysis though.

Comment 33

11 days ago
Pushed by evilpies@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/7deb7a5cb370
Part 1 - Add JSOP_HASOWN to Interpreter and BytecodeEmitter. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/50e8be7ee748
Part 2 - Baseline fallback support for HasOwn. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/07b10177f708
Part 3 - CacheIR for HasOwn with baseline support. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/5e1a2ab034ae
Part 4 - Megamorphic stub. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/a9d036ef05e8
Part 5 - CacheIR HasOwn in Ion. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/56e3c896e6cc
Test. r=jandem

Comment 34

11 days ago
Pushed by evilpies@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2ca1453ae574
Part 6 - Port not defined property optimzation to HasOwn. r=jandem

Comment 35

10 days ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/7deb7a5cb370
https://hg.mozilla.org/mozilla-central/rev/50e8be7ee748
https://hg.mozilla.org/mozilla-central/rev/07b10177f708
https://hg.mozilla.org/mozilla-central/rev/5e1a2ab034ae
https://hg.mozilla.org/mozilla-central/rev/a9d036ef05e8
https://hg.mozilla.org/mozilla-central/rev/56e3c896e6cc
https://hg.mozilla.org/mozilla-central/rev/2ca1453ae574
Status: NEW → RESOLVED
Last Resolved: 10 days ago
status-firefox55: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55

Comment 36

10 days ago
These patches improved sunspider-tagcloud by 15% and six-speed-for-of-object-es5 by 45%, according to AWFY.
(Reporter)

Comment 37

6 days ago
Comment on attachment 8857692 [details] [diff] [review]
Implement more stuff for Speedometer

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

::: js/src/jit/CacheIR.cpp
@@ +2034,5 @@
>      PropertyResult prop;
>      if (!LookupOwnPropertyPure(cx_, obj, key, &prop))
>          return false;
>  
> +    if (!prop.isFound())

File a follow up bug to make similar changes to JSOP_IN?

@@ +2052,2 @@
>      emitIdGuard(keyId, key);
> +    TestMatchingReceiver(writer, obj, nullptr, objId, &expandoId);

Hm TestMatchingReceiver's shape argument is unused? We should remove it but followup is fine.

Also TestMatchingReceiver guards on the expando object but we don't need that guard for non-expando properties (we only want a group guard). I wonder if it would be simpler to move the unboxed object case out of this method, but not sure about expando properties.
Attachment #8857692 - Flags: review?(jdemooij) → review+
(Assignee)

Comment 38

6 days ago
(In reply to Jan de Mooij [:jandem] from comment #37)
> Comment on attachment 8857692 [details] [diff] [review]
> Implement more stuff for Speedometer
> 
> Review of attachment 8857692 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/CacheIR.cpp
> @@ +2034,5 @@
> >      PropertyResult prop;
> >      if (!LookupOwnPropertyPure(cx_, obj, key, &prop))
> >          return false;
> >  
> > +    if (!prop.isFound())
> 
> File a follow up bug to make similar changes to JSOP_IN?
> 
> @@ +2052,2 @@
> >      emitIdGuard(keyId, key);
> > +    TestMatchingReceiver(writer, obj, nullptr, objId, &expandoId);
> 
> Hm TestMatchingReceiver's shape argument is unused? We should remove it but
> followup is fine.
>
> Also TestMatchingReceiver guards on the expando object but we don't need
> that guard for non-expando properties (we only want a group guard). I wonder
> if it would be simpler to move the unboxed object case out of this method,
> but not sure about expando properties.
Just to clarify, we don't need to guard on the expando shape or existance, when the property is contained by the unboxed object, because we can't delete to properties without a new group?
(Reporter)

Comment 39

5 days ago
(In reply to Tom Schuster [:evilpie] from comment #38)
> Just to clarify, we don't need to guard on the expando shape or existance,
> when the property is contained by the unboxed object, because we can't
> delete to properties without a new group?

Correct.
Jan, just wanted to track it in this bug for posterity: As this started a a finding in speedometer, what kind if improvement did we see for that benchmark?
Flags: needinfo?(jdemooij)
(Reporter)

Comment 41

3 hours ago
(In reply to :Harald Kirschner :digitarald from comment #40)
> Jan, just wanted to track it in this bug for posterity: As this started a a
> finding in speedometer, what kind if improvement did we see for that
> benchmark?

It's hard to say because Speedometer runs a bunch of different tests and then reports a single number like 60 points so you need pretty big wins to move that.

Follow-up bug 1356315 will optimize the hasOwnProperty-inside-for-in pattern that shows up in a lot of JS code (like React and Ember) and that might be the bigger improvement.
Flags: needinfo?(jdemooij)
You need to log in before you can comment on or make changes to this bug.