path: root/notes/260920-use-alloc-2.md

# Using Meta Alloc, Attempt 2

<!--TOC-->

_2026 September_

After chatting with people and LLMs a bit over the original design of
the general-purpose allocator and/or GC I'm planning to build on top
of Meta Alloc, some issues came up.


## Size Class Count

For one, using mere 64-byte alignment even for very large allocations
means there's an ungodly number of size classes, because alignment is
basically the steps between size classes.  Using 64-byte alignment on
any allocation between 16 KiB and 256 KiB means we have:

    (256 KiB - 16 KiB) / 64 Bytes = 15360 Size Classes

Not even counting those under 16 KiB.  This leads to two issues:

* Way too many free-list roots per thread, since we want thread-local
  cached free-lists.  (Or free-arrays, meaning even more memory use.)

* Potentially large amounts of freed memory never being reused due to
  the application never requesting that exact size again.  E.g. if an
  allocation of 76800 bytes (64 x 1200) is made and then freed, then
  one of 80000 bytes (64 x 1250), then one of 78400 bytes (64 x 1225),
  all three would end up being separate allocations (no memory reuse
  despite freeing in between) because they're different size classes.

General-purpose allocators apparently tend to have four or eight size
classes between powers of two.  That seems like a good middle ground
between too coarse and too fine-grained size classes.

This comes out to be equivalent to using power of two steps for the
alignment of different size "categories" so to speak.  Although we
start with 8-byte alignment for the first few categories, and only
begin doubling at a later point.

Here's a table of how this maps to Meta Alloc slabs:

<style>
td:first-child { font-weight: bold; }
td:not(:first-child) { font-family: mono; }
td { text-align: right; }
</style>

| Slab | Block size | Alignment | Min Size | Max Size | Class Count |
|------|------------|-----------|----------|----------|-------------|
|    1 |        128 |         8 |        8 |        8 |           1 |
|    2 |        256 |         8 |       16 |       16 |           1 |
|    3 |        512 |         8 |       24 |       32 |           2 |
|    4 |       1024 |         8 |       40 |       64 |           4 |
|    5 |       2048 |        16 |       80 |      128 |           4 |
|    6 |       4096 |        32 |      160 |      256 |           4 |
|    7 |       8192 |        64 |      320 |      512 |           4 |
|    8 |       16 K |       128 |      640 |     1024 |           4 |
|    9 |       32 K |       256 |     1280 |     2048 |           4 |
|   10 |       64 K |       512 |     2560 |     4096 |           4 |
|   11 |      128 K |      1024 |     5120 |     8192 |           4 |
|   12 |      256 K |      2048 |    10240 |    16384 |           4 |
|   13 |      512 K |      4096 |    20480 |    32768 |           4 |
|   14 |     1024 K |      8192 |    41960 |    65536 |           4 |
|   15 |     2048 K |     16384 |    81920 |   131072 |           4 |
|   16 |     4096 K |     32768 |   163840 |   262144 |           4 |

This means, for example, that Slab 3 hosts size classes 24 and 32,
Slab 4 hosts size classes 40, 48, 56, and 64, and Slab 10 hosts the
size classes 2048 + 512, 2048 + 1024, 2048 + 1536, and 4096.

Slabs 1 and 2 are just for the size classes 8 and 16, respectively.

This yields a total of 56 size classes.  If for each size class we
have a `[32]u32` to represent the thread-local free slot cache, that
comes out to `56 * 32 * 4 = 7 KiB`, which seems reasonable enough.

Maybe double or even quadruple that because for small sizes we may
want a lot of thread-local free entries; even 28 KiB would still be
acceptable per thread, I think.  Although it may be smarter to use
explicit dynamic allocation at thread creation, because for larger
size classes, most of the space will remain empty, as they'll have
smaller upper limits for the thread-local caches.  Anyway, details
will emerge during implementation; the point is that having 56 size
classes is vastly superior to having many thousands.

Reuse between allocations close in size also dramatically improves,
without imposing *too* much alignment waste.  Using the example from
before: The allocations of size 76800, 80000, and 78400 would all be
rounded up to size class 81920, so if you free one then allocate the
next, it will use the same memory.


## Small Size Alignment

I had the idea of quickly increasing alignment to 16, and then 32,
using an alignment sequence like 8, 16, 32, 32, 32, 32, ... but that
forces every allocation just over 16 to be padded to 32 bytes, and
those just over 32 to be padded to 64 bytes.  That hurts density too
much, so it's best to stick with 8-byte alignment for small classes.

