Functional Updates and State Diffing TODO

Algorithms · Day 4 / 100 · A. Advanced Algorithms & Data Structures (Day 1-19)

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.

Where it lands in Jayverse

• Verex: benchmark before choosing path copying for the order book. Turn the trade-off the concept describes into an actual decision — measure GC pressure and cache-miss cost of HAMT-style snapshots against a mutable book under real order volume, then pick, instead of assuming O(log n) makes it free.
• Wallet: give transaction simulation the same structural sharing. When a user edits a simulated transaction before signing, snapshot and revert speculative state cheaply with path copying rather than deep-copying the whole simulated state each edit.
• gitboard: diff dashboard states by reference, not by value. If gitboard shows how a service's state changed between refreshes, skip subtrees whose references are unchanged instead of deep-diffing the whole payload each time.

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/.

한국어

함수형 업데이트와 상태 diff TODO

Algorithms · Day 4 / 100 · A. 고급 알고리즘·자료구조 (Day 1–19)

copy-on-write의 실제 비용

개념

함수형 업데이트는 기존 자료구조를 변형하지 않고 변경분만 반영한 새 버전을 만들어 반환하는 방식이다. 이를 값싸게 하는 핵심 기법이 path copying으로, 루트에서 수정 지점까지의 경로에 있는 노드만 복사하고 나머지 서브트리는 이전 버전과 포인터로 공유한다(structural sharing). 균형 트리나 HAMT 같은 트라이 계열에서는 경로 길이가 O(log n)이므로 한 번의 업데이트 비용도 O(log n) 노드 복사로 억제된다. 대신 진짜 비용은 점근 복잡도가 아니라 상수항에 숨어 있다. 업데이트마다 새 노드를 할당하므로 allocation·GC 압력이 커지고, 노드가 힙에 흩어져 포인터 추적이 늘어나 캐시 지역성이 나빠진다. 반면 이전 버전이 그대로 남으므로 두 버전의 diff는 참조가 같은 서브트리를 통째로 건너뛰며 변경된 부분만 훑을 수 있다.

불변 상태를 쓰는 프론트엔드·상태머신 코드에서 "복사는 O(log n)이니 공짜"라고 믿다가 GC 스파이크와 캐시 미스로 처리량이 무너지는 일이 흔하다. 반대로 diff를 참조 비교로 처리할 수 있다는 점은 리렌더·변경 전파 최적화의 근거가 된다.

코드 · 수식

# 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

연습

해시맵을 (1) 매번 전체 복사, (2) HAMT식 path copying, (3) 가변 맵 세 가지로 구현해 10만 회 삽입 시 실행 시간·할당량·GC 시간을 측정해 비교하라.

실무 · Verex 연결

EVM은 revert를 위해 상태 변경을 저널에 쌓아 스냅샷/롤백하고 상태 트라이 자체도 블록마다 경로 복사로 새 루트를 만드는데, 이는 copy-on-write 구조가 그대로 온체인에 나타난 사례다. Verex의 인메모리 오더북도 스냅샷 기반 롤백이나 버전별 diff 전송을 설계할 때 같은 트레이드오프를 만난다.

Jayverse에서의 위치

• Verex: 오더북에 패스 카피를 적용하기 전에 벤치마크부터 한다. 개념이 설명하는 트레이드오프를 실제 결정으로 바꾼다. 실제 주문량 아래에서 HAMT 방식 스냅샷의 GC 압력과 캐시 미스 비용을 뮤터블 오더북과 비교해 측정한 뒤 고른다. O(log n)이라서 공짜라고 가정하지 않는다.
• Wallet: 트랜잭션 시뮬레이션에도 같은 구조적 공유를 적용한다. 사용자가 서명 전 시뮬레이션된 트랜잭션을 수정할 때, 매번 전체 시뮬레이션 상태를 깊이 복사하는 대신 패스 카피로 추측 상태를 값싸게 스냅샷하고 되돌린다.
• gitboard: 대시보드 상태는 값이 아니라 참조로 diff한다. gitboard가 새로고침 사이 서비스 상태 변화를 보여준다면, 매번 전체 페이로드를 깊이 비교하는 대신 참조가 바뀌지 않은 서브트리는 건너뛴다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.