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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
# Using Meta Alloc, Attempt 3
_2026 September_
Here's a fairly concrete design proposal.
## Block Alloc
This is a simple manual alloc/free allocator, based on the Meta Alloc
slabs/blocks, simply adding support for the more granular size classes
we discussed earlier.
It uses the coarse power-of-two Meta Alloc blocks for efficiently
managing the backing memory. (Not needing to use mmap all the time.)
It simply uses thread-local free caches, occasionally flushed to or
refreshed from shared free-lists. (Meta Alloc does the same thing,
just for larger blocks.)
In short, Meta Alloc + Block Alloc simply offer a fairly simple,
highly efficient, thread-safe, always O(1), multi-layered (slab ->
block -> slot), completely general-purpose manual allocator with 56
size classes.
It still has the caveats that it requires a size argument to `free()`
so it knows which size class the freed slot belongs to, and inherits
the Meta Alloc limitation of 256 GiB total heap / 16 GiB per slab.
(Every four size classes, roughly; first few classes being exceptions
e.g. 8-byte size class gets an entire slab for itself.)
## GC Alloc
A fully concurrent (virtually "zero pause") mark-sweep tracing GC
built on top of Meta Alloc, supporting the same 56 size classes as
Block Alloc, with the following collection strategy:
* For each Meta Alloc slab a "GC occupancy bitmap array" is allocated
in virtual memory via `mmap()`. Each element (bitmap) of the array
corresponds to a Meta Alloc block, whose index is easily calculated
in few CPU instructions.
* Using `gc_alloc()` sets bits in the GC occupancy bitmap for the
current block, acquiring a new block if needed.
* If there are interleaved uses of the manual Block Alloc `alloc()`,
and `gc_alloc()`, then some bitmaps in the array remain zero, since
Block Alloc takes a Meta Alloc block and dedicates it to itself.
This isn't ideal, as it creates holes in the GC bitmap array, but
should be acceptable, and doesn't break the design.
* When the concurrent mark phase begins, a fresh, seconary, all-zero
bitmap array is allocated. (Or the previous one explicitly zeroed
out; may be faster than having fresh memory paged in. We can swap
back and forth between two bitmap arrays.)
* The new bitmap array is swapped in eagerly, so new allocations will
set bits directly in the new one. Object graph tracing now begins,
locating live objects, setting bits in the new bitmap array. Store
barriers are used to safely handle concurrent object graph mutation,
making sure the new bitmap array remains accurate.
* When the mark phase has ended and concurrent sweeping begins, we
walk through the original (old, stored away) bitmap array and the
new (already swapped into place) bitmap array in parallel, using
"AND NOT" to identify memory slots that were live before the mark
phase (bit was set in original) but have been found not to be live
anymore (bit not set in new).
* If an entire block comes out empty, we can release it directly back
to Meta Alloc. Otherwise, we perform a `free()` on individual "now
dead" memory slots which does something similar to Block Alloc, but
freeing directly to the shared free-list of the appropriate size
class, instead of thread-local caches. The mutator threads have
thread-local caches anyway, filled from the global free-list in
chunks, as an optimization.
* We need a way to identify what size class a block is for. Remember
that the blocks supporting multiple size classes use a `u32` but
don't need all bits in it; at most 25 bits are used for occupancy
data. We can dedicate 2 bits at the "other end" of the integer to
identify which of the (up to 4 possible) size classes the block is
currently used for.
* It may be good to double the size of each Meta Alloc block (i.e.,
smallest Meta Alloc size class becomes 256) so we can use `u64`
bitmaps instead of `u32` which should boost throughput.
* The old bitmap array that was used to identify "previously live"
memory slots can be zeroed out and used as the new bitmap array in
the next GC cycle.
It's possible to add a compaction phase to this design, using load
barriers with colored pointers and whatnot, like ZGC. It's unclear
whether the CPU overhead would be justified; all it gives you is
potentially improved spatial locality of objects in memory.
Oh, and with regards to object pinning, Gemini gave me a really cool
idea on how to do it efficiently:
* A third bitmap array is used to represent pinned memory slots.
* When the mark phase begins, it's used to "seed" the new bitmaps
(immediately marking those slots as live) and also as GC roots.
* To prevent the need to scan the entire pinned objects bitmap array
which would typically be *very* sparsely populated, a "summary"
bitmap array is used, where one bit represents a span of N slots.
When pinning, the bit representing the relevant span is marked in
the summary bitmap, so during scanning we can look at the summary
and only scan the spans that have any bits in them at all.
The span size N is probably best decided such that a bit represents a
cache line i.e. 64 bytes i.e. 512 bits of the actual pinned objects
bitmap array. Assuming that one uses a u32 for the first two block
sizes, and u64 beyond that, our bitmap memory needs are:
| Slab | Regular Bitmap | Summary Bitmap |
|------|----------------|----------------|
| 1 | 256 MiB | 0.5 MiB |
| 2 | 128 MiB | 0.25 MiB |
| 3 | 128 MiB | 0.25 MiB |
| 4 | 64 MiB | 0.0125 MiB |
| 5 | (halve it...) | (halve it...) |
| ... | ... | ... |
| SUM | ~640 MiB | ~1.25 MiB |
That's a very lean summary bitmap. The regular bitmaps are bigger,
and unfortunately there's three of them, but that still gives us:
(3 * 640 MiB) / 256 GiB ~= 0.73% metadata overhead
That's quite good I think.
|
