Bug 196886

Summary: DFG should be able to constant fold Object.create() with a constant prototype operand
Product: WebKit Reporter: Robin Morisset <rmorisset>
Component: JavaScriptCoreAssignee: Robin Morisset <rmorisset>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, ews-watchlist, keith_miller, mark.lam, msaboff, sbarati, webkit-bug-importer, ysuzuki
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
See Also: https://bugs.webkit.org/show_bug.cgi?id=186199
Attachments:
Description Flags
Patch
ysuzuki: review+
Patch
none
Patch
none
Patch
sbarati: commit-queue-
PatchForLanding none

Description Robin Morisset 2019-04-12 17:37:31 PDT
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).
Comment 1 Robin Morisset 2019-04-12 17:44:22 PDT
Created attachment 367361 [details]
Patch
Comment 2 Yusuke Suzuki 2019-04-12 18:48:30 PDT
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?
Comment 3 EWS Watchlist 2019-04-15 09:31:45 PDT
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.
Comment 4 Saam Barati 2019-04-15 09:33:02 PDT
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...”?
Comment 5 Saam Barati 2019-04-15 09:49:55 PDT
Comment on attachment 367361 [details]
Patch

r=me too with Yusuke’s comments addressed
Comment 6 Robin Morisset 2019-04-15 11:08:00 PDT
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"?
Comment 7 Robin Morisset 2019-04-15 11:11:07 PDT
(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.
Comment 8 Robin Morisset 2019-04-15 11:15:59 PDT
Created attachment 367431 [details]
Patch
Comment 9 Saam Barati 2019-04-15 11:34:19 PDT
(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.
Comment 10 Saam Barati 2019-04-15 11:35:16 PDT
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
Comment 11 EWS Watchlist 2019-04-15 11:56:44 PDT
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.
Comment 12 Yusuke Suzuki 2019-04-15 12:02:20 PDT
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?
Comment 13 Robin Morisset 2019-04-15 12:42:02 PDT
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.
Comment 14 Saam Barati 2019-04-15 12:45:29 PDT
(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.
Comment 15 Saam Barati 2019-04-15 12:48:19 PDT
(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".
Comment 16 Robin Morisset 2019-04-15 12:56:15 PDT
(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?
Comment 17 Robin Morisset 2019-04-15 13:11:42 PDT
Created attachment 367446 [details]
Patch

New name: emptyObjectStructureConcurrently

I was not aware that Concurrently canonically implies try/ifExists.
Comment 18 Saam Barati 2019-04-15 14:45:40 PDT
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.
Comment 19 Saam Barati 2019-04-15 14:45:58 PDT
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 "}"
Comment 20 Saam Barati 2019-04-15 14:47:06 PDT
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
Comment 21 Saam Barati 2019-04-15 14:47:35 PDT
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!
Comment 22 Saam Barati 2019-04-15 15:17:23 PDT
*** Bug 186199 has been marked as a duplicate of this bug. ***
Comment 23 Robin Morisset 2019-04-15 16:22:20 PDT
(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.
Comment 24 Robin Morisset 2019-04-15 16:22:50 PDT
Created attachment 367475 [details]
PatchForLanding
Comment 25 WebKit Commit Bot 2019-04-15 17:28:53 PDT
Comment on attachment 367475 [details]
PatchForLanding

Clearing flags on attachment: 367475

Committed r244313: <https://trac.webkit.org/changeset/244313>
Comment 26 WebKit Commit Bot 2019-04-15 17:28:55 PDT
All reviewed patches have been landed.  Closing bug.
Comment 27 Radar WebKit Bug Importer 2019-04-15 17:29:19 PDT
<rdar://problem/49924798>