Data Layout, Algorithms, and Locality

Part II followed work down through processors, memory, runtimes, storage, networks, virtual resources, and specialized devices. Part III changes the design question. The machine is no longer given one isolated operation; software chooses how to represent state, which work to perform, which work to defer, and which components must coordinate. Those choices compose the mechanisms beneath them.

The comparison unit is not “lookup” or “sort.” It is one correct workload outcome. For a representation (r), begin with a cost vector:

[ C_r(w) = \langle O_r, B_r, A_r, R_r, S_r, M_r, P_r \rangle ]

where (O) is logical work such as comparisons or probes, (B) is bytes touched at named boundaries, (A) is allocation and reclamation, (R) is irregular control flow, (S) is synchronization or ownership transfer, (M) is maintenance work under updates, and (P) is persistence or representation conversion. The workload (w) includes operation mix, size, key and value distributions, arrival phases, update semantics, concurrency, and the required result.

Big-O notation constrains how one component grows. It remains indispensable. It does not assign values to the rest of this vector, identify the active size range, describe a cache or storage hierarchy, or prove that the compared implementations return the same result. Part III therefore begins with a stricter rule: choose the asymptotically acceptable candidates, then charge the full path.

Big-O removes bad candidates; the workload orders the survivors

An (O(n)) scan cannot be rescued indefinitely when (n) grows and every item must be visited. An expected (O(1)) hash lookup does not become free. It may hash a long key, probe multiple locations, follow a pointer, miss in several caches, compare the key, and occasionally resize or reclaim storage. A binary search performs (O(\log n)) comparisons but visits nonadjacent positions. A sorted merge is (O(n+m)), yet can stream compact identifiers with predictable control flow. A tree preserves ordered operations and incremental updates while paying node, pointer, balancing, and allocation costs.

Constants matter most when the real operating range is far from the asymptotic crossover or when one implementation turns logical operations into cheaper physical work. That is not permission to dismiss growth. It is a requirement to locate the crossover under representative inputs and to include maintenance. A precomputed table can make reads cheap while moving cost into build time, memory, invalidation, and recovery. A compact scan can win at 64 items and fail at 64 million. The decision record should show both regions.

The result contract must be equal before time is compared. If one search returns an approximate candidate set and another returns exact authorized results, their durations do not answer the same question. If one path excludes deleted records from a snapshot while another sees concurrent deletion, their consistency semantics differ. Count correct, deadline-compliant outcomes over the same population.

Logical shape and physical shape are separate decisions

Arrays place elements in an addressable sequence. Their strengths are compact metadata, cheap indexed access, traversal locality, and efficient bulk movement. Insertion in the middle can move elements, and a large mutable array can make snapshots expensive unless ownership or chunking limits the copied region.

Linked structures make insertion or splicing cheap when the node is already known, but each node needs linkage and usually an allocation strategy. Traversal follows addresses chosen by placement rather than by the next logical position. The flexibility can turn one logical walk into many dependent memory accesses.

Trees preserve order, range operations, and bounded-height navigation. Their fan-out and node layout matter. A binary tree exposes many pointers and branches; a wider, packed tree spends each fetched block on more keys and children. The right node size depends on the boundary being optimized—cache, page, or storage block—and on update and concurrency rules.

Hash structures favor exact key access without order. Load factor, collision strategy, key representation, table growth, deletion markers, and iteration needs determine physical cost. A hash table that keeps control bytes and values compact can behave differently from a pointer-rich chained table even though both advertise expected (O(1)) lookup.

Bitmaps represent membership or small categorical state by position. They can combine sets with word-wise operations and very low logical bytes when the identifier universe is dense or can be mapped densely. Sparse universes require compression, chunking, or another mapping; a nominal one-bit test can still fetch a cache line or page for a random identifier.

Probabilistic structures spend bounded memory to answer a narrower question approximately. A Bloom filter answers “definitely absent” or “possibly present” without false negatives under its declared construction and lifecycle; it does not return the item or make “possibly present” exact. Frequency sketches estimate counts with bounded error under assumptions. Sampling estimates a population only when inclusion and weighting support the target inference. Approximation is a semantic design, not merely a smaller container.

