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
210
211
212
213
214
215
216
217
|
# Using Meta Alloc
<!--TOC-->
_2026 August_
The design and implementation of Meta Alloc is mostly complete.
* [Documentation](/zisp/doc/0/A-meta_alloc.html)
* [Implementation](https://git.tkammer.de/zisp/tree/src/zisp/gc/meta_alloc.zig)
Some tweaks needed to make it work across operating systems, but the
basic principles, data structures, and algorithms, are all sound and
should offer peak performance for coarse allocations.
The only problem is it's a bit too coarse. The smallest size class
being 128 bytes, and size classes going up in exact powers of two,
means you would suffer ridiculous amounts of internal fragmentation
from using it directly.
Need a 16-byte heap object? Say hello to 112 bytes of padding. Want
to allocate an array of 300 bytes? Best I can do is 512, so there's
212 wasted bytes. Ridiculous.
This is an intentional design strategy to offer extreme simplicity,
and efficiency, which you can use as a basis to implement various
other allocation strategies on top. Hence "Meta" Allocator.
## Block Alloc
So here's an intermediate allocator based on Meta Alloc. This first
originated from thoughts about how to directly implement a GC on top
of Meta Alloc, but as I'm writing this, I realize it may be cleaner
having another intermediate layer. Or maybe not; we'll see.
Block Alloc supports allocations of any size, with fairly reasonable
internal fragmentation limits. There are two things controlling the
amount of fragmentation:
1. Alignment
* Objects up to 64 bytes in size have 8-byte alignment.
* Objects 65 to 1024 bytes in size have 16-byte alignment.
* Objects 1025 bytes to 16 KiB in size have 32-byte alignment.
* Finally, those up to 256 KiB in size have 64-byte alignment.
Those are four-step jumps in powers of two, making it trivial to
calculate the alignment.
2. Block placement
* Meta Alloc slots are used as Blocks.
* An object is put into the smallest Block size that can hold at
least 16 of those objects, taking into account its alignment.
* E.g.:
* up to 8 bytes -> 128-byte Block (smallest Meta Alloc class)
* up to 16 bytes -> 256-byte Block
* up to 32 bytes -> 512-byte Block
* ...
* up to 256 KiB -> 4 MiB Block (largest Meta Alloc class)
* Objects beyond 256 KiB are served by direct `mmap()` calls.
Maybe it's better to explain this with a table:
<style>
td:first-child { font-weight: bold; }
td:not(:first-child) { font-family: mono; }
td { text-align: right; }
</style>
| Slab | Block size | Max obj. size | Alignment |
|------|------------|---------------|-----------|
| 1 | 128 | 8 | 8 |
| 2 | 256 | 16 | 8 |
| 3 | 512 | 32 | 8 |
| 4 | 1024 | 64 | 8 |
| 5 | 2048 | 128 | 16 |
| 6 | 4096 | 256 | 16 |
| 7 | 8192 | 512 | 16 |
| 8 | 16 K | 1024 | 16 |
| 9 | 32 K | 2048 | 32 |
| 10 | 64 K | 4096 | 32 |
| 11 | 128 K | 8192 | 32 |
| 12 | 256 K | 16 K | 32 |
| 13 | 512 K | 32 K | 64 |
| 14 | 1024 K | 64 K | 64 |
| 15 | 2048 K | 128 K | 64 |
| 16 | 4096 K | 256 K | 64 |
The maximum "tail waste" for each block is equal to maximum object
size minus alignment. E.g. a 512-byte block can waste at most 24
bytes due to the next 32-byte object not fitting.
That waste calculation is not taking into account the waste from the
alignment padding, but that'll be relatively small as well if you do
the calculations, I'm pretty sure. In any case, no worse than other
general-purpose allocators, I'm pretty sure.
## Occupancy bitmaps
The occupancy status of a Block is tracked with a bitmap, which must
have granularity corresponding to the alignment of the size category
of objects.
For example, blocks of size 128 to 1024, which contain object sizes 8
to 64, with 8-byte alignment, need the occupancy of each 8-byte unit
tracked. That's from 16 bits for a 128-byte block up to 128 bits for
a 1024-byte block. Blocks of size 2 to 16 KiB need tracking in units
of 16 bytes, so that's from 128 bits for a 2 KiB block to 1024 bits
for a 16 KiB block. Repeat the math for the larger alignments.
Allocating a new slot should of course not require scanning possible
huge numbers of bitmaps from start to end. We keep track of the last
acquired Block and try to fit the next allocation, acquiring a new
Block if it doesn't fit. Given that objects can only occupy up to
1/16 of a Block, this means we waste at most that about that much
space at the end of a Block due to the next object not fitting.
(The maximum waste is *just under* 1/16, because if exactly 15/16 of
the block is full then another 1/16 sized object fits perfectly, but
anyhow; let's just say waste is capped to 1/16 of Block size.)
So when do we know to reuse freed spots in previous Blocks? This is
the part where I'm questioning the wisdom of separating this from the
garbage collector.
I suppose we could implement some free-list kind of system, with per
thread caches, just like Meta Alloc itself does. But before getting
too into the weeds about this without a clear bigger picture, let's
switch gears to another topic instead where I have a somewhat clear
picture of what to do.
## Object index
Our NaN-packing strategy currently uses 32-bit index values for the
identification of various heap objects.
Is that enough to every individual address that could be returned by
Block Alloc? No, it isn't. But there are solutions.
Given that code will typically branch on the heap type tag of a NaN
anyway, we can give the 32-bit indexes different meanings.
For example, any objects that we know to always need exactly 8 or 16
bytes on the heap will be known to end up somewhere in the first two
slabs of Meta Alloc. And as it so happens, each slab only has up to
2^31 different "positions" (counted in 8-byte units), meaning that
within 32 bits we can perfectly fit an index spanning two slabs!
So, heap types that fit into a small fixed size are solved. But what
about heap types with a huge span of possible sizes, like an array?
This is where we will abuse the fact that heap type tags are 8 bits,
which is way more than what you'd typically need. We can use the 4
high bits as a coarse type tag, and the lower 4 for some sub-type
shenanigans.
A simple strategy would be using those 4 bits to identify which slab
of Meta Alloc an index points into. Given that there's exactly 16
slabs, that works out to be perfect.
If we're "strapped for bits" then we can use a smarter strategy too:
Two bits identify the Size Category of the array or other heap object
with highly variable size:
1. Tiny: Slabs 1 & 2 of Meta Alloc, 8-byte indexing
2. Small: Slabs 3 & 4 of Meta Alloc, 8-byte indexing
3. Medium: Slabs 5 to 8 with 16-byte indexing
4. Large: Slabs 9 to 16 with 32-byte indexing
In other words:
* Tiny and Small correspond to objects up to size 64, which Block
Alloc uses 8-byte alignment for (hence 8-byte indexing works) and
allocates in the first four slabs; we just need to distinguish two
categories to know which two-slab region the 32-bit index is for.
* The 16-byte indexing starting from Medium overlaps perfectly with
16-byte alignment Block Alloc uses for sizes 65 to 1024, which are
allocated in the next four slabs. We can address all four of those
slabs with 32-bit indexes thanks to the 16-byte alignment!
* For larger objects, Block Alloc uses a minimum of 32-byte alignment
so our 32-byte indexing works, and these are allocated in the last
eight slabs, which we can all address thanks to 32-byte indexing.
We *don't* have a separate category for 64-byte aligned sizes, since
we blew two categories for 8-byte aligned sizes, but thankfully this
works out perfectly anyway since 32-byte index resolution works for
64-byte aligned objects too.
This strategy is conceptually quite complicated, but I in terms of
implementation, it should just be a few CPU instructions to shift
integers left and right and select the correct slab base offset.
Probably better to just go with the variant that uses 4 bits and a
uniform 8-byte address resolution, because it's simpler, but if we
ever end up needing to save two bits in our NaN-packing scheme, we
know where to find them! For some of the heap NaN tags anyway.
|
