Add note.

2 files changed, 219 insertions, 0 deletions

diff --git a/notes/261002-free-bitmap.md b/notes/261002-free-bitmap.md
new file mode 100644
index 0000000..eebccc8
--- /dev/null
+++ b/notes/261002-free-bitmap.md
@@ -0,0 +1,218 @@
+# 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.
diff --git a/notes/index.md b/notes/index.md
index de4675a..c3d3387 100644
--- a/notes/index.md
+++ b/notes/index.md
@@ -2,6 +2,7 @@
 
 ## 2026 Q3
 
+* [2026-10-02: Free-List Improvement](261002-free-bitmap.html)
 * [2026-09-29: Pointer Color Bits](260929-color-bits.html)
 * [2026-09-25: No-STW SATB](260925-gc.html)
 * [2026-09-23: Green Tea](260923-green-tea.html)