With one bit per region the current overhead looks like: ```
Bug 1980047 Comment 6 Edit History
Note: The actual edited comment in the bug view page will always show the original commenter’s name and original timestamp.
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.