1288541 - Self-host and inline SetIterator.prototype.next

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P3)

Description

[André Bargull [:anba]]

Basically just bug 1129313 and bug 1248289 for SetIterator.prototype.next.

micro-benchmark:
---
function f() {
    var s = new Set(Array.from({length:10}, (k, i) => i));
    var d = Date.now();
    // for (var i = 0; i < 100000; ++i) s.forEach(() => {});
    for (var i = 0; i < 100000; ++i) for (var k of s);
    return Date.now() - d;
}

// warm-up
for (var i = 0; i < 10; ++i) d += f();

var d = 0;
for (var i = 0; i < 15; ++i) d += f();
print(d / 15);
---

Before:
- forEach: 620 ms
- for-of: 610 ms

After:
- forEach: 56 ms
- for-of: 40 ms

Comment 1

[André Bargull [:anba]]

Attachment: Self-host SetIterator.prototype.next

Comment 2

[André Bargull [:anba]]

Attachment: Inline _GetNextSetEntryForIterator

I have no idea if this is the correct approach (from the JIT point of view and from the general C++ language point of view - e.g. should I use template specialization in jit/CodeGenerator.cpp or is there a better alternative?). Therefore asking for your feedback because you've written the patch for bug 1248289. Thank you! :-)

Comment 3

[Tooru Fujisawa [:arai]]

Comment on attachment 8773482 [details] [diff] [review]
Inline _GetNextSetEntryForIterator

Review of attachment 8773482 [details] [diff] [review]:
-----------------------------------------------------------------

This is excellent :D

I don't see any issue in template etc in the code.

::: js/src/jit/CodeGenerator.cpp
@@ +6342,5 @@
> +{
> +    size_t dataElementOffset = ValueSet::offsetOfImplDataElement();
> +    size_t elementsOffset = NativeObject::offsetOfFixedElements();
> +
> +    Address keyAddress(front, dataElementOffset + 0);

" + 0" could be removed.

Comment 4

[André Bargull [:anba]]

Attachment: Part 1 - Self-host SetIterator.prototype.next

Comment 5

[André Bargull [:anba]]

Attachment: Part 2 - Inline _GetNextSetEntryForIterator

Comment 6

[Tooru Fujisawa [:arai]]

Comment on attachment 8773896 [details] [diff] [review]
Part 2 -  Inline _GetNextSetEntryForIterator

Review of attachment 8773896 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you again :)

I overlooked several things before, can you please address the following comments?

::: js/src/jit/CodeGenerator.cpp
@@ +6234,5 @@
> +
> +template <class OrderedHashTable>
> +static void
> +RangePopFront(MacroAssembler& masm, Register range, Register front, Register dataLength,
> +              Register temp, size_t sizeOfData, size_t keyOffset)

it was pre-existing thing tho,
`sizeOfData` should always be OrderedHashTable::sizeofImplData(), and the value is used only for addPtr here (compared to RangeFront), so `sizeOfData` parameter can be removed.  And we can remove assertion on the OrderedHashTable::sizeofImplData() from RangePopFront below.

Can you rewrite it to pass OrderedHashTable::sizeofImplData() directly to addPtr while you're modifying this?

Also, `keyOffset` can also be moved to OrderedHashTable static function, like OrderedHashTable::offsetOfEntryKey() or something.

@@ +6249,5 @@
>      masm.branch32(Assembler::AboveOrEqual, i, dataLength, &done);
>  
> +    masm.addPtr(Imm32(sizeOfData), front);
> +
> +    Address elementAddress(front, OrderedHashTable::offsetOfImplDataElement() + keyOffset);

`front` points the element, not Data, so OrderedHashTable::offsetOfImplDataElement() should be removed here.

>         T& front() {
>             MOZ_ASSERT(valid());
>             MOZ_ASSERT(!empty());
>             return ht->data[i].element;
>         }

It would be nice to assert OrderedHashTable::offsetOfImplDataElement() is 0 in RangeFront.

