jonnifyelixir
F4 / F4.06 / iteration

F4.06 · part 2 of 3

Cache-friendly iteration

Walking a CHAMP is a pre-order over the tree: at each node, yield the packed entry array first, then descend into each child. Because the entries are contiguous and held apart from child pointers, that first step is a linear read of adjacent memory — a much friendlier access pattern than a HAMT, whose single array interleaves entries with pointers and gaps. The order is also canonical: the same map always yields its entries in the same sequence.

The same node, walked as a CHAMP and as a HAMT. Select the step, or compare the layouts.

Entries first, then descend Advanced: canonical order & diffs

Entries first, then descend

A node’s own entries come out before any child’s, in slot order; then each child is walked the same way. Select what to read — the entry sweep, the descent, or the HAMT layout it improves on.

What to read · select one

CHAMP NODE entries[] k→v 1 k→v 2 then nodes[] child 3 child 4 one contiguous sweep: entries, then children HAMT NODE k→v · ptr · k→v ptr · k→v entries and pointers interleaved with gaps across 32 slots the packed entry array is read first, in canonical slot order 

      

      
role: entries are contiguous, read first

      
result: walk entries[] linearly

    

    
Contiguous entries turn a node’s contribution into a straight-line read; the canonical
      order makes that read reproducible. A HAMT gets the same answer but pays in cache misses, hopping over gaps
      and past child pointers.

  


  

    
Advanced: canonical order & diffs

    

      
The traversal is the eager Enum/lazy Stream story from
        F3.04, now over a tree: reduce this node’s entries, then reduce its children. Two properties make it
        useful beyond speed. First, the order is canonical, so iterating the same map twice — or two equal
        maps — yields identical sequences, which is what makes a deterministic snapshot possible. Second,
        because an update reuses every untouched child by sharing, walking a changed map re-reads only the parts
        that differ. For the course’s page registry that is the cheap path: take a snapshot, edit one page,
        and the diff against the previous snapshot is the single changed sub-tree — the same idea a LiveView
        uses to send only what changed.

    

    
# pre-order walk: this node's packed entries, then each child
def reduce(%Champ.Node{entries: es, nodes: ns}, acc, fun) do
  acc = Enum.reduce(es, acc, fun)            # contiguous, canonical order
  Enum.reduce(ns, acc, fn child, a -> reduce(child, a, fun) end)
end

# same sequence every time  ->  snapshot, then diff only the changed sub-tree

    

      

        
F3.04 · Enum walks a collection

        
Reduce folds elements in order into an accumulator.

      

      
      

        
F4.06.2 · a cache-friendly pre-order

        
Reduce the packed entries, then each child — contiguous, canonical, diff-friendly.

      

    

    
Next: canonical equality —
      what that one fixed shape per map buys when you compare two of them.

  


  

    
References

    
Primary sources for the CHAMP traversal, and where it connects in the course.

    

      
Sources

      
      
Related in this course