Bug 174355 – [JSC] Optimize Map iteration with intrinsic

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

Let's implement super fast Map iteration by accessing HashMapBucket directly.

[Yusuke Suzuki]

Created attachment 317861 [details]
Patch

[Yusuke Suzuki]

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

[Keith Miller]

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.

[Yusuke Suzuki]

(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.

[Yusuke Suzuki]

After considering, I think it is still useful if the user invokes next() function / the user uses Map.prototype.forEach.

[Yusuke Suzuki]

Created attachment 318603 [details]
Patch

[Build Bot]

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

[Yusuke Suzuki]

Created attachment 318631 [details]
Patch

[Build Bot]

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.

[Build Bot]

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

[Build Bot]

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

[Build Bot]

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

[Yusuke Suzuki]

Created attachment 318638 [details]
Patch

[Build Bot]

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

[Build Bot]

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

[Build Bot]

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

[Build Bot]

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

[Build Bot]

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

[Build Bot]

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

[Yusuke Suzuki]

Created attachment 318737 [details]
Patch

[Saam Barati]

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?

[Yusuke Suzuki]

Created attachment 318864 [details]
Patch

[Yusuke Suzuki]

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).

[Yusuke Suzuki]

Created attachment 318866 [details]
Patch

[Yusuke Suzuki]

Created attachment 318871 [details]
Patch

[Saam Barati]

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.

[Yusuke Suzuki]

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.

[Saam Barati]

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?

[Saam Barati]

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

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

Created attachment 318897 [details]
Patch

Patch for landing

[Yusuke Suzuki]

Committed r221110: <http://trac.webkit.org/changeset/221110>

[Radar WebKit Bug Importer]

<rdar://problem/34045565>

[Yusuke Suzuki]

Committed r221113: <http://trac.webkit.org/changeset/221113>