Lesson 18: What the HAMT debate reveals about the gap between design philosophy and performance reality
When I wrote about immutability in Clojure last month, I focused on the philosophical argument: that treating state as a value rather than a mutable location changes how you reason about programs. What I didn't dig into was the performance story — and it turns out that story has a genuinely interesting wrinkle that the Clojure community has been quietly arguing about for years.
Here's the wrinkle: Clojure's persistent data structures are not O(1). They're O(log n). And the way that distinction got blurred — by the language's own creator, in a HOPL paper — is worth understanding, because it reveals something real about how language designers think about the gap between theoretical bounds and practical behavior.
The Data Structure Underneath Everything
Clojure's maps, sets, and vectors are built on a data structure called the Hash Array-Mapped Trie, or HAMT — invented by Phil Bagwell and adapted by Rich Hickey for Clojure's persistent collections. The HAMT is a tree with a branching factor of 32, meaning each node can have up to 32 children. Because it's a tree, lookup time is proportional to tree depth, which is proportional to the logarithm of the number of elements.
Scott Burson, writing on his blog, puts the complexity argument plainly: the correct description of HAMT operations is O(log n), not "effectively O(1)" or "near-constant." The base-32 branching factor means the tree stays very shallow in practice — 32⁴ is over a million, so a four-level tree handles maps with more than a million entries — but that's a constant-factor argument, not a complexity argument. Big-O notation ignores constant factors by definition.
What makes this interesting is that Hickey himself, in his HOPL 2020 paper A History of Clojure, wrote that performance was "more akin to O(1) than the theoretical bounds of O(log N)." Burson's reading of that sentence is that Hickey may have been testing collections that never grew large enough for the logarithmic behavior to emerge — that at the sizes he benchmarked, the tree-walking time was dominated by the cost of hashing the key, making the whole operation look flat. Which is plausible. But it's not the same as the operation being O(1).
This matters not because Clojure's collections are slow — they're not, for most workloads — but because the framing shapes how programmers think about when to reach for them and when to reach for something else.
What "Effectively Constant" Actually Costs You
The practical consequences of the O(log n) reality show up at the edges. A recent performance investigation by Ertu into a compute-heavy Clojure workload — 100,000 matrix transforms per frame — found that the JVM's JIT compiler cannot auto-vectorize loops the way Clang can, and that even small indirections (like storing a vector "species" descriptor in a Clojure var instead of a compile-time constant) can cause a 10x slowdown due to the JIT losing its ability to fold the value. The lesson there isn't that Clojure is slow; it's that the performance model is layered and non-obvious, and that "it's fast enough in practice" can stop being true in ways that are hard to predict without measurement.
The same logic applies to persistent collections. For the vast majority of application code — web services, data pipelines, business logic — the difference between O(log n) with a base-32 tree and O(1) is genuinely invisible. But in tight loops over large collections, it isn't. And if you've been told the operations are "effectively constant," you might not think to look there when profiling.
The Clojure community's own tooling reflects this awareness: the ecosystem has developed profiling tools like clj-async-profiler and flamegraph support precisely because "it should be fast" and "it is fast" are different claims that require measurement to distinguish.
The Design Lesson That Survives the Correction
None of this undermines the core design argument for persistent data structures. Immutability genuinely does simplify concurrent code — you can share a persistent map across threads without locks because no one can mutate it. The Concurrency Freaks blog, writing from the perspective of concurrent algorithm researchers, acknowledged this directly: even critics of the performance tradeoffs recognized that persistent structures "simplify the way we code" and that the immutable model addresses real problems with object-oriented concurrency.
The HAMT is a genuinely clever piece of engineering. Bagwell's invention, Hickey's adaptation — the base-32 branching factor is a real insight, not a marketing claim. The tree stays shallow enough that the logarithmic overhead is small in absolute terms for almost any realistic collection size.
But "small in absolute terms" and "O(1)" are not the same thing. The design philosophy — that immutability is worth a performance cost, and that the cost is manageable — is sound. The specific claim that the cost is negligible enough to describe as constant-time is where the argument overreaches.
What Clojure actually demonstrates is something more interesting than "immutability is free." It demonstrates that a carefully chosen data structure can make immutability cheap enough to be the default — and that "cheap enough" is a different, more honest, and ultimately more useful claim than "free."
That's the lesson worth carrying into whatever language you're working in next.
