1980047 - Convert to free-list allocation within runs

Status: ASSIGNED

(Core :: Memory Allocator, task)

Description

[Paul Bone [:pbone]]

Mozjemalloc uses bitmap scanning allocation to find a free region within a run. Convert this to a free list so that multiple thread local free lists can be co-located in the same memory.

Comment 1

[Paul Bone [:pbone]]

Attachment: Bug 1980047 - pt 1. Refactor region allocation r=glandium

Comment 2

[Paul Bone [:pbone]]

Attachment: Bug 1980047 - pt 2. Use a bytemap encoded free list for region allocation

Comment 3

[Paul Bone [:pbone]]

Attachment: Bug 1980047 - pt 2. give arena_run_t a constructor r=glandium

Comment 4

[Paul Bone [:pbone]]

Attachment: WIP: Bug 1980047 - pt 3. Move PRNG initialisation

Comment 5

[Paul Bone [:pbone]]

Attachment: WIP: Bug 1980047 - pt 4. Randomise the free lists during run initalisation

Comment 6

[Paul Bone [:pbone]]

With one bit per region the current overhead per size class looks like:

 Size | Reg per run | Run size | Overhead | Theoretical best 
------|-------------|----------|----------|------------------
   16 |         251 |     4KiB |    1.99% |            0.78%
   32 |         126 |     4KiB |    1.59% |            0.39%
   48 |          84 |     4KiB |    1.59% |            0.26%
   64 |          63 |     4KiB |    1.59% |            0.20%
   80 |          50 |     4KiB |    2.40% |            0.16%
   96 |          42 |     4KiB |    1.59% |            0.13%
  112 |          36 |     4KiB |    1.59% |            0.11%
  128 |          63 |     8KiB |    1.59% |            0.10%
  144 |          28 |     4KiB |    1.59% |            0.09%
  160 |          50 |     8KiB |    2.40% |            0.08%
  176 |          23 |     4KiB |    1.19% |            0.07%
  192 |          21 |     4KiB |    1.59% |            0.07%
  208 |          39 |     8KiB |    0.99% |            0.06%
  224 |          18 |     4KiB |    1.59% |            0.06%
  240 |          51 |    12KiB |    0.39% |            0.05%
  256 |          63 |    16KiB |    1.59% |            0.05%
  272 |          45 |    12KiB |    0.39% |            0.05%
  288 |          14 |     4KiB |    1.59% |            0.04%
  304 |          40 |    12KiB |    1.05% |            0.04%
  320 |          38 |    12KiB |    1.05% |            0.04%
  336 |          12 |     4KiB |    1.59% |            0.04%
  352 |          23 |     8KiB |    1.19% |            0.04%
  368 |          11 |     4KiB |    1.19% |            0.03%
  384 |          21 |     8KiB |    1.59% |            0.03%
  400 |          51 |    20KiB |    0.39% |            0.03%
  416 |          39 |    16KiB |    0.99% |            0.03%
  432 |          28 |    12KiB |    1.59% |            0.03%
  448 |           9 |     4KiB |    1.59% |            0.03%
  464 |          35 |    16KiB |    0.89% |            0.03%
  480 |          34 |    16KiB |    0.39% |            0.03%
  496 |          41 |    20KiB |    0.71% |            0.03%
  512 |          63 |    32KiB |    1.59% |            0.02%
  768 |          21 |    16KiB |    1.59% |            0.02%
 1024 |          63 |    64KiB |    1.59% |            0.01%
 1280 |          19 |    24KiB |    1.05% |            0.01%
 1536 |          21 |    32KiB |    1.59% |            0.01%
 1792 |           9 |    16KiB |    1.59% |            0.01%
 2048 |          63 |   128KiB |    1.59% |            0.01%
 2304 |           7 |    16KiB |    1.59% |            0.01%
 2560 |          19 |    48KiB |    1.05% |            0.00%
 2816 |          13 |    36KiB |    0.70% |            0.00%
 3072 |          21 |    64KiB |    1.59% |            0.00%
 3328 |          11 |    36KiB |    0.70% |            0.00%
 3584 |           9 |    32KiB |    1.59% |            0.00%
 3840 |          17 |    64KiB |    0.39% |            0.00%

With one byte per region and a limit of 254 regions per run, encoding the free list in the indexes the overhead is:

 Size | Reg per run | Run size | Overhead | Theoretical best 
