If you need to update a single element in an immutable list containing one million items, you do not have to copy all one million elements. Instead, functional ecosystems like Scala, Clojure, and Immutable.js use a 32-way tree structure (a bitmapped vector trie). Through structural sharing, they only copy a tiny path of four nodes, preserving memory and ensuring near-instant updates.
I often chat with developers who are highly skeptical of immutability purely because of performance concerns. On paper, it sounds terrible: if I change one item in an immutable list of a million elements, I should have to copy all one million elements to keep the original state intact. I completely understand why engineers look at that overhead and worry about the sheer garbage collection pressure and CPU cycles it would waste.
But in practice, it works incredibly fast. I want to take you under the hood of how functional languages and libraries pull this off without blowing up your memory budget.
How do immutable lists update without copying everything?
I find it easiest to understand this by looking at how immutable lists replace flat arrays with trees. Instead of copying a flat array, these data structures copy only the specific nodes along the direct path to the modified element, leaving the rest of the tree completely shared.
To explain this, I like to use the analogy of a nested directory of files. Imagine you have a nested directory of folders on your computer. If you want to modify a single text file inside a deeply nested folder, you do not copy the entire hard drive. You only create a new path of folders leading to your new, modified text file. The rest of your file system remains completely untouched.
In an immutable vector, every node in the tree holds up to 32 elements. Because the tree is so wide, it is incredibly shallow. When you update a single item, the system only duplicates the small 32-element arrays along the direct path to that item. It then links the new root node to these new copies, while the rest of the pointers point directly back to the original unmodified branches of the old tree.
What is structural sharing in functional programming?
I define structural sharing as an optimization technique where multiple versions of a data structure share references to identical, unmodified nodes. This allows us to create new versions of our data with virtually zero memory overhead because we only allocate memory for the changes.
Here is a quick look at how a flat array copy compares to a 32-way bitmapped trie copy during updates:
| Feature | Flat Array (Naive Copy) | Bitmapped Trie (Structural Sharing) |
|---|---|---|
| Time Complexity (Lookup) | O(1) | O(log base 32 of N) (effectively O(1)) |
| Time Complexity (Update) | O(N) | O(log base 32 of N) (effectively O(1)) |
| Memory Overhead (Update) | Copies all N elements | Copies at most 4-6 small nodes |
| Garbage Collection Pressure | Very high for large N | Extremely low |
How does the math behind a 32-way trie work?
I like to break down the math of a 32-branching factor to show how incredibly flat these trees actually remain. Because each node can branch 32 times, a tree with a depth of just four levels can hold over a million items, meaning I never have to traverse more than four hops to read or update an element.
I find it helpful to map out the exponentiation of a branching factor of 32 to show how this scales:
- Level 1: 32 elements
- Level 2: 32 * 32 = 1,024 elements
- Level 3: 1,024 * 32 = 32,768 elements
- Level 4: 32,768 * 32 = 1,048,576 elements
- Level 5: 1,048,576 * 32 = 33,554,432 elements
If you have a list of one million items, any single element is at most four hops away from the root of the tree. To update that element, the system only copies four nodes of 32 elements each. You copy 128 references instead of one million.
This makes the time complexity log base 32 of N. For all practical purposes in software engineering, this is effectively constant time, O(1). Even if you scale up to a billion items, the tree only reaches six levels deep.
Here is how simple this looks in practice when using a library like Immutable.js:
import { List } from 'immutable';
// Creating a list of one million elements
const originalList = List(Array.from({ length: 1000000 }, (_, i) => i));
// This set operation only copies 4 tiny nodes under the hood
const updatedList = originalList.set(500000, 999999);
console.log(originalList.get(500000)); // Outputs: 500000
console.log(updatedList.get(500000)); // Outputs: 999999
Both originalList and updatedList coexist perfectly, and they share 99.9% of their memory footprint.
FAQ
Why is the branching factor specifically 32?
The branching factor of 32 is chosen because it aligns beautifully with modern CPU cache lines. Walking a node with 32 pointers minimizes CPU cache misses, making memory access incredibly fast while keeping the tree shallow enough to limit lookups to a handful of hops.
Is structural sharing thread-safe?
Yes. Because the nodes are strictly read-only, multiple threads can read the shared parts of the tree simultaneously without any locks or risk of race conditions. If a thread needs to write, it simply creates its own path of new nodes without affecting the other threads.
Do arrays and trees behave differently for sequential reads?
Yes. Because a vector is a tree under the hood, sequential iteration is slightly slower than traversing a flat, contiguous memory array. However, engines optimize this by processing nodes in chunks of 32, minimizing the performance penalty during standard loops.
Top comments (0)