No family wins in isolation. Ordered iteration, predecessor search, prefix compression, deletion rate, snapshotting, and range scans can outweigh point-lookup complexity. The physical structure should be named precisely enough that a profile can confirm its expected behavior.

Equivalent records can impose different memory work

Suppose a search candidate is logically described by a document identifier, tenant class, liveness flag, freshness epoch, score, and payload handle. An array of structures (AoS) stores those fields together for each candidate. A structure of arrays (SoA) stores one dense sequence per field. Both encode the same logical records; they favor different operations.

AoS is attractive when the path consumes most fields of one record before moving to the next. It keeps per-record construction and serialization intuitive. It can also pull cold score and payload bytes into a filter that initially needs only tenant class and liveness. Padding and alignment may increase the stride. A field update can acquire ownership of the same cache line used by readers of other fields.

SoA is attractive when one phase touches a few fields across many records, when dense values can be vectorized or compressed separately, or when hot mutable fields should not share lines with cold immutable fields. It increases the number of base pointers and can make insert/delete coordination harder. Reconstructing a whole record crosses arrays, and independent arrays must share an index and lifecycle contract.

Atlas Search filters 12,000 candidate documents for a large tenant. Authorization must be exact: no document can be returned without an authoritative membership decision. The first phase needs a four-byte tenant class and a one-byte liveness value. Eighteen percent survive and require eight cold bytes of freshness and score for the next phase.

The simple AoS model charges a 32-byte record for each candidate:

[ B_{AoS} = 12{,}000 \times 32 = 384{,}000\ bytes/query ]

The staged SoA model first touches five hot bytes for every candidate, then eight cold bytes for 2,160 survivors:

[ B_{SoA} = 12{,}000 \times 5 + 2{,}160 \times 8 = 77{,}280\ bytes/query ]

This is a modeled reduction of 79.875%. It is not a promise of the same latency reduction. Hardware may transfer data at cache-line granularity; prefetching, alignment, translation, vector width, runtime representation, and concurrent writes change actual traffic. The model earns an experiment: measure named memory-hierarchy events and elapsed time while checking identical outputs.

The computation order is as important as the storage. Filtering liveness and tenant class before reading score and payload makes cold work conditional. Sorting or grouping candidate identifiers by segment can turn random bitmap or page probes into clustered access, but only if the reorder cost and output-order restoration are charged. Pushing the cheapest predicate first is wrong when it has low selectivity and prevents a more selective vectorized pass; compare expected bytes eliminated per unit of work.

A cost table forces physical claims into the review

The companion fixture declares one logical model for the same 12,000-candidate operation:

These numbers are inputs to a falsifiable model, not measurements. “Logical bytes” estimates useful structure data selected by the operation; it is not last-level-cache traffic. The table deliberately separates comparisons from bytes, allocation, and branches so that a reviewer can ask which term is observed. A real benchmark should add build cost, resident and retained memory, mutation throughput, pause/reclamation work, synchronization, result cardinality, and relevant counter evidence.

The table also prevents a common category error. The sorted representation performs far more comparisons in this point-probe formulation, yet a sorted merge over two already ordered batches can be a streaming (O(n+m)) operation. Change the operation and the cost vector changes. Container labels are not results.

Indexes and materialization exchange future work for present obligations

An index duplicates some relation so a later operation can avoid scanning or computing it. Precomputation evaluates a stable function early. Materialization stores a derived result. Each can move a path from CPU or storage work to memory and maintenance, but each creates five obligations:

1. define the authoritative state and the derived state;
2. name when the derived state becomes visible;
3. bound freshness or version lag;
4. handle update, deletion, partial build, and schema change; and
5. prove rebuild and recovery before the old representation is removed.