But what if there's a struct of 24 bytes, but with a 128-bit element
that needs 16-byte alignment?  Should the allocator include logic to
insert padding to guarantee some alignment given as an argument?

I think I have a neat, simple solution to this:

First of all, size classes are isolated within their blocks.  A whole
512-byte block will be used either exclusively for 24-byte objects or
exclusively for 32-byte objects.

The size class 24 will not support 16-byte alignment guarantees.  But
size class 32 inherently has 32-byte alignment, so all you need to do
is pad your struct to 32 bytes total, and then you decide whether to
put the 128-bit value in the first or second half; both halves have
16-byte alignment.

I initially thought that SIMD operations perform better when e.g. a
16-byte object is aligned to 16 bytes, but apparently that is not so
with modern hardware; the start offset of the object could be *any*
byte at all, and the performance of the 16-byte SIMD op will be the
same so long as it's within a single cache line.

Size class 32 will guarantee cache line isolation anyway, thanks to
the inherent 32-byte alignment; size class 24 guarantees neither any
alignment beyond 8, nor cache line isolation, but the improved memory
density from *not* adding superfluous padding should be the superior
choice anyway.

If you really need an entire 24-byte object to always be within the
same cache line, you'll once again need to use explicit padding and
allocate 32 bytes for it.


## Occupancy Bitmaps

For small size classes, we end up with potentially a *lot* of bitmaps
so it would be neat if we could minimize them as much as possible.

The 128-byte blocks and 256-byte blocks, serving exclusively the size
classes 8 and 16 respectively, fit exactly 16 objects in a block, so
they should use 16-bit integers for their occupancy bitmaps.

A 512-byte block may serve the size classes 24 or 32, so it can fit
either 21 or 16 objects.  Other blocks fit 25, 21, 18, or 16 objects
depending on which size class the block currently serves.

Since we want each block to map to a bitmap in an array with parallel
indexes, we must assume the largest bit count.  And although we could
save a little memory by using tightly packed bit arrays, this causes
problems with concurrent access, as a single bitmap ends up possibly
crossing cache line or even byte boundaries.

So, for the bitmaps of block sizes 128 and 256 we use u16 arrays, and
for the others we use u32 arrays.

This may sound like it would require branching, but I think there's a
branchless solution to select between u16 and u32:

* Shift-right the size class value such that 8 and 16 become zero and
  anything beyond non-zero.

* Use CMOV or arithmetic trickery to scale a bitmap index value by 2
  (u16) or 4 (u32) to get the raw offset from the starting address of
  the bitmap array.

* Always load a `u32` from that address.

We need to handle an edge case where loading the very last bitmap may
load two bytes beyond what would be allocated for that bitmap array,
if it's one of the u16 arrays; this is solved by simply adding 1 to
the array length (another u16 i.e. 2 bytes at the end).

(This last trick suffers from the unfortunate issue that sometimes we
may end up faulting in an entire page of memory just for 2 bytes that
will be ignored.  I can't think of a solution to that, but it's still
better than doubling bitmap size, which would altogether double the
number of page faults from bitmap fetching.)

At this point, we always have a u32, but depending on the size class,
we only care about the first 16, 18, 21, or 25 bits.  How do we use
the u32 to represent the occupancy of 16, 18, 21, or 25 slots, while
ignoring remaining bits?

Just do a bitwise NOT on the bitmap, then CLZ (aka TZCNT) to find the
index of the first unoccupied slot.  Here we need a branch anyway, to
check if the block is full, so we just test the index value resulting
from the TZCNT against an `INDEX_MAX` which I guess we simply look up
from a static `[4]u8` indexed by `population_count(size_class) - 1`.
(A size class always has exactly 1, 2, 3, or 4 bits set, if you think
about it, due to powers of two divided into steps of 4.)

This way, it doesn't matter whether the bits beyond the first 16, 18,
21, or 25 bits are all zero, or gibberish values.  Any value between
`INDEX_MAX` and 32, returned from TZCNT, means the same thing: block
fully occupied; allocate next block.  Hence the trick of loading 32
bits even for the 16-bit bitmaps works without the need for any extra
masking operations, though that would be easy to add in a branchless
manner as well if needed.


## Block Identification

During manual memory management, we never need to identify whether
some block out there is currently serving one or another size class.

Alloc and free are both given the size class explicitly.  (Or a size
from which the class is derived.)  For each size class, there will be
a pointer to the current block from which allocations are served, so
alloc just checks if there's still room there and otherwise requests
another block.  Free just puts the pointer into the thread local free
cache for that size class, or transfers a chunk of free-list entries
to the shared free-list for that size class.  No need to ever know
what some block out there currently holds.

