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
|
# Allocation strategy
_2026 July_
While implementing the "list pool" that offers packed allocations of
small arrays for maximum memory density and cache locality for AST
nodes, I've made the realization:
I can't necessarily rely on a platform's allocator actually aligning
an allocation of 4K exactly to one page. Some allocators add various
metadata right next to the pointer returned to the user, so you can't
always be sure that you're making optimal use of natural boundaries
like pages or cache lines.
Furthermore, since I'll be using 32-bit heap indexes instead of raw
pointers, I'll need to implement some kind of custom allocator that
stays within a given region of memory.
For these reasons, and also because it's fun, I've decided that I'll
completely ditch platform provided allocators and implement entirely
custom memory allocation based purely on `mmap()` or equivalents.
I'll need a number of different allocators, based on purpose:
* A sort-of general-purpose allocator for miscellaneous internal use
within the runtime.
* An allocator for VM stacks.
* Allocators for the various heaps (main, list, istr).
And maybe more.
The sort-of general-purpose one *may* actually serve as the core
underlying allocator for everything else; I'm not yet sure.
In any case, I came up with the following interesting design for this
internal allocator:
* Map a 64 GiB virtual memory area upfront with mmap; divide it into
16 equally sized regions of 4 GiB each.
* Each 4 GiB region serves one size class; these go from 8 bytes all
the way up to 256 KiB as powers of two. Let's just enumerate them:
8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
65536, 131072, 262144.
* Allocations larger than 256K fall back to direct mmap.
* Since this is an "in-house" allocator, the rest of the code-base
should simply be aware that the size classes are powers of two and
make efficient use of this fact. For example, if implementing some
kind of cache array, make sure to use a power of two size. I think
it should be rare that we happen to need an *exact* allocation of a
size that's not a power of two. Right? Let's hope so.
* Since each region is limited to 4 GiB, we can use a single 32-bit
integer to represent the current "watermark" within the region like
a bump allocator. That's 16 4-byte integers; exactly a cache line.
(That's probably micro-optimization territory, but anyway.)
* We can use an atomic fetch-and-add operation on the 32-bit integer
for extremely fast, lock-free allocation.
* The bigger size classes don't have many slots in total. E.g. the
256 KiB size class has a mere 16K slots since 4 GiB / 256 KiB = 16K.
That should be fine; the runtime should rarely ever use the bigger
size classes. Honestly, the entire runtime should probably never
even reach a total of 4 GiB of internal memory use; remember this
excludes VM stacks and the actual object heaps.
* Freed slots are put into "intrusive" free-list stacks per class:
There's a root pointer to "top of free slots stack" starting with
NULL for each size class, and every time a slot is freed, the first
8 bytes of it get overwritten with the current top pointer, and the
top pointer made to point to that last freed slot. This is per size
class of course; there's 16 root pointers.
* Since that's two pointer writes, it needs a mutex or equivalent; we
can use thread-local free-list caches up to 32 or 64 slots or so,
and move them all to the global free-list when they fill up; thus
only every 32 or 64 `free()` operations are expensive, and that's
assuming you just keep freeing instead of reusing.
* Need to think more about what to do if the thread-local cached free
list is empty. Maybe we can "steal" entries in chunks just like we
can write back entries in chunks?
* Consolidating the last two points, let's settle on this: The caches
hold up to 64 slots, but transfers between global and local happen
in chunks of 32 only; this way hitting the cap doesn't lead to a
sudden emptying of the local cache.
* As a low-cost high-yield optimization, freeing the last allocation
simply decrements the region's index instead of putting the object
into a free-list stack. In some cases we may use sub-allocators in
arena fashion, releasing all their memory in reverse order to make
use of this feature. (The list pool allocator already does this.)
* Need some solution to "false sharing" for the smaller size classes.
Not sure how to best do that. I guess there could be thread-local
32-bit indexes and then a global one; then need some machinery to
synchronize all that in such a way that each cache line is claimed
by one thread at a time. Ugh. I'll figure it out.
I'm not sure if I've missed anything significant. Maybe once I start
implementing this, I'll notice some glaring problems, but so far it
sounds quite good.
The biggest size class could actually be used for VM thread stacks;
there should probably be a sane upper limit on the number of native
threads, like 1024 or something, and beyond that the user is expected
to use some kind of green thread thing.
The list heap, which uses the list pool sub-allocator, should use a
modified version of this core allocator, since it needs to be limited
to 32 GiB total, and doesn't need so many different *underlying* size
classes; it has its own size class logic.
As for the generic heap, I'm not sure. We will probably need a large
number of size classes, but also need to stick to 32 GiB total, while
it's also not acceptable to limit each size class to a small cap like
2 GiB, since some user applications could make very heavy use of one
or two specific size classes. So I guess the main heap will need a
totally different strategy. The main heap will also be the main one
needing a sophisticated garbage collector, so I guess it's OK to not
use this super simple core allocator for it.
## Addendum A
To prevent false sharing issues, it may be best to have 64 bytes be
the smallest size class. Objects smaller than this should generally
reside on the stack, or be allocated from some kind of pool; remember
again this isn't for regular language-domain arbitrary heap objects.
Sticking to 16 size classes, this makes the largest 2 MiB, of which
there can only be 2048, which is fine. Reducing to 8 size classes
would make the biggest 8 KiB, which is no good.
The 32-bit index, by the way, should use a scaling factor (say 8, so
it's zero-cost via the LEA instruction) so it can't overflow, even if
the 4 GiB slab for a size class is saturated. This means we could go
up to e.g. 16 GiB slabs (for a total of 256 GiB of vmem) which fully
eliminates concerns about ever saturating a size class.
This also enables a remarkably clean strategy for checking for OOM:
Use a *signed* 32-bit integer for the watermark, and let it overflow
to negative when the last slot of a size class is used. Now we only
need to check if it's negative before an allocation.
The new 16 GiB slab size means we can have 8192 active slots of the
biggest 2 MiB size class, which is even finer than 2048.
New Summary:
* 256 GiB total vmem divided into 16 slabs of 16 GiB.
* Size classes go from 64 bytes to 2 MiB.
* The watermark of each slab is kept track of via a 32-bit signed int
using 8-byte units for "free" shifting in certain CPU instructions
on x86-64 and AArch64.
* Atomic fetch-and-add on the watermark for fresh allocations; check
the fetched value for a negative to decide if we raise OOM due to
slab saturation. (Fetch-and-add returns *previous* value before
addition.) So, every last slot of a 16 GiB slab is usable, and
checking for OOM is a simple less-than-zero check.
* The biggest size class of 2 MiB can have up to 8192 active slots;
much more than what we would ever realistically need. Just make
sure not to abuse big size classes based on the logic: "It's just
virtual memory anyway; I can reserve lots of 2 MiB slots and only
fill each as much as it needs." No, use a smaller size class; for
example, if you're allocating stacks for green threads or such, of
which there could be millions, use 8 KiB dynamic stack segments or
some strategy like that.
* Thread-local free-list caches hold up to 64 nodes, transferred in
chunks of 32 to and from the global free-list for the given size
class. Note this is for native threads, not green threads. The
green threads don't need thread-local caches since each can only
execute within one specific native thread.
The previously discussed "low-cost high-yield" optimization of simply
decrementing the watermark if the last allocation is freed does not
actually make sense in a multi-threaded context with thread-local
caches, so scrap that. However, the following are possible:
* We might eventually implement an expensive cleanup procedure that
checks whether the last N slots of a slab are currently free by
traversing the global free-list, removing them from the free list,
and accordingly decreasing the watermark. Probably overkill, but
possible.
* If we use a GC strategy involving a global STW, we could even do
that in a way that involves all thread-local free list caches, just
as an extra "side mission" of the GC; these slabs are not otherwise
subject to any kind of GC since they are not for the regular heap.
If either or both of these is implemented, we could then also free
memory back to the OS if a slab watermark drops significantly.
|
