Functional Updates and State Diffing TODO
Concept
A functional update leaves the existing data structure untouched and instead returns a new version that reflects only the change. The key technique that makes this cheap is path copying: only the nodes along the path from the root to the modification point are copied, while the rest of the subtrees are shared by pointer with the previous version (structural sharing). In balanced trees or trie-based structures like HAMTs, the path length is O(log n), so a single update is bounded by O(log n) node copies. But the real cost hides not in the asymptotic complexity but in the constant factor. Every update allocates new nodes, which increases allocation and GC pressure, and scatters nodes across the heap, which hurts cache locality due to more pointer chasing. On the upside, since the previous version stays intact, diffing two versions can skip entire subtrees whose references are identical and only walk the parts that actually changed.
In frontend and state-machine code that relies on immutable state, it's common to assume "copying is O(log n), so it's basically free" — and then watch throughput collapse under GC spikes and cache misses. On the flip side, the fact that diffing can be done by reference comparison is exactly what justifies re-render and change-propagation optimizations.
Code & Formula
# Day 4: 함수형 업데이트와 상태 diff — copy-on-write의 실제 비용
# 불변 이진트리(배열)를 path copying으로 갱신하고, 두 버전의 diff를 노드 공유 여부로 빠르게 계산한다.
class Leaf:
__slots__ = ("value",)
def __init__(self, value):
self.value = value
class Branch:
__slots__ = ("left", "right")
def __init__(self, left, right):
self.left = left
self.right = right
def build(values):
if len(values) == 1:
return Leaf(values[0])
mid = len(values) // 2
return Branch(build(values[:mid]), build(values[mid:]))
def update(node, index, value, size):
if size == 1:
return Leaf(value)
half = size // 2
if index < half:
return Branch(update(node.left, index, value, half), node.right) # right는 그대로 공유
return Branch(node.left, update(node.right, index - half, value, size - half))
def collect(node, out):
if isinstance(node, Leaf):
out.append(node.value)
else:
collect(node.left, out)
collect(node.right, out)
def count_leaves(node):
return 1 if isinstance(node, Leaf) else count_leaves(node.left) + count_leaves(node.right)
def diff(a, b, offset, changed):
if a is b:
return # 포인터가 같으면 서브트리 전체가 동일 -> 즉시 종료
if isinstance(a, Leaf):
if a.value != b.value:
changed.append(offset)
return
mid = offset + count_leaves(a.left)
diff(a.left, b.left, offset, changed)
diff(a.right, b.right, mid, changed)
n = 8
v0 = build(list(range(n)))
v1 = update(v0, 5, 999, n)
v2 = update(v1, 2, -1, n)
out0, out1, out2 = [], [], []
collect(v0, out0); collect(v1, out1); collect(v2, out2)
print("v0 =", out0)
print("v1 (index5 갱신) =", out1)
print("v2 (v1에서 index2 갱신) =", out2)
changed01 = []
diff(v0, v1, 0, changed01)
print("v0 -> v1 diff =", changed01, ", left 서브트리 공유:", v0.left is v1.left)
changed12 = []
diff(v1, v2, 0, changed12)
print("v1 -> v2 diff =", changed12, ", right 서브트리 공유:", v1.right is v2.right)
docs/code/algorithms/algorithms-4.py
Exercise
Implement a hash map three ways — (1) full copy on every update, (2) HAMT-style path copying, and (3) a mutable map — and measure execution time, allocation volume, and GC time over 100,000 insertions to compare them.
Practical Connection
The EVM stacks state changes in a journal for snapshot/rollback on revert, and the state trie itself produces a new root every block via path copying — a direct on-chain instance of a copy-on-write structure. Verex's in-memory order book runs into the same trade-off when designing snapshot-based rollback or per-version diff transmission.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.