Update last note.

1 files changed, 109 insertions, 0 deletions

diff --git a/notes/261002-free-bitmap.md b/notes/261002-free-bitmap.md
index eebccc8..10edf25 100644
--- a/notes/261002-free-bitmap.md
+++ b/notes/261002-free-bitmap.md
@@ -216,3 +216,112 @@ entails more broadly.
 * 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.