From 9af41f2ae68f7a7f8f7fc50f1ac643e943c63a56 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Mon, 27 Jul 2026 09:33:03 +0200 Subject: Add a note. --- notes/260727-alloc.md | 127 ++++++++++++++++++++++++++++++++++++++++++++++++++ notes/index.md | 1 + 2 files changed, 128 insertions(+) create mode 100644 notes/260727-alloc.md diff --git a/notes/260727-alloc.md b/notes/260727-alloc.md new file mode 100644 index 0000000..73af511 --- /dev/null +++ b/notes/260727-alloc.md @@ -0,0 +1,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. diff --git a/notes/index.md b/notes/index.md index 96ade16..4db530a 100644 --- a/notes/index.md +++ b/notes/index.md @@ -35,3 +35,4 @@ * [Cons cell optimization AGAIN](260611-fastcons4.html) * [AST Optimizations](260625-optimize.html) * [Further list array optimization](260626-fastcons5.html) +* [Allocation strategy](260727-alloc.html) -- cgit v1.2.3