Bug 196886 – DFG should be able to constant fold Object.create() with a constant prototype operand

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Robin Morisset]

It is a fairly simple and limited patch, as it only works when the DFG can prove the exact object used as prototype.
But when it applies it can be a significant win:

                                                 Baseline                   Optim                                       

object-create-constant-prototype              3.6082+-0.0979     ^      1.6947+-0.0756        ^ definitely 2.1292x faster
object-create-null                           11.4492+-0.2510     ?     11.5030+-0.2402        ?
object-create-unknown-object-prototype       15.6067+-0.1851     ?     15.7500+-0.2322        ?
object-create-untyped-prototype               8.8873+-0.1240     ?      8.9806+-0.1202        ? might be 1.0105x slower

<geometric>                                   8.6967+-0.1208     ^      7.2408+-0.1367        ^ definitely 1.2011x faster

The only subtlety is that we need to to access the StructureCache concurrently from the compiler thread (see https://bugs.webkit.org/show_bug.cgi?id=186199)
I solved this with a simple lock, taken when the compiler thread tries to read it, and when the main thread tries to modify it.
I expect it to be extremely low contention, but will watch the bots just in case.
The lock is taken neither when the main thread is only reading the cache (it has no-one to race with), nor when the GC purges it of dead entries (it does not free anything while a compiler thread is in the middle of a phase).

[Robin Morisset]

Created attachment 367361 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 367361 [details]
Patch

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

Looks nice. r=me with nits.

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2595
> +            else {
> +                RELEASE_ASSERT(base.isObject());

Since this child1 is `UntypedUse`, any value can come here. Let's do `else if (base.isObject())` instead.
And initialize `structure` with nullptr since we now have a path that does not assign anything to the variable structure :)

I think we can write a test, like,

function test()
{
    for (var i = 0; i < 1e6; ++i) {
        try { Object.create(undefined); } catch { }
    }
}

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2599
> +            if (!!structure) {

Personally I like `if (structure)`.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:759
> +                        RELEASE_ASSERT(base.isObject());

Ditto.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:763
> +                    if (!!structure) {

Ditto.

> Source/JavaScriptCore/runtime/StructureCache.cpp:63
> +    holdLock(m_lock);

This immediately discards the LockHolder after this statement finishes, and unlocked.
Use `auto locker = holdLock(m_lock);` instead.

> Source/JavaScriptCore/runtime/StructureCache.cpp:74
> +    holdLock(m_lock);

Ditto.

> Source/JavaScriptCore/runtime/StructureCache.h:61
>      StructureMap m_structures;

This is WeakGCMap. So it is held by Heap, and collector checks this without taking this lock.
I think it is safe since we don't run GC end phase while compiler thread is running.
Another thing I would like to ensure is that this holds Weak<> handles.
I think this does not return dead cells when the compiler threads successfully read it concurrently.
Can you ensure they are safe?

[EWS Watchlist]

Attachment 367361 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/StructureCache.h:55:  The parameter name "globalObject" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 1 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

Comment on attachment 367361 [details]
Patch

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

> Source/JavaScriptCore/runtime/StructureCache.cpp:68
> +Structure* StructureCache::tryEmptyObjectStructureForPrototypeFromCompilerThread(JSGlobalObject* globalObject, JSObject* prototype, unsigned inlineCapacity)

Name nit: maybe “tryGetEmpty...”?

[Saam Barati]

Comment on attachment 367361 [details]
Patch

r=me too with Yusuke’s comments addressed

[Robin Morisset]

Thanks for the review!

> 
> > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2595
> > +            else {
> > +                RELEASE_ASSERT(base.isObject());
> 
> Since this child1 is `UntypedUse`, any value can come here. Let's do `else
> if (base.isObject())` instead.
> And initialize `structure` with nullptr since we now have a path that does
> not assign anything to the variable structure :)
> 
> I think we can write a test, like,
> 
> function test()
> {
>     for (var i = 0; i < 1e6; ++i) {
>         try { Object.create(undefined); } catch { }
>     }
> }

Done. I've added a couple lines to JSTests/stress/object-create-undefined.js to that effect.

> 
> > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2599
> > +            if (!!structure) {
> 
> Personally I like `if (structure)`.

Fixed.

> > Source/JavaScriptCore/runtime/StructureCache.cpp:63
> > +    holdLock(m_lock);
> 
> This immediately discards the LockHolder after this statement finishes, and
> unlocked.
> Use `auto locker = holdLock(m_lock);` instead.

Oops, that was a big mistake on my part. Thank you for catching it.
I will add WARN_UNUSED_RESULT to holdLock in a separate patch.

> > Source/JavaScriptCore/runtime/StructureCache.h:61
> >      StructureMap m_structures;
> 
> This is WeakGCMap. So it is held by Heap, and collector checks this without
> taking this lock.
> I think it is safe since we don't run GC end phase while compiler thread is
> running.
> Another thing I would like to ensure is that this holds Weak<> handles.
> I think this does not return dead cells when the compiler threads
> successfully read it concurrently.
> Can you ensure they are safe?

I don't understand what you mean here. The main thread outside of GC can only add things to the cache, not remove them. The compiler thread can never race with the GC end phase, as it only runs between compiler phases. And the lock ensures that additions to the cache are atomic to the compiler thread (it cannot see a half-written value). So I don't see how the compiler could ever read stuff that has not been properly written into the cache, and since it is a WeakGCMap, they are automatically Structure* referred by a Weak<> handle. We then registerStructure them, making sure they won't be GC-ed even after our phase ends.

What do you mean by "safe"?

[Robin Morisset]

(In reply to Saam Barati from comment #4)
> Comment on attachment 367361 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=367361&action=review
> 
> > Source/JavaScriptCore/runtime/StructureCache.cpp:68
> > +Structure* StructureCache::tryEmptyObjectStructureForPrototypeFromCompilerThread(JSGlobalObject* globalObject, JSObject* prototype, unsigned inlineCapacity)
> 
> Name nit: maybe “tryGetEmpty...”?

The webkit style guide (https://webkit.org/code-style-guidelines/#names) recommends only using the "Get" verb for functions that return their result through an argument: 'Use bare words for getters [..] Precede getters that return values through out arguments with the word “get”.'

But I agree that the current name is a monstrosity, I was just unsure what better name to pick.

[Robin Morisset]

Created attachment 367431 [details]
Patch

[Saam Barati]

(In reply to Robin Morisset from comment #7)
> (In reply to Saam Barati from comment #4)
> > Comment on attachment 367361 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=367361&action=review
> > 
> > > Source/JavaScriptCore/runtime/StructureCache.cpp:68
> > > +Structure* StructureCache::tryEmptyObjectStructureForPrototypeFromCompilerThread(JSGlobalObject* globalObject, JSObject* prototype, unsigned inlineCapacity)
> > 
> > Name nit: maybe “tryGetEmpty...”?
> 
> The webkit style guide (https://webkit.org/code-style-guidelines/#names)
> recommends only using the "Get" verb for functions that return their result
> through an argument: 'Use bare words for getters [..] Precede getters that
> return values through out arguments with the word “get”.'
> 
> But I agree that the current name is a monstrosity, I was just unsure what
> better name to pick.

I would ignore the style guide here given that the current name doesn't resemble anything sensible and we probably ignore it in other places. Alternately, we've picked names like this for stuff like this in the past:

"emptyObjectStructureForPrototypeConcurrently"

I think that's good enough.

[Saam Barati]

Comment on attachment 367431 [details]
Patch

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

> Source/JavaScriptCore/runtime/StructureCache.cpp:62
> +    // We do need to lock here to avoid a race with a compiler thread that may be accessing the cache in read-only mode.

No need for this comment, it's obvious.

> Source/JavaScriptCore/runtime/StructureCache.cpp:73
> +    // We need to hold a lock to make sure the main thread is not modifying the underlying hash table from under us.

ditto

[EWS Watchlist]

Attachment 367431 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/StructureCache.h:55:  The parameter name "globalObject" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 1 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Yusuke Suzuki]

Comment on attachment 367361 [details]
Patch

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

>> Source/JavaScriptCore/runtime/StructureCache.h:61
>>      StructureMap m_structures;
> 
> This is WeakGCMap. So it is held by Heap, and collector checks this without taking this lock.
> I think it is safe since we don't run GC end phase while compiler thread is running.
> Another thing I would like to ensure is that this holds Weak<> handles.
> I think this does not return dead cells when the compiler threads successfully read it concurrently.
> Can you ensure they are safe?

Sorry, I'll simplify the questions. Can you answer the following questions?

1. WeakGCMap is registered to the Heap, and GC repeatedly looks into it. But at that time, collector does not take this m_lock. Is it safe?
2. WeakGCMap holds Weak<>, and concurrent compiler reads cells from it. Do concurrent compilers read the live cells or nullptr from this Weak<> handles?

[Robin Morisset]

Created attachment 367441 [details]
Patch

Went with tryEmptyObjectStructureConcurrently, it is significantly shorter, respect the style guide, and still makes it clear that it can fail.
The 'ForPrototype' part of the name is less important in my view, considering that there is an argument called prototype, it should be sufficiently clear.

Also removed the comments that Saam finds obvious, and updated the year in the top-of-file copyright comments.

[Saam Barati]

(In reply to Robin Morisset from comment #13)
> Created attachment 367441 [details]
> Patch
> 
> Went with tryEmptyObjectStructureConcurrently, it is significantly shorter,
> respect the style guide, and still makes it clear that it can fail.
> The 'ForPrototype' part of the name is less important in my view,
> considering that there is an argument called prototype, it should be
> sufficiently clear.
I still don't like that name. I'm not sure what our style guideline says here, but I think we tend to not choose names like this that would make a grammatically incorrect sentence.

> 
> Also removed the comments that Saam finds obvious, and updated the year in
> the top-of-file copyright comments.

[Saam Barati]

(In reply to Saam Barati from comment #14)
> (In reply to Robin Morisset from comment #13)
> > Created attachment 367441 [details]
> > Patch
> > 
> > Went with tryEmptyObjectStructureConcurrently, it is significantly shorter,
> > respect the style guide, and still makes it clear that it can fail.
> > The 'ForPrototype' part of the name is less important in my view,
> > considering that there is an argument called prototype, it should be
> > sufficiently clear.
> I still don't like that name. I'm not sure what our style guideline says
> here, but I think we tend to not choose names like this that would make a
> grammatically incorrect sentence.
> 
> > 
> > Also removed the comments that Saam finds obvious, and updated the year in
> > the top-of-file copyright comments.

I guess if we followed the style guide to a T, we'd end up with:
emptyObjectStructureIfExists.

FWIW, "Concurrently" in JSC is sorta like "IfExists" in the rest of WebKit. I think we use "Concurrently" to generally mean "can return null".

[Robin Morisset]

(In reply to Yusuke Suzuki from comment #12)
> Comment on attachment 367361 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=367361&action=review
> 
> >> Source/JavaScriptCore/runtime/StructureCache.h:61
> >>      StructureMap m_structures;
> > 
> > This is WeakGCMap. So it is held by Heap, and collector checks this without taking this lock.
> > I think it is safe since we don't run GC end phase while compiler thread is running.
> > Another thing I would like to ensure is that this holds Weak<> handles.
> > I think this does not return dead cells when the compiler threads successfully read it concurrently.
> > Can you ensure they are safe?
> 
> Sorry, I'll simplify the questions. Can you answer the following questions?
> 
> 1. WeakGCMap is registered to the Heap, and GC repeatedly looks into it. But
> at that time, collector does not take this m_lock. Is it safe?

The collector can read into the WeakGCMap whenever it wants, that won't cause trouble to the compiler thread that only reads it too. The collector only mutates it at the end of GC phase, when the compiler thread is paused between phases, so no race there either.

The lock clearly protects against races between the mutator main thread and the compiler threads.

So it only leaves mutator main thread/collector as a potential hazard. I am not sure how that one is safe, but since it was not changed in any way by my change, I don't see how I could have made it unsafe.

> 2. WeakGCMap holds Weak<>, and concurrent compiler reads cells from it. Do
> concurrent compilers read the live cells or nullptr from this Weak<> handles?

I think (with low confidence) that it should read the live cells, as Heap::runEndPhase basically goes "pause all compiler threads -> reap weak handles -> prune weakGCMaps", so the compiler thread should never see a weakGCMap with reaped but not pruned Weak<>.
The good news is that even if I am wrong on that point it should not matter: tryEmptyObjectStructureConcurrently is always allowed to return nullptr for any reason (since it does not try to build the structure if it is not already in the cache), and both of its clients check that the return is not null.


Did this answer your questions?

[Robin Morisset]

Created attachment 367446 [details]
Patch

New name: emptyObjectStructureConcurrently

I was not aware that Concurrently canonically implies try/ifExists.

[Saam Barati]

Comment on attachment 367446 [details]
Patch

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

> Source/JavaScriptCore/runtime/StructureCache.h:55
> +    JS_EXPORT_PRIVATE Structure* tryEmptyObjectStructureConcurrently(JSGlobalObject*, JSObject* prototype, unsigned inlineCapacity);

still using the old name.

[Saam Barati]

Comment on attachment 367446 [details]
Patch

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

> Source/JavaScriptCore/runtime/StructureCache.cpp:71
> +    PrototypeKey key { prototype, nullptr, inlineCapacity, JSFinalObject::info(), globalObject};

nit: space before "}"

[Saam Barati]

Comment on attachment 367446 [details]
Patch

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

> Source/JavaScriptCore/runtime/StructureCache.cpp:74
> +        ASSERT(prototype->mayBePrototype());

this assertion is wrong. Nothing guaranteeing that this thing is already a prototype

[Saam Barati]

Comment on attachment 367446 [details]
Patch

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

>> Source/JavaScriptCore/runtime/StructureCache.cpp:74
>> +        ASSERT(prototype->mayBePrototype());
> 
> this assertion is wrong. Nothing guaranteeing that this thing is already a prototype

oops. Ignore me! It's in the map, so of course it's already a prototype!

[Saam Barati]

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

[Robin Morisset]

(In reply to Saam Barati from comment #18)
> Comment on attachment 367446 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=367446&action=review
> 
> > Source/JavaScriptCore/runtime/StructureCache.h:55
> > +    JS_EXPORT_PRIVATE Structure* tryEmptyObjectStructureConcurrently(JSGlobalObject*, JSObject* prototype, unsigned inlineCapacity);
> 
> still using the old name.

oh?! I must have updated the wrong patch. Fixing it now.

[Robin Morisset]

Created attachment 367475 [details]
PatchForLanding

[WebKit Commit Bot]

Comment on attachment 367475 [details]
PatchForLanding

Clearing flags on attachment: 367475

Committed r244313: <https://trac.webkit.org/changeset/244313>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/49924798>