Bug 172413 – [JSC] Map and Set constructors should have fast path for cloning

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Yusuke Suzuki]

We always use forEachIterable(), that's not good!

[Yusuke Suzuki]

And now, we always use adder function from C++, that's not good.
If we know add function is not replaced, we should add values from C++ interface directly. (This can be easily figured out by setting watchpoint).

[Yusuke Suzuki]

I believe this is related to ARES-6 Air, since we can see that Set() constructor takes too much time in sampling results.

[Yusuke Suzuki]

First, we should support cloning case.

[Yusuke Suzuki]

ARES-6 Air frequently executes LocalCalc(). In which, we perform `new Set(set)` cloning. This can be optimized super well if

1. we know Set.prototype.add is not changed.
2. we know the given set iterator protocol is not changed.

I've just hacked JSC a bit. My rough implementation does not have correct watchpoint for the above ones. But setting a watchpoint is easy.
ARES-6 Air shows another great performance improvement!

Before:
Running... Air ( 1  to go)
firstIteration:     75.96 +- 21.43 ms
averageWorstCase:   40.30 +- 7.67 ms
steadyState:        9.25 +- 0.22 ms
summary:            35.66 +- 2.18 ms

After:
Running... Air ( 1  to go)
firstIteration:     75.07 +- 22.41 ms
averageWorstCase:   38.89 +- 8.26 ms
steadyState:        8.89 +- 0.18 ms

Yay! SteadyState shows another 4% improvement!

I'm now WIP.

[Saam Barati]

