1920433 - Improve InlineTable data structure

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P1)

Description

[Jan de Mooij [:jandem]]

I'm using InlineMap for bug 1920430, but I noticed it has a number of issues:

• Removed inline entries are set to a tombstone value, but are never reused. This means we can expand to a full HashMap/HashSet before using all inline entries.
• Support was added for customizing tombstone values through KeyPolicy, but this is incomplete. There are still multiple places where we rely on key values being 'truthy'.
• Tombstone values add some complexity - see the separate inlCount_ vs inlNext_ fields.

It's simpler to implement removal by swapping the last item in the array with the removed item.

Also, the class contains both an array of inline entries and a HashMap/HashSet. We can save space by using a Variant.

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1920433 part 1 - Remove dead code from InlineTable.h. r?arai!

Also use private instead of protected in a few places.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Bug 1920433 part 2 - Don't use tombstones for removed inline entries in InlineTable. r?arai!

InlineTable supports customizing tombstone values through KeyPolicy, but this was
incomplete. Some places still relied on valid keys being 'truthy'.

Also, removed inline entries were never reused. This means we could expand to a
HashMap/HashSet before using all inline entries.

This patch implements removal by swapping the removed item with the last item.
This also lets us merge the inlNext_ and inlCount_ fields.

A later patch will add mutationCount assertions to ensure we don't remove items
from the table while iterating.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1920433 part 3 - Use Variant for InlineTable array/table. r?arai!

This is more memory efficient and also means we don't initialize the
HashMap/HashSet if it's not used.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1920433 part 4 - Rename InlineArray::inlCount to InlineArray::count. r?arai!

Also use uint32_t instead of size_t to save some space. This will never be a
large value.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1920433 part 5 - Add assertions to check for mutations. r?arai!

Add assertions to check no entries are added/removed while using Ptr/AddPtr or Range.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Bug 1920433 part 6 - Use reserve() in InlineTable::switchToTable. r?arai!

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/7933f2426217
part 1 - Remove dead code from InlineTable.h. r=arai
https://hg.mozilla.org/integration/autoland/rev/67349f52462c
part 2 - Don't use tombstones for removed inline entries in InlineTable. r=arai
https://hg.mozilla.org/integration/autoland/rev/e41d64b380a3
part 3 - Use Variant for InlineTable array/table. r=arai
https://hg.mozilla.org/integration/autoland/rev/a04d374230a3
part 4 - Rename InlineArray::inlCount to InlineArray::count. r=arai
https://hg.mozilla.org/integration/autoland/rev/2390753f710e
part 5 - Add assertions to check for mutations. r=arai
https://hg.mozilla.org/integration/autoland/rev/e88470b69a09
part 6 - Use reserve() in InlineTable::switchToTable. r=arai

Comment 8

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/7933f2426217
https://hg.mozilla.org/mozilla-central/rev/67349f52462c
https://hg.mozilla.org/mozilla-central/rev/e41d64b380a3
https://hg.mozilla.org/mozilla-central/rev/a04d374230a3
https://hg.mozilla.org/mozilla-central/rev/2390753f710e
https://hg.mozilla.org/mozilla-central/rev/e88470b69a09