What about GC operations?  We'll probably want to move objects from
sparsely populated blocks to blocks with few vacancies, as a form of
defragmentation, so we can then free emptied blocks.

But even then, we can learn about blocks serving various size classes
during the mark phase.  When you have a pointer to object of size K,
fitting into size class C, you know that the block from which that
pointer originates currently serves C.  Finding the address of the
block itself is a trivial integer division by a power of 2, i.e. a
shift-right operation.

So, I don't think we need to store any metadata anywhere to mark the
size class that's currently active for a block.


## Object Index

This hasn't changed from the original design: We need either 4 bits
identifying which Meta Alloc slab a 32-bit index points into, or we
use 2 bits to identify which one of four categories the index falls
into, which use different index scaling:

1. Tiny: Slabs 1 & 2 of Meta Alloc, 8-byte indexing

2. Small: Slabs 3 & 4 of Meta Alloc, 8-byte indexing

3. Medium: Slabs 5 to 8 with 16-byte indexing

4. Large: Slabs 9 to 16 with 32-byte indexing

Given that slab 5 uses 16-byte alignment, and it keeps doubling from
there, this strategy still works.


## Free-Lists

I think I'll do something very similar to Meta Alloc itself here, but
there's one significant issue.

With Meta Alloc, the smallest allocation is 128 bytes, which can fit
16 x 4-byte indexes, so the globally shared free-list for each size
class can hold a whole array of free-list entries that can be very
efficiently transferred to and from thread-local free caches.

With the general-purpose alloc, the smallest allocation size will be
only 8 bytes, which fits only two 4-byte indexes.

I think I'll split the logic between small and large sizes, and maybe
use some monomorphization to reduce branching within the code if the
size class for an allocation is statically known.  (E.g. allocating a
specific managed object type, like a closure, represented by a struct
of a specific size; or a 128-bit complex number; and so on.)

In the most extreme case there may be a bunch of functions for the
different small sizes, like alloc8, alloc16, alloc24, etc. up to 64,
and then one taking a dynamic size argument.  Or maybe that's way too
overkill just to reduce a little branching?  We'll see.

In any case, the split in the logic is as follows:

* For size classes 80 and up, we can do it just like Meta Alloc does,
  because we can fit 16 x 4-byte indexes into 80 bytes, plus 16 more
  bytes for the "next" pointer and inline index count.

* For smaller classes, we actually need the globally shared linked
  lists to be used like a more traditional free-list where one entry
  points to the next.  But I'll still apply some optimization here to
  minimize the amount of pointer chasing and synchronization work.

To minimize pointer chasing / memory access, we can use a structure
such as the following:

    Root{ head_idx: u32, aba_counter: u32 }
           |
           v
        HeadNode{ next_head_idx: u32, idx1: u32, ... idxN: u32 }
                  /                                   /
            _____/          _________________________/
           |               |
           |               v
           |            Node{ idx0: u32, ... idxN: u32 }
           |                                  /
           |                _________________/
           |               |
           |               v
           |            Node{ idx0: u32, ... idxN: u32 }
           |                                  /
           |                _________________/
           |               |
           |               v
           |            Node{ ... }
           |
           |
           v
        HeadNode{ ... }

What the heck is this?  OK so, in Meta Alloc each "head node" has a
pointer (index) to the next head, a count of inline indexes, and the
array of inline indexes.  Here we can't have the count and array as
there's not enough room, so instead the "contents" of the head are
themselves a linked list.

But those contents are not a simple linked list either; each node of
this sub-linked-list may directly contain up to N-1 payload indexes.
Only the last (Nth) index, if not NULL, is followed.  (Also the head
can hold N-2 direct payload indexes.)

In the case of 8-byte allocations, the head node only has the 4-byte
next head index, and a single 4-byte index pointing to the start of
the sub-list; each entry of the sub-list then contains one payload
index and one continuation index.  (N = 2)

In the case of 16-byte allocations, the head has the next head index,
two direct payload indexes, and the sub-list continuation index; each
sub-list node has three payloads and one continuation.  (N = 4)

N increases in steps of 2, and goes up to 16, for size class 64.

If you know a little about SIMD and branch prediction and whatnot, it
may be apparent why monomorphization over N is attractive here, but
maybe it wouldn't offer a significant improvement given modern branch
predictors; I'm not sure.