path: root/notes/261002-free-bitmap.md

# Free-List Improvement

<!--TOC-->

_2026 October_

Here's a set of optimizations for small size classes.


## Bitmap in Free-List

Instead of referencing individual slots within Meta Alloc blocks,
free-list entries of the GC could consist of:

    Inside Block 0x557799A0:

    Slot 0x557799A5 = {
      free: u32,
      next: u32,
    }

The pointer to the free slot would be an implicit reference to the
containing block.  The field `free` is a bitmap declaring which slots
of that block (other than this one) are free.  Thus, one entry of the
free-list can declare up to 31 empty slots.  (If all 32 were empty,
the whole block would have been released to Meta Alloc.)

That's for the smallest two size classes, which fit 32 elements at
most per block.  Starting from size classes that can fit more, the
bitmap can be a `u64`.

At some point, it stops making sense to use this strategy, since you
don't want a single thread to hog an entire block, given the massive
sizes they have for the bigger size classes.

A sane cutoff would probably be the fourth block size.  It serves the
size classes up to 64 bytes, and the block size is 2048, so a thread
will hog at most 2 KiB, and temporally close allocations will also be
spatially close, sharing a page; and if you're lucky, a cache line.

So, for the first two block sizes, holding up to 32 slots each, we
would use the struct above.  For the next two block sizes, we would
use a version where the `free` field is a `u64`.  Starting from the
fifth block size, where the smallest hosted size class is 80 bytes,
Meta Alloc style chunky free-list entries can be used again.

I've not made clear whether this design is only for global free-lists
of small size classes, or also the thread-local "free-cache" arrays.
Both should work.  In the local arrays, we can pre-link the entries,
despite keeping them in an array, so later we only need to push one
node onto the list.

Oh, that's assuming support for manual freeing, by the way.  If that
weren't part of the design, then the local arrays would only ever be
filled from the global free-list, while the GC recycles memory into
that global free-lists, and so on.  One way cycle.  But I'd like to
support manual free even of GC-managed memory, for those who need a
performance boost.


## Manual free

How to best support one by one freeing of objects in blocks, when the
entries in our local free-cache arrays correspond to entire blocks?
Each free action must check whether any of the existing entries are
for the same block, and manipulate the bitmap of that.  It should be
possible to make this highly efficient with SIMD operations, so that
there's still a benefit to this.  And then, if no entry in the array
matches, do we flush?

At this point I realize that may be a bad idea, because it's just too
easy to use it wrong.  If you fill the array with entries for blocks
that each have a single free slot, then the next free would have to
flush a bunch of single-slot entries into the global free-list.

Perhaps it's best to transparently ignore manual freeing if the local
free-cache array is full, and the user calls `free()` on a slot that
isn't in any of the blocks represented by the free-cache entries.


## Batch-update 'Allocated'

Imagine a thread has just acquired a 256-byte block from Meta Alloc,
and used 120 of them to serve 15 allocations of 8 bytes.  Then the GC
runs, and 12 of them are dead already.  Is it really worth adding a
free-list entry for just 12 slots, when our bitmap strategy allows
representing up to 31 freed 8-byte slots?

For small size classes, the allocator shouldn't immediately update a
bit in the Allocated Bitmap.  It should do so when the current Meta
Alloc block is filled up and a new one is being requested.

Given this behavior, we wouldn't ever end up with partially-filled
bitmaps in the Allocated Bitmap, which makes one wonder whether it
could be drastically cut down in size (one bit per block) but that
won't work for the following reason.

Say a block was filled up, and later, the GC discovers that 30/32 of
the objects in it are dead.  Without a compaction strategy, we have
two options:

1. Don't free any object in the block.  Hope that, on a subsequent GC
   cycle, the remaining objects will be dead, so it can be collected
   altogether.  This is not good, as a single live object could keep
   the whole block uncollected forever.  Multiply by N blocks and we
   get tons of wasted memory (enormous fragmentation).

