1809662 - Re-implement new Set methods

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, enhancement, P2)

Description

[André Bargull [:anba]]

The original implementation from bug 1566146 no longer matches the current spec proposal.

Comment 1

[André Bargull [:anba]]

Attachment: Bug 1809662 - Part 3: Expose Set.prototype.delete and Set.prototype.size to self-hosted code. r=#spidermonkey-reviewers!

Comment 2

[André Bargull [:anba]]

Attachment: Bug 1809662 - Part 2: Remove old implementation of new Set methods. r=#spidermonkey-reviewers!

Depends on D166558

Comment 3

[André Bargull [:anba]]

Attachment: Bug 1809662 - Part 4: Implement new Set methods. r=#spidermonkey-reviewers!

Depends on D166559

Comment 4

[André Bargull [:anba]]

Attachment: Bug 1809662 - Part 5: Add tests for new Set methods. r=#spidermonkey-reviewers!

Depends on D166560

Comment 5

[André Bargull [:anba]]

Note: The patches need to be updated for https://github.com/tc39/proposal-set-methods/issues/81 and https://github.com/tc39/proposal-set-methods/issues/84, therefore they're still marked as WIP.

Comment 6

[Dan Minor [:dminor]]

Hi Anba, do you have any concerns about: https://github.com/tc39/proposal-set-methods/issues/91?

Comment 7

[André Bargull [:anba]]

The current spec text assumes an implementation which is similar to our current implementation. (The spec actually even links to https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables, which is the design document of our current implementation, see also bug 743107 when OrderedHashTable was added.) So it's not difficult for us to implement the current spec, all that was needed was a way to compare pointers to the internal data structures of the OrderedHashTable: https://phabricator.services.mozilla.com/D166560 adds UnsafeRef which is then used in the new SetObject::toSorted method.

The hash table implementation in JSC uses a linked list + hash table approach where the individual hash buckets are kept in a doubly linked list. Additionally, the hash buckets are GC allocated. This approach has some nice properties, for example when deleting an entry, the bucket is simply removed from the linked list. The GC will eventually clean up the bucket's memory and live iterators only need to skip over deleted entries. Live iterators don't need to be updated in any way. This is far nicer from our current implementation, where we need to keep track of all live iterators. [1]

So when only considering SpiderMonkey, I don't think we have any concerns about the current spec. But when taking the overall language design into account, the proposed spec may force implementers to choose a specific hash table design. And this could be seen as problematic, because it could make it more difficult or even impossible to use different designs in the future.

---

[1] It's not strictly needed to keep track of all live iterators, for example V8 uses a different approach, even though their overall ordered hash table approach (more or less) matches our implementation.

Comment 8

[Dan Minor [:dminor]]

Thanks for the additional context, that's really helpful :)

Comment 9

[André Bargull [:anba]]

Attachment: Bug 1809662 - Part 1: Enable new Set methods by default on Nightly. r=#spidermonkey-reviewers!

The proposal is now on stage 3, so it can be enabled by default on Nightly.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/3e702cfb426f
Part 1: Enable new Set methods by default on Nightly. r=dminor
https://hg.mozilla.org/integration/autoland/rev/10edaa5fbf14
Part 2: Remove old implementation of new Set methods. r=dminor
https://hg.mozilla.org/integration/autoland/rev/9272df0c5120
Part 3: Expose Set.prototype.delete and Set.prototype.size to self-hosted code. r=dminor
https://hg.mozilla.org/integration/autoland/rev/71abf3f7e529
Part 4: Implement new Set methods. r=dminor
https://hg.mozilla.org/integration/autoland/rev/4db1e159eecf
Part 5: Add tests for new Set methods. r=dminor

Comment 12

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/3e702cfb426f
https://hg.mozilla.org/mozilla-central/rev/10edaa5fbf14
https://hg.mozilla.org/mozilla-central/rev/9272df0c5120
https://hg.mozilla.org/mozilla-central/rev/71abf3f7e529
https://hg.mozilla.org/mozilla-central/rev/4db1e159eecf