Immutability — Optimize & Reconcile¶

Immutability buys safety: no aliasing bugs, free thread-safety, trivial caching and equality. It is never free. Every "update" is logically a new object, and a naive implementation copies the whole structure. This file reconciles immutable by default with the handful of measured hot paths where copy cost, allocation pressure, or boxing actually shows up in a profile. Each scenario states the cost with concrete numbers, then resolves it with the smallest, most principled deviation — usually persistent structures or locally-scoped mutation, not abandoning immutability.

Table of Contents¶

1. Copy-on-every-update vs structural sharing (O(n) vs O(log n))
2. Defensive copy at the boundary vs unmodifiable view vs trust
3. Allocation/GC pressure from short-lived immutable objects
4. Autoboxing of immutable wrappers (Java)
5. Go value copies vs pointers; escape analysis
6. Building a list in a loop with + / with (O(n²) copies)
7. Transients: mutate locally, then freeze
8. String immutability and the StringBuilder lesson
9. Deep copy vs shallow copy of nested immutables
10. Recomputing derived values on every "updated" copy
11. Frozen-dataclass attribute-access overhead (Python)
12. Mutation in a hot path as a measured de-optimization
13. Rules of Thumb
14. Related Topics

Scenario 1 — Copy-on-every-update vs structural sharing¶

Scenario. A configuration service holds an immutable map of ~50,000 feature flags. On each toggle it produces a new map so readers never see a torn state:

// Naive immutable update: full defensive copy
public final class FlagStore {
    private final Map<String, Boolean> flags;          // 50,000 entries

    public FlagStore set(String key, boolean value) {
        var copy = new HashMap<>(flags);               // copies all 50,000
        copy.put(key, value);
        return new FlagStore(Map.copyOf(copy));
    }
}

Toggles arrive at ~2,000/sec during a rollout.

Measurement / reasoning. Each set copies 50,000 entries → 50,000 entry rehashes + ~50,000-element backing array allocation. At 2,000 toggles/sec that is ~10⁸ entry-copies/sec, plus ~2,000 short-lived arrays of ~400 KB each → ~800 MB/sec of garbage. The structure is O(n) per update where n is the whole map, even though one key changed.

// io.vavr.collection.HashMap — HAMT, structural sharing
import io.vavr.collection.HashMap;

public final class FlagStore {
    private final HashMap<String, Boolean> flags;
    public FlagStore set(String key, boolean value) {
        return new FlagStore(flags.put(key, value)); // copies ~4 nodes, shares the rest
    }
}

Scenario 2 — Defensive copy vs unmodifiable view vs trust¶

Scenario. A value object exposes its internal list. To preserve immutability it copies on the way in and on the way out:

public final class Route {
    private final List<Stop> stops;
    public Route(List<Stop> stops) { this.stops = new ArrayList<>(stops); } // copy in
    public List<Stop> stops() { return new ArrayList<>(stops); }            // copy out
}

// Renderer reads stops() 60×/sec for a 2,000-stop route:
for (int frame = 0; frame < 60; frame++)
    for (Stop s : route.stops()) draw(s);   // copies 2,000 stops, 60×/sec

Measurement / reasoning. The copy-out clones 2,000 elements 60 times/sec = 120,000 element-copies/sec for data that never changes. Pure waste — the caller only iterates.

private final List<Stop> stops;
public Route(List<Stop> stops) { this.stops = List.copyOf(stops); } // copy ONCE, in
public List<Stop> stops() { return stops; }                         // List.copyOf is already unmodifiable

public void forEachStop(Consumer<Stop> action) { stops.forEach(action); }
public int stopCount() { return stops.size(); }

Scenario 3 — GC pressure from short-lived immutable objects¶

Scenario. A pricing pipeline produces a fresh immutable Money per arithmetic step. A single quote does ~20 operations and the service handles 50,000 quotes/sec → ~10⁶ Money allocations/sec.

public final class Money {
    private final long minorUnits; private final String currency;
    public Money plus(Money o) { return new Money(minorUnits + o.minorUnits, currency); }
}

A teammate proposes a mutable accumulator "to reduce GC."

