1690274 - Investigate non-removable BloomFilter for property duplication detection

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P3)

Description

[Tooru Fujisawa [:arai]]

bug 1688534 patch tried to use mozilla::BloomFilter for detecting duplicate property while building object literal,
but given the current in-tree mozilla::BloomFilter impl supports "remove" operation, and thus it uses uint8_t for each slot, and that results in large storage than expected.

we could add non-removable variant of bloom filter that uses 1 bit for each slot, and use it there.

Comment 1

[Tooru Fujisawa [:arai]]

There's no BloomFilter::remove consumer in tree.
so we should be able to replace it with (or at least add) single bit bloom filter

Comment 2

[Tooru Fujisawa [:arai]]

with current HashSet impl, here's the heap allocated data size for each number of properties:

number of properties	heap allocated data
0	0 bytes
1	256 bytes
25	512 bytes
49	1024 bytes
97	2048 bytes
193	4096 bytes

(note, when 25 properties are allocated, 256 bytes are allocated, and then freed, and then 512 bytes are allocated)

then, according to bug 1688534 comment #10, bloom-filter with KeySize = 12 should be sufficient to cover most case,
and if we use single-bit bloom-filter, it requires 1 << (12 - 3) = 512 bytes,
and also it's allocated on stack.
so this should be beneficial.

Comment 3

[Tooru Fujisawa [:arai]]

tried using bloom-filter with KeySize = 12, and there's one false positive in self-hosted JS
https://searchfox.org/mozilla-central/source/js/src/builtin/intl/SanctionedSimpleUnitIdentifiersGenerated.js#21

maybe we can have dedicate mode for self-hosted JS (and maybe chrome-priv code?) that
checks duplication only on debug-build.

Comment 4

[Tooru Fujisawa [:arai]]

Attachment: Bug 1690274 - Part 1: Rename mozilla::BloomFilter to mozilla::CountingBloomFilter.

Comment 5

[Tooru Fujisawa [:arai]]

Attachment: Bug 1690274 - Part 2: Add mozilla::BitBloomFilter.

Depends on D104689

Comment 6

[Tooru Fujisawa [:arai]]

Attachment: Bug 1690274 - Part 3: Use mozilla::BitBloomFilter instead of mozilla::CountingBloomFilter.

Depends on D104690

Comment 7

[Tooru Fujisawa [:arai]]

Attachment: Bug 1690274 - Part 4: Use mozilla::BitBloomFilter in ObjLiteralWriter.

Depends on D104691

Comment 8

[Tooru Fujisawa [:arai]]

Attachment: Bug 1690274 - Part 5: Do not check duplicate properties in self-hosted JS on non-debug build.

Depends on D104692

Comment 9

[Tooru Fujisawa [:arai]]

To get the consistent result, we could fallback to HashSet if possible duplication is detected.

If possible duplication is detected during emitting object literal, we can set a flag to the ObjLiteralWriter,
and when finishing, if the flag is set, we can enumerate property keys by reading the generated code,
and check again with HashMap, and use that result in the ObjLiteralStencil,
so that false-positive doesn't happen in the generated stencil.

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/9cb6b53bd14d
Part 1: Rename mozilla::BloomFilter to mozilla::CountingBloomFilter. r=sg
https://hg.mozilla.org/integration/autoland/rev/dd047f91142e
Part 2: Add mozilla::BitBloomFilter. r=sg
https://hg.mozilla.org/integration/autoland/rev/07c5c0c0c198
Part 3: Use mozilla::BitBloomFilter instead of mozilla::CountingBloomFilter. r=sg
https://hg.mozilla.org/integration/autoland/rev/39f7ea721104
Part 4: Use mozilla::BitBloomFilter in ObjLiteralWriter. r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/4652ece1e892
Part 5: Do not check duplicate properties in self-hosted JS on non-debug build. r=mgaudet

Comment 11

[Noemi Erli[:noemi_erli]]

https://hg.mozilla.org/mozilla-central/rev/9cb6b53bd14d
https://hg.mozilla.org/mozilla-central/rev/dd047f91142e
https://hg.mozilla.org/mozilla-central/rev/07c5c0c0c198
https://hg.mozilla.org/mozilla-central/rev/39f7ea721104
https://hg.mozilla.org/mozilla-central/rev/4652ece1e892