jonnifyelixir
F4 / F4.05 / bitmap

F4.05 · part 1 of 3

Bitmapped nodes

A HAMT node could be a 32-element array, but most slots in most nodes are empty, so that wastes space. Instead a node keeps one 32-bit bitmap — a bit set for each occupied slot — and one packed array holding only the occupants, in slot order. To find a slot’s position in that array you take a popcount: the number of set bits below it.

A node with entries at slots 1 and 6 and a child at slot 4 (8 of 32 slots shown). One array holds all three. Select what to read.

One bitmap, one array Advanced: leaves and children, mixed

One bitmap, one array

The bitmap says which slots are used; the array holds the contents densely. Reading a slot is two steps: test the bit, then index into the array by the popcount of the lower bits. Select the bitmap, the array, or watch the index get computed.

What to read · select one

0 1 2 3 4 5 6 7 bitmap → slots[] (packed) k→v ● k→v @1 @4 @6 slot 4 is set — its index in slots[] is: popcount(bitmap below slot 4) = 1 set bit (slot 1) → slots[1] bitmap marks slots 1, 4 and 6 — three occupants, packed 

      

      
role: which slots are occupied

      
result: bitmap → 3 packed slots

    

    
A bitmap plus a popcount replaces a 32-wide array of mostly-empty slots with a compact one. The node
      stores one small array and one integer, and still finds any slot in constant time.

  


  

    
Advanced: leaves and children, mixed

    

      
That one array holds two kinds of thing: an inline entry (a key and its value) and a child node (a pointer to
        the next level). They sit together, so the code that reads a slot needs a way to tell them apart — a tag
        on each cell, or a side table. The bitmap alone does not say which is which; it only says the slot is used.
        That mixing is the one compromise the layout makes, and it is the thing F4.06 removes by keeping
        two bitmaps and two arrays, one per kind. The index trick is the same popcount either way, and
        popcount is a single CPU instruction on modern hardware, so the lookup stays cheap.

      
This compact node is the unit the rest of the spine builds on: a HAMT stacks these into a tree (F4.05.2),
        an insert copies a path of them and shares the rest (F4.05.3), and a CHAMP refines the node into its
        canonical, two-bitmap form (F4.06). The portal’s page registry is stored in nodes like this, one per
        level of a key’s hash.

    

    
import Bitwise

# is slot i occupied? — test the one bitmap
def occupied?(bitmap, i), do: (bitmap &&& (1 <<< i)) != 0

# position in the packed array = popcount of the lower bits
def index(bitmap, i), do: popcount(bitmap &&& ((1 <<< i) - 1))
# index(bitmap, 4) = popcount(bits 0..3) = 1  ->  slots[1]
# each slots[] cell is a leaf or a child — a tag says which

    

      

        
F4.05.1 · one bitmap, one mixed array

        
Leaves and children share a single packed array; a tag tells them apart.

      

      
      

        
F4.06 · two bitmaps, two arrays

        
A CHAMP separates entries from children, so no tag is needed and the shape is canonical.

      

    

    
Next: hash-prefix indexing — how the
      key’s hash chooses which slot to read at each level of the tree.

  


  

    
References

    
Primary sources for this lesson, and where it connects in the course.

    

      
Sources

      
      
Related in this course