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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
# Green Tea
<!--TOC-->
_2026 September_
I thought I could use Go's Green Tea GC optimization strategy for the
GC design I have in mind, but realized it won't work for two reasons:
1. If I understand correctly, Go's bitmaps track 8-byte memory slots,
so it can mark individual memory slots that may contain pointers.
My bitmaps are more specialized, and only mark the position of an
object of a certain size class within a Meta Alloc slab; this cuts
down bitmap memory use substantially. Besides, Zisp object fields
may contain NaN-packed pointers as well as raw pointers, or other
representations of an object address, so I really need "layout"
information when scanning a heap object's memory.
2. Zisp heap objects don't have a fully generic object header telling
you what type it is / what the memory layout of the object on the
heap is. Some types have a specific header format, like an array
header encoding its length among other things, but the NaN-packed
pointer to an object may already contain all its metadata, such
that there's no metadata whatsoever on the heap.
So, unlike in Green Tea, the mark phase of the Zisp GC cannot simply
push memory spans onto the work stack. It has to push work objects
that consist of the object's address and type.
## Radix Bush
The Meta Alloc heap's 256 GiB cap once again comes in handy, allowing
us to use an incredibly efficient radix-tree-like data structure for
the working set of the GC's tracing algorithm.
Level 0: A 64-bit map where each bit represents a 4 GiB region of our
total heap space. (256 GiB / 64 = 4 GiB.) If a bit is set, it means
there's work to do in there. Use `LZCNT` to locate a bit, using the
index as an index into Level 1.
Level 1: A 64 x 64 = 4096-bit map where each bit represents a 64 MiB
segments of the heap. (4 GiB / 64 = 64 MiB.) The index from Level 0
already told us which 64-bit part of this map to use `LZCNT` on, to
get a Level 2 index.
Level 2: A 64 x 64 x 64 = 262,144-bit map where each bit represents a
1 MiB span of the heap. (64 MiB / 64 = 1 MiB.) Use `LZCNT` and get
the Level 3 index.
(Note: 262,144 bits is 32 KiB which is OK to allocate statically.)
Level 3: A 64 x 64 x 64 = 262144-element array of Work Table Header
structs, which consist of a 64-bit pointer to a buffer of memory, and
a 64-bit summary bitmap indicating which portions of it contain valid
entries right now.
Using 128 bits per Work Table Header means the Level 3 array is 4 MiB
in size. This could be allocated statically, or with mmap; static is
supposed to be fine because the `.bss` section of ELF merely declares
the required size, and the kernel then maps it in virtual memory and
pages it in on demand. But when in doubt, use mmap.
Typically, the same parts of this array will be used over and over
again. For example, if we only ever touch the first 512 MiB of the
first 16 GiB Meta Alloc slab, then only the first 512 entries of the
first 1/16 of the array will be used. After that, there will be an
untouched gap, before entries corresponding to the next slab of Meta
Alloc begin. So, as usual, the kernel's demand paging helps us here.
## Work Table
Given that each Work Table corresponds to a 1 MiB span of the heap,
and the smallest object size is 8 bytes, there can be at most 2^17
(131,072) objects in a Work Table.
For each object, we need to know its type; 16 bits are enough, with
headroom to represent "invalid" to indicate an unoccupied spot in the
work array.
(In our NaN packing strategy, regular heap pointers use 8 bits for a
type tag, but there's also two special NaN tags for short strings and
arrays that use an 8-bit length tag instead. We won't ever actually
use all possible 8-bit values for the regular heap type tag; we can
reserve two for the special types that use another 8 bits for their
length, and another one to mean "invalid.")
If Zisp supports fully static typing one day, such that every single
user-defined heap type needs a static type ID that the GC knows of,
then we could use 32 or 64 bits instead, doubling or quadrupling the
Work Table size in terms of memory use (but not entry count).
In any case, remember that in Level 3 of the Radix Bush there was a
64-bit "summary bitmap." This specifies which portions of the full
Work Table actually contain any entries. Divide 2^17 by 2^6 and we
have 2^13 = 2048 possible entries per portion that will be scanned
linearly to find valid entries. (This is why we need the "invalid"
type tag.)
When we locate a valid type tag, the index at which we found it is
implicitly the index of the heap object to work on, relative to the
start address of the span of memory we're on.
Assuming 16-bit entries, that's 4096 bytes of memory to scan, in one
linear pass, which should be extremely efficient via SIMD and memory
prefetching. It's also a single page, which is neat because we won't
fault in an unneeded page.
To be clear: We don't immediately populate the entire Work Table with
"invalid" entries upon allocation; only the portions that the summary
bitmap says are occupied.
Heck, I'll just make sure that the type tag 0 stands for invalid, so
there's no need to do anything special at all.
### Table Size
Let's assume 16 bits per Work Table entry, meaning the entire table
needs `2^17 * 2 = 256 KiB` of memory at most; for larger object sizes
where there can be fewer objects per 1 MiB span, the size is smaller.
The exact maximum size is a bit tricky to calculate for some classes.
For example, although the second slab hosts 16-byte objects, meaning
we can simply halve the buffer size, the third slab can host 24-byte
objects or 32-byte objects. So we can't just keep halving.
The simplest solution is to just stagger the halving sequence by one
step after the second slab. In other words, the smallest size class
in a category is rounded down to a power of two. This feels off but
it's a consequence of the first few slabs being a bit special in the
size classes they support.
| Slab | Size Classes | Min Alloc | Rounded | Buffer Size |
| 0 | 8 | 8 | 8 | 256 KiB |
| 1 | 16 | 16 | 16 | 128 KiB |
| 2 | 24, 32 | 24 | 16 | 128 KiB |
| 3 | 40 - 64 | 40 | 32 | 64 KiB |
| 4 | 80 - 128 | 80 | 64 | 32 KiB |
| ... | ... | ... | ... | ... |
(Assuming 2-byte Work Table entries.)
## Slab Exhaustion?
There's an interesting theoretical failure mode of the strategy.
The fact that Level 3 of the Radix Bush has 256 Ki entries in total
means that for each slab (1/16) it has 16 Ki entries.
As it turns out, Meta Alloc can only support 64 Ki slots of 256 KiB
(2-byte work entries), 32 Ki slots of 512 KiB (4-byte work entries),
or exactly 16 Ki slots of 1 MiB (8-byte work entries), due to the 16
GiB per-slab limit.
And remember that Meta Alloc is used for the actual application heap
as well, not just for GC and other runtime metadata.
So, in theory, the GC could exhaust 25% of the 256 KiB slab, or with
large work entries (full static typing; bigger type tags), 50% of the
512 KiB slab or 100% of the 1 MiB slab.
However, it seems extremely unlikely that this would actually happen,
given that the work-set of a tracing GC typically contains a small
fraction of the live object graph at any given moment.
Still, imagine a humongous array of heterogeneous Zisp values, say a
billion, and every single one happens to point to an 8-byte object.
That's about half of all 8-byte objects that can be allocated (the
limit is exactly 2 Gi since a slab is 16 GiB) so when the GC traces
this array it would really use a substantial portion of a slab.
Honestly, the short answer to this problem is: Don't do that, then.
Just to put things in perspective: A billion 64-bit values (which is
what a heterogeneous Zisp array is) consumes 8 GiB of RAM. If you're
wondering where in Meta Alloc that would even fit: Nowhere, since the
Block Alloc / GC Alloc strategy will be to allocate any object beyond
256 KiB outside the Meta Alloc heap, and represent it with a handle.
So it *could* exist in Zisp, but if you're using 8 GiB just for that
array, and another 8 GiB for the billion 8-byte objects it will hold,
then hopefully your heap contains almost nothing else, and the GC can
use a large portion of the 256 KiB or 512 KiB slab?
This is an interesting failure mode to keep in mind, but in practice
it's probably not something anyone would ever encounter unless they
completely abuse the runtime. This kind of crazy use-case is where
you should really stop relying on a GC and reach for manual `mmap()`
usage and whatnot.
## Thread Safety?
I've been "discussing" this strategy with Google Gemini and it says
that thread safety shouldn't be an issue per se (as in, the way I've
designed it could lend itself to lockless thread-safe strategies via
atomic ops), but it may also be acceptable to have a single-threaded
concurrent GC unless you have highly aggressive allocation rates
across dozens of threads.
Supposedly, a single GC thread not being able to catch up with many
allocating threads is a real and common problem in heavy networked
services, though I would question the architectural decisions they
make.
When I actually get to implementing it, I'll have to think about the
cost of making the GC algorithm concurrent with itself, both in terms
of CPU throughput, and code complexity.
|
