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
|
# 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.
|