Atlas can materialize a compact tenant-membership representation and a liveness bitmap. A query then intersects candidates with derived state before reading cold ranking fields. The speedup is useful only while authorization semantics remain exact. If updates arrive at 537/s and the derived view is allowed to lag, the product must define whether a newly revoked document can appear. For authorization, stale-positive behavior is usually unacceptable. The design may synchronously remove revocations, version the query snapshot, or fail closed while a shard is uncertain. “Eventually updated” is not enough.

Precomputation can also increase tail latency. A refresh storm competes with queries for memory bandwidth and cache capacity. Rebuilding every tenant after a schema change may exceed memory headroom. A large materialization can extend startup and recovery. Admission should distinguish normal, guarded, reject, and recovery states: defer optional refresh in guarded operation, reject before exactness is uncertain, rebuild from versioned exact state, validate a holdout, and restore load gradually.

Regular control flow helps only when it preserves useful work

Branches become expensive when their direction is hard to predict and the machine speculatively follows the wrong path. Replacing a branch with masking or partitioned passes can make control flow regular and expose vector work. It can also compute both sides, add instructions, or write a large temporary mask. The comparison is useful completions per resource, not “branchless” as a style rule.

Data distribution drives predictability. A liveness flag that is true for 99.99% of candidates behaves differently from a pseudo-random 50/50 flag. Sorted or grouped inputs can make runs predictable; a later shuffle can erase the result. Record branch instructions and misses for the representative distribution and inspect generated code when the compiler/runtime can transform the source.

Traversal order changes the reuse distance between accesses. Row-major versus column-major traversal, graph frontier ordering, key grouping, and loop interchange can determine whether a fetched block is consumed before eviction. Blocking or tiling makes a large computation operate on subproblems that fit a chosen memory level. Cache-oblivious algorithms recursively divide work without baking one cache size into the source, but their theoretical transfer advantage does not remove base cases, call overhead, associativity, translation, prefetch, or parallel scheduling effects. They are candidates to measure, not automatic replacements.

Working-set size needs a boundary. “The cache” is not one store: cores, sockets, accelerators, and storage paths have several levels and sharing rules. Report the active data and metadata footprint, reuse interval, access distribution, placement, and concurrency. A structure that fits alone may thrash beside another tenant or background rebuild. Chapter 10’s hierarchy and NUMA model supplies the physical evidence; this chapter supplies the representation hypothesis.

Mutation, immutability, and copy cost move the ownership boundary

Mutable structures update in place and can avoid whole-version copies. Concurrent mutation then needs ownership, synchronization, validation, or a carefully defined lock-free algorithm. Readers may observe intermediate state unless the structure provides a snapshot or transaction boundary. Reclamation becomes part of correctness when a reader can retain an old node.

Immutable structures make versions explicit. Readers can share a stable root without a writer changing reachable nodes. Path copying or structural sharing limits duplication to changed regions, but “immutable” does not mean allocation-free. High update rates can allocate nodes, increase pointer traversal, retain old versions, and delay reclamation. A flat copy-on-write array can be excellent for rare updates and disastrous for a large hot table.

Choose update semantics before syntax. Ask whether readers need a point-in-time snapshot, whether updates commute, how conflicts are detected, how long versions remain reachable, and what recovery must reconstruct. Separate data by ownership when possible. A single writer per shard can keep a compact mutable representation and publish immutable snapshots. Chapter 18 examines the coordination cost of that choice.

Approximation may nominate work; exact state must authorize it

A Bloom filter with (m) bits, (n) inserted items, and (k) well-distributed hash locations has the familiar approximate false-positive probability:

[ p \approx \left(1-e^{-kn/m}\right)^k ]

The fixture assigns 10 bits/item and seven hashes to 1.5 million items. Its modeled probability is about 0.819%. Among 9,840 nonmember candidates, that implies about 80.63 extra authoritative checks. False positives cost work; they do not change the result because every “possibly present” answer goes to exact state. A “definitely absent” response may safely avoid that check only while the construction and deletion lifecycle preserve the no-false-negative claim.

Use this decision path:

Can the result be approximate?
├─ no
│  ├─ Can approximation only nominate or reject work without changing truth?
│  │  ├─ yes → approximate prefilter → authoritative exact check
│  │  └─ no  → exact representation only
│  └─ specify snapshot, mutation, deletion, and recovery semantics
└─ yes
   ├─ define the error direction: false positive, false negative, or bounded estimate
   ├─ budget error for each population and operating state
   ├─ validate skew, adversarial keys, merge, aging, and reset behavior
   └─ retain an exact control sample and an escape path

Sketches can estimate heavy hitters or frequencies without retaining every key. Sampling can reduce measurement work. Both can fail quietly under distribution shift, correlated inclusion, adversarial inputs, counter saturation, or incorrect merge/decay. Store configuration, seeds where relevant, version, population, and an exact audit sample. Never use a probabilistic positive as an authorization decision merely because its aggregate error rate is low.

Persistence makes layout a compatibility contract

An in-memory representation is optimized for the current process: native alignment, pointer width, object headers, allocator placement, endianness, and runtime version may be implicit. A persistent representation must define byte order, field widths, offsets, schema/version, checksums, partial-write behavior, and recovery. Writing raw process memory usually freezes assumptions that were never intended as a durable contract.

Alignment between in-memory and on-disk layouts can remove parsing or copying, especially with memory mapping, but it does not create free I/O. Page faults, validation, decompression, pointer swizzling, endian conversion, and access order remain. A page-oriented tree aligns navigation with durable blocks; a log aligns writes with append order; a columnar format aligns analytical scans with field projection. Each favors an operation family and imposes compaction, repair, and evolution work.

SQLite’s documented file format is a useful primary example of the discipline: fixed page and header contracts make durable bytes interpretable across process lifetimes. The lesson is not to copy its layout. It is to treat persistence as a versioned interface. Benchmark warm and cold states separately, include load and rebuild time, corrupt or truncate fixtures deliberately, and validate that a new reader and old data agree before claiming “zero copy.”

The tiny microbenchmark proves less than it appears to

The fixture times Array.includes and Set.has in the local Node process for eight integer keys, six repeated hits, two misses, and 100,000 repetitions. On this run, the array took about 6.96 ms and the set about 4.84 ms; both produced the same 600,000-hit checksum. Another process, runtime, host state, or run can reverse or narrow that relation.

The annotation is the important artifact:

The asymptotic statement—linear search versus expected constant-time set membership—is true and still insufficient. The timing cannot validate Atlas’s 12,000-candidate filter because the size, representation, distribution, operation mix, lifecycle, correctness boundary, and machine evidence differ.

A transferable benchmark manifest records runtime/compiler and flags, host and topology, input generator and seeds, structure implementation, resident memory, build state, warm-up, repetitions and independent runs, operation mix, key/value sizes, hit ratio, skew, mutation and snapshot phases, correctness oracle, timers, counters, raw results, and environment noise. Interleave alternatives when drift matters. Prevent dead-code elimination in compiled code. Do not average percentiles from independent processes as though they form one latency population.

Google Benchmark’s current guide documents warm-up, repetitions, random interleaving, counters, memory reporting, and optimization barriers. Those facilities do not choose the workload or establish transfer. Profile the benchmark and production path with the same named cost terms: instructions/comparisons, branch behavior, allocation, resident bytes, cache and translation events, memory bandwidth, synchronization, storage traffic, and correct completion.

Operational decision table

The conditional rule is compact: choose a structure from operation mix, data distribution, working set, update and snapshot semantics, persistence, and concurrency. Big-O bounds the candidates; measured whole-outcome cost orders them.

Field checklist