------|-------------|----------|----------|------------------
   16 |         239 |     4KiB |    7.11% |            6.25%
   32 |         123 |     4KiB |    4.07% |            3.12%
   48 |          82 |     4KiB |    4.07% |            2.08%
   64 |          62 |     4KiB |    3.23% |            1.56%
   80 |          50 |     4KiB |    2.40% |            1.25%
   96 |          41 |     4KiB |    4.07% |            1.04%
  112 |          35 |     4KiB |    4.49% |            0.89%
  128 |          63 |     8KiB |    1.59% |            0.78%
  144 |          28 |     4KiB |    1.59% |            0.69%
  160 |          50 |     8KiB |    2.40% |            0.62%
  176 |          46 |     8KiB |    1.19% |            0.57%
  192 |          21 |     4KiB |    1.59% |            0.52%
  208 |          39 |     8KiB |    0.99% |            0.48%
  224 |          18 |     4KiB |    1.59% |            0.45%
  240 |          33 |     8KiB |    3.43% |            0.42%
  256 |          47 |    12KiB |    2.13% |            0.39%
  272 |          44 |    12KiB |    2.67% |            0.37%
  288 |          14 |     4KiB |    1.59% |            0.35%
  304 |          40 |    12KiB |    1.05% |            0.33%
  320 |          38 |    12KiB |    1.05% |            0.31%
  336 |          12 |     4KiB |    1.59% |            0.30%
  352 |          23 |     8KiB |    1.19% |            0.28%
  368 |          11 |     4KiB |    1.19% |            0.27%
  384 |          21 |     8KiB |    1.59% |            0.26%
  400 |          40 |    16KiB |    2.40% |            0.25%
  416 |          39 |    16KiB |    0.99% |            0.24%
  432 |          28 |    12KiB |    1.59% |            0.23%
  448 |           9 |     4KiB |    1.59% |            0.22%
  464 |          35 |    16KiB |    0.89% |            0.22%
  480 |          33 |    16KiB |    3.43% |            0.21%
  496 |          41 |    20KiB |    0.71% |            0.20%
  512 |          39 |    20KiB |    2.56% |            0.20%
  768 |          21 |    16KiB |    1.59% |            0.13%
 1024 |          35 |    36KiB |    2.86% |            0.10%
 1280 |          19 |    24KiB |    1.05% |            0.08%
 1536 |          21 |    32KiB |    1.59% |            0.07%
 1792 |           9 |    16KiB |    1.59% |            0.06%
 2048 |          33 |    68KiB |    3.03% |            0.05%
 2304 |           7 |    16KiB |    1.59% |            0.04%
 2560 |          19 |    48KiB |    1.05% |            0.04%
 2816 |          13 |    36KiB |    0.70% |            0.04%
 3072 |          21 |    64KiB |    1.59% |            0.03%
 3328 |          11 |    36KiB |    0.70% |            0.03%
 3584 |           9 |    32KiB |    1.59% |            0.03%
 3840 |          17 |    64KiB |    0.39% |            0.03%

With two bytes per run we can increase the length of a run:

 Size | Reg per run | Run size | Overhead | Theoretical best 
------|-------------|----------|----------|------------------
   16 |        3411 |    60KiB |   12.58% |           12.50%
   32 |        1806 |    60KiB |    6.31% |            6.25%
   48 |        1228 |    60KiB |    4.23% |            4.17%
   64 |         930 |    60KiB |    3.23% |            3.12%
   80 |         748 |    60KiB |    2.67% |            2.50%
   96 |         125 |    12KiB |    2.40% |            2.08%
  112 |         143 |    16KiB |    2.30% |            1.79%
  128 |          94 |    12KiB |    2.13% |            1.56%
  144 |         140 |    20KiB |    1.59% |            1.39%
  160 |          50 |     8KiB |    2.40% |            1.25%
  176 |          91 |    16KiB |    2.30% |            1.14%
  192 |          42 |     8KiB |    1.59% |            1.04%
  208 |          58 |    12KiB |    1.86% |            0.96%
  224 |          36 |     8KiB |    1.59% |            0.89%
  240 |          50 |    12KiB |    2.40% |            0.83%
  256 |          63 |    16KiB |    1.59% |            0.78%
  272 |          59 |    16KiB |    2.09% |            0.74%
  288 |          14 |     4KiB |    1.59% |            0.69%
  304 |          40 |    12KiB |    1.05% |            0.66%
  320 |          38 |    12KiB |    1.05% |            0.62%
  336 |          12 |     4KiB |    1.59% |            0.60%
  352 |          23 |     8KiB |    1.19% |            0.57%
  368 |          22 |     8KiB |    1.19% |            0.54%
  384 |          21 |     8KiB |    1.59% |            0.52%
  400 |          50 |    20KiB |    2.40% |            0.50%
  416 |          39 |    16KiB |    0.99% |            0.48%
  432 |          28 |    12KiB |    1.59% |            0.46%
  448 |           9 |     4KiB |    1.59% |            0.45%
  464 |          35 |    16KiB |    0.89% |            0.43%
  480 |          42 |    20KiB |    1.59% |            0.42%
  496 |          41 |    20KiB |    0.71% |            0.40%
  512 |          63 |    32KiB |    1.59% |            0.39%
  768 |          21 |    16KiB |    1.59% |            0.26%
 1024 |          63 |    64KiB |    1.59% |            0.20%
 1280 |          19 |    24KiB |    1.05% |            0.16%
 1536 |          21 |    32KiB |    1.59% |            0.13%
 1792 |           9 |    16KiB |    1.59% |            0.11%
 2048 |          29 |    60KiB |    3.45% |            0.10%
 2304 |           7 |    16KiB |    1.59% |            0.09%
 2560 |          19 |    48KiB |    1.05% |            0.08%
 2816 |          13 |    36KiB |    0.70% |            0.07%
 3072 |          21 |    64KiB |    1.59% |            0.07%
 3328 |          11 |    36KiB |    0.70% |            0.06%
 3584 |           9 |    32KiB |    1.59% |            0.06%
 3840 |          17 |    64KiB |    0.39% |            0.05%

