We always use forEachIterable(), that's not good!
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).
I believe this is related to ARES-6 Air, since we can see that Set() constructor takes too much time in sampling results.
First, we should support cloning case.
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.
(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.
(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.
Created attachment 310810 [details] Patch WIP: Need to add files to xcodeproj
(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.
Created attachment 310838 [details] Patch
Created attachment 310839 [details] Patch
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.
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
Created attachment 310848 [details] Patch
(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; }
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)
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.
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.
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
(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.
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.
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.
(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.
(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, """).
Created attachment 310976 [details] Patch
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.
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
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.
Committed r217525: <http://trac.webkit.org/changeset/217525>
Committed r217527: <http://trac.webkit.org/changeset/217527>
<rdar://problem/32479819>