We should reform our Set/Map iterator implementation. 1. We should take the design similar to our current Array iterator design to encourage object allocation sinking. 2. Our iterator should hold hash bucket and iterate it. We will implement it in C++ function. And then, we annotate it with intrinsic. And DFG should handle it.
Let's implement super fast Map iteration by accessing HashMapBucket directly.
Created attachment 317861 [details] Patch
Instead of adding a special care of Map bucket types, 1. use it as usual cell type 2. GetMapBucket should return a dummy cell instead of nullptr
I'm actually working on making iteration fast in all the tiers for Array, Map, Set, and String. I think I have a plan that avoids all allocations (with the exception of the array tuple in the Map case) in the fast path in every tier. This is worth landing but there is some chance that I will end up re-writing a bunch of this code in the future.
(In reply to Keith Miller from comment #4) > I'm actually working on making iteration fast in all the tiers for Array, > Map, Set, and String. I think I have a plan that avoids all allocations > (with the exception of the array tuple in the Map case) in the fast path in > every tier. This is worth landing but there is some chance that I will end > up re-writing a bunch of this code in the future. Wow, that's cool! I think your plan is better than introducing optimization like the current array iteration here.
After considering, I think it is still useful if the user invokes next() function / the user uses Map.prototype.forEach.
Created attachment 318603 [details] Patch
Comment on attachment 318603 [details] Patch Attachment 318603 [details] did not pass jsc-ews (mac): Output: http://webkit-queues.webkit.org/results/4349572 New failing tests: jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout-no-llint jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout-ftl-eager-no-cjit jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout-ftl-no-cjit jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout-no-cjit jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout-no-llint jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout-ftl-no-cjit jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout-no-cjit jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout-no-cjit jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout-dfg-eager-no-cjit jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout-no-llint jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout-dfg-eager-no-cjit jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout-ftl-eager-no-cjit jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout-ftl-no-cjit jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout-ftl-eager-no-cjit jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout-no-ftl jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout-no-ftl jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout jsc-layout-tests.yaml/js/script-tests/symbol-in-map.js.layout es6.yaml/es6/Map_-0_key_converts_to_+0.js.default jsc-layout-tests.yaml/js/script-tests/map-foreach-calls-back-with-right-args.js.layout-no-ftl jsc-layout-tests.yaml/js/script-tests/basic-map.js.layout-dfg-eager-no-cjit
Created attachment 318631 [details] Patch
Comment on attachment 318631 [details] Patch Attachment 318631 [details] did not pass mac-debug-ews (mac): Output: http://webkit-queues.webkit.org/results/4354118 Number of test failures exceeded the failure limit.
Created attachment 318635 [details] Archive of layout-test-results from ews112 for mac-elcapitan The attached test failures were seen while running run-webkit-tests on the mac-debug-ews. Bot: ews112 Port: mac-elcapitan Platform: Mac OS X 10.11.6
Comment on attachment 318631 [details] Patch Attachment 318631 [details] did not pass mac-ews (mac): Output: http://webkit-queues.webkit.org/results/4354134 New failing tests: inspector/model/remote-object-mutated-iterators.html
Created attachment 318636 [details] Archive of layout-test-results from ews103 for mac-elcapitan The attached test failures were seen while running run-webkit-tests on the mac-ews. Bot: ews103 Port: mac-elcapitan Platform: Mac OS X 10.11.6
Created attachment 318638 [details] Patch
Comment on attachment 318638 [details] Patch Attachment 318638 [details] did not pass mac-ews (mac): Output: http://webkit-queues.webkit.org/results/4354407 New failing tests: inspector/model/remote-object-mutated-iterators.html
Created attachment 318642 [details] Archive of layout-test-results from ews103 for mac-elcapitan The attached test failures were seen while running run-webkit-tests on the mac-ews. Bot: ews103 Port: mac-elcapitan Platform: Mac OS X 10.11.6
Comment on attachment 318638 [details] Patch Attachment 318638 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.webkit.org/results/4354480 New failing tests: inspector/model/remote-object-mutated-iterators.html
Created attachment 318644 [details] Archive of layout-test-results from ews106 for mac-elcapitan-wk2 The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews. Bot: ews106 Port: mac-elcapitan-wk2 Platform: Mac OS X 10.11.6
Comment on attachment 318638 [details] Patch Attachment 318638 [details] did not pass mac-debug-ews (mac): Output: http://webkit-queues.webkit.org/results/4354489 New failing tests: inspector/model/remote-object-mutated-iterators.html
Created attachment 318646 [details] Archive of layout-test-results from ews116 for mac-elcapitan The attached test failures were seen while running run-webkit-tests on the mac-debug-ews. Bot: ews116 Port: mac-elcapitan Platform: Mac OS X 10.11.6
Created attachment 318737 [details] Patch
Comment on attachment 318737 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318737&action=review LGTM, but r- because I think I found a few real bugs. Also other comments to follow. > Source/JavaScriptCore/builtins/MapIteratorPrototype.js:44 > + return { done, value }; I think this is wrong, for example: ``` let x = new Map; let i = x[Symbol.iterator](); let o = i.next(); Object.hasOwnProperty(o, "value") // false ``` Let's add a test for this and for the Set version below. > Source/JavaScriptCore/builtins/MapPrototype.js:29 > +{ "use strict"? > Source/JavaScriptCore/builtins/MapPrototype.js:50 > + if (!@isMap(this)) Does this work even when subclassing Map? > Source/JavaScriptCore/builtins/SetPrototype.js:29 > +{ "use strict"? > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1059 > + forNode(node).setType(m_graph, SpecCell); Maybe it's worth giving the exact structure here since it's constant? > Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:2903 > + if (argumentCountIncludingThis != 2) > + return false; Why isn't this an assert? Don't we only call this from our builtins? > Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:762 > + setPrediction(SpecCell); Why not SpecCellOther here? > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10190 > + m_jit.loadPtr(MacroAssembler::Address(mapGPR, HashMapImpl<HashMapBucket<HashMapBucketDataKey>>::offsetOfHead()), bucketGPR); I think it's worth a static_assert that JSSet::offsetOfHead() == JSMap::offsetOfHead() == your offset here. > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10202 > + m_jit.loadPtr(MacroAssembler::Address(bucketGPR, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfNext()), resultGPR); ditto about static assert > Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.h:120 > + macro(HashMapImpl_head, HashMapImpl<HashMapBucket<HashMapBucketDataKey>>::offsetOfHead()) \ > macro(HashMapBucket_value, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfValue()) \ > macro(HashMapBucket_key, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfKey()) \ > + macro(HashMapBucket_next, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfNext()) \ > + macro(HashMapBucket_deleted, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfDeleted()) \ Please add static_asserts that these are the same for JSSet and JSMap and their respective buckets > Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8285 > + if (m_node->bucketOwnerUseKind() == MapObjectUse) > + noBucketResult = m_out.anchor(weakPointer(vm().sentinelMapBucket.get())); > + else > + noBucketResult = m_out.anchor(weakPointer(vm().sentinelSetBucket.get())); This is wrong, you need to branch to something that sets the noBucketResult here. It'd be good if you add a test that catches this bug. > Source/JavaScriptCore/runtime/JSGlobalObject.cpp:772 > + createMapIteratorPrivateFunction->putDirect(vm, vm.propertyNames->prototype, mapIteratorPrototype); I think this can be putDirectWithoutTransition. > Source/JavaScriptCore/runtime/JSGlobalObject.cpp:775 > + createSetIteratorPrivateFunction->putDirect(vm, vm.propertyNames->prototype, setIteratorPrototype); ditto > Source/JavaScriptCore/runtime/JSMapIterator.cpp:34 > +const ClassInfo JSMapIterator::s_info = { "Map Iterator", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSMapIterator) }; why nullptr instead of JSCell::info? > Source/JavaScriptCore/runtime/JSSetIterator.cpp:34 > +const ClassInfo JSSetIterator::s_info = { "Set Iterator", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSSetIterator) }; ditto > Source/JavaScriptCore/runtime/JSSetIterator.h:34 > +// Now, it is only used for serialization. what do you mean here?
Created attachment 318864 [details] Patch
Comment on attachment 318737 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318737&action=review Thanks, I've uploaded the revised one. >> Source/JavaScriptCore/builtins/MapIteratorPrototype.js:44 >> + return { done, value }; > > I think this is wrong, for example: > ``` > let x = new Map; > let i = x[Symbol.iterator](); > let o = i.next(); > Object.hasOwnProperty(o, "value") // false > ``` > Let's add a test for this and for the Set version below. I think this is correct. Even if done is true, we set value which value is undefined. I think we need to use hasOwnProperty in the form of, o.hasOwnProperty("value"); // true I added the test to ensure this :) >> Source/JavaScriptCore/builtins/MapPrototype.js:29 >> +{ > > "use strict"? Oops, fixed. >> Source/JavaScriptCore/builtins/MapPrototype.js:50 >> + if (!@isMap(this)) > > Does this work even when subclassing Map? Yeah, it handles this well. (isMap checks JSType). >> Source/JavaScriptCore/builtins/SetPrototype.js:29 >> +{ > > "use strict"? Fixed. I also add "use strict" to array iterator constructor. >> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1059 >> + forNode(node).setType(m_graph, SpecCell); > > Maybe it's worth giving the exact structure here since it's constant? OK, fixed. >> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:2903 >> + return false; > > Why isn't this an assert? Don't we only call this from our builtins? Yeah, this should be assertion. Fixed. >> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:762 >> + setPrediction(SpecCell); > > Why not SpecCellOther here? Previously, we returned Empty value if we do not find the bucket for the key (GetMapBucket). But this patch changes this: instead GetMapBucket returns sentinel bucket held in VM. So now, it always returns the cells. It simplify the handling of buckets. (For example, we can drop special bucket value handling in FTL). >> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10190 >> + m_jit.loadPtr(MacroAssembler::Address(mapGPR, HashMapImpl<HashMapBucket<HashMapBucketDataKey>>::offsetOfHead()), bucketGPR); > > I think it's worth a static_assert that JSSet::offsetOfHead() == JSMap::offsetOfHead() == your offset here. Unfortunately, we cannot do static_assert here since offsetOfHead()'s OBJECT_OFFSETOF cannot be constexpr. (since it uses reinterpret_cast). C and C++ offers `offsetof`. But it is only available for standard layout class, and JSMap, and JSSet are not. Instead, I added usual ASSERT here. >> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10202 >> + m_jit.loadPtr(MacroAssembler::Address(bucketGPR, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfNext()), resultGPR); > > ditto about static assert Add ASSERT() here because of the same reason as above. >> Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.h:120 >> + macro(HashMapBucket_deleted, HashMapBucket<HashMapBucketDataKeyValue>::offsetOfDeleted()) \ > > Please add static_asserts that these are the same for JSSet and JSMap and their respective buckets I added ASSERT instead. >> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8285 >> + noBucketResult = m_out.anchor(weakPointer(vm().sentinelSetBucket.get())); > > This is wrong, you need to branch to something that sets the noBucketResult here. > It'd be good if you add a test that catches this bug. Fixed. >> Source/JavaScriptCore/runtime/JSGlobalObject.cpp:772 >> + createMapIteratorPrivateFunction->putDirect(vm, vm.propertyNames->prototype, mapIteratorPrototype); > > I think this can be putDirectWithoutTransition. Ah, no. Currently, these global private functions are created with the same Function structure. (So, they have the same structure). Using putDirectWithoutTransition breaks the shared one. >> Source/JavaScriptCore/runtime/JSGlobalObject.cpp:775 >> + createSetIteratorPrivateFunction->putDirect(vm, vm.propertyNames->prototype, setIteratorPrototype); > > ditto Ditto. >> Source/JavaScriptCore/runtime/JSMapIterator.cpp:34 >> +const ClassInfo JSMapIterator::s_info = { "Map Iterator", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSMapIterator) }; > > why nullptr instead of JSCell::info? Becasue JSCell does not have s_info. When inheriting JSCell, we set this field "nullptr". (e.g. FunctionRareData) >> Source/JavaScriptCore/runtime/JSSetIterator.cpp:34 >> +const ClassInfo JSSetIterator::s_info = { "Set Iterator", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSSetIterator) }; > > ditto Becasue JSCell does not have s_info. When inheriting JSCell, we set this field "nullptr". (e.g. FunctionRareData) >> Source/JavaScriptCore/runtime/JSSetIterator.h:34 >> +// Now, it is only used for serialization. > > what do you mean here? JSSetIterator / JSMapIterator are not used as user-observable JS's map iterator. They are just used for serialization in WebCore (structured cloning).
Created attachment 318866 [details] Patch
Created attachment 318871 [details] Patch
Comment on attachment 318737 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318737&action=review >>> Source/JavaScriptCore/builtins/MapIteratorPrototype.js:44 >>> + return { done, value }; >> >> I think this is wrong, for example: >> ``` >> let x = new Map; >> let i = x[Symbol.iterator](); >> let o = i.next(); >> Object.hasOwnProperty(o, "value") // false >> ``` >> Let's add a test for this and for the Set version below. > > I think this is correct. Even if done is true, we set value which value is undefined. > I think we need to use hasOwnProperty in the form of, > > o.hasOwnProperty("value"); // true > > I added the test to ensure this :) I see. So maybe our old implementation got this wrong? >>> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:762 >>> + setPrediction(SpecCell); >> >> Why not SpecCellOther here? > > Previously, we returned Empty value if we do not find the bucket for the key (GetMapBucket). > But this patch changes this: instead GetMapBucket returns sentinel bucket held in VM. > So now, it always returns the cells. It simplify the handling of buckets. (For example, we can drop special bucket value handling in FTL). That's not what SpecCellOther is. SpecCell means you can be literally any cell: an object, a string, a symbol, etc. SpecCellOther has a comment that describes what it is: static const SpeculatedType SpecCellOther = 1ull << 24; // It's definitely a JSCell but not a subclass of JSObject and definitely not a JSString or a Symbol. FIXME: This shouldn't be part of heap-top or bytecode-top. https://bugs.webkit.org/show_bug.cgi?id=133078 Which is what we want here.
Comment on attachment 318737 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318737&action=review >>>> Source/JavaScriptCore/builtins/MapIteratorPrototype.js:44 >>>> + return { done, value }; >>> >>> I think this is wrong, for example: >>> ``` >>> let x = new Map; >>> let i = x[Symbol.iterator](); >>> let o = i.next(); >>> Object.hasOwnProperty(o, "value") // false >>> ``` >>> Let's add a test for this and for the Set version below. >> >> I think this is correct. Even if done is true, we set value which value is undefined. >> I think we need to use hasOwnProperty in the form of, >> >> o.hasOwnProperty("value"); // true >> >> I added the test to ensure this :) > > I see. So maybe our old implementation got this wrong? I think the old implementation also has "value" own property. So I think the behavior is not changed. >>>> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:762 >>>> + setPrediction(SpecCell); >>> >>> Why not SpecCellOther here? >> >> Previously, we returned Empty value if we do not find the bucket for the key (GetMapBucket). >> But this patch changes this: instead GetMapBucket returns sentinel bucket held in VM. >> So now, it always returns the cells. It simplify the handling of buckets. (For example, we can drop special bucket value handling in FTL). > > That's not what SpecCellOther is. > SpecCell means you can be literally any cell: an object, a string, a symbol, etc. > > SpecCellOther has a comment that describes what it is: > static const SpeculatedType SpecCellOther = 1ull << 24; // It's definitely a JSCell but not a subclass of JSObject and definitely not a JSString or a Symbol. FIXME: This shouldn't be part of heap-top or bytecode-top. https://bugs.webkit.org/show_bug.cgi?id=133078 > Which is what we want here. Ah, oops! I'm confused with SpecCell | SpecMisc. Now, the patch uses set(.., targetStructure). And its type should be SpecCellOther.
Comment on attachment 318871 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318871&action=review r=me > Source/JavaScriptCore/builtins/MapPrototype.js:83 > + if (bucket == @sentinelMapBucket) let's use === instead of == > Source/JavaScriptCore/builtins/SetPrototype.js:73 > + if (bucket == @sentinelSetBucket) Let's use === instead of ==. Also, do all of our tiers properly handle comparing cells to each other that aren't strings/symbols? > Source/JavaScriptCore/dfg/DFGClobberize.h:152 > + case CompareEqPtr: Nice catch! > Source/JavaScriptCore/dfg/DFGNode.h:2541 > + return m_opInfo.as<UseKind>(); Style nit: This feels like a weird override of UseKind, and I think it's a little confusing to see it used in this context. Why not just create your own separate enum for this purpose?
Comment on attachment 318871 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318871&action=review > Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:762 > + setPrediction(SpecCell); SpecCellOther for reasons stated in previous comment
Comment on attachment 318871 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=318871&action=review Thank you for your review! >> Source/JavaScriptCore/builtins/MapPrototype.js:83 >> + if (bucket == @sentinelMapBucket) > > let's use === instead of == Oops, nice. Fixed. >> Source/JavaScriptCore/builtins/SetPrototype.js:73 >> + if (bucket == @sentinelSetBucket) > > Let's use === instead of ==. > Also, do all of our tiers properly handle comparing cells to each other that aren't strings/symbols? Fixed. And, nice. We should have SpecCellOther fixup for CompareStrictEq. I'll open the bug for that. >> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:762 >> + setPrediction(SpecCell); > > SpecCellOther for reasons stated in previous comment Nice catch! Fixed.
Created attachment 318897 [details] Patch Patch for landing
Committed r221110: <http://trac.webkit.org/changeset/221110>
<rdar://problem/34045565>
Committed r221113: <http://trac.webkit.org/changeset/221113>