Bug 190047 – [JSC] Optimize Object.keys by caching own keys results in StructureRareData

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Yusuke Suzuki]

Let's cache the own keys in StructureRareData and reuse it to optimize Object.keys.
We will put JSImmutableButterfly in StructureRareData. And Object.keys will generate JSArray wrapping it!

[Yusuke Suzuki]

Object.keys are super heavily called in web-tooling-benchmarks.

[Saam Barati]

When is it safe to cache this? Object.keys is just self keys, right? Not prototype chain? So I guess if we're not a dictionary we can cache?

[Saam Barati]

(In reply to Saam Barati from comment #2)
> When is it safe to cache this? Object.keys is just self keys, right? Not
> prototype chain? So I guess if we're not a dictionary we can cache?

We should also have some story of cleaning up this value.

[Yusuke Suzuki]

(In reply to Saam Barati from comment #3)
> (In reply to Saam Barati from comment #2)
> > When is it safe to cache this? Object.keys is just self keys, right? Not
> > prototype chain? So I guess if we're not a dictionary we can cache?
> 
> We should also have some story of cleaning up this value.

I think we can align the lifetime of the cache to the JSPropertyEnumerator cache (for-in cache).
But currently, we do not clear JSPropertyEnumerator cache.

[Yusuke Suzuki]

Created attachment 351069 [details]
WIP

Initial patch

[Yusuke Suzuki]

(In reply to Yusuke Suzuki from comment #4)
> (In reply to Saam Barati from comment #3)
> > (In reply to Saam Barati from comment #2)
> > > When is it safe to cache this? Object.keys is just self keys, right? Not
> > > prototype chain? So I guess if we're not a dictionary we can cache?
> > 
> > We should also have some story of cleaning up this value.
> 
> I think we can align the lifetime of the cache to the JSPropertyEnumerator
> cache (for-in cache).
> But currently, we do not clear JSPropertyEnumerator cache.

Possible ways.

1. Do not add clearing path.

Anyway, when Structure is collected, the cache is also collected.
This is the same lifetime to the existing for-in cache.

2. Use Weak.

Once the cached JSImmutableButterfly is not reachable from elsewhere, it will be collected.

3. Clear cache in Heap::finalize()

It would be a bit costly to iterate StructureRareData (iterating IsoHeap), but we can clear these data when finalizing the collector.

[Yusuke Suzuki]

This is an initial attempt. It improves two benchmarks in SixSpeed since both use Object.keys.

                            baseline                  patched

object-assign.es5      333.2122+-4.8252     ^    219.6000+-3.3567        ^ definitely 1.5174x faster
for-of-object.es6      272.0637+-3.3468     ^    128.9627+-3.7837        ^ definitely 2.1096x faster

And it improves web-tooling-benchmark/lebab since it heavily uses Object.keys.

Before:  lebab:  5.76 runs/s
After:   lebab:  6.84 runs/s

[Yusuke Suzuki]

Created attachment 351070 [details]
WIP

[Yusuke Suzuki]

Created attachment 356924 [details]
WIP

[Yusuke Suzuki]

Created attachment 356953 [details]
Patch

[Yusuke Suzuki]

Ping?

[Keith Miller]

Comment on attachment 356953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=356953&action=review

r=me. Although, I agree with Saam that we should probably have a story for collecting stale enumerations. Can you file a bug?

Maybe something like: clear on FullGC + Structure is only referenced via a transition? Not sure how we would determine the latter though...

> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:62
> +    return m_cachedOwnKeys.get();

Do we have an ASSERT(!compilationOrGCThread())?

[Yusuke Suzuki]

Comment on attachment 356953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=356953&action=review

Thanks. I've opened the bug for tracking GC enhancement. https://bugs.webkit.org/show_bug.cgi?id=192659

>> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:62
>> +    return m_cachedOwnKeys.get();
> 
> Do we have an ASSERT(!compilationOrGCThread())?

Sounds nice! Fixed.

[Yusuke Suzuki]

Committed r239153: <https://trac.webkit.org/changeset/239153>

[Radar WebKit Bug Importer]

<rdar://problem/46688655>

[Yusuke Suzuki]

Committed r239154: <https://trac.webkit.org/changeset/239154>

[Yusuke Suzuki]

Committed r239155: <https://trac.webkit.org/changeset/239155>

[Saam Barati]

Comment on attachment 356953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=356953&action=review

I have a few comments.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:769
> +            case ObjectKeys: {

I really wish we had a way of duplicating less code between AI and constant folding

> Source/JavaScriptCore/runtime/ObjectConstructor.cpp:956
> +                            structure->setCachedOwnKeys(vm, jsCast<JSImmutableButterfly*>(vm.sentinelImmutableButterfly.get()));

Is the whole point of this just to cache after we ask for keys more than once? Why not just store a sentinel using the number 1? The getter can then just return nullptr to people when it’s really 1. You could then get a rid of a lot of pointer compares to this sentinel value too

> Source/JavaScriptCore/runtime/Structure.h:331
> +        WTF::loadLoadFence();

Why? All your loads are dependent loads based off of this

> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:68
> +    WTF::loadLoadFence();

Ditto as to why

> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:74
> +    WTF::storeStoreFence();

This one makes sense and is required

[Saam Barati]

(In reply to Keith Miller from comment #12)
> Comment on attachment 356953 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=356953&action=review
> 
> r=me. Although, I agree with Saam that we should probably have a story for
> collecting stale enumerations. Can you file a bug?
> 
> Maybe something like: clear on FullGC + Structure is only referenced via a
> transition? Not sure how we would determine the latter though...
We could do an even simpler thing:
Delete it if it hasn’t been used since the last GC. We just need to store a bit when we use it.
> 
> > Source/JavaScriptCore/runtime/StructureRareDataInlines.h:62
> > +    return m_cachedOwnKeys.get();
> 
> Do we have an ASSERT(!compilationOrGCThread())?

[WebKit Commit Bot]

Re-opened since this is blocked by bug 192715

[Ryan Haddad]

*** Bug 192673 has been marked as a duplicate of this bug. ***

[Yusuke Suzuki]

(In reply to Ryan Haddad from comment #21)
> *** Bug 192673 has been marked as a duplicate of this bug. ***

OK, I think I found the issue.
When executing Object.keys, we first create JSImmutableButterfly, then store JSString keys into this immutable butterfly.
The problem is that we allocates JSString* after creating JSImmutableButterfly.
So, when the collector is waken up in this JSString* allocation, it will see JSImmutableButterfly which holds many uninitialized hidden fields.
If the marker want to mark them, then we have a bad time.

I think calling `setStartingValue(JSValue())` for Contiguous shape case would be good way to fix the issue.

[Yusuke Suzuki]

Comment on attachment 356953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=356953&action=review

>> Source/JavaScriptCore/runtime/ObjectConstructor.cpp:956
>> +                            structure->setCachedOwnKeys(vm, jsCast<JSImmutableButterfly*>(vm.sentinelImmutableButterfly.get()));
> 
> Is the whole point of this just to cache after we ask for keys more than once? Why not just store a sentinel using the number 1? The getter can then just return nullptr to people when it’s really 1. You could then get a rid of a lot of pointer compares to this sentinel value too

This a bit simplifies the marking code in StructureRareData::visitChildren and the user code of cachedOwnKeys.
I'll attempt to change it to some dummy value.

>> Source/JavaScriptCore/runtime/Structure.h:331
>> +        WTF::loadLoadFence();
> 
> Why? All your loads are dependent loads based off of this

Right, removed.

>> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:68
>> +    WTF::loadLoadFence();
> 
> Ditto as to why

Ah, after considering about it, I think it is not necessary. No load-load barrier is required.

[Yusuke Suzuki]

Created attachment 357399 [details]
Patch

[Saam Barati]

Comment on attachment 357399 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357399&action=review

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2587
> +            if (structureSet.isFinite() && structureSet.size() == 1) {

Do we ever think we’d see two structures with the same ownKeys array? We could serialize this across >1 structure somehow if we ever found it useful

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2590
> +                    auto* immutableButterfly = rareData->cachedOwnKeysConcurrently();

Why not just make the getter return nullptr if it’s the sentinel? Then you could have some function like getIgnoringSentinel for the only getter you call that cares if it’s actually the sentinel value

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:2695
> +    case ObjectKeysIntrinsic: {

Is Object.keys observable if the input isn’t a Proxy?

> Source/JavaScriptCore/dfg/DFGNode.cpp:229
> +    setOpAndDefaultFlags(NewArrayBuffer);

Does this node do the right thing if we’re having a bad time?

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:12394
> +            slowCases.append(m_jit.branch32(CCallHelpers::Equal, CCallHelpers::Address(scratchGPR, JSCell::structureIDOffset()), TrustedImm32(bitwise_cast<int32_t>(m_jit.vm()->structureStructure->structureID()))));

This is how we determine its RareData? Does StructureRareData have a a JSType?

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:12399
> +            slowCases.append(m_jit.branchPtr(CCallHelpers::Equal, scratchGPR, TrustedImmPtr(bitwise_cast<void*>(StructureRareData::cachedOwnKeysSentinel()))));

You can combine both branches here if you assert the sentinel is “1”, and branch BelowOrEqual

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:5531
> +                m_out.branch(m_out.notEqual(cachedOwnKeys, m_out.constIntPtr(bitwise_cast<void*>(StructureRareData::cachedOwnKeysSentinel()))), unsure(useCacheCase), unsure(slowCase));

Ditto about combining branches

> Source/JavaScriptCore/runtime/JSImmutableButterfly.h:123
> +        if (hasContiguous(indexingType())) {

Why is this needed?

> Source/JavaScriptCore/runtime/ObjectConstructor.cpp:939
> +                        auto* cachedButterfly = structure->cachedOwnKeys();

Based on earlier comment, this would be the only call to something like “cachedOwnKeysIgnorningSentinel”

[Yusuke Suzuki]

Comment on attachment 357399 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357399&action=review

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2587
>> +            if (structureSet.isFinite() && structureSet.size() == 1) {
> 
> Do we ever think we’d see two structures with the same ownKeys array? We could serialize this across >1 structure somehow if we ever found it useful

Currently, I think we do not have the use cases that receive benefit from it. Once it is required, we need to consider the optimization.
But even in that case, ObjectKeys is accelerated if the given Structure has the cache.

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2590
>> +                    auto* immutableButterfly = rareData->cachedOwnKeysConcurrently();
> 
> Why not just make the getter return nullptr if it’s the sentinel? Then you could have some function like getIgnoringSentinel for the only getter you call that cares if it’s actually the sentinel value

Interesting. Basically, all the concurrent functions do not care about sentinel since they do not set a new JSImmutableButterfly. So, only the function called from the main thread matters.
Fixed.

>> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:2695
>> +    case ObjectKeysIntrinsic: {
> 
> Is Object.keys observable if the input isn’t a Proxy?

No, it's not observable if the input isn't a Proxy. But as a first step, I think the current implementation is OK.
We could optimize it further by adding special care to clobberizing rules in the subsequent patch.

Moreover, if ObjectKeys only takes one Structure which is proven in AI, then it is converted into NewArrayBuffer, which tells us that it does not have any side effect.
So, I think large part of the use cases is already covered by this.

>> Source/JavaScriptCore/dfg/DFGNode.cpp:229
>> +    setOpAndDefaultFlags(NewArrayBuffer);
> 
> Does this node do the right thing if we’re having a bad time?

We convert ObjectKeys into NewArrayBuffer only when we can watch the HavingABadTimeWatchpoint.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:12394
>> +            slowCases.append(m_jit.branch32(CCallHelpers::Equal, CCallHelpers::Address(scratchGPR, JSCell::structureIDOffset()), TrustedImm32(bitwise_cast<int32_t>(m_jit.vm()->structureStructure->structureID()))));
> 
> This is how we determine its RareData? Does StructureRareData have a a JSType?

Yes. You can see Structure::isRareData function. And StructureRareData does not have a JSType.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:12399
>> +            slowCases.append(m_jit.branchPtr(CCallHelpers::Equal, scratchGPR, TrustedImmPtr(bitwise_cast<void*>(StructureRareData::cachedOwnKeysSentinel()))));
> 
> You can combine both branches here if you assert the sentinel is “1”, and branch BelowOrEqual

Nice. fixed.

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:5531
>> +                m_out.branch(m_out.notEqual(cachedOwnKeys, m_out.constIntPtr(bitwise_cast<void*>(StructureRareData::cachedOwnKeysSentinel()))), unsure(useCacheCase), unsure(slowCase));
> 
> Ditto about combining branches

Fixed.

>> Source/JavaScriptCore/runtime/JSImmutableButterfly.h:123
>> +        if (hasContiguous(indexingType())) {
> 
> Why is this needed?

If this does not exist, the storage of JSImmutableButterfly (Contiguous) remains uninitialized when it is created.
This leads to the crash if we perform allocation after JSImmutableButterfly is created and before all the storage is filled.
This patch is rolled out because of this GC issue.

Two possible fixes are considered,
(1) Put DeferGC on ObjectKeys' appropriate path. But since ObjectKeys would create so many JSString*, it is not so desirable.
(2) Fill JSImmutableButterfly Contiguous storage fields.

In this patch, I took (2). This approach can fix the above scenario, which can easily happen.
And since JSValue() is JSEmpty (nullptr in 64bit), the following code could be compiled into very efficient one.

>> Source/JavaScriptCore/runtime/ObjectConstructor.cpp:939
>> +                        auto* cachedButterfly = structure->cachedOwnKeys();
> 
> Based on earlier comment, this would be the only call to something like “cachedOwnKeysIgnorningSentinel”

Fixed.

[Yusuke Suzuki]

Created attachment 357412 [details]
Patch

[Yusuke Suzuki]

Created attachment 357427 [details]
Patch

[Saam Barati]

Comment on attachment 357427 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357427&action=review

r=me. Nice!

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2591
> +                    auto* immutableButterfly = rareData->cachedOwnKeysConcurrently();
> +                    if (immutableButterfly && immutableButterfly != StructureRareData::cachedOwnKeysSentinel()) {

This should now just be:
if (auto* immutableButterfly = rareData->cachedOwnKeysConcurrently()) { ... }

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:776
> +                            auto* immutableButterfly = rareData->cachedOwnKeysConcurrently();
> +                            if (immutableButterfly && immutableButterfly != StructureRareData::cachedOwnKeysSentinel()) {

ditto

> Source/JavaScriptCore/runtime/JSImmutableButterfly.h:126
> +        if (hasContiguous(indexingType())) {
> +            for (unsigned index = 0; index < length; ++index)
> +                toButterfly()->contiguous().at(this, index).setStartingValue(JSValue());
> +        }

Why not only do this for Object.keys? Seems like this might affect other callers too? Seems like there should be some kind of ::create that has this in its name?

> Source/JavaScriptCore/runtime/ObjectConstructor.cpp:939
> +                            // Cache the immutable butterfly!

nit: This comment has no purpose.

> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:85
> +    WTF::storeStoreFence();

nit: Only needs to be done on the "else"

[Yusuke Suzuki]

Comment on attachment 357427 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357427&action=review

Thank you!

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2591
>> +                    if (immutableButterfly && immutableButterfly != StructureRareData::cachedOwnKeysSentinel()) {
> 
> This should now just be:
> if (auto* immutableButterfly = rareData->cachedOwnKeysConcurrently()) { ... }

Fixed.

>> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:776
>> +                            if (immutableButterfly && immutableButterfly != StructureRareData::cachedOwnKeysSentinel()) {
> 
> ditto

Fixed.

>> Source/JavaScriptCore/runtime/JSImmutableButterfly.h:126
>> +        }
> 
> Why not only do this for Object.keys? Seems like this might affect other callers too? Seems like there should be some kind of ::create that has this in its name?

I think this is not bad. If the code creates JSImmutableButterfly and does some allocations before filling up the storage, then we have a bad time if this code does not exist.
If we would like to remove this code, I think we should put `DisallowGC` on all the places creating JSImmutableButterfly, putting some optimized path for that use cases.

>> Source/JavaScriptCore/runtime/ObjectConstructor.cpp:939
>> +                            // Cache the immutable butterfly!
> 
> nit: This comment has no purpose.

Removed.

>> Source/JavaScriptCore/runtime/StructureRareDataInlines.h:85
>> +    WTF::storeStoreFence();
> 
> nit: Only needs to be done on the "else"

OK, fixed.

[Yusuke Suzuki]

Committed r239324: <https://trac.webkit.org/changeset/239324>