jonnifyelixir
F4 / F4.10 / profiling

F4.10 · part 3 of 3 · choosing a lookup

Profiling & complexity

Every active session has to be found on every request. Keep sessions in a list and a lookup scans it — O(n), growing with the user base. Keep them in the branded-CHAMP store of F4.09 and a lookup descends a few trie levels — O(log₃₂ n), effectively flat. The right structure is not a matter of taste here; you can read the difference straight from the code and watch it widen as the Portal grows.

The same lookup, the two structures, at three user-base sizes. Pick a size and compare the work each one does.

Read the cost from the shape Advanced: measure, but reason first

Read the cost from the shape

A list scan touches up to one element per entry; a CHAMP lookup touches one node per five bits of the hash, so its depth grows with the logarithm of the count, base thirty-two. Pick a size to see both as operation counts.

Active sessions · select one

List.keyfind/3 · O(n) 1,000 comparisons Champ.get/2 · O(log₃₂ n) 2 node hops bars are on a logarithmic scale; labels are the actual operation counts about 500× fewer operations 

      

      
list scan: 1,000 ops

      
map lookup: 2 hops

    

    
The list and the map agree at small sizes and diverge without bound. At ten million sessions the
      scan is millions of comparisons and the map is five hops — the reason the Portal’s store is a CHAMP.

  


  

    
Advanced: measure, but reason first

    

      
Reasoning about complexity tells you how a cost scales; measuring with
        :timer.tc/1 tells you what it is at one size on one machine. You want both, in that
        order. Big-O picks the structure — a lookup that must stay cheap as the user base grows cannot be a list
        — and a measurement confirms the constant factors are sane once it is built. Reaching for the profiler
        first tends to optimise a fast operation while an O(n) one waits to dominate at scale.

      
Two honest caveats. O(log₃₂ n) is not literally
        O(1): it is at most about six hops for any count up to a billion, so it is flat in
        practice but still grows. And constant factors cut the other way at small sizes — a list of ten entries
        is contiguous and needs no hashing, so it beats a trie there. The point is not that maps are always faster;
        it is that the Portal’s collections grow, and a structure whose lookup is logarithmic stays usable where
        a linear one does not.

    

    
# reason: which scales? then measure to confirm the constant factor
{t_list, _} = :timer.tc(fn -> List.keyfind(sessions, sid, 0) end)  # O(n)
{t_map,  _} = :timer.tc(fn -> Champ.get(store, sid) end)            # O(log₃₂ n)

# at 10_000_000 sessions: ~10_000_000 comparisons vs ~5 node hops
# the list keeps growing; the map barely moves — so the store is a CHAMP

    

      

        
a structure choice

        
List or map for the session store.

      

      
      

        
a complexity

        
O(n) that grows with users, or O(log₃₂ n) that stays flat.

      

    

    
That completes F4.10: the request validates with a with chain, reports
      stream lazily, and lookups ride a structure chosen for how it scales. Next module: F4.11 —
      Dynamic programming in Elixir.

  


  

    
References

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

    

      
Sources

      
      
Related in this course