2 files changed, 128 insertions, 0 deletions
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)