2. Create a free-list entry for those 30 slots of the block.  Later,
   some thread will take that entry, use up the 30 slots, and now it
   needs some way to register this in the Allocated Bitmap, so we do
   need slot-level granularity in the Allocated Bitmap after all.
   (The other 2 slots may or may not still be allocated!)

There's an interesting implementation detail that comes up here, by
the way:  When partially free blocks like that are acquired for use,
their original occupancy status must be remembered, so once we used
all the slots that were still free when we acquired it, we set only
the corresponding bits in the Allocated Bitmap.

As for the other slots (in this example, the remaining 2/32) they may
actually be freed at any point, but we don't know that; we must only
record the changes that we make, with an atomic RMW on the Allocated
Bitmap.

Essentially, the 2/32 and 30/32 slots get split into two independent
sets of slots.  But if at any point they're all allocated at the same
time, they can merge again.  That is:

1. Some thread acquires the fresh block.  It "remembers" the initial
   state of all slots being free.  (This is just because it would be
   simplest to have one implementation for full & partial blocks.)

2. Once all 32 slots are used up, it commits the 32-bit update to the
   Allocated Bitmap and acquires another.

3. At some point, 30/32 slots are collected, and inserted into the
   global free-list with the structure explained further up in the
   first section of this note.

4. At some other point, the other 2/32 slots have the same happen.

5. Some thread acquires the 30/32.  It "remembers" that only 30 were
   free when acquired.

6. Some thread acquires the 2/32 and does the same.

7. When the 30 slots fill up, the corresponding bits in the Allocated
   Bitmap get updated.

8. Likewise at some point for the other 2 slots.  Consequently, the
   Allocated Bitmap now once again has a full 32-bit allocated block.

9. Now if all objects in the block die at once, it can be collected
   entirely, or it could be split up again in some way.

(Some of the listed events can occur in different order; 4 to 8 can
pretty much happen in any order, I think.)

The worst-case scenario for this strategy is that we keep collecting
singular dead objects in tons of separate blocks.  At that point, it
basically degenerates into a basic linked-list style free-list with
one slot per entry.

As a mitigation strategy: The GC could refuse to free objects in a
block if they would form a free slot set smaller than N.  The value
should probably be very small, to cap worst-case memory waste to N-1
slots that remain unfreed.

At N = 5 it's 4/32 = 12.5%; at N = 3 it's 2/32 = 6.25%; either choice
would be defensible, or exactly in between with N = 4 for 3/32 = ~10%.

When a thread takes an entry from the global free-list, it gets at
least N slots to use, but hopefully many more on average.

One could combine this with a strategy akin to the chunky free-list
entries of Meta Alloc, for size classes greater than 8 bytes, but it
probably isn't worth the complexity.


## Summary

So, we have a split strategy depending on size class:

1. Up to size class 64, corresponding to the first four Meta Alloc
   slabs / block sizes, we use the bitmap-based free-list entries.

2. For larger size classes, we use Meta Alloc style chunky free-list
   entries with embedded pointers to N other free slots.

The second is nothing new, but let's sum up the first and what it
entails more broadly.

* Each thread has a "current block" from which allocations are served
  and an "original occupancy" bitmap declaring how it started out, as
  well as the "current occupancy" bitmap to know what slot is next in
  line to be given out and when the block is full.

* When full, the diff between the original and current bitmap is used
  to perform an atomic update to the Allocated Bitmap, and the next
  block is acquired, either from the thread-local free-cache or the
  global free-list.

* The thread-local free-cache can be filled by manual freeing as an
  optimization for advanced users.  The expectation is that objects
  allocated together are freed together, so freeing entails a lookup
  for existing entries corresponding to the block containing the slot
  being freed, so we just update the bitmap of that entry.  The free
  call is silently ignored if the free-cache array is full and no
  entry for the containing block was found.

* The local cache can be filled in chunks by following N links in the
  global free-list, and updating the head pointer to a corresponding
  later node; thus we steal N nodes with one atomic CAS.  (This may
  not be worth it?  Not sure.)

* When the GC sweeps, there's a lower limit N, below which it refuses
  to free slots in a block, so it doesn't add free-list entries with
  very few slots.