Measurement / reasoning. These objects are tiny (~24 bytes) and die within microseconds. That is exactly the workload a generational collector is built for: allocation is a pointer bump in the TLAB (a few ns), and a young-gen (minor) GC reclaims dead objects in O(live) — it never even visits the dead ones. The cost is proportional to survivors, and these never survive. Benchmark intuition: on HotSpot G1, ~10⁶ tiny ephemeral allocations/sec typically costs single-digit-millisecond pauses every few hundred ms — usually < 1% of throughput.

// Fused: one allocation for the result, none for the 20 intermediates.
long acc = 0;
for (LineItem li : items) acc += li.minorUnits();
return new Money(acc, currency);

Scenario 4 — Autoboxing of immutable wrappers (Java)¶

Scenario. An immutable event carries a numeric id stored as List<Long> (immutable wrapper) of matched user ids. A hot filter sums them:

List<Long> ids = event.matchedUserIds(); // immutable, but Long not long
long total = 0;
for (Long id : ids) total += id;          // unboxing per element

The list has ~1M ids and this runs per request.

Measurement / reasoning. Each Long is a heap object (~16 bytes) versus 8 bytes for a long, and the boxed list also stores 8-byte references → ~3× the memory and a pointer-chase per element (cache-hostile). The loop unboxes 1M times/request. Boxed-collection numeric loops commonly run 3–6× slower than a long[] due to cache misses and unbox overhead. Worse: valueOf only caches Long in −128..127, so ids outside that range allocate.

public final class Event {
    private final long[] ids;                       // primitive, no boxing
    public Event(long[] ids) { this.ids = ids.clone(); }     // copy once in
    public long idSum() { return Arrays.stream(ids).sum(); } // no boxing, vectorizable
}

Scenario 5 — Go value copies vs pointers, and escape analysis¶

Scenario. Go has no final/const for structs; immutability is a convention enforced by passing/returning values (copies). A geometry type is large:

type Mesh struct {
    Vertices [256]Vec3 // 256 * 24 bytes = 6 KB, by value
    Name     string
}

func translate(m Mesh, d Vec3) Mesh { // copies 6 KB in, 6 KB out
    for i := range m.Vertices { m.Vertices[i] = m.Vertices[i].Add(d) }
    return m
}

// Hot loop, 100k meshes:
for i := range meshes { meshes[i] = translate(meshes[i], delta) }

Measurement / reasoning. Each call copies ~6 KB in and ~6 KB out = ~12 KB/call × 100k = ~1.2 GB of memcpy per frame. Value semantics give immutability (the caller's Mesh is untouched until reassigned) but at full-copy cost for large structs. Meanwhile a small value type like Vec3 (24 bytes) copies essentially for free and stays on the stack — escape analysis (go build -gcflags='-m') proves it never escapes, so there is zero GC involvement.

func translated(m *Mesh, d Vec3) *Mesh { // returns a NEW mesh; input untreated
    out := *m                            // one 6 KB copy
    for i := range out.Vertices { out.Vertices[i] = out.Vertices[i].Add(d) }
    return &out
}

Scenario 6 — Building a collection in a loop (O(n²))¶

Scenario. Code builds an immutable list by repeatedly producing a new list with one more element — the most common accidental quadratic in immutable code.

# Python — list "+" creates a new list each time
result = ()                       # immutable tuple
for x in source:                  # n = 1,000,000
    result = result + (transform(x),)   # copies the whole tuple each iteration

// Java — same shape with an "immutable" copy per step
List<T> result = List.of();
for (T x : source) {
    var next = new ArrayList<>(result); // copies all so-far elements
    next.add(transform(x));
    result = List.copyOf(next);
}

Measurement / reasoning. Iteration k copies k elements → total work 1+2+…+n = n(n+1)/2 = O(n²). For n = 1,000,000 that is ~5×10¹¹ element-copies — minutes-to-hours instead of milliseconds, and ~n intermediate arrays of growing size as garbage.

buf = []                          # local, never escapes
for x in source:
    buf.append(transform(x))      # amortized O(1)
result = tuple(buf)               # freeze once -> immutable
# Or simply: result = tuple(transform(x) for x in source)

List<T> result = source.stream()        // builder-internal mutation, frozen output
    .map(this::transform)
    .toList();                          // immutable, built in O(n)

Scenario 7 — Transients: mutate locally, then freeze¶

Scenario. You must apply 100,000 updates to a persistent map (Scenario 1) before publishing it. Even at O(log n) per update, each put allocates ~4 fresh path nodes → ~400,000 transient node allocations for an intermediate map nobody else will ever observe.

;; Clojure — persistent, but 100k intermediate versions
(reduce (fn [m [k v]] (assoc m k v)) {} updates) ; ~4 nodes allocated per assoc

Measurement / reasoning. Persistent updates are cheap per step but still allocate a new path each time. For a batch of 100k updates building one final map, those ~400k intermediate nodes are pure garbage — the structural sharing benefit (keeping old versions) is worthless when no old version is retained.

(persistent!
  (reduce (fn [t [k v]] (assoc! t k v))      ; mutates in place, no per-step path copy
          (transient {}) updates))

Scenario 8 — String immutability and the StringBuilder lesson¶

Scenario. Building a CSV row by concatenation — the canonical immutable-copy trap, because strings are immutable in Java, Python, and Go alike:

String row = "";
for (String field : fields)       // m fields per row
    row += field + ",";           // each += allocates a new String

Measurement / reasoning. Strings are immutable, so += allocates a brand-new char array each time and copies all characters so far → O(m²) characters copied per row (same quadratic as Scenario 6). For a row of 200 fields averaging 16 chars, that is ~200×3200/2 ≈ 320k char-copies per row. At 100k rows/sec that is ~3×10¹⁰ char-copies/sec. (Note: the Java compiler rewrites a + b + c within one expression into a StringBuilder, but it cannot fuse across loop iterations — the per-iteration += is the killer.)

var sb = new StringBuilder(fields.size() * 16); // pre-size to avoid regrowth copies
for (String field : fields) sb.append(field).append(',');
String row = sb.toString();                     // one immutable String

row = ",".join(fields)            # C-level single-pass join; O(total length)

var b strings.Builder
b.Grow(len(fields) * 16)          // pre-size like StringBuilder capacity
for _, f := range fields { b.WriteString(f); b.WriteByte(',') }
row := b.String()                 // immutable string, no extra copy (builder hands off its buffer)

Scenario 9 — Deep copy vs shallow copy of nested immutables¶

Scenario. An "update one field" on a nested immutable tree deep-copies everything:

import copy
@dataclass(frozen=True)
class Org:
    name: str
    teams: tuple          # tuple of Team, each with a tuple of Member

def rename_org(org, new_name):
    clone = copy.deepcopy(org)        # copies every team and member
    object.__setattr__(clone, "name", new_name)
    return clone

Measurement / reasoning. deepcopy recursively clones every node — for an org with 50 teams × 100 members = 5,000 objects, that is ~5,000 allocations to change one top-level string. The subtrees are themselves immutable and never change, so copying them is pure waste.

@dataclass(frozen=True)
class Org:
    name: str
    teams: tuple
    def with_name(self, new_name):
        return dataclasses.replace(self, name=new_name) # shares the SAME teams tuple

Scenario 10 — Recomputing derived values on every copy¶

Scenario. An immutable Polygon recomputes its area, bounding box, and hash every time it is constructed — including the thousands of intermediate copies produced while transforming it:

public final class Polygon {
    private final List<Point> points;
    public Polygon(List<Point> points) {
        this.points = List.copyOf(points);
        this.area = computeArea(this.points);   // O(n)
        this.bbox = computeBbox(this.points);    // O(n)
        this.hash = points.hashCode();           // O(n)
    }
    public Polygon translate(Vec d) { /* new Polygon(shifted points) */ }
}

A transform applies 1,000 translations; each constructs a new Polygon and re-derives area/bbox over n points.

Measurement / reasoning. For an n=10,000-vertex polygon, each copy does ~3 O(n) passes = ~30,000 ops, × 1,000 transforms = ~3×10⁷ ops — most of it recomputing an area that is translation-invariant and a bbox that just shifts by d. The eager precompute, normally a win (compute-once), becomes a tax when the object is copied frequently.

public Polygon translate(Vec d) {
    return new Polygon(shift(points, d), this.area, this.bbox.shift(d)); // O(n) shift, no re-derive
}

private volatile Double cachedHash;
public int hashCode() {
    Double h = cachedHash;
    if (h == null) cachedHash = h = (double) points.hashCode();
    return h.intValue();
}

Scenario 11 — Frozen-dataclass attribute-access overhead (Python)¶

Scenario. A simulation reads particle.x, particle.y, particle.vx, particle.vy billions of times. The particle is a @dataclass(frozen=True) for safety.

@dataclass(frozen=True)
class Particle:
    x: float; y: float; vx: float; vy: float

Measurement / reasoning. frozen=True overrides __setattr__/__delattr__ to raise — this only affects writes, so reads are normal attribute lookups and frozen adds no read overhead. The real cost in tight numeric loops is that any Python object attribute access is a dict lookup (~tens of ns), and a per-object Python instance is ~56+ bytes with no memory locality. Construction is slightly slower (frozen __init__ uses object.__setattr__), but that is irrelevant to a read-bound loop.

@dataclass(frozen=True, slots=True)
class Particle: x: float; y: float; vx: float; vy: float

xs = np.array([p.x for p in particles])   # build once
xs += vxs * dt                            # vectorized, C-speed, no per-object lookup

Scenario 12 — Mutation in a hot path as a measured de-optimization¶

Scenario. A real-time pathfinder (A* over a 1M-cell grid) used an immutable persistent set for the open/closed frontier. A profiler shows 40% of CPU in HAMT node allocation; the per-frame budget (16 ms) is blown.

// Persistent set update on every node expansion (millions/sec)
closed = closed.Add(node) // allocates path nodes each call; Go has no std HAMT — hand-rolled

Measurement / reasoning. A expands millions of nodes per query; each Add/Contains on a persistent set allocates and chases pointers. The frontier is a transient, single-threaded, function-local* accumulator that is never shared and never needs old versions — every property that justifies immutability is absent here. Flame graph: ~40% allocation + GC, search latency ~70 ms vs the 16 ms budget.

func aStar(grid *Grid, start, goal Cell) []Cell {
    closed := make(map[Cell]struct{}, grid.size/4) // plain mutable map, local
    open   := &cellHeap{}
    // ... expand: closed[node] = struct{}{}; O(1), zero per-op allocation
    return reconstruct(came, goal) // the RESULT is a fresh immutable slice
}

Decision flow¶

Rules of Thumb¶

1. Immutable by default; deviate only with a number. Mutation is the exception you justify with a profiler reading, confine to a scope, and document — never the default reached for on a hunch.
2. A "cost of immutability" complaint is usually a "cost of naive full copy" complaint. Before abandoning immutability, switch the data structure: persistent/HAMT update is O(log n) with structural sharing, not O(n).
3. Copy once, at the trust boundary. Defensive copy on input where the caller might still mutate; never copy on a getter that already returns immutable data — return an unmodifiable view or the frozen object itself.
4. Build immutable collections with a mutable local buffer, then freeze. StringBuilder → String is the template. Concatenating/+-ing immutables in a loop is O(n²); a builder is O(n).
5. Transients for batch construction of persistent structures. Mutate internal nodes in place, persistent!/freeze once. Use only when no intermediate version is observed and it stays on one thread.
6. Generational GC makes many small short-lived immutables cheap. Allocation rate alone is not a problem — survivor pressure is. Don't pool/mutate to "reduce GC" without a flame graph showing GC dominates.
7. Representation is orthogonal to immutability. Boxing, slots, structure-of-arrays, value vs pointer — choose the densest layout that preserves the invariant. Frozen costs nothing on reads.
8. Never deepcopy an immutable tree. Shallow-copy the changed spine and alias the unchanged immutable subtrees — safe precisely because they're immutable.
9. Immutability makes memoization free of correctness locks. Cache derived values lazily; propagate transform-invariant derived data instead of recomputing it on every copy.
10. In Go, "immutable" is a discipline, not a keyword. Pass small values by value (free immutability, stays on stack); share pointers to never-mutated structs for large ones; confirm with -gcflags='-m'.
11. Confined mutation behind an immutable boundary is still clean. A function-local mutable accumulator that never escapes keeps the public contract immutable — that is the correct way to build immutable results, not a violation.

Related Topics¶

• find-bug.md — aliasing bugs when a "local" mutable buffer or returned reference accidentally escapes.
• professional.md — communicating a deliberate immutability/performance trade-off in code review.
• ../README.md — the positive rules of this Immutability chapter.
• ../05-objects-and-data-structures/README.md — why exposing internal collections at all is the deeper smell behind defensive copies.
• ../../functional-programming/README.md — persistent data structures, structural sharing, and pure-function discipline that immutability rests on.