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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
# Using Meta Alloc, Attempt 3
<!--TOC-->
_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 a block was completely full, but is now completely empty, we can
free it back to Meta Alloc. (If only some slots were occupied and
now the whole block is empty, we can't free it, since some of its
unoccupied slots may be in a free-list.)
* Otherwise, we `free()` individual "now dead" memory slots in it,
which works similarly to the `free()` of Block Alloc, but putting
the slots directly into the shared free-list of the size class, in
chunks to decrease contention. (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.
### Pinning
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.
### Explicit free
As an optimization trick offered to application code that otherwise
uses GC, there could be a special explicit `gc_free()` function.
This would clear the GC occupancy bit for the given memory slot, and
place it into the thread-local allocation buffer. (The same that's
fed from the global shared free-list for a size class.)
Clearing the occupancy bit ensures that the sweep phase doesn't touch
it and the block it's placed in can't be freed to Meta Alloc. It's
basically as if it had been swept by the GC, but lands immediately
within the thread-local alloc buffer.
If the local buffer is full, I suppose a chunk of it would be flushed
into the shared free-list of the size class. Basically the same as
Block Alloc and Meta Alloc. That's somewhat costlier than simply
putting it into the local buffer, but should still remain under a
microsecond I suppose.
This way, an application that allocates and frees a bunch of objects
in a tight loop could make sure that it keeps reusing the same few
memory slots already in L1D cache.
If the allocation happens at the start of the loop and the freeing at
the end, then the programmer could have just used manual alloc/free,
or used stack memory, and a smart optimizer should even detect this
pattern and turn it into stack usage anyway...
But if the loop crosses across module boundaries, conditionals are
involved, or it frees some old objects at the start of the loop and
then creates new ones or creates them at the end, I could see some
situations where this is a useful API to offer.
(Conditional free is probably the strongest case; in all other cases
the object didn't need to be created with `gc_alloc()` to begin with,
I think. Haven't thought hard enough about it.)
### GC handover
An object initially allocated as a manually managed object could be
simply handed over to the GC, if there is some logical reason to do
such a thing.
All this entails is setting the GC occupancy bit for the memory slot.
That's literally all; the object is now GC managed.
Of course, if the object acts as the root of a whole graph of objects
that were manually allocated and are meant to be handed over to GC,
then a traversal of that graph may be necessary to hand all of them
over to GC.
|
