jonnifyfsharp

Module C4.06

CHAMP maps

The same lookup as a HAMT, a smaller node, and one canonical shape per map — the structure a persistent registry calls for.

Inside a CHAMP node The three dives EchoMQ in F# References

popcount finds a slot's index

datamap (8 of 32 slots) 0 1 2 3 4 5 6 7 data array (packed, no gaps) [0] [1] [2] select a set slot above dataIndex datamap bit = popcount(datamap & (bit-1))

datamap = 0b01001010 · bits 1, 3, 6 set
Pick a set slot. Its position in the packed data array is the count of set bits below it.

Inside a CHAMP node

A CHAMP — Compressed Hash-Array Mapped Prefix-tree — is the compressed successor to the HAMT of C4.05. It keeps the same O(log₃₂ n) lookup but lays each node out differently. Where a HAMT mixes inline entries and child pointers in one array, a CHAMP splits its 32 slots into two groups: the datamap bitmap marks the slots holding key/value entries, the nodemap marks the slots holding sub-nodes. Each kind lives in its own packed array, so there are never gaps to skip.

This is the F# reflection of the Elixir course's E4.06; it re-derives the same three consequences of that split — the layout, cache-friendly iteration, and the canonical shape that makes equality cheap — and adds the F# implementation and cost notes. One difference matters up front: F#'s built-in Map is a balanced tree, so on .NET a CHAMP is a structure you build, not one FSharp.Core hands you.

The angle · select one (8 of 32 slots shown)

datamap → entries (packed) k→v k→v nodemap → sub-nodes (packed) ● ● canonical form one shape per map two bitmaps, two packed arrays — no empty slots 

      

      
role: two bitmaps, two dense arrays

    

    
The split is the whole idea. Keeping entries apart from sub-nodes, each packed with no gaps,
      is what makes a CHAMP smaller than a HAMT, quicker to walk, and canonical — the three dives take each
      consequence in turn.

  


  
  

    
The three dives

    

      
In order: how a node is laid out, why iteration is cache-friendly, and how the canonical shape makes the
        HAMT→CHAMP improvement concrete — each tied to the persistent registry the F# bus port keeps. Every
        // val it: echo in the dives was produced by dotnet fsi.

    

    

      live module hub
      built dive ready
      soon specified
    

    

      

        
          
C4.06.1built

          
The CHAMP layout

          
Two bitmaps — datamap and nodemap — and two packed arrays, with a slot's position found by popcount.

          
  • layoutthe registry a queue needs: a branded-key→row persistent map

        
        
          
C4.06.2built

          
Iteration

          
Contiguous entries walk linearly in a fixed canonical order, with far fewer cache misses than a HAMT's interleaved slots.

          
  • iterationbrowsing the registry; how Store exposes its rows

        
        
          
C4.06.3built

          
HAMT vs CHAMP

          
The improvement over C4.05, why the bus's registry calls for CHAMP, and the swap-in-behind-the-same-surface discipline.

          
  • comparethe same lookup, a smaller node, a canonical shape

        
      

    

  


  
  

    
EchoMQ in F#

    
Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

    

      
The bus needs a registry: every job's row, reachable by its identity, persistent so an edit returns a new
        map and leaves the old one intact. That is what a CHAMP is for. The F# port — echo_fs,
        the skeleton of the Elixir echo/apps/echo_mq bus — declares the registry as a
        Map keyed by the branded id, and keeps the surface ready for the compact CHAMP to
        slot in behind it.

    


    

      
EchoMQ in F# · the registry

      
In echo_fs/EchoMQ/Store.fs, a queue's state holds its rows as a persistent map
        keyed by the branded id:

      
// echo_fs/EchoMQ/Store.fs — "Rows are a Map keyed by branded id"
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>
      // ... schedule, active, dead, paused, counts }

      
That Rows: Map<string, Job> is an F# balanced tree today. It
        stands in for the production branded CHAMP. The honest framing the port’s own README states:
        the in-memory Store stands in for the branded CHAMP behind the same
        enqueue/claim/complete/retry/promote/reap surface, “so the durable backing
        swaps in with no caller change”.

      
Living status. The production Elixir bus is backed by a branded CHAMP;
        echo_fs does not implement a CHAMP yet — its Store.Rows
        is a Map standing in for it. The compact CHAMP and the Valkey transport
        (EchoMQ.Connector, listed coming soon in the README) land next, behind
        the same surface.

    


    

      

        
C4.05 · the HAMT

        
One bitmap, one array per node, mixing entries and children — the persistent map underneath F#’s tree.

      

      
      

        
C4.06 · the CHAMP

        
Two bitmaps, two packed arrays — canonical, smaller, faster to walk: the compact form the registry becomes.

      

    

  


  
  

    
References

    

      

        
Sources

        
      

      

        
Related in this course