## Update

It's not nice if we have to use a CAS loop to pop an entry off of the
global free-list only to receive 4 or so usable slots.

After mulling over it a bit, I came up with a neat solution.  And it
allows bringing "N" (see above) all the way down to 2 if desired, for
minimal memory waste.

Given that `N >= 2`, each free-list entry represents a block that has
at least one *other* free slot than the one being used to represent
the entry.  As such, we can combine the bitmap strategy with the one
originally described here:

* [Using Meta Alloc, Attempt 2](260920-use-alloc-2.html): See section
  about Free-List representation, with the neat ASCII graphic.

There, the idea was that each entry points not only to the next node
of the main free-list, but also starts a sub-linked-list (with some
inline slot pointers per node, for further density) so that popping
one free-list entry with a single CAS loop gives you an arbitrarily
sized set of free slots to put into your thread-local cache.

Since we now use 4 bytes for a bitmap, we don't have place (in the
smallest size class) for a further sub-list head index.  However,
since the bitmap informs us of at least one other free slot, we can
simply use that!

This is quite a complicated structure, but to sum it up:

* Each main free-list entry points to a slot of at least 8 bytes; it
  contains a 4-byte index to the next main entry, and a 4-byte bitmap
  declaring the presence of *at least one other* slot within the same
  block that belongs to this free slot set.

* The >= 1 other slots each contain two 4-byte indexes to two other
  slots, each representing a sub-set of free slots under this main
  free slot set.

Assuming 8-byte slots:

    Root{ head_idx: u32, aba_counter: u32 }
           |
           |    Block 0x223344A0 {
           |      Slot 0x223344A1 { occupied }
           |      Slot 0x223344A2 { occupied }
           |      ...
           `----> Slot 0x223344A8 { ("Main Head Slot")
                    next_head_index: u32
                    block_occupancy: u32 --------. (intra-block links)
                  }                              |
                  Slot 0x223344A9 { occupied }   |
                  Slot 0x223344B0 { occupied }   |
                  ...                            |
                  Slot 0x223344B4 { <------------|  ("Carrier Slot")
                    subset1_head_index: u32      |
                    subset2_head_index: u32      |
                  }                              |
                  ...                            |
                  Slot 0x223344B7 { <------------'  ("Carrier Slot")
           .------- subset1_head_index: u32  (inter-block link)
           |        subset2_head_index: u32  (inter-block link)
           |      }
           |      ...
           |    }
           |
           |    Block 0x556677D0 {
           |      Slot 0x556677D1 { occupied }
           |      Slot 0x556677D2 { occupied }
           |      ...
           `----> Slot 0x556677D5 { ("Sub Head Slot")
                    next_subhead_index: u32
                    block_occupancy: u32 ----.
                  }                          |
                  ...                        |
                  Slot 0x556677D9 { <--------'  ("Carrier Slot")
                    subset1_head_index: u32
                    subset2_head_index: u32
                  }
                  ...
                }

Yeah, I'm a little proud of this graphic.

For minimum free slots N per block, each main head or sub head slot
points at N-1 carrier slots, each of which point to exactly two sub
head slots.

We could optimize this further for size classes greater than 8 bytes,
but I really don't think it's worth the added complexity and looping
construct (i.e. branch instructions) needed to implement that.

I'm too lazy to calculate the worst-case number of pointer hops for
the pessimal choice of N = 2 (optimal to minimize waste, pessimal to
minimize pointer chasing) but it ought to be something acceptable.

Given upper bound M for the number of free slots represented by each
such tree of free slots, the time cost of "unfolding" it is amortized
`O(1)` if we want `gc_alloc()` to do so eagerly, though we could also
leave it in tree form in thread-local caches; that would just require
changing the strategy used to handle manual free calls.  For example,
we could simply have a separate flat array of "immediate reuse" slot
indexes.  Just need to think about how it interacts with the bitmap
used to track allocation status; either you make sure to atomically
clear the bit for the individual freed slot, or you leave it dirty
while making sure that these local "immediate reuse" buffers are
considered part of a thread's root set during marking.