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