ByteTrie Allocator
Here's a tentative allocator design for the ByteBitmapMap:
Recall we're storing 256-bit (32-byte) bitmaps to branch with the bytes of a key
We require value types to be 64 bits (8 bytes), and we can have at most 256 of them (256*8=2048 bytes)
Defining the map pointer type as evict (1 bit), small (1 bit), revision (6/8 bits), children (8 bits), and page-index (32 bits)
Defining a node (page-sized, 4096 bytes) as dense value memory (2048 bytes) and up to 64 revisions of the bitmaps (64*32=2048 bytes)
Defining a small node (shares a page with other nodes) as a shared dense value memory (2048 bytes) and indices (up to 256 indices/bytes)
Creating a mmap: 4096*2^32 bytes
```
assign(n, bitmap, children)
MEM[n.index:n.index+8*n.children] = children // this access makes the page
MEM[n.index+2048+32*n.revision:n.index+2048+32*(n.revision+1)] = bitmap
assign_small(n, indices, children)
for i in 0..n.children:
MEM[n.index+8*indices[i]:n.index+8*indices[i+1]] = child // the first access makes the page
MEM[n.index+2048+32*n.revision-n.children:n.index+2048+32*n.revision] = indices
alloc_upto_64(ns):
small = [n.children <= EVICT_THRESHOLD for n in ns]
addresses = [alloc(n) if n > EVICT_THRESHOLD else nullptr for n in ns]
if sum(n.children for n in ns if small[n]) < 256:
pack_page(small, &ns, &addresses)
return addresses
if PREFER_COMPUTE:
// compute good groups of n (can use VP2INTERSECT), delegate to different pack_page calls
else: // prefer to use more memory
// eagerly delegate to alloc if children above MIN_EVICT_THRESHOLD else pack_page
```