(In reply to Yusuke Suzuki from comment #4)
> ARES-6 Air frequently executes LocalCalc(). In which, we perform `new
> Set(set)` cloning. This can be optimized super well if
> 
> 1. we know Set.prototype.add is not changed.
> 2. we know the given set iterator protocol is not changed.
And that there is no add property on the base set. 
> 
> I've just hacked JSC a bit. My rough implementation does not have correct
> watchpoint for the above ones. But setting a watchpoint is easy.
> ARES-6 Air shows another great performance improvement!
> 
> Before:
> Running... Air ( 1  to go)
> firstIteration:     75.96 +- 21.43 ms
> averageWorstCase:   40.30 +- 7.67 ms
> steadyState:        9.25 +- 0.22 ms
> summary:            35.66 +- 2.18 ms
> 
> After:
> Running... Air ( 1  to go)
> firstIteration:     75.07 +- 22.41 ms
> averageWorstCase:   38.89 +- 8.26 ms
> steadyState:        8.89 +- 0.18 ms
> 
> Yay! SteadyState shows another 4% improvement!
> 
> I'm now WIP.

[Yusuke Suzuki]

(In reply to Saam Barati from comment #5)
> And that there is no add property on the base set. 

Right. This should be done as is the similar to the iterator protocol's check. (getDirect() etc.).
In this bug, I'll just attempt to optimize `new Set(set)` case.
Broader optimization (for generic iterators etc.) will be done with https://bugs.webkit.org/show_bug.cgi?id=172419 change.

[Yusuke Suzuki]

Created attachment 310810 [details]
Patch

WIP: Need to add files to xcodeproj

[Yusuke Suzuki]

(In reply to Yusuke Suzuki from comment #6)
> (In reply to Saam Barati from comment #5)
> > And that there is no add property on the base set. 
> 
> Right. This should be done as is the similar to the iterator protocol's
> check. (getDirect() etc.).
> In this bug, I'll just attempt to optimize `new Set(set)` case.
> Broader optimization (for generic iterators etc.) will be done with
> https://bugs.webkit.org/show_bug.cgi?id=172419 change.

After considering about it, I think we do not need to check "add" / "set" existence.
This is because,

1. Our check ensures that generated set / map's [[Prototype]] is Set.prototype or Map.prototype.
2. This constructor newly creates an object. Thus object instance itself does not have any properties.

[Yusuke Suzuki]

Created attachment 310838 [details]
Patch

[Yusuke Suzuki]

Created attachment 310839 [details]
Patch

[Build Bot]

Comment on attachment 310839 [details]
Patch

Attachment 310839 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/3793108

Number of test failures exceeded the failure limit.

[Build Bot]

Created attachment 310844 [details]
Archive of layout-test-results from ews117 for mac-elcapitan

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews117  Port: mac-elcapitan  Platform: Mac OS X 10.11.6

[Yusuke Suzuki]

Created attachment 310848 [details]
Patch

[Yusuke Suzuki]

(In reply to Yusuke Suzuki from comment #13)
> Created attachment 310848 [details]
> Patch

BTW, later, after @nakedConstructor thing is landed, we can extend this Map / Set constructors something like,

function Map()
{
    "use strict";
    var iterable = @argument(0);
    if (iterable == null)
        return @constructMap(new.target);
    var iteratorFunction = @tryGetById(iterable, Symbol.iterator);
    if (iteratorFunction === @mapIteratorFunction)
        return @constructMap(new.target, iterable); // Set watchpoint in DFG
    var result = @constructMap(new.target);
    var adder = result.add;
    for (var value of iterable)
        adder.@call(result, value);
    return result;
}

[Saam Barati]

Comment on attachment 310848 [details]
Patch

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

Mostly LGTM, but I think I found one bug, and have some overall comments. r- b/c the bug.

> Source/JavaScriptCore/runtime/HashMapImpl.h:348
> +        if ((Checked<uint32_t>(base->m_keyCount) * 2).unsafeGet() >= powerOf2)
> +            powerOf2 = (Checked<uint32_t>(powerOf2) * 2).unsafeGet();

How is this condition ever not true? Is it only when keyCount is 0 or 1?

Also, why *2 here, and not *4? After creating this set, if anybody adds anything to it, we'll rehash and grow the table. Are we just guessing that nobody adds to it?

> Source/JavaScriptCore/runtime/HashMapImpl.h:360
> +        makeAndSetNewBuffer(exec, vm);
> +        RETURN_IF_EXCEPTION(scope, void());
> +
> +        m_head.set(vm, this, HashMapBucketType::create(vm));
> +        m_tail.set(vm, this, HashMapBucketType::create(vm));
> +
> +        m_head->setNext(vm, m_tail.get());
> +        m_tail->setPrev(vm, m_head.get());
> +        m_head->setDeleted(true);
> +        m_tail->setDeleted(true);

Nit: This is identical to the other finishCreation. It's probably worth having a helper function.

> Source/JavaScriptCore/runtime/HashMapImpl.h:460
> +    ALWAYS_INLINE void addNormalizedNonExistingForCloning(ExecState* exec, JSValue key, JSValue value = JSValue())

Why does just calling add not work? This function seems nearly identical to the regular add, it feels like there should be a way to combine them. Perhaps the hash lookup loop could take a lambda that does returns a boolean indicating if we can store to the current bucket.

> Source/JavaScriptCore/runtime/InternalFunction.h:51
> +    ALWAYS_INLINE static Structure* createSubclassStructure(ExecState*, JSValue newTarget, Structure*);

I thought this needed to be marked ALWAYS_INLINE on the implementation of the function, not declaration?

> Source/JavaScriptCore/runtime/InternalFunction.h:52
> +    JS_EXPORT_PRIVATE static Structure* createSubclassStructureSlow(ExecState*, JSValue newTarget, Structure*);

this should be private

> Source/JavaScriptCore/runtime/JSSet.cpp:48
> +bool JSSet::isIteratorProtocolFastAndNonObservable()

The name of this function is misleading since returning true does not mean the protocol is fast and non observable. Maybe this doesn't even need to be a function. We can just combine this and "addFastAndNonObservable" into a single function since they both have just one caller, and it's the same function.
(Same comments for the JSMap variant)

> Source/JavaScriptCore/runtime/JSSet.cpp:81
> +    // This is the fast case. Many sets will be an original set.
> +    if (structure == globalObject->setStructure())
> +        return true;
> +
> +    if (structure->storedPrototype() != globalObject->jsSetPrototype())
> +        return false;
> +
> +    return true;

This proof does not look correct. Consider:
```
let x = new Set;
x.add = 42;
```

> Source/JavaScriptCore/runtime/JSSet.h:85
> +template<typename To, typename From>
> +inline typename std::enable_if<std::is_same<typename std::remove_pointer<To>::type, JSSet>::value, To>::type jsDynamicCast(VM&, From* from)
> +{
> +    if (LIKELY(from->type() == JSSetType))
> +        return static_cast<To>(from);
> +    return nullptr;
> +}
> +
> +template<>
> +inline JSSet* jsDynamicCast<JSSet*>(VM&, JSValue from)
> +{
> +    if (LIKELY(from.isCell() && from.asCell()->type() == JSSetType))
> +        return static_cast<JSSet*>(from.asCell());
> +    return nullptr;
> +}

I'd mark JSSet as "final", and static assert that it's final here, otherwise we could have a bad time if anybody ever inherits from them. This will future proof the code with a static assert. (Same for JSMap)

[Yusuke Suzuki]

Comment on attachment 310848 [details]
Patch

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

Thanks!

>> Source/JavaScriptCore/runtime/HashMapImpl.h:348
>> +            powerOf2 = (Checked<uint32_t>(powerOf2) * 2).unsafeGet();
> 
> How is this condition ever not true? Is it only when keyCount is 0 or 1?
> 
> Also, why *2 here, and not *4? After creating this set, if anybody adds anything to it, we'll rehash and grow the table. Are we just guessing that nobody adds to it?

Right. When keyCount is 0 or 1, the above becomes false.

*4 may be ok. But I'm also worried about making this set too big. Because we perform roundUpToPowerOfTwo, powerOf2 * 4 may become very large.
How about changing the above `WTF::roundUpToPowerOfTwo(base->m_keyCount)` to `WTF::roundUpToPowerOfTwo(base->m_keyCount + 1)` and * 2?

>> Source/JavaScriptCore/runtime/HashMapImpl.h:360
>> +        m_tail->setDeleted(true);
> 
> Nit: This is identical to the other finishCreation. It's probably worth having a helper function.

Nice. Fixed.

>> Source/JavaScriptCore/runtime/HashMapImpl.h:460
>> +    ALWAYS_INLINE void addNormalizedNonExistingForCloning(ExecState* exec, JSValue key, JSValue value = JSValue())
> 
> Why does just calling add not work? This function seems nearly identical to the regular add, it feels like there should be a way to combine them. Perhaps the hash lookup loop could take a lambda that does returns a boolean indicating if we can store to the current bucket.

Looks fine. This function also does not check `shouldRehashAfterAdd()`, but maybe, it's not a big deal since rehash() never happens.

>> Source/JavaScriptCore/runtime/InternalFunction.h:51
>> +    ALWAYS_INLINE static Structure* createSubclassStructure(ExecState*, JSValue newTarget, Structure*);
> 
> I thought this needed to be marked ALWAYS_INLINE on the implementation of the function, not declaration?

OK, changed.

>> Source/JavaScriptCore/runtime/InternalFunction.h:52
>> +    JS_EXPORT_PRIVATE static Structure* createSubclassStructureSlow(ExecState*, JSValue newTarget, Structure*);
> 
> this should be private

Right. Fixed.

>> Source/JavaScriptCore/runtime/JSSet.cpp:48
>> +bool JSSet::isIteratorProtocolFastAndNonObservable()
> 
> The name of this function is misleading since returning true does not mean the protocol is fast and non observable. Maybe this doesn't even need to be a function. We can just combine this and "addFastAndNonObservable" into a single function since they both have just one caller, and it's the same function.
> (Same comments for the JSMap variant)

OK, I'll merge them to canCloneFastAndNonObservable().

>> Source/JavaScriptCore/runtime/JSSet.cpp:81
>> +    return true;
> 
> This proof does not look correct. Consider:
> ```
> let x = new Set;
> x.add = 42;
> ```

Discussed with Saam at IRC. This condition is valid since newly cloned Set never has its instance variables.
I'll address the other comments, like unifying the above functions to canCloneFastAndNoObservable().

>> Source/JavaScriptCore/runtime/JSSet.h:85
>> +}
> 
> I'd mark JSSet as "final", and static assert that it's final here, otherwise we could have a bad time if anybody ever inherits from them. This will future proof the code with a static assert. (Same for JSMap)

Marking JSSet and JSMap as final is good. But this implementation is OK as long as a derived class also uses the JSSetType.
While `asCell()->info() == JSMap::info()` is problematic, using type() is ok.
You can create a derived JSMap C++ class which has JSMapType as its JS type.

[Yusuke Suzuki]

Comment on attachment 310848 [details]
Patch

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

>>> Source/JavaScriptCore/runtime/HashMapImpl.h:348
>>> +            powerOf2 = (Checked<uint32_t>(powerOf2) * 2).unsafeGet();
>> 
>> How is this condition ever not true? Is it only when keyCount is 0 or 1?
>> 
>> Also, why *2 here, and not *4? After creating this set, if anybody adds anything to it, we'll rehash and grow the table. Are we just guessing that nobody adds to it?
> 
> Right. When keyCount is 0 or 1, the above becomes false.
> 
> *4 may be ok. But I'm also worried about making this set too big. Because we perform roundUpToPowerOfTwo, powerOf2 * 4 may become very large.
> How about changing the above `WTF::roundUpToPowerOfTwo(base->m_keyCount)` to `WTF::roundUpToPowerOfTwo(base->m_keyCount + 1)` and * 2?

For example, if you have 10 keys, capacity now becomes 16 * 2 = 32. 64 is too much big.

[Saam Barati]

Comment on attachment 310848 [details]
Patch

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

>>> Source/JavaScriptCore/runtime/JSSet.h:85
>>> +}
>> 
>> I'd mark JSSet as "final", and static assert that it's final here, otherwise we could have a bad time if anybody ever inherits from them. This will future proof the code with a static assert. (Same for JSMap)
> 
> Marking JSSet and JSMap as final is good. But this implementation is OK as long as a derived class also uses the JSSetType.
> While `asCell()->info() == JSMap::info()` is problematic, using type() is ok.
> You can create a derived JSMap C++ class which has JSMapType as its JS type.

I agree. But marking it final, and statically asserting that here will make anybody who creates such a subclass *have* to change this function. That could be through:
1. Removing the static assert and making sure that subclass's structure uses JSSetType
2. Removing this function entirely
3. something else altogether

[Saam Barati]

(In reply to Yusuke Suzuki from comment #17)
> Comment on attachment 310848 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=310848&action=review
> 
> >>> Source/JavaScriptCore/runtime/HashMapImpl.h:348
> >>> +            powerOf2 = (Checked<uint32_t>(powerOf2) * 2).unsafeGet();
> >> 
> >> How is this condition ever not true? Is it only when keyCount is 0 or 1?
> >> 
> >> Also, why *2 here, and not *4? After creating this set, if anybody adds anything to it, we'll rehash and grow the table. Are we just guessing that nobody adds to it?
> > 
> > Right. When keyCount is 0 or 1, the above becomes false.
> > 
> > *4 may be ok. But I'm also worried about making this set too big. Because we perform roundUpToPowerOfTwo, powerOf2 * 4 may become very large.
> > How about changing the above `WTF::roundUpToPowerOfTwo(base->m_keyCount)` to `WTF::roundUpToPowerOfTwo(base->m_keyCount + 1)` and * 2?
> 
> For example, if you have 10 keys, capacity now becomes 16 * 2 = 32. 64 is
> too much big.

I see. This makes sense. Ignore my *4 comment.

[Yusuke Suzuki]

Comment on attachment 310848 [details]
Patch

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

>>>> Source/JavaScriptCore/runtime/JSSet.h:85
>>>> +}
>>> 
>>> I'd mark JSSet as "final", and static assert that it's final here, otherwise we could have a bad time if anybody ever inherits from them. This will future proof the code with a static assert. (Same for JSMap)
>> 
>> Marking JSSet and JSMap as final is good. But this implementation is OK as long as a derived class also uses the JSSetType.
>> While `asCell()->info() == JSMap::info()` is problematic, using type() is ok.
>> You can create a derived JSMap C++ class which has JSMapType as its JS type.
> 
> I agree. But marking it final, and statically asserting that here will make anybody who creates such a subclass *have* to change this function. That could be through:
> 1. Removing the static assert and making sure that subclass's structure uses JSSetType
> 2. Removing this function entirely
> 3. something else altogether

Can we add a static_assert for that? We do not have static relation between JSSetType and JSSet C++ class.

[Saam Barati]

All I'm propsing is if we add a static assert that the class is final, if anybody creates a subclass, they'll need to consider how to change this jsDynamicCast function.

[Saam Barati]

(In reply to Saam Barati from comment #21)
> All I'm propsing is if we add a static assert that the class is final, if
> anybody creates a subclass, they'll need to consider how to change this
> jsDynamicCast function.

To clarify, this isn't the most important thing in the world. There are plenty of ways we can break things and we can't always statically assert them. It's up to you if you want to do this or not.

[Yusuke Suzuki]

(In reply to Saam Barati from comment #21)
> All I'm propsing is if we add a static assert that the class is final, if
> anybody creates a subclass, they'll need to consider how to change this
> jsDynamicCast function.

Ah, ok. I've just added static_assert(std::is_final<JSSet>::value, """).

[Yusuke Suzuki]

Created attachment 310976 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 310976 [details]
Patch

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

OK, I've updated the patch.

> Source/JavaScriptCore/runtime/HashMapImpl.h:341
> +        capacity = std::max<uint32_t>(WTF::roundUpToPowerOfTwo(capacity), 4U);

shouldRehashAfterAdd() condition must be met.

[Saam Barati]

Comment on attachment 310976 [details]
Patch

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

Nice. r=me

> Source/JavaScriptCore/runtime/HashMapImpl.h:526
> +    ALWAYS_INLINE void addNormalizedInternal(ExecState* exec, JSValue key, JSValue value, const CanUseBucket& canUseBucket)

Nit: I’d add ASSERT(key == normalizedKey(key))

> Source/JavaScriptCore/runtime/JSMap.cpp:75
> +        if (structure == globalObject->mapStructure())

Nit: this check is essentially no faster than the below branch. Perhaps it can be removed in favor of just the branch below. I understand the check in the nice case since it prevents a hahsmap lookup. But that’s not the case here.

> Source/JavaScriptCore/runtime/JSSet.cpp:75
> +        if (structure == globalObject->setStructure())

Ditto

[Yusuke Suzuki]

Comment on attachment 310976 [details]
Patch

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

Thanks!

>> Source/JavaScriptCore/runtime/HashMapImpl.h:526
>> +    ALWAYS_INLINE void addNormalizedInternal(ExecState* exec, JSValue key, JSValue value, const CanUseBucket& canUseBucket)
> 
> Nit: I’d add ASSERT(key == normalizedKey(key))

Nice. Added.

>> Source/JavaScriptCore/runtime/JSMap.cpp:75
>> +        if (structure == globalObject->mapStructure())
> 
> Nit: this check is essentially no faster than the below branch. Perhaps it can be removed in favor of just the branch below. I understand the check in the nice case since it prevents a hahsmap lookup. But that’s not the case here.

Yeah, right. We do not have hash lookup here. Dropped.

>> Source/JavaScriptCore/runtime/JSSet.cpp:75
>> +        if (structure == globalObject->setStructure())
> 
> Ditto

Dropped.

[Yusuke Suzuki]

Committed r217525: <http://trac.webkit.org/changeset/217525>

[Yusuke Suzuki]

Committed r217527: <http://trac.webkit.org/changeset/217527>

[Radar WebKit Bug Importer]

<rdar://problem/32479819>