jonnifyelixir
F4 / F4.05 / sharing

F4.05 · part 3 of 3

Structural sharing

The trie nodes are immutable, so an insert cannot edit them in place. Instead it builds new nodes only along the path from the root to the changed leaf, and reuses every other sub-tree exactly as it was. The result is a second map that shares almost all of its structure with the first — and the first map is still there, unchanged.

Adding one page to the registry, "PGE0NcQgyPQEbI", turning version v1 into v2. Select what to highlight.

Copy the path, share the rest Advanced: persistence and snapshots

Copy the path, share the rest

An insert walks the new key’s hash down the tree, rebuilding each node it passes and leaving everything off that path untouched. The new root points to the rebuilt path and to the old, shared sub-trees; the old root still points only to the old ones. Select the copied path, the shared sub-trees, or both versions at once.

What to highlight · select one

v1 root v2 root (new) sub-tree A sub-tree C shared by both roots node B node B′ (rebuilt) + new leaf v2 rebuilds the root, the path node, and the new leaf — three nodes 

      

      
role: copy only the path

      
result: 3 rebuilt, the rest shared

    

    
An insert costs new nodes only along one root-to-leaf path — about
      log₃₂ n of them — and shares the rest. That is what makes an
      immutable map cheap to update and its old versions free to keep.

  


  

    
Advanced: persistence and snapshots

    

      
Because each insert keeps the old map intact and shares all but one path, a sequence of edits is a sequence of
        versions that overlap almost entirely. A history of a hundred edits does not cost a hundred copies of the map;
        it costs a hundred short paths, with every untouched sub-tree shared across all of them. That is the meaning of
        a persistent data structure: old versions stay valid and cheap, so holding a snapshot is
        nearly free.

      
For the portal’s page registry — read on every request, edited when a page is added — that
        is the property that matters: a new registry shares its structure with the one before it, so a LiveView can
        diff two snapshots by comparing references and skip the shared sub-trees entirely. F4.06 (CHAMP) keeps this
        sharing and adds a canonical shape, which makes those snapshot comparisons cheaper still; the
        stack’s BrandedChamp trie (F4.07) is that structure, keyed by branded Snowflake
        ids.

    

    
# v1 holds three pages; adding one returns v2 — v1 is untouched
v1 = %{"PGE0NXh7MFjxT6" => modules, "PGE0NbLeJJpTmr" => sorting, "PGE0NbWMtkolM0" => maps}
v2 = Map.put(v1, "PGE0NcQgyPQEbI", trees)

# only the nodes on the path to the new leaf are rebuilt
# v2's other sub-trees are the same references as v1's — shared, not copied
v1["PGE0NbWMtkolM0"] == v2["PGE0NbWMtkolM0"]   # true; v1 still works

    

      

        
F4.05.3 · path-copy sharing

        
An insert copies one path and shares the rest; old versions survive.

      

      
      

        
F4.06 · a canonical shape

        
CHAMP keeps the sharing and gives the tree one shape per map, so diffs are cheaper.

      

    

    
That completes F4.05: a HAMT packs each node with a bitmap, indexes by five-bit chunks of the
      hash, and shares structure on every insert. Next module:
      F4.06 — CHAMP maps, the compressed successor that
      splits the node into two bitmaps and two arrays — the next step of the persistent-map spine.

  


  

    
References

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

    

      
Sources

      
      
Related in this course