diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/261002-free-bitmap.md | 109 |
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. |