What Lies Beneath - A Deep Dive Into Clojure's Data Structures
summary
Explains how Clojure implements persistent maps and vectors using a bitmapped array-mapped trie with 32-way branching (5-bit symbols), bitwise shifting/masking and CPU popcount to turn hash codes into path digits. Claims lookups on huge maps take a handful of steps (roughly 6 hops to a leaf for millions of keys), persistence via path-copying of affected nodes works with excellent sharing, sorted maps use red‑black trees, vectors use a tail pointer for fast conj, and int-map or RRB variants solve heavy-merge and concat/subvec pain points.
AI-written summary · about
chapters (31)
- 0:00Intro
- 0:53TOWERS OF ABSTRACTION
- 3:01ABSTRACT DATA TYPE
- 4:06THE CHALLENGE
- 4:30CHALLENGE ACCEPTED
- 5:11KEY IDEAS
- 5:21STRUCTURAL SHARING
- 6:47HYBRID STRUCTURES
- 7:04LETS DIVE IN!
- 7:54THE MAP INTERFACE
- 8:09WHAT MAKES A GOOD MAP?
- 9:08KEY VALUE PAIRS
- 9:46TREES TO THE RESCUE
- 11:20RED BLACK TREES
- 13:03A PRETTY GOOD MAP!
- 13:26CONSTRAINTS
- 15:07FINITE STATE MACHINE
- 15:35LOOKUP TABLES
- 16:33NOT A GREAT MAP!
- 20:39USING BITMAPS
- 23:18A DECENT MAP
- 23:53STEP 2
- 25:31BIT JUGGLING!
- 26:40BEST COMMENT EVER.
- 27:20NODE POLYMORPHISM
- 27:48EXAMPLE
- 29:10REGULAR HASH TABLE?
- 29:52INTUITION
- 30:42THE TAIL OPTIMIZATION
- 34:04Reading List
- 34:58QUESTIONS?