@@ +6268,5 @@
> +void
> +RangePopFront<ValueMap>(MacroAssembler& masm, Register range, Register front, Register dataLength,
> +                        Register temp)
> +{
> +    MOZ_ASSERT(ValueMap::sizeofImplData() == 24);

this can be removed.

@@ +6278,5 @@
> +void
> +RangePopFront<ValueSet>(MacroAssembler& masm, Register range, Register front, Register dataLength,
> +                        Register temp)
> +{
> +    MOZ_ASSERT(ValueSet::sizeofImplData() == 16);

here too.

@@ +6307,5 @@
> +template <>
> +void
> +CodeGenerator::emitLoadIteratorValues<ValueMap>(Register result, Register temp, Register front)
> +{
> +    size_t dataElementOffset = ValueMap::offsetOfImplDataElement();

Please remove dataElementOffset here.

@@ +6310,5 @@
> +{
> +    size_t dataElementOffset = ValueMap::offsetOfImplDataElement();
> +    size_t elementsOffset = NativeObject::offsetOfFixedElements();
> +
> +    Address keyAddress(front, dataElementOffset + ValueMap::Entry::offsetOfKey());

and here.

@@ +6311,5 @@
> +    size_t dataElementOffset = ValueMap::offsetOfImplDataElement();
> +    size_t elementsOffset = NativeObject::offsetOfFixedElements();
> +
> +    Address keyAddress(front, dataElementOffset + ValueMap::Entry::offsetOfKey());
> +    Address valueAddress(front, dataElementOffset + ValueMap::Entry::offsetOfValue());

and here.

@@ +6339,5 @@
> +template <>
> +void
> +CodeGenerator::emitLoadIteratorValues<ValueSet>(Register result, Register temp, Register front)
> +{
> +    size_t dataElementOffset = ValueSet::offsetOfImplDataElement();

and here.

@@ +6342,5 @@
> +{
> +    size_t dataElementOffset = ValueSet::offsetOfImplDataElement();
> +    size_t elementsOffset = NativeObject::offsetOfFixedElements();
> +
> +    Address keyAddress(front, dataElementOffset);

it would be better replacing `dataElementOffset` with ValueSet::offsetOfEntryKey() or something.

Comment 7

[André Bargull [:anba]]

Attachment: Part 2 - Inline _GetNextSetEntryForIterator

Updated patch for part 2. Addressed the review comments and also replaced the MOZ_ASSERTs with static_assert where applicable. 


Btw, why is |ValueMap::sizeofImplData() == 24| on 32-bit machines? I still haven't figured this out yet. ValueMap::Entry is composed of HashableValue and HeapPtr<Value>, where sizeof(HashableValue) = 8 and sizeof(HeapPtr<Value>) = 8, that means sizeof(ValueMap::Entry) = 8 + 8 = 16. The Data struct for ValueMap::Impl contains the element (= ValueMap::Entry) and a Data* pointer. So, sizeof(ValueMap::Impl::Data) = sizeof(ValueMap::Entry) + sizeof(Data*) = 16 + 4 = 20, which contradicts |ValueMap::sizeofImplData() == 24|, doesn't it?

Comment 8

[Tooru Fujisawa [:arai]]

(In reply to André Bargull from comment #7)
> Btw, why is |ValueMap::sizeofImplData() == 24| on 32-bit machines? I still
> haven't figured this out yet. ValueMap::Entry is composed of HashableValue
> and HeapPtr<Value>, where sizeof(HashableValue) = 8 and
> sizeof(HeapPtr<Value>) = 8, that means sizeof(ValueMap::Entry) = 8 + 8 = 16.
> The Data struct for ValueMap::Impl contains the element (= ValueMap::Entry)
> and a Data* pointer. So, sizeof(ValueMap::Impl::Data) =
> sizeof(ValueMap::Entry) + sizeof(Data*) = 16 + 4 = 20, which contradicts
> |ValueMap::sizeofImplData() == 24|, doesn't it?

I thought, that's because JS::Value is aligned to 8 bytes, by JSVAL_ALIGNMENT.
but it has an effect only on some compiler...
https://dxr.mozilla.org/mozilla-central/rev/4c05938a64a7fde3ac2d7f4493aee1c5f2ad8a0a/js/public/Value.h#37

Comment 9

[Tooru Fujisawa [:arai]]

okay, thank you for pointing that out :)

> 07/26 06:36 <arai> Is JS::Value always aligned to 64-bit ?  it's related to
>                    bug 1288541
> ...
> 07/26 08:05 <Waldo> arai: it contains a uint64_t inside a union, so its
>                     alignment *should* be alignof(uint64_t); but there are
>                     platforms that align double to 4-byte boundaries, so
>                     that may not be a guarantee

so, we may need to add another code path for |ValueMap::sizeofImplData() == 20| case and
|ValueSet::sizeofImplData() == 12| case, depending on the size.
fortunately, we have to add it only to |RangeFront| function.

Comment 10

[Tooru Fujisawa [:arai]]

Comment on attachment 8774474 [details] [diff] [review]
Part 2 - Inline _GetNextSetEntryForIterator

Review of attachment 8774474 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you again :)

Can you address the following?  (sorry for loose review :P

::: js/src/jit/CodeGenerator.cpp
@@ +6209,5 @@
> +static void
> +RangeFront(MacroAssembler&, Register, Register, Register);
> +
> +template <>
> +void RangeFront<ValueMap>(MacroAssembler& masm, Register range, Register i, Register front)

can you put newline after "void"?

@@ +6222,5 @@
>      masm.addPtr(i, front);
>  }
>  
> +template <>
> +void RangeFront<ValueSet>(MacroAssembler& masm, Register range, Register i, Register front)

and here?

@@ +6251,5 @@
>      masm.branch32(Assembler::AboveOrEqual, i, dataLength, &done);
>  
> +    // We can add sizeof(Data) to |front| to select the next element, because
> +    // |front| and |range.ht.data[i]| point to the same location.
> +    static_assert(OrderedHashTable::offsetOfImplDataElement() == 0, "offsetof(Data, element) is 0");

Thank you for clarification :)

::: js/src/jit/MIR.h
@@ +8539,5 @@
> +
> +  private:
> +    Mode mode_;
> +
> +    explicit MGetNextEntryForIterator(MDefinition* iter, MDefinition* result, Mode mode)

Any reason to move constructor under "private:" ?
It was under "protected:".

Comment 11

[André Bargull [:anba]]

(In reply to Tooru Fujisawa [:arai] from comment #8)
> I thought, that's because JS::Value is aligned to 8 bytes, by
> JSVAL_ALIGNMENT.
> but it has an effect only on some compiler...
> https://dxr.mozilla.org/mozilla-central/rev/
> 4c05938a64a7fde3ac2d7f4493aee1c5f2ad8a0a/js/public/Value.h#37

Maybe we should simply replace JSVAL_ALIGNMENT with alignas(8), that way it shouldn't be necessary to add code paths for |ValueMap::sizeofImplData() == 20| and |ValueSet::sizeofImplData() == 12|. WDYT?

Comment 12

[Tooru Fujisawa [:arai]]

(In reply to André Bargull from comment #11)
> (In reply to Tooru Fujisawa [:arai] from comment #8)
> > I thought, that's because JS::Value is aligned to 8 bytes, by
> > JSVAL_ALIGNMENT.
> > but it has an effect only on some compiler...
> > https://dxr.mozilla.org/mozilla-central/rev/
> > 4c05938a64a7fde3ac2d7f4493aee1c5f2ad8a0a/js/public/Value.h#37
> 
> Maybe we should simply replace JSVAL_ALIGNMENT with alignas(8), that way it
> shouldn't be necessary to add code paths for |ValueMap::sizeofImplData() ==
> 20| and |ValueSet::sizeofImplData() == 12|. WDYT?

yeah, the document [1] says it's okay to use |alignas|, so it would solve this.
anyway, so I'd forwarding the question to Waldo :)

[1] https://developer.mozilla.org/en-US/docs/Using_CXX_in_Mozilla_code

Comment 13

[André Bargull [:anba]]

Attachment: Part 2 - Inline _GetNextSetEntryForIterator

Fixed style nit in RangeFront.

Comment 14

[André Bargull [:anba]]

(In reply to Tooru Fujisawa [:arai] from comment #10)
> ::: js/src/jit/MIR.h
> @@ +8539,5 @@
> > +
> > +  private:
> > +    Mode mode_;
> > +
> > +    explicit MGetNextEntryForIterator(MDefinition* iter, MDefinition* result, Mode mode)
> 
> Any reason to move constructor under "private:" ?
> It was under "protected:".

I've changed it to `private` because that seems to be default visibility for most MIR-classes. Was there any reason it needs to be `protected`?

Comment 15

[Tooru Fujisawa [:arai]]

(In reply to André Bargull from comment #14)
> I've changed it to `private` because that seems to be default visibility for
> most MIR-classes. Was there any reason it needs to be `protected`?

Thanks :)
looks like I chose wrong one to copy from when creating the MIR,
so changing it to `private` makes sense.

Comment 16

[Till Schneidereit [:till]]

Comment on attachment 8773895 [details] [diff] [review]
Part 1 -  Self-host SetIterator.prototype.next

Review of attachment 8773895 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice, thank you!

I added some comments below, but except for the step comments in Set.js, they're all optional.

::: js/src/builtin/MapObject.cpp
@@ +928,4 @@
>  }
>  
>  bool
> +SetIteratorObject::next(JSContext* cx, Handle<SetIteratorObject*> setIterator,

I know this is copied from MatIteratorObject, but it's as confusing here as it is there to have a bool function that takes a JSContext* as its first parameter but where the bool doesn't indicate whether an exception was thrown. I think the usual way to get around this is moving the cx parameter to the back of the list. r=me on doing that here and for Map, but up to you.

::: js/src/builtin/Set.js
@@ +40,5 @@
>  }
>  _SetCanonicalName(SetSpecies, "get [Symbol.species]");
> +
> +
> +var setIteratorTemp = { setIterationResult : null };

I think we can do something slightly nicer here. Instead of having setIteratorTemp an setIterationResult, we can have a sentinel value `var setIterationDoneSentinel = {}` that we pass in to _GetNextSetEntryForIterator. If that same value is returned, the iteration is done.

@@ +42,5 @@
> +
> +
> +var setIteratorTemp = { setIterationResult : null };
> +
> +function SetIteratorNext() {

This needs comments for the steps.

@@ +56,5 @@
> +
> +    var retVal = {value: undefined, done: true};
> +
> +    var done = _GetNextSetEntryForIterator(O, setIterationResult);
> +    if (!done) {

So this would become
var nextEntry = _GetNextSetEntryForIterator(O, setIterationDoneSentinel);
if (nextEntry !== setIterationDoneSentinel) {

@@ +64,5 @@
> +        if (itemKind === ITEM_KIND_VALUE) {
> +            result = setIterationResult[0];
> +        } else {
> +            assert(itemKind === ITEM_KIND_KEY_AND_VALUE, itemKind);
> +            result = [setIterationResult[0], setIterationResult[0]];

This and the above usage would just use `nextEntry`.

@@ +67,5 @@
> +            assert(itemKind === ITEM_KIND_KEY_AND_VALUE, itemKind);
> +            result = [setIterationResult[0], setIterationResult[0]];
> +        }
> +
> +        setIterationResult[0] = null;

And this could go away.

Comment 17

[André Bargull [:anba]]

Attachment: Part 1 - Self-host SetIterator.prototype.next

Updated part 1 per review comments, carrying r+ from till.

Updates:
- Add missing step comments
- Move context argument to last position in infallible next() methods

I've also tried the other suggestion using a sentinel value, but I didn't manage to write the inlining part for that approach. :-(

Comment 18

[André Bargull [:anba]]

Attachment: Part 2 - Inline _GetNextSetEntryForIterator

Reuploading part 2 after resolving a merge conflict when applying the review changes for part 1. Otherwise no change in behaviour compared to the previous version.

Comment 19

[Jeff Walden [:Waldo]]

(In reply to Tooru Fujisawa [:arai] from comment #12)
> > Maybe we should simply replace JSVAL_ALIGNMENT with alignas(8), that way it
> > shouldn't be necessary to add code paths for |ValueMap::sizeofImplData() ==
> > 20| and |ValueSet::sizeofImplData() == 12|. WDYT?
> 
> yeah, the document [1] says it's okay to use |alignas|, so it would solve
> this.
> anyway, so I'd forwarding the question to Waldo :)

Yeah, I think we want compilers doing this, makes sense.

Comment 20

[Tooru Fujisawa [:arai]]

now JS::Value has alignas(8), and we don't need a branch for each sizeofImplData value.

anba, can you please rebase patches and ask review again?

Comment 21

[André Bargull [:anba]]

Attachment: Part 1 - Self-host SetIterator.prototype.next

Updated part 1 to apply cleanly on inbound, carrying r+ from Till.

Comment 22

[André Bargull [:anba]]

Attachment: Part 2 - Inline _GetNextSetEntryForIterator

Updated part 2 to apply cleanly on inbound, re-requesting review per comment 20.

Comment 23

[Tooru Fujisawa [:arai]]

Comment on attachment 8802591 [details] [diff] [review]
Part 2 - Inline _GetNextSetEntryForIterator

Review of attachment 8802591 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you :D

Comment 24

[André Bargull [:anba]]

Attachment: Part 1 - Self-host SetIterator.prototype.next

Updated part 1 again to apply cleanly on inbound, carrying r+ from Till.

Comment 25

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/d6f70d015857
Part 1: Self-host SetIterator.prototype.next(). r=till
https://hg.mozilla.org/integration/mozilla-inbound/rev/150a4de2c5d9
Part 2: Inline _GetNextSetEntryForIterator intrinsic. r=arai

Comment 26

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/d6f70d015857
https://hg.mozilla.org/mozilla-central/rev/150a4de2c5d9