Which cannot improve overhead since in many cases where there are more than 254 regions per run the theoretical limit is higher than the practical limit in the table above. But it does provide performance benefits (Bug 2035696). I will measure practical overhead next.

Comment 7

[Paul Bone [:pbone]]

I figured out that it's possible to have 10 or 12 bit values. I previously thought this would require a compare-and-swap loop to update the values. But it does not. on x86 OR can be locked, and on aarch64 LDSET provides the same semantics. This requires that zeros represent allocated.

• To add something to a list, it was already allocated so its field within a 64bit word contains zeros. OR can be used to store a value.
• To remove something from a list, LOCK AND can be used with a complimentary bit pattern to clear the existing bits.

12 bits allows values up to 4096 and permits 5 fields per 64bit word.
10 bits allows values up to 1024 and permits 6 fields per 64bit word.

Weather this is better I don't know, it depends if these atomic updates are in practice slower than regular non-atomic stores (probably, but by how much?). But I wanted to write it down before I forget.

It has the following restrictions: Only really makes sense on 64bit systems where we can use 64bit words. It might not have general cross-platform support, and even where it is supported may need inline assembler rather than std::atomic. We should how a std::atomic solution actually gets compiled (does it result in CAS loops anyway?).

Comment 8

[Paul Bone [:pbone]]

AWSY results:

https://perf.compare/compare-results?baseRev=1ed049fa89a8df5b21fea882b6377d1dac8c8a5f&baseRepo=try&newRev=89ed14337a3f68c34d1102f421d21f0845575247&newRepo=try&newRev=f12f0e9219a2c69acc924badf23e98dcfbf4cf52&newRepo=try&framework=4&test_version=mann-whitney-u

Firstly it looks like the byte-encoded list sometimes saves memory over one bit per cell. That's possibly because it needs to shorten runs and may result in less fragmentation.

The uint16 encoded list uses between 1% and 4% more memory, depending on the test. This is more than I'd like but at the same time it doesn't seem prohibitive. I will ask around. It uses 13.5%, 7.1%, 4.1% (Linux, Windows, MacOS) for a base content process, which is concerning for fission.

We (Jens and I) were considering moving forward with the uint16 encoding because it allows for more performance (Bug 2014781), at least in the short-term then revisiting other options later.

Comment 9

[Paul Bone [:pbone]]

(In reply to Paul Bone [:pbone] from comment #8)

AWSY results:

https://perf.compare/compare-results?baseRev=1ed049fa89a8df5b21fea882b6377d1dac8c8a5f&baseRepo=try&newRev=89ed14337a3f68c34d1102f421d21f0845575247&newRepo=try&newRev=f12f0e9219a2c69acc924badf23e98dcfbf4cf52&newRepo=try&framework=4&test_version=mann-whitney-u

Firstly it looks like the byte-encoded list sometimes saves memory over one bit per cell. That's possibly because it needs to shorten runs and may result in less fragmentation.

The uint16 encoded list uses between 1% and 4% more memory, depending on the test. This is more than I'd like but at the same time it doesn't seem prohibitive. I will ask around. It uses 13.5%, 7.1%, 4.1% (Linux, Windows, MacOS) for a base content process, which is concerning for fission.

We (Jens and I) were considering moving forward with the uint16 encoding because it allows for more performance (Bug 2014781), at least in the short-term then revisiting other options later.

I discussed this with jrmuizel, he said:

I don't want to use more memory than libpas/paritionalloc and be slower
If I need to choose between less memory than libpas/paritionalloc and slower vs the same memory and speed as libpas/partitionalloc I think I'd choose the same memory and speed

libpas encodes free list information "cleverly" with a big "it depends" based on which heap is being used. partitionalloc encodes free lists as pointer within the data of each cell, it does encode them to harden against use after free. That means that partitionalloc uses less memory for free lists. And "it depends" of weather any of our options are smaller than libpas.

I'm going to try uint16_t but make it easy to adjust. Later we can come back and try to be "clever" or try uint8_t again.

Comment 10

[Phabricator Automation]

Comment on attachment 9516812 [details]
Bug 1980047 - pt 2. give arena_run_t a constructor r=glandium

Revision D266580 was moved to bug 2050727. Setting attachment 9516812 [details] to obsolete.

Comment 11

[Paul Bone [:pbone]]

Attachment: WIP: Bug 1980047 - pt 1. Turn the region bitmap into a uint16_t array

This patch prepares for the next one where the array is used to encode a
free list.

Comment 12

[Paul Bone [:pbone]]

Attachment: WIP: Bug 1980047 - pt 5. Use a byte array instead