1976826 - Replace use of EncodedSize with bitmap in buffer allocator

Status: RESOLVED FIXED

(Core :: JavaScript: GC, task, P1)

Description

[Jon Coppeard (:jonco)]

EncodedSize was added to represent a buffer size in a more compact way so we didn't have to use more than one byte per possible allocation start in a chunk. However I saw memset showing up in some benchmarks from clearing the size array when allocating small buffers in chunks with the changes in bug 1973033.

I realized that, clever though EncodedSize was, it's more efficient to store a bitmap of the end position of allocations. This is slightly less efficient when looking up the size but that happens rarely outside of sweeping. This has another advantage too as it means we can support allocations that are any multiple of the granularity so it's less restrictive that using EncodedSize.

Replacing the encoding size with a bitmap reduces the size of BufferChunk header by 192 bytes, nearly halving its size.

This change also opens the door to future sweeping optimisations where we can find free regions by using bitmap operations instead of iterating through every allocation.

Comment 1

[Jon Coppeard (:jonco)]

Attachment: Bug 1976826 - Part 1: Add an iterator for mozilla::BitSet r?sfink

Refactor AllocIter into a more general purpose BitSetIter which we can use for
our other bitmaps.

Comment 2

[Jon Coppeard (:jonco)]

Attachment: Bug 1976826 - Part 2: Factor out a class to convert from a bitmap iterator to an iterator over pointers into a block of memory r?sfink

We have a bunch of these bitmaps were each bit set corresponds to a location in
memory. This adds a template class to make an iterator over these locations out
of a bitmap iterator.

Comment 3

[Jon Coppeard (:jonco)]

Attachment: Bug 1976826 - Part 3: Remove encoded sizes and replace with an allocation end bitmap r?sfink

The new bitmap has a bit set corresponding the the byte after the end of each
allocation, except if it abuts the end of the chunk.

Comment 4

[Jon Coppeard (:jonco)]

Attachment: Bug 1976826 - Part 4: Pass old size to realloc methods r?sfink

Reading the current allocation size is now a race for allocations in chunks
that are currently being swept, and this affects realloc operations which need
to know how much data to copy even if the chunk is being swept. One option is
to make allocEndBitmap atomic, but it's simpler to pass the current allocation
size in since it's always known.

Comment 5

[Jon Coppeard (:jonco)]

Attachment: Bug 1976826 - Part 5: Don't allow getAllocSize during sweeping r?sfink

This can also now race with sweeping so don't allow it. We only use this for
debugging support so this doesn't have too much impact.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/8b32923552c9
https://hg.mozilla.org/integration/autoland/rev/74c430ab20d9
Part 1: Add an iterator for mozilla::BitSet r=sfink
https://github.com/mozilla-firefox/firefox/commit/376286385acf
https://hg.mozilla.org/integration/autoland/rev/1bd14903e3b1
Part 2: Factor out a class to convert from a bitmap iterator to an iterator over pointers into a block of memory r=sfink
https://github.com/mozilla-firefox/firefox/commit/ef0094e92ef3
https://hg.mozilla.org/integration/autoland/rev/8b2d0fbfb68b
Part 3: Remove encoded sizes and replace with an allocation end bitmap r=sfink
https://github.com/mozilla-firefox/firefox/commit/f962a9989415
https://hg.mozilla.org/integration/autoland/rev/cc1513d9c3aa
Part 4: Pass old size to realloc methods r=sfink
https://github.com/mozilla-firefox/firefox/commit/1d424ecf7f2c
https://hg.mozilla.org/integration/autoland/rev/44ec9d7f58f3
Part 5: Don't allow getAllocSize during sweeping r=sfink

Comment 7

[pstanciu]

https://hg.mozilla.org/mozilla-central/rev/74c430ab20d9
https://hg.mozilla.org/mozilla-central/rev/1bd14903e3b1
https://hg.mozilla.org/mozilla-central/rev/8b2d0fbfb68b
https://hg.mozilla.org/mozilla-central/rev/cc1513d9c3aa
https://hg.mozilla.org/mozilla-central/rev/44ec9d7f58f3