1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
# Radix Bush Improvement
_2026 October_
This may be a dumb micro-optimization, or not; here goes.
Context:
* [Green Tea](260923-green-tea.html): See 'Radix Bush' section.
The "Level 1" is 512 bytes and the "Level 2" is 32 KiB.
Most applications will use a small fraction of the total 256 GiB vmem
that Meta Alloc manages. But it will be spread across the slabs that
are each 16 GiB. So, the GC will need to touch widely spread apart
locations of Level 1 and 2.
For example, if the application uses 1 MiB from the first and 1 MiB
from the fifth slab:
* Level 1: Touches u64 bitmap at index 0, and u64 bitmap at index 16
if my math is correct. That's two separate cache lines.
* Level 2: Touches u64 bitmap at index 0, and at index 1024, again if
my math is correct. That's two separate *pages* of memory.
Consider the following alternative: From the full 35-bit Meta Alloc
unit index (that's 31 bits per slab and 4 bits to identify the slab)
we could put the highest 4 bits at the front instead (i.e., swap the
positions of the 31-bit intra-slab index and the 4-bit slab index).
Now the above becomes:
* Level 1: Touches only one u64 bitmap, at index 0, because it covers
the first 4 GiB of each slab.
* Level 2: Touches only one u64 bitmap, at index 0, because it covers
the first 1 MiB of each slab.
At level 2, we don't touch a second cache line until one slab reaches
over 64 MiB of memory use. At level 1, we don't touch a second cache
line until a slab reaches a whopping 4 GiB of memory use.
Yeah, I think that's pretty good!
We may need to pay with some additional arithmetic, but I think that
should be fine. And in fact, given that we already have to do some
arithmetic on Meta Alloc indexes, we may actually end up with an
equivalent count of CPU instructions; I've not analyzed it yet.
|
