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