• What exact outcome and consistency version are being timed?
• What are the point, range, scan, insert, delete, snapshot, rebuild, and recovery proportions?
• Which size, skew, hit ratio, value size, and mutation distributions define the workload?
• How many useful bytes, transferred bytes, comparisons/probes, allocations, and unpredictable branches occur?
• Which memory, page, storage, or network boundary is expected to bind?
• Does layout isolate hot fields and ownership, or does unrelated mutation share fetched blocks?
• What state is authoritative, derived, materialized, approximate, or cached?
• Can approximation change truth, or can it only nominate work for an exact check?
• Are build, conversion, serialization, reclamation, compaction, and recovery charged?
• Does the benchmark reproduce lifecycle and concurrency, validate outputs, retain raw results, and expose causal counters?
• What happens under memory pressure, update bursts, partial rebuild, corrupted persistence, and recovery?

Applied work

Reproduce examples/performance-engineering-system-design-handbook/part-03/data-layout-locality/.

First, audit the 79.875% logical-byte reduction. Identify the assumptions that make five first-stage bytes and eight survivor bytes meaningful, then name the counters or profiles that could falsify a latency claim. Change the survivor fraction to 60% and decide whether staging remains worthwhile after accounting for an extra pass.

Second, design Atlas’s large-tenant membership path for eight million documents, 12,000 candidates/query, 537 updates/s, a 7% large-tenant arrival class, and exact authorization. Compare a pointer-rich hash, sorted compact identifiers, dense or compressed bitmap chunks, and a Bloom-assisted exact design. Specify memory, update, snapshot, revocation, overload, rebuild, and recovery behavior. Reject any design whose probabilistic positive can return a document.

A strong answer does not select from the fixture’s logical-byte table alone. It proposes a representative benchmark matrix, includes mutation and retained memory, preserves an exact oracle, and states which production distribution would reverse the choice.

Principal drill: challenge the algorithm win

A team replaces a scan with a hash index and reports a 12× lookup microbenchmark improvement. Production p99 changes by less than 2%, resident memory grows 2.4×, deployment warm-up doubles, and one shard now pauses during table growth. Candidate lists are usually 24 items but reach 40,000 for one tenant class. Deletions arrive in bursts, and reads require a point-in-time authorization view.

Produce a decision record that:

1. separates the small and large populations rather than averaging them;
2. reconstructs full-path service, bytes, allocation, growth, snapshot, and recovery costs;
3. proposes at least two representation policies, including a size-dependent hybrid if justified;
4. preserves authorization semantics during deletion and rebuild;
5. names the profile and counter evidence needed to locate the unchanged p99 constraint;
6. defines a benchmark matrix with skew, mutation, warm/cold, and independent-run uncertainty; and
7. sets a rollback threshold for memory, pause, correctness, and deployment time.

The correct answer may retain the scan for small lists, change layout without adding an index, or use a compact index only for the large class. An asymptotic improvement is evidence about growth, not a deployment decision.

Evidence and transfer limits

• Intel 64 and IA-32 Architectures Optimization Reference Manual, Volume 1 is a current primary guide to locality, memory access, branches, and processor-specific optimization. Its recommendations require validation on the deployed processor and software stack.
• Google Benchmark user guide documents current controls for warm-up, repetition, interleaving, optimization barriers, counters, memory reporting, and profiling. A harness cannot repair an unrepresentative workload.
• Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors” establishes the classic filter and error trade-off. The linked copy preserves the original Communications of the ACM paper; the chapter’s numbers are fixture calculations, not measurements from it.
• Frigo et al., “Cache-Oblivious Algorithms” develops the ideal-cache transfer model and recursive design approach. The linked university copy preserves the original paper; real machines and concurrent runtimes add effects outside that model.
• SQLite database file format is a current primary example of a versioned page and byte-level persistence contract. It is not a recommendation to use SQLite’s representation for Atlas.
• The Atlas values are modeled or locally observed teaching evidence reproduced by examples/performance-engineering-system-design-handbook/part-03/data-layout-locality/. The fixture validates arithmetic and output checksum; it does not validate hardware traffic or production capacity.

Data layout decides which bytes become neighbors and which mutations share ownership. The next constraint appears when multiple executors try to act on that representation at once. Chapter 18 asks how much of the work is genuinely independent, where synchronization serializes it, and whether changing ownership removes more cost than changing the lock.