Part I: Foundations — Seeing Programs as Data Transformations#

This part begins below programming languages and above electrical engineering. Its purpose is not to turn you into a processor designer. Its purpose is to give you a useful model for asking why a program does work, what data that work needs, and how Rust can express a better arrangement. Every hardware description here is a simplified model, not a universal measurement. Different processors, operating systems, compilers, and workloads behave differently. Consequently, none of the layouts in this part is guaranteed to be faster. We will predict, preserve meaning, measure, and then decide. By the end, you will be able to derive DOD's core questions from a simple model of memory and work.

1. Programs transform data#

A program receives data, changes or combines it, and produces data. That sentence includes interactive applications, servers, compilers, games, simulations, and command-line tools. A text formatter receives characters and options, transforms them, and produces formatted characters. A game receives input and prior world state, transforms both, and produces a new world state plus images and sounds. A web service receives a request and stored facts, transforms them, and produces a response and perhaps updated facts. Even a program described as “behaving” can be examined as a sequence of data transformations. This perspective does not deny behavior, users, or domain meaning. It gives us another question: what data must move through the machine for that behavior to happen? Suppose a payroll rule says to increase every active employee's pay by three percent. The domain question asks whether the rule is legally and financially correct. The data question asks where active status and pay are stored, how many employees exist, and in what order records are visited. Both questions matter, but they answer different concerns. Data has a form: booleans, numbers, text, records, images, or something else. Data has a quantity: one item, ten items, or ten million items. Data has a frequency: once during startup, every request, or every frame. Data has a probability: always needed, occasionally needed, or almost never needed. Data has a lifetime: one expression, one task, one session, or years. Data has an access order: sequential, random, grouped, or dependent on previous results. Those properties influence the cost of a transformation even when the answer remains identical.

input data  --->  transformation  --->  output data
                     |
                     +-- reads some fields
                     +-- computes values
                     +-- writes some fields

The arrows are conceptual; real programs may loop, branch, wait, and communicate. The diagram nevertheless prompts concrete questions instead of vague wishes to “make it fast.” Prediction checkpoint: If two implementations produce identical invoices, can their data costs differ? Answer: Yes. One might repeatedly scan scattered customer records while another gathers required fields once and processes them sequentially.

2. Bits, bytes, and values#

A bit is a storage unit with two distinguishable states, conventionally written 0 and 1. Bits become useful through interpretation. Eight bits can represent 256 distinct patterns because each position doubles the number of combinations. A byte is the smallest addressable storage unit in Rust's abstract machine and on mainstream machines; Rust defines a byte as eight bits. We commonly write byte quantities using units such as KiB, where one KiB is 1024 bytes. A bit pattern alone does not tell us what it means. The pattern 01000001 might be interpreted as the integer 65, part of a floating-point value, flags, or the letter A in a particular encoding. A value is an interpreted piece of information such as true, 65, or a coordinate. A type describes which values are valid and which operations make sense. Rust's u8 type represents unsigned integers from 0 through 255. Rust's i32 type represents signed integers using 32 bits. Rust's bool type represents false or true, while its exact layout matters when stored. The char type represents a Unicode scalar value, not an arbitrary byte and not necessarily a displayed character. The String type owns a growable sequence of UTF-8 bytes elsewhere in memory. Types let the compiler reject nonsense, choose operations, and determine many layout requirements. They do not make representation irrelevant. For example, two values can have the same mathematical meaning but different byte encodings. Serialization explicitly converts in-memory values into a defined sequence of bytes for storage or communication. Deserialization performs the reverse transformation while validating the input.

let flags: u8 = 0b0000_0101;
let can_read = flags & 0b0000_0001 != 0;
let can_write = flags & 0b0000_0010 != 0;
let can_execute = flags & 0b0000_0100 != 0;
assert!(can_read && !can_write && can_execute);

This example packs three yes-or-no facts into bits of one byte. Packing can save space, but extracting bits also adds operations and may complicate code. The best representation depends on the transformation, not on smallest size alone. Exercise: List three interpretations that the byte 0 could have in a program.

Possible answer: The integer zero, a false flag, a string terminator in a C-compatible format, or one channel value in a pixel are all plausible.

3. Addresses, memory, and identity#

Memory is storage that the processor can read and write through addresses. An address is a number-like identifier for a location in an address space. If a byte is a house, an address is closer to a house number than to the contents inside. Adjacent addresses identify adjacent bytes in the simplified model. A multi-byte value occupies a range of addresses. Alignment is a requirement or preference that a value begin at an address divisible by some amount. Alignment helps hardware access values and can cause unused padding bytes in records. Endianness describes the byte order used for a multi-byte number. These details matter in binary formats and unsafe code, but safe Rust usually handles ordinary loads and stores. Memory is not one giant Rust array that application code may freely inspect. The language, compiler, operating system, and hardware establish rules about valid access. Reading an address that does not belong to a live value is invalid even if some physical storage exists there. Writing through an immutable reference violates Rust's rules unless a defined interior-mutability mechanism applies. Object identity and address are also different ideas. A logical customer can remain the same customer after its record moves to a new allocation. Conversely, an allocator can reuse an old address for an unrelated value after the first value dies. DOD often benefits from stable integer identifiers rather than treating addresses as lasting identities. An identifier can index a table, survive relocation, and be checked for stale generations. That design is not mandatory; it is one option derived from access and lifetime needs.

address:  1000 1001 1002 1003 1004 1005 1006 1007
bytes:      2A   00   00   00   FF   10   10   10
            |---------|    |--------------------|
             one u32?          four separate u8s?

The labels depend on type and byte-order interpretation. Memory supplies bytes; the program supplies valid meaning.

4. Structs, arrays, pointers, and references#

A struct groups fields that together describe a value. An array stores a fixed number of values of one type contiguously, meaning one immediately after another. A slice is a view of a contiguous sequence; in Rust it carries a starting pointer and a length conceptually. A pointer stores an address-like location and may be raw or managed by a library type. A Rust reference, written &T or &mut T, is a pointer-like value with language-enforced validity and aliasing rules. Aliasing means that multiple access paths refer to the same storage. Rust controls aliasing so safe code cannot mutate data concurrently through incompatible references. A Vec<T> owns a growable contiguous buffer of T values. The Vec value itself conceptually tracks a buffer pointer, a length, and a capacity. Its elements normally live in a separate allocation when capacity is nonzero. A Box<T> owns a T in an allocation and gives it a stable location while that Box owns it. Following a pointer means reading the pointer value and then accessing the target location. One follow is often harmless; a long dependency chain can constrain hardware because each next address depends on the previous load.

struct Particle {
	position: [f32; 3],
	velocity: [f32; 3],
	mass: f32,
}

let particles: Vec<Particle> = Vec::new();
// The Particle values are contiguous in the vector's element buffer.

Field order, alignment, and representation attributes influence a struct's layout. Rust does not promise that the default Rust representation follows source field order or stays stable across compilations. Consult the Rust Reference layout chapter when exact guarantees matter. Do not infer a wire format from an ordinary struct's current observed bytes. For performance reasoning, inspect actual size and generated behavior rather than assuming an imagined layout.

Prediction checkpoint: Does Vec<Box<Particle>> place all Particle values consecutively?

Answer: No guarantee. The boxes are consecutive as vector elements, but each Particle is in a separately obtained allocation and may be scattered.

5. The stack and the heap without folklore#

The stack is a region and discipline commonly used for function call state and values with conveniently nested lifetimes. A stack pointer tracks the current end, and reserving a frame can be as simple as adjusting that pointer. The heap is a region managed by an allocator for storage whose size, lifetime, or ownership movement does not fit simple call nesting. An allocator finds suitably sized and aligned blocks and later accepts them back for reuse. “Stack value” and “heap value” are shorthand, not moral categories. Rust semantics do not promise that every local variable physically sits in memory on a conventional stack. The optimizer may keep a local in a register, merge it, remove it, or place it elsewhere while preserving observable behavior. Likewise, a heap allocation can be cached, contiguous, and frequently accessed. The statement “the stack is always faster” is folklore because it confuses allocation mechanism, access pattern, and actual location. Creating ordinary stack frames is often cheap, but accessing data depends on where bytes are and what else the processor needs. Heap allocation can cost bookkeeping, synchronization, finding a block, and later deallocation. Its larger performance effect may be indirect: separate allocations can scatter related values and enlarge metadata. Allocation also establishes lifetime and ownership boundaries, which may be worth the cost. A vector typically performs occasional allocations while many element accesses happen without allocating. Reserve capacity when a credible size estimate avoids repeated growth, but measure whether this matters. Small short-lived allocations may be optimized by specialized arenas or pools when evidence supports that complexity. An arena obtains larger regions and serves many related objects, often releasing them together. That works especially well when the objects share a lifetime. It works poorly if individual retention needs cause the arena to preserve mostly dead data.

let local = 7_u32;
let boxed = Box::new(7_u32);
assert_eq!(local, *boxed);

These values have equal meaning despite likely different storage strategies. Choose ownership for correctness first; reshape allocation only under a performance hypothesis.

6. CPU, registers, and instructions#

The central processing unit, or CPU, executes instructions that implement computations and data movement. An instruction is an encoded operation understood by a processor architecture, such as adding numbers, loading memory, storing memory, comparing, or branching. A register is a small storage location inside a CPU core that instructions can access directly. Registers are limited and are not addressed like ordinary application memory. The compiler translates Rust into lower-level operations, eventually producing machine instructions for a chosen target. One Rust expression does not correspond reliably to one instruction. An expression may disappear through optimization, expand into many instructions, or call a library routine. Modern CPUs can begin and complete multiple instructions in overlapping fashion. They may execute independent operations out of program order internally while preserving the required visible result. This ability is called instruction-level parallelism. A dependency limits overlap: b = a + 1 must wait until a is available. A chain of dependent pointer loads is therefore harder to overlap than several independent array loads. CPU cores usually have separate concerns for fetching instructions and loading program data. The instruction stream itself occupies cache capacity and can miss, just as data can. Large or unpredictable code paths can pressure instruction caches even when data layout is excellent. DOD includes the executed transformation, not merely compact data records. Fewer source lines do not imply fewer executed instructions. More source lines do not imply slower machine code. Compiler optimization, target features, and input determine what runs.

Rust source -> compiler transformations -> machine instructions -> CPU execution
                meaning preserved          target specific       input dependent

Use compiler output when necessary, but first use profiles to locate relevant work. Reading assembly without a workload can optimize an irrelevant path perfectly.

7. Latency, bandwidth, and stalls#

Latency is the elapsed time between starting an operation and receiving its result. Bandwidth is the amount of work or data that can be completed per unit time once activity is flowing. A water pipe analogy helps: travel time through the pipe resembles latency, while liters per second resembles bandwidth. The analogy is imperfect because processors overlap operations and share resources dynamically. A CPU stall is a period when useful progress is delayed because a needed result or resource is unavailable. A load whose data is not nearby can stall dependent instructions. Independent work may continue and hide some of that delay. Memory-level parallelism is the ability to have several memory operations in progress together. Sequential loops often expose predictable, independent accesses that hardware can overlap. Pointer chasing often exposes the next request only after the prior request completes. No single latency number is universally correct. Costs vary by processor, clock state, cache state, contention, memory topology, operating system, and access pattern. Published numbers can build intuition but cannot replace measurement on the relevant target. Throughput is another word commonly used for completed operations per unit time. An operation can have high latency and still support high throughput when many operations overlap. Conversely, an individually quick operation can face poor throughput under a shared bottleneck. Performance questions should state whether response time, total throughput, frame time, energy, memory, or another metric matters. Reducing average time may worsen worst-case time. Reducing CPU work may increase memory usage. A design choice is evaluated against explicit constraints, not a universal scoreboard.

Exercise: A service handles many independent records. Which gives the CPU more opportunity to hide load latency: one dependency chain or several independent records?

Possible answer: Several independent records usually offer more overlap, although actual gains depend on compiler, hardware, and bottlenecks.

8. The cache hierarchy#

A cache is smaller, faster storage that keeps copies of data likely to be used near the CPU. Modern systems commonly have multiple cache levels, often named L1, L2, and L3 or last-level cache. Names, sizes, sharing, and policies differ across processors. The useful model is a hierarchy: small nearby storage, larger less-nearby storage, and main memory farther away. Access first checks or is served by nearby levels according to hardware rules. A cache hit means the requested data is found in a relevant cache. A cache miss means it must be obtained from another level. Caches move data in blocks called cache lines rather than fetching only the exact requested byte. Many current CPUs use a 64-byte cache line, but this is not universal and must not become a baked-in truth. If a program reads one four-byte field, hardware may bring neighboring bytes in the same line too. Those neighbors are useful if accessed soon and wasted traffic if never used before eviction. Eviction replaces cached data to make room for other data. Capacity misses happen when the useful working data exceeds available effective cache capacity. Conflict effects happen when addresses compete for limited cache placements. Coherence keeps private cache copies consistent among cores according to a protocol. Multiple threads writing different values on the same line can interfere, a phenomenon called false sharing. False sharing is “false” only because variables are logically independent; the hardware still transfers a shared line. Alignment or partitioning can help, but indiscriminate padding can increase the working set. Again, derive changes from observed contention.

CPU registers
     |
small nearby cache (often L1)
     |
larger cache (often L2)
     |
shared or last-level cache (common, not universal)
     |
main memory
     |
storage or network when the program explicitly needs them

This pyramid omits many details and is an explanatory model only. It says nearer levels are generally smaller and lower latency, not that every access follows a literal staircase.

9. Locality and working sets#

Spatial locality means accessing addresses near addresses accessed recently. Walking an array from start to end has strong spatial locality. Temporal locality means reusing the same data within a short span of execution. Updating a small accumulator repeatedly has strong temporal locality. A working set is the collection of code and data actively needed during a phase or time window. The exact window must be stated because a whole application's data set may be huge while one phase needs little. If the active working set fits effectively in nearby caches, reuse can be cheap. If phases interleave unrelated large sets, each phase may evict data needed by the next. Phase separation can improve locality: gather input, perform one uniform transformation, then emit results. It can also add temporary storage or latency, so it is not automatically superior. Hot data is accessed frequently or on a performance-critical path. Cold data is accessed infrequently in that context. Temperature is workload-relative: an error message is cold during normal operation and hot during an outage storm. Hot/cold splitting stores frequently used fields separately from rarely used fields. The split can reduce bytes brought into cache for the hot operation. It can make operations needing the complete record more complicated. The meaningful unit is bytes touched for a transformation, not the elegance of a type diagram alone.

hot loop needs: position, velocity
cold fields:    display_name, audit_note, creation_timestamp

mixed record scan: [hot cold hot cold][hot cold hot cold]...
split hot scan:    [hot hot][hot hot][hot hot]...

Prediction checkpoint: Is data cold because its type is rarely instantiated?

Answer: Not necessarily. Temperature concerns access frequency and criticality in a specific workload, not a permanent property of a type.

10. Pages, virtual memory, and the TLB#

Programs usually use virtual addresses rather than direct physical memory addresses. Virtual memory gives each process an address-space view that the operating system and hardware map to physical storage or other backing. The mapping is managed in fixed-size units called pages. Page size is platform- and configuration-dependent; larger special page sizes may also exist. A page table records mappings and permissions. Address translation turns a virtual address into the physical location needed by hardware. A translation lookaside buffer, or TLB, caches recent address translations. If the needed translation is in the TLB, translation is quick relative to a page-table walk. A TLB miss requires additional work to discover the mapping. Touching a large number of scattered pages can pressure TLB capacity even if only a few bytes per page are useful. Contiguous arrays often use pages densely and produce predictable translation access. Separately allocated objects may still land near each other, but no general layout guarantee says they will. A page fault occurs when software intervention is needed for a page, such as first materialization or retrieval from backing storage. Not every TLB miss is a page fault, and not every virtual-memory discussion concerns swapping. The operating system may commit, lazily initialize, share, protect, or relocate physical backing without changing virtual pointers. Resident set size roughly concerns pages currently resident for a process, though tools define and report memory differently. Allocating address space does not always mean every byte immediately consumes distinct physical memory. This complexity is why memory metrics need names and tools rather than casual claims.

virtual address -> [virtual page number | offset]
                         |
                   TLB / page table
                         |
physical address -> [physical page number | same offset]

The diagram leaves out permissions, multiple table levels, huge pages, and architecture details. Its lesson is that address translation has its own locality and finite caches.

11. Branches and prediction#

A branch chooses which instruction path executes next. An if expression, loop test, match, or function return can involve branches, though compilers may implement them differently. Conditional branches depend on a condition such as active versus inactive. Modern CPUs predict branch outcomes so they can continue fetching and executing before the condition is fully resolved. A correct prediction keeps the pipeline supplied. A wrong prediction discards speculative work and redirects execution, causing a cost whose size varies. Predictable data patterns, such as long runs of true then false, can be easier than irregular outcomes. Branchless code replaces control decisions with unconditional calculations or selections. Branchless is not synonymous with faster: it may execute more instructions, load unnecessary data, or inhibit simpler compiler output. Grouping records by state can make a transformation uniform and reduce per-record decisions. Grouping itself costs time and may disrupt another useful order. Filter once and process a dense list when the filtered set is reused enough to repay construction. Otherwise a direct conditional scan may be clearest and fastest.

fn sum_active(values: &[u32], active: &[bool]) -> u64 {
	values
		.iter()
		.zip(active)
		.filter(|(_, is_active)| **is_active)
		.map(|(value, _)| u64::from(*value))
		.sum()
}

Iterator syntax expresses a transformation but does not dictate whether the final machine code contains a branch. Inspect and measure the compiled program when that distinction matters.

Exercise: Why might sorting booleans improve one loop but hurt the entire program?

Possible answer: It can improve branch regularity while spending time sorting and destroying an order required by later work.

12. Prefetching and sequential access#

Prefetching means bringing data closer to the processor before an instruction urgently needs it. Hardware prefetchers observe address patterns and may request upcoming cache lines automatically. Sequential and regular-stride scans are often friendly to hardware prefetching. Software prefetch instructions can request data explicitly on some targets. They are advanced, target-specific hints whose timing and usefulness are easy to get wrong. Fetching too early can evict useful data before use. Fetching too late does not hide latency. Fetching data never used consumes bandwidth and cache capacity. Start by arranging real access in a predictable order before adding manual prefetches. Sequential access is powerful because it combines spatial locality, dense page use, and predictable requests. It is not automatically optimal when most elements are irrelevant. An index of relevant elements can avoid scanning a huge sparse set. The index then introduces its own reads and potentially indirect access. Compaction can move relevant values into a dense temporary array. Compaction pays copying cost to improve later passes. Whether it wins depends on selectivity, reuse count, element size, and target hardware.

sequential:     A0 -> A1 -> A2 -> A3 -> A4
fixed stride:   A0 ----> A2 ----> A4 ----> A6
pointer chain:  A0 -> ?B7 -> ?Q2 -> ?C9

The question marks emphasize that each pointer-chain destination may only become known after the prior load.

13. Allocation as a data-layout decision#

Allocation reserves storage with a size, alignment, ownership arrangement, and lifetime. Deallocation returns storage for reuse after values are no longer live. General-purpose allocators must support varied sizes and interleaved lifetimes. Their metadata and synchronization strategies differ. Many tiny allocations can add bookkeeping and make traversal indirect. One contiguous allocation can reduce metadata and group elements, but resizing may move it. Capacity is reserved element space; length is the number of initialized elements. Vec growth usually allocates a larger buffer and moves elements, though exact growth policy is not a stable contract to design around. Repeatedly appending when final size is known suggests with_capacity. That is a hypothesis: fewer reallocations should reduce allocation and movement during construction. It says nothing about workloads where construction is negligible. Object pools recycle slots and can stabilize allocation behavior. Pools can retain memory, complicate stale-reference handling, and worsen locality if traversal follows a sparse free-list history. Generational indices pair a slot index with a generation counter to detect reuse. They can replace long-lived raw identity pointers while permitting packed or managed storage. Reference counting shares ownership by maintaining a count. It can add metadata updates and atomics when thread-safe, but often provides exactly the ownership semantics required. Never remove Rc or Arc merely because counting sounds expensive; first understand correctness and profile its role. Lifetime grouping is a strong allocation clue: data created and discarded together can often share an arena or buffer.

let input_count = 10_000;
let mut squares = Vec::with_capacity(input_count);
for value in 0..input_count {
	squares.push(value * value);
}

The capacity estimate is exact here, so it avoids growth while preserving simple ownership.

14. From one record to a batch#

Business descriptions often use singular nouns: update an account, move a particle, price an item. Running software usually performs the operation for a collection. One-record thinking starts with a richly self-contained record and asks each record to update itself. Batch thinking starts with the whole transformation and asks which fields it consumes and produces across all records. Neither view is inherently correct; they expose different design facts. Consider moving particles by velocity over a time step.

struct ParticleRecord {
	position: [f32; 3],
	velocity: [f32; 3],
	mass: f32,
	color: [u8; 4],
	name: String,
}

fn advance_one(particle: &mut ParticleRecord, dt: f32) {
	for axis in 0..3 {
		particle.position[axis] += particle.velocity[axis] * dt;
	}
}

fn advance_all(particles: &mut [ParticleRecord], dt: f32) {
	for particle in particles {
		advance_one(particle, dt);
	}
}

This is clear and may be entirely sufficient. The update uses position and velocity but not mass, color, or the String fields. Scanning records brings chunks containing needed and unneeded fields through the memory hierarchy. Because layout and cache-line boundaries vary, we cannot claim an exact byte count from source alone. We can still make a useful logical trace.

Per particle, semantic data used by advance:
read position:  3 x f32
read velocity:  3 x f32
write position: 3 x f32

Not semantically used by advance:
mass, color, String's pointer/length/capacity, and name bytes

“Semantically used” differs from physical traffic; stores, cache policies, alignment, and compiler code affect traffic. The trace identifies a mismatch worth testing rather than pretending to measure hardware from a type definition.

15. Reshaping the particle transformation#

A structure of arrays stores each field in its own contiguous collection instead of storing complete records consecutively. The name contrasts with an array of structures, which is the Vec<ParticleRecord> arrangement.

struct Particles {
	positions: Vec<[f32; 3]>,
	velocities: Vec<[f32; 3]>,
	masses: Vec<f32>,
	colors: Vec<[u8; 4]>,
	names: Vec<String>,
}

fn advance_batch(particles: &mut Particles, dt: f32) {
	assert_eq!(particles.positions.len(), particles.velocities.len());
	for (position, velocity) in particles.positions.iter_mut().zip(&particles.velocities) {
		for axis in 0..3 {
			position[axis] += velocity[axis] * dt;
		}
	}
}

Now the hot loop walks position and velocity arrays without interleaved names, colors, and masses. That can reduce unused bytes fetched and present regular streams to prefetchers. It may also make adding or removing one complete particle more error-prone because parallel lengths must stay synchronized. The private Particles API can preserve that invariant through methods. Encapsulation therefore helps DOD rather than opposing it. An array-of-structures-of-arrays compromise groups a small fixed block of positions and velocities together. That can support vector operations while keeping chunks manageable. No arrangement dominates every transformation. Rendering might need position and color together. An inspector might need all fields for one selected particle. Deletion might favor stable slots, while physics might favor compaction. The design should prioritize costly frequent transformations and provide deliberate paths for uncommon ones.

Prediction checkpoint: Will advance_batch definitely beat advance_all?

Answer: No. Small collections may fit in cache, compiler output may differ, extra arrays may add overhead, and another bottleneck may dominate. Benchmark representative inputs.

16. Tracing bytes without inventing measurements#

A byte trace records which logical bytes or fields a transformation requests in order. It is distinct from a hardware trace, which can include cache-line fills, writebacks, speculative loads, and translation activity. Begin with a table of fields, sizes, access modes, and frequency.

The f32 byte size is defined, while String metadata layout should not be assumed as a portable fixed record. For N active particles, the semantic advance pass consumes 24N field bytes and produces 12N field bytes, counting reads and writes separately. That arithmetic does not predict bus traffic exactly. A write may require ownership of a cache line, and a line can contain multiple particles or fields. Some position bytes may already be cached from an earlier pass. The compiler may vectorize operations or keep intermediate values in registers. Hardware may prefetch unused neighboring lines. Treat the table as a model that reveals ratios and candidates. If each record were logically 100 bytes and a pass needed 8 bytes, 92 percent of record content would be unused by that pass. Physical waste could be lower or higher depending on lines, reuse, and boundaries. Next, record the order: positions 0, 1, 2, and so on is more predictable than positions selected through an arbitrary linked list. Then record reuse: if color follows immediately in rendering, separating it may lose temporal locality. Finally, validate with counters, timing, and representative end-to-end behavior.

Exercise: For 1,000 records, a pass reads one 4-byte status and updates one 8-byte total. What is the logical field traffic?

Possible answer: 4,000 bytes read for status, 8,000 bytes read for totals, and 8,000 bytes written for totals, while physical traffic remains hardware-dependent.

17. Sequential scan versus pointer chasing#

Consider a set of jobs where processing needs only each job's numeric cost. A linked representation stores a pointer or index to the next job with each node. An array representation stores jobs consecutively and uses an integer loop position.

struct Node {
	cost: u64,
	next: Option<Box<Node>>,
}

fn linked_total(mut node: Option<&Node>) -> u64 {
	let mut total = 0;
	while let Some(current) = node {
		total += current.cost;
		node = current.next.as_deref();
	}
	total
}

fn slice_total(costs: &[u64]) -> u64 {
	costs.iter().copied().sum()
}

The linked loop reads a node, extracts cost, and reads next before knowing the next node's address. Each Box commonly represents a separate allocation, so nodes need not be adjacent. The slice loop knows the address pattern from base pointer, element size, and index. Hardware can often prefetch upcoming lines and overlap independent loads. The slice also omits per-node next pointers from the scanned data. Yet the linked list supports cheap insertion when the exact insertion point is already known and node stability matters. The array may shift elements for insertion and invalidate indices or references depending on design. If traversal dominates and mutation is batched, the array is a strong candidate. If arbitrary insertion dominates and traversal is rare, the list may be reasonable. Alternative designs include dense values plus a separate ordering array, chunked lists, or slot maps. DOD asks for workload proportions rather than selecting a fashionable container.

Prediction checkpoint: Does O(1) linked-list insertion prove the list is faster overall than a vector?

Answer: No. Complexity describes growth under a model; finding the insertion point, allocations, traversal locality, and actual operation mix still matter.

18. Algorithmic complexity and machine behavior#

Algorithmic complexity describes how resource use grows as input size grows. Big-O notation usually gives an upper growth class while ignoring constant multipliers and lower-order terms. An O(n) scan grows proportionally with n under its operation model. An O(n squared) pairwise comparison grows much faster and usually becomes untenable at sufficiently large n. Data layout does not rescue a fundamentally unsuitable growth rate at large scale. Constant factors still decide among realistic sizes and algorithms with similar growth. Two O(n) loops can differ greatly because one reads eight dense bytes per item and another follows pointers through 200-byte records. An O(n log n) preprocessing step can outperform repeated O(n squared) queries once reuse repays the setup. Conversely, constructing an index for five items may cost more than scanning them. Cache complexity models count transfers between levels and can explain behavior omitted by simple operation counts. They too are models with assumptions, not universal stopwatch results. Performance engineering combines asymptotic reasoning, data-volume reasoning, and empirical measurement. First reject explosive growth where scale requires it. Then compare bytes, dependencies, branches, allocations, and reuse. Finally measure the whole relevant operation.

Question 1: Does the algorithm scale acceptably?
Question 2: What data and instructions does each unit of work require?
Question 3: What happens on representative machines and inputs?

A faster constant factor cannot change quadratic growth into linear growth. A theoretically better algorithm can still lose below a crossover point. Document expected input ranges so future readers understand the choice.

19. Deriving Data-Oriented Design#

We can now derive the central idea rather than treating it as a slogan. Programs perform transformations over data. Transformations have particular inputs, outputs, quantities, frequencies, probabilities, lifetimes, and access orders. Hardware moves blocks through finite hierarchies and executes instructions with dependencies and predictions. Therefore, representation and organization should be chosen with important transformations and real hardware behavior in mind. Data-Oriented Design, or DOD, is the practice of designing software around the data required by its transformations, including data layout, access patterns, lifetime, and scale. It seeks arrangements that make required work clear and efficient while preserving correctness and maintainability. DOD is not a bag of low-level performance tricks. Tricks begin with techniques; DOD begins with data, workload, and constraints. DOD is not synonymous with an Entity Component System, or ECS. An ECS is one family of architectures that can group components for set-oriented processing. You can practice DOD without entities or components, and an ECS can still have poor access patterns. DOD is not database-only design, though databases also reason about sets, columns, indexes, and query workloads. DOD applies to in-memory applications, files, networks, graphics, and any data transformation. DOD is not merely procedural programming. Procedures can process well- or poorly-arranged data; methods can do the same. DOD is not the opposite of functional programming. Pure transformations and explicit data flow can support analysis, while excessive intermediate allocation can still matter. DOD is not hostility toward object-oriented programming, or OOP. Objects, interfaces, and encapsulation can protect invariants and express domain responsibilities. DOD asks that object boundaries not conceal costly bulk behavior from consideration. DOD is not premature optimization when used to identify scale, ownership, and transformation requirements early. Premature optimization is committing complexity to unverified bottlenecks without evidence or need.

Richard Fabian's free Data-Oriented Design book develops the subject in much greater breadth. Mike Acton's influential CppCon talk emphasizes understanding concrete data and transformations. These sources motivate questions; measurements and explanations must still support decisions in your program.

20. Domain models and data models#

A problem-domain model describes concepts users and experts care about: invoice, customer, particle, permission, or shipment. A data model describes representation and relationships needed to store and transform information. The models overlap but answer different questions. A domain model may say that an Order owns Lines and computes a total under pricing policy. A processing model may store quantities, product indices, and prices in separate arrays for bulk calculation. An API can expose an Order view while internally processing columns. Encapsulation means controlling access so invariants survive change. It does not require placing every related byte in one allocation. A struct with private parallel vectors and checked methods can be strongly encapsulated. An object graph with public mutable fields can be weakly encapsulated. Therefore, “objects versus data” is a misleading fight. The useful question is which boundaries communicate meaning and which representation serves costly transformations. Views, handles, iterators, and query methods can bridge these concerns. A view can temporarily present one logical record assembled from several arrays without copying all fields. A command can record a requested domain action for later batch application. This delay may improve batching but changes when errors and side effects occur, so semantics must be explicit. Stable public interfaces can permit internal layout experiments. Overly leaky interfaces, such as returning long-lived references into a vector, can prevent compaction later. Choose APIs that expose required guarantees, not accidental storage details.

struct Accounts {
	balances: Vec<i64>,
	active: Vec<bool>,
}

impl Accounts {
	fn balance(&self, id: usize) -> Option<i64> {
		self.active.get(id).copied().filter(|active| *active)?;
		self.balances.get(id).copied()
	}
}

The method protects bounds and activity semantics even though storage is set-oriented.

21. A worked transformation: applying discounts#

Imagine a shop applies a discount to active products in one category. The initial record model is direct and readable.

#[derive(Clone, Debug, PartialEq, Eq)]
struct Product {
	name: String,
	category: u16,
	price_cents: u32,
	active: bool,
	description: String,
}

fn discount_records(products: &mut [Product], category: u16, percent: u32) {
	for product in products {
		if product.active && product.category == category {
			product.price_cents -= product.price_cents * percent / 100;
		}
	}
}

The transformation reads active and category for every product. It reads and writes price only for matching products. It never examines name or description, though each record contains String metadata among hot fields. The pointed-to text bytes are not necessarily loaded merely because metadata is scanned, but metadata occupies record space. If most products match and this pass runs frequently, columns may reduce irrelevant traffic.

struct ProductTable {
	names: Vec<String>,
	categories: Vec<u16>,
	prices_cents: Vec<u32>,
	active: Vec<bool>,
	descriptions: Vec<String>,
}

fn discount_columns(table: &mut ProductTable, category: u16, percent: u32) {
	let rows = table.prices_cents.len();
	assert_eq!(table.categories.len(), rows);
	assert_eq!(table.active.len(), rows);
	for row in 0..rows {
		if table.active[row] && table.categories[row] == category {
			let price = &mut table.prices_cents[row];
			*price -= *price * percent / 100;
		}
	}
}

This code still branches and performs bounds checks that the optimizer may or may not eliminate. Zipping equal-length slices can express the relation more directly, but API clarity should guide the final form. If only one percent of products belongs to the category, a category index may avoid nearly all rows. Maintaining that index makes writes more expensive and consumes memory. The transformation portfolio, not this one loop in isolation, determines the design.

22. The semantic oracle#

Optimization is a controlled change that must preserve required meaning. A semantic oracle is a trusted way to decide whether candidate output has the same required meaning as the baseline. The oracle can be a simple implementation, specification examples, property tests, differential tests, or validated production snapshots. “Oracle” does not mean infallible magic; it means the reference we deliberately trust for comparison. For discounts, the record implementation can serve as a readable oracle for a column implementation. Generate many product sets, clone them, apply both versions, and compare prices by logical row. Include zero prices, maximum safe values, inactive products, nonmatching categories, and percentages at defined boundaries. The existing arithmetic can overflow for large values in debug or wrap under some release settings, so semantics must define allowed ranges. Changing integer evaluation order can change overflow and rounding behavior. Floating-point regrouping can change results because floating-point addition is not generally associative. Parallel execution can change ordering, tie-breaking, and externally visible timing. An optimization is incorrect if it violates required semantics even when averages look plausible.

fn prices(products: &[Product]) -> Vec<u32> {
	products.iter().map(|product| product.price_cents).collect()
}

// In a test, construct equivalent record and column inputs,
// run both transformations, then compare their logical price rows.

Write the oracle before a risky reshape when possible. It makes experiments cheaper because failures are caught automatically. The oracle also reveals which behavior is intentional and which was accidental. Performance tests without correctness checks can reward missing work.

Exercise: What semantic issue arises if a batch implementation reorders customer notifications?

Possible answer: If notification order is observable or contractually required, equal final balances are insufficient; the oracle must compare event order too.

23. The performance hypothesis#

A performance hypothesis is a testable explanation connecting a proposed change to a metric. It states the workload, suspected bottleneck, mechanism, expected direction, and possible trade-offs. “SoA is faster” is not a useful hypothesis. “For the million-particle advance pass, separating position and velocity should reduce bytes fetched for unused names and colors, lowering median pass time on target machines” is useful. The hypothesis can be wrong without the experiment being a failure. A rejected hypothesis teaches us that the model, bottleneck, implementation, or workload needs revision. Specify the baseline and candidate build modes. Use optimized builds for performance because debug Rust includes checks and lacks normal optimization. Control or record input size, data distribution, warmup, thread count, machine, and compiler version. Run enough samples to see variation rather than celebrating one minimum. Separate setup from the operation when setup is not part of the metric. Include setup when users actually pay it. Use wall-clock timing for user-visible duration and profilers or hardware counters to investigate causes. Counters are model-specific and can be misinterpreted; consult processor and tool documentation. Benchmark changes can alter code generation, so avoid tiny unrealistic microbenchmarks as sole evidence. Check end-to-end outcomes because a locally faster pass can slow later passes or increase allocation.

Workload: 1,000,000 particles; all active; advance called 60 times.
Baseline: Vec<ParticleRecord>.
Candidate: separate position and velocity arrays.
Mechanism: fewer irrelevant bytes in the hot scan and regular streams.
Primary metric: time per complete advance phase.
Guardrails: identical positions, no unacceptable memory or API regression.
Result: to be measured, not assumed.

The Rust Performance Book offers practical profiling and benchmarking guidance.

24. Measuring honestly#

Begin with a user or system goal, such as keeping a simulation step within its frame budget. Profile the representative program to find where time or resources are spent. A profiler samples or instruments execution to attribute cost to code paths. Sampling periodically observes execution and usually perturbs less than detailed instrumentation. Instrumentation records events explicitly and can offer precision with additional overhead. Benchmark harnesses repeatedly run controlled operations and summarize timing distributions. The operating system, background tasks, thermal state, frequency scaling, and allocator state introduce noise. Noise does not make measurement useless; it requires repeated trials and honest uncertainty. Compare distributions, not decorative decimal places. Avoid changing several independent mechanisms at once because causality becomes unclear. Retain correctness checks in an appropriate form. Measure on every hardware class that matters, or clearly limit the conclusion. A server CPU, laptop CPU, phone, game console, and WebAssembly runtime can reward different choices. Even processors sharing an instruction set can differ in caches, predictors, execution width, and memory systems. Compilers also evolve, changing whether a loop vectorizes or bounds checks disappear. Record enough context for someone to reproduce or challenge a result.

cargo test --release
cargo bench

These commands are examples, not a complete methodology; a project needs suitable tests and benchmark targets. For this textbook's examples, inspect optimized behavior rather than timing unoptimized pedagogical code. Never report “Rust is slow” or “columns are fast” from one microbenchmark. Report the operation, input, environment, comparison, and uncertainty.

25. Common myths and careful replacements#

Myth: Cache lines are always 64 bytes. Many important processors use that size, but hardware differs; query or document the target when exact line size drives a decision. Myth: Stack memory is always faster than heap memory. Access cost depends on location, caching, and pattern; stack allocation is often cheap, while heap allocation has different lifetime and bookkeeping properties. Myth: Fewer allocations always means faster. Fewer allocations may reduce overhead, but one giant sparse buffer can worsen memory use and locality. Myth: Contiguous data is always best. It often helps scans, but sparse queries, stability requirements, mutations, and copying costs can favor other structures. Myth: Branches are slow. Predictable branches can be cheap enough, and branchless alternatives may do more work. Myth: Big-O tells the whole performance story. It describes growth under assumptions, not constants, cache behavior, allocation, or the actual input range. Myth: DOD means using an ECS. An ECS is one possible architecture; DOD is the broader practice of organizing around transformations and data properties. Myth: DOD forbids objects. Objects and encapsulation can present meaningful interfaces and guard data-oriented storage. Myth: Every struct should become separate arrays. Splitting fields can hurt operations that need complete records and increases invariant management. Myth: A benchmark proves a universal truth. A benchmark supports a bounded claim about tested software, workload, metric, and environment. Myth: The CPU executes Rust statements in source order one by one. The compiler transforms code and hardware overlaps operations while preserving specified observable behavior. Myth: Smaller data always wins. Compression and bit packing can reduce traffic while adding decoding, masking, contention, or complexity. Myth: Allocation is only about speed. Allocation also expresses ownership, lifetime, stability, and failure behavior. Myth: Optimizing data layout is premature by definition. Early workload reasoning is design; unmeasured complexity aimed at imagined bottlenecks is premature optimization. Myth: A cache miss means a page fault. CPU caches, TLB translation caches, and operating-system page residency are distinct layers. Myth: Faster is guaranteed if fewer bytes are logically touched. Instructions, alignment, prefetching, reuse, and bottlenecks can reverse the result, so measure.

26. Beginner glossary#

Address: An identifier for a location in an address space. Alignment: A restriction or preference on where a value begins in memory. Allocation: Reserving suitably sized and aligned storage for a lifetime. Aliasing: Having multiple access paths to the same storage. Array: A fixed-length contiguous sequence of one element type. Bandwidth: Work or data completed per unit time while activity flows. Batch: A collection processed as a group rather than as isolated calls. Bit: A storage unit with two distinguishable states. Branch: A choice of which instruction path executes next. Byte: An addressable group of eight bits in Rust's model. Cache: Smaller nearby storage holding copies likely to be used soon. Cache line: The block granularity at which a cache commonly transfers data. Cache miss: Failure to find requested data in a relevant cache level. Cold data: Data accessed infrequently in the workload under discussion. Contiguous: Located consecutively in address order without unrelated gaps. CPU: The processor component that executes machine instructions. Data-Oriented Design: Designing around transformations, layouts, access, lifetime, and scale of data. Dependency: A requirement that one operation await another's result. Encapsulation: Controlling access to preserve invariants and hide changeable details. Heap: Storage managed by an allocator for varied sizes and lifetimes. Hot data: Data accessed frequently or on a critical path in a workload. Instruction: A machine-level operation such as load, add, compare, or branch. Latency: Time from starting an operation until its result is available. Locality: Nearness of accesses in space or time. Memory: Addressable storage used for program code and data. Object: A bundled unit of state, identity, behavior, or interface, depending on the programming model. Page: A fixed-size unit used for virtual-memory mapping. Pointer: A value representing a memory location, with validity governed by its kind and context. Prefetch: Requesting data before an urgent demand needs it. Reference: Rust's checked pointer-like borrow, &T or &mut T. Register: Small CPU-internal storage directly used by instructions. Semantic oracle: A trusted mechanism for checking preservation of required behavior. Spatial locality: Accessing addresses near recently accessed addresses. Stack: Storage and a discipline commonly used for nested function-call lifetimes. Stall: Delayed useful CPU progress while a result or resource is unavailable. Struct: A type grouping named fields into one value. Temporal locality: Reusing data within a short execution interval. Throughput: Completed operations per unit time. TLB: A hardware cache of recent virtual-to-physical address translations. Type: A description of valid values, operations, and relevant representation rules. Value: Interpreted information represented in a program. Virtual memory: An address-space abstraction mapped to physical or other backing storage. Working set: Code and data actively needed during a stated phase or window.

27. End-of-part decision checklist#

Before changing representation, can I name the important transformation precisely? Do I know its required inputs, outputs, and observable side effects? Have I recorded form, quantity, frequency, probability, lifetime, and access order? Which fields are hot for this transformation, and which are cold? What is the logical byte trace, and where does it avoid claiming exact hardware traffic? Is access sequential, fixed-stride, indexed, random, or pointer-dependent? What is the active working set for the relevant phase? Are instruction-cache effects or code size plausible concerns as well as data access? Does the algorithm's growth rate fit expected input sizes? Could a better algorithm matter more than layout? Are allocations frequent, scattered, contended, or simply irrelevant to the bottleneck? Do values with shared lifetimes have a useful grouping opportunity? Are stable addresses truly required, or would stable logical identifiers suffice? Would hot/cold splitting improve the dominant pass but damage another important pass? Can batching expose reuse, regular access, or independent work? Would filtering or compaction cost more than later passes save? What invariants must encapsulation preserve after reshaping? Can the public API avoid promising accidental storage details? What is the semantic oracle, and does it cover order, errors, overflow, and side effects? What profile evidence identifies a meaningful bottleneck? Can I state one testable performance hypothesis rather than a slogan? What metric matters: latency, throughput, frame time, memory, energy, or predictability? Are setup and conversion costs included whenever users pay them? Are inputs and distributions representative, including uncommon but important cases? Am I measuring an optimized build with enough repetitions to see noise? Which processors, operating systems, compiler versions, and runtime environments matter? Have I avoided assuming universal cache-line sizes or latency numbers? Did I measure end to end after the local benchmark? Did I check memory use, complexity, debuggability, and maintenance guardrails? Is the measured benefit large and stable enough to justify the added complexity? If the candidate loses, have I recorded the useful negative result? Can the simpler design remain until evidence changes?

28. What foundation makes possible#

You now have a vocabulary for discussing bytes without reducing software to bytes alone. You can distinguish value from representation, identity from address, and allocation from access cost. You can explain why contiguous scans often help without claiming that they always win. You can reason about cache lines without assuming one universal size. You can separate CPU cache misses, TLB misses, and page faults. You can compare algorithmic growth with constant factors and memory behavior. You can treat domain models and processing models as collaborators rather than enemies. Most importantly, you can frame optimization as preserving semantics while testing a performance hypothesis. The recurring method is simple but demanding: describe the transformation, characterize its data, predict a mechanism, and measure. Hardware differs, compilers differ, and workloads differ. Faster is never guaranteed merely because a layout looks data-oriented. Clarity about required work is valuable even when a benchmark shows no speedup. It can reveal ownership, lifetimes, invariants, unnecessary conversions, and missing tests. The next part moves from foundations to concrete reshaping patterns. We will examine field splitting, grouping, dense and sparse sets, indexing, compaction, batching, and double buffering. Each pattern will be presented as a trade-off with an oracle and hypothesis, not as a commandment.

Part II: The Craft of Reshaping Data and Work#

This part turns the foundational model into repeatable design patterns and comparison methods. By the end, you will be able to reshape data around observed work without treating one layout as doctrine.

1. Begin With Evidence, Not a Favorite Layout#

Data-oriented design is a method for matching representation to actual work. It is not a rule saying that arrays are always fast. It starts by observing data, loops, boundaries, and measurable costs. The central question is simple: what data must move for useful work? Before changing code, write down quantities: ten orders or ten million? Record distributions, not merely averages, because tails often dominate latency. An average message may be small while rare messages exhaust memory. Measure lifetimes: permanent catalog entries differ from one-frame particle events. Measure mutation rates: immutable descriptions deserve different indexes from counters. Record optionality: does every record have a note, or only one percent? Record access order: sequential scans differ from unpredictable key lookups. Estimate selectivity, meaning the fraction surviving a filter or query. A one-percent filter can justify an index that a ninety-percent filter cannot. Find the working set, the bytes needed during one important phase. Working sets matter because processors move memory through finite cache levels. Mark producer and consumer boundaries: who creates, transforms, and destroys values? Boundaries reveal conversion, ownership transfer, synchronization, and buffering costs. Use a workload notebook rather than relying on architectural intuition.

quantity: 2,000,000 particles; peak 3,500,000
lifetime: median 0.8 s; p99 12 s
mutation: position every frame; color only at spawn
optional: collision metadata on 4%
order: update sequentially; render grouped by material
selectivity: visible 35%; collidable 4%
working set: position + velocity + age
boundary: simulation produces; renderer consumes

These observations are hypotheses until instrumentation confirms them under load. Keep units beside every number: records, bytes, frames, requests, or seconds. Distinguish steady state from startup, spikes, recovery, and shutdown behavior. Prediction checkpoint: which matters more, record size or touched-field size? Answer: touched-field size often matters, but allocation and access order can overturn it. The repeatable method is observe, model, reshape, preserve invariants, then measure.

2. Quantities, Distributions, and Lifetimes#

Begin with counts at minimum, typical, high percentile, and hard maximum. Percentiles describe distributions: p99 means ninety-nine percent fall below it. Do not size a hot structure using an unrepresentative development fixture. Histograms often expose two populations that deserve separate representations. For example, most orders contain three lines, but wholesale orders contain thousands. One universal path may punish ordinary orders or fail on wholesale outliers. Lifetimes determine allocation strategy and whether references can safely persist. Frame-local values can live in reusable scratch storage and disappear together. Session values need isolation from permanent catalogs and global application state. Mutation rate is frequency, scope, and pattern, not merely mutable versus immutable. Ask whether mutation touches one field, every field, or whole contiguous ranges. Optionality has shape: independent rare fields differ from correlated feature bundles. If five fields always appear together, model one optional component, not five flags. Access order should include insertion, iteration, lookup, deletion, and serialization. Selectivity should be measured after realistic earlier filters have already run. The working set changes by phase, so calculate it per major loop.

struct Observation {
	name: &'static str,
	typical_count: usize,
	peak_count: usize,
	bytes_touched_per_item: usize,
	updates_per_second: f64,
	selected_fraction: f64,
}

fn estimated_useful_bytes(o: &Observation) -> f64 {
	o.typical_count as f64 * o.bytes_touched_per_item as f64
		* o.updates_per_second * o.selected_fraction
}

This estimate is intentionally crude; its purpose is to expose assumptions. Useful bytes are fields required by work, not all bytes in records. Moved bytes include cache lines, copies, decoding, temporary storage, and output. Latency, bandwidth, and instruction costs can each become the limiting resource. Prediction checkpoint: should rare long-lived values share storage with common short-lived values? Answer: usually investigate separation, but shared access patterns may justify keeping them together. Never optimize from counts alone; include frequency and bytes per operation.

3. Access Matrices and Honest Cost Estimates#

An access matrix lists systems as rows and fields as columns. Mark reads, writes, frequencies, and whether access is sequential or random. The matrix makes accidental coupling visible before code obscures the issue.

particle system | pos | vel | age | color | material | collision
integrate       | RW  | R   | -   | -     | -        | -
expire          | -   | -   | RW  | -     | -        | -
render          | R   | -   | -   | R     | R        | -
collide         | RW  | RW  | -   | -     | -        | R
serialize       | R   | R   | R   | R     | R        | R

Add estimated executions beside each row rather than treating rows equally. Serialization once per minute should not dictate a sixty-hertz simulation layout. For each dominant row, estimate useful bytes and likely moved bytes. Suppose a 64-byte particle record supplies 24 useful integration bytes. Scanning one million records nominally exposes 64 MB to move 24 MB usefully. Actual hardware transfers cache lines, prefetches, and sometimes avoids repeated traffic. Therefore the estimate is a model, not a benchmark result. Hot/cold splitting moves frequently used fields away from rarely touched fields. Hot means frequent in a specific workload, not universally important. Cold descriptions can remain ergonomic records keyed by stable particle identity. Splitting increases joins, bookkeeping, allocations, and potential synchronization points.

candidate                     useful/frame   nominal scan/frame   ratio
64-byte records               24 MB          64 MB                37.5%
24-byte hot records           24 MB          24 MB               100.0%
three compact columns         24 MB          24 MB               100.0%
blocked records, estimated    24 MB          28 MB                85.7%

Ratios ignore instructions, alignment, write allocation, and downstream conversions. Use them to rank experiments, never to announce guaranteed speedups. Prediction checkpoint: does a perfect useful-byte ratio guarantee the fastest loop? Answer: no; gathers, branches, conversions, dependencies, and API costs still matter.

4. AoS, SoA, and Blocked Layouts#

Array of structures, or AoS, stores complete records next to each other. Structure of arrays, or SoA, stores each field in its own column. Blocked AoSoA stores small groups of field columns repeatedly.

#[derive(Clone, Copy)]
struct Particle {
	position: [f32; 2],
	velocity: [f32; 2],
	age: f32,
	color: u32,
}

struct ParticleColumns {
	positions: Vec<[f32; 2]>,
	velocities: Vec<[f32; 2]>,
	ages: Vec<f32>,
	colors: Vec<u32>,
}

struct ParticleBlock<const N: usize> {
	x: [f32; N],
	y: [f32; N],
	vx: [f32; N],
	vy: [f32; N],
	age: [f32; N],
}

AoS is excellent when operations consume most fields of one object. It is also simple for APIs, debugging, insertion, serialization, and ownership. SoA helps when dominant loops scan a few fields across many items. It can reduce moved bytes and offer regular loops to the compiler. SoA also creates parallel-length invariants and makes single-record operations awkward. AoSoA balances field locality with manageable chunks and explicit block sizes. Blocks can fit cache behavior, worker jobs, or vector-friendly lane groups. But an unfortunate block size wastes tails and complicates insertion and deletion.

AoS:   [x y vx vy age color] [x y vx vy age color] ...
SoA:   [x x x x ...] [y y y y ...] [age age age ...]
AoSoA: [xxxx][yyyy][ages] [xxxx][yyyy][ages] ...

Never claim SoA always wins; representation follows measured access patterns. If every operation reconstructs records from columns, conversion may erase gains. If counts are tiny, clarity may dominate any theoretical locality improvement. Rust slices make column loops explicit and bounds checks often optimize well. Keep equal-length and aligned-index assumptions behind a narrow owning API. Prediction checkpoint: a renderer needs position and color together; choose pure SoA? Answer: maybe paired render records or blocks are better; benchmark the real handoff.

5. Dense Tables, Columns, and Relationship Shape#

Dense arrays excel when active items are compact and iteration dominates. A table is logically rows, even if physically represented as independent columns. Columns allow scanning selected attributes without dragging unrelated payloads. Normalization stores a fact once and refers to it by an identifier. Denormalization deliberately duplicates facts to accelerate a known read path. Consider orders, products, inventory, prices, and fulfillment status.

orders:      order_id, customer_id, state, created_at
order_lines: order_id, product_id, quantity, captured_price
products:    product_id, title, current_price, warehouse_class
inventory:   product_id, available, reserved

Captured price belongs on the order line because history must not change. Product title could remain normalized if display reads are relatively rare. A shipping screen might denormalize warehouse class into a prepared work queue. Excessive normalization turns every hot loop into pointer chasing and joins. Excessive denormalization creates update fan-out and inconsistent duplicate facts. Ask which copy is authoritative and when derived copies become valid. Dense storage usually allows swap-remove: replace a removed item with the last. This preserves density but changes iteration order and the moved item's location. Order-sensitive consumers need explicit sorting, stable slots, or documented instability.

struct OrderBatch {
	ids: Vec<u64>,
	states: Vec<OrderState>,
	totals_cents: Vec<u64>,
}

impl OrderBatch {
	fn len(&self) -> usize {
		debug_assert_eq!(self.ids.len(), self.states.len());
		debug_assert_eq!(self.ids.len(), self.totals_cents.len());
		self.ids.len()
	}
}

This API protects only part of the invariant; constructors must protect the rest. Decision rule: normalize stable shared truth; denormalize measured repeated reads.

6. Membership, State Partitions, and Bitsets#

A boolean inside every record is not the only membership representation. For rare membership, store the members in a set or dense side table. Existence in that structure means true; absence means false. This is existence-based processing: iterate only objects that have relevant work. Two million records with four percent collidable need not run two million branches. The set must be maintained whenever membership changes, which is real debt. Use an enum when states are mutually exclusive and transitions carry meaning. Partitioning stores each state in a separate collection or contiguous range.

enum JobState {
	Ready,
	Running { worker: u16 },
	Waiting { dependency: u64 },
	Finished,
}

fn process_ready(ready_job_ids: &[u64]) {
	for &job_id in ready_job_ids {
		issue_job(job_id);
	}
}

fn issue_job(_job_id: u64) {
	// The command boundary is intentionally small.
}

Separate ready, waiting, and finished queues remove repeated state tests. Transitions now move identifiers between collections and must be atomic logically. A bitset stores one membership bit per dense numeric position. It offers compact storage, fast intersections, and predictable scanning. Bitsets are poor when identifiers are enormous and sparse without chunking. They also require a stable mapping from identity to current bit position.

visible:   1 1 0 1 0 0 1 0
selected:  0 1 0 1 1 0 0 0
both AND:  0 1 0 1 0 0 0 0

Prediction checkpoint: should every frequently queried boolean become a bitset? Answer: no; mutation, mapping, sparsity, and query combinations determine value. Prefer explicit transition functions that update state and derived membership together.

7. Buckets, Sorting, Grouping, and Branch Distribution#

Branches are not inherently bad; unpredictable distributions make them costly. More importantly, branches often reveal mixed work with different data needs. Bucket items by material, message kind, priority, size, or processing path. Then each bucket runs a simpler loop over more uniform data. Sorting creates groups when bucket keys are numerous or ordering is already useful. Sorting costs comparisons, movement, temporary memory, and delayed first output. Small fixed key spaces often favor direct buckets over general sorting.

enum TokenKind {
	Word,
	Number,
	Punctuation,
}

fn partition_tokens(kinds: &[TokenKind]) -> (Vec<usize>, Vec<usize>) {
	let mut words = Vec::new();
	let mut numbers = Vec::new();
	for (index, kind) in kinds.iter().enumerate() {
		match kind {
			TokenKind::Word => words.push(index),
			TokenKind::Number => numbers.push(index),
			TokenKind::Punctuation => {}
		}
	}
	(words, numbers)
}

The parser pays one classification pass, then specialized consumers avoid reclassification. This helps only when later work is substantial enough to repay partitioning. Branch distribution should be measured with realistic text, not uniform random tokens. Skew can help prediction while adversarial alternation can hurt it. Doing less work beats making unnecessary work branchless. Filter early using cheap, selective tests before expensive parsing or allocation. Keep rejection paths capable of explaining errors when semantics require diagnostics. Prediction checkpoint: sort ten items every frame to improve branch behavior? Answer: probably not; overhead and complexity likely exceed tiny-loop savings.

8. Batching and Command Buffers#

Batching groups operations so setup costs are paid fewer times. Examples include database writes, draw submissions, decompression, and network sends. A command buffer records intent now and executes it at a controlled boundary. This separates producers from consumers and enables sorting or coalescing commands.

enum InventoryCommand {
	Reserve { product: u64, quantity: u32 },
	Release { product: u64, quantity: u32 },
}

fn apply_commands(commands: &[InventoryCommand], inventory: &mut [i64]) {
	for command in commands {
		match *command {
			InventoryCommand::Reserve { product, quantity } => {
				inventory[product as usize] -= quantity as i64;
			}
			InventoryCommand::Release { product, quantity } => {
				inventory[product as usize] += quantity as i64;
			}
		}
	}
}

Real code validates identifiers and prevents inventory from becoming invalid. Commands create latency because effects are not immediately visible. They also need ordering, error, capacity, cancellation, and ownership semantics. Batching everything is an anti-pattern: interactive work may require prompt response. Large batches increase memory spikes and make individual failures harder to attribute. Choose a flush condition: item count, byte count, deadline, or explicit barrier. Bound buffers so a stalled consumer cannot consume unlimited memory. Coalescing repeated updates is safe only when operations are semantically equivalent. Two additions can combine; two externally observed state transitions might not. Prediction checkpoint: can inventory reservations be freely reordered by product? Answer: only if transaction, fairness, failure, and audit semantics allow reordering.

9. Double Buffering and Scratch Reuse#

Double buffering keeps separate current and next representations of evolving data. Readers observe current while writers construct next, then roles swap. This avoids in-place updates accidentally observing partially updated neighbors.

fn step(current: &[f32], next: &mut [f32]) {
	assert_eq!(current.len(), next.len());
	if let Some(&first) = current.first() {
		next[0] = first;
	}
	if current.len() > 1 {
		let last = current.len() - 1;
		next[last] = current[last];
	}
	for index in 1..current.len().saturating_sub(1) {
		next[index] = (current[index - 1] + current[index] + current[index + 1]) / 3.0;
	}
}

fn run_step(a: &mut Vec<f32>, b: &mut Vec<f32>) {
	step(a, b);
	std::mem::swap(a, b);
}

Double buffering doubles relevant storage and can increase memory traffic. It is unnecessary when safe in-place order is part of the algorithm. Scratch buffers are temporary vectors reused across calls to avoid allocation churn. Clear a vector while retaining capacity when previous peak capacity remains reasonable. Occasionally shrink pathological peaks rather than retaining enormous memory forever. Scratch ownership should be explicit: local context, worker-local arena, or caller-provided. Global scratch creates contention, reentrancy bugs, and surprising lifetime coupling. Never return references into scratch that will be overwritten on the next call. Producer and consumer may exchange whole buffers, transferring ownership cheaply. Back pressure is still required when the producer outruns the consumer. Prediction checkpoint: does reuse always reduce total memory? Answer: no; retained peak capacity can increase resident memory despite fewer allocations.

10. Precomputation, Caches, and Index Maintenance Debt#

Precomputation moves repeated work to an earlier phase or update boundary. A cache stores results so equivalent future requests can reuse them. An index stores a derived path from query key to matching data. All three trade freshness, storage, and maintenance work for cheaper reads. An index is not free after construction; every relevant mutation owes maintenance. That obligation is maintenance debt, paid eagerly, lazily, or during rebuilds.

derived structure     helps                         debt
product-id index      direct lookup                 update on insert/delete
state buckets         process active orders         move on every transition
lowercase text cache  repeated case-insensitive use invalidate on source edit
tile summary          distant image rendering       rebuild dirty tiles

Stale indexes are dangerous because results look plausible while being incomplete. Choose and document a consistency contract: immediate, snapshot, eventual, or manual. Version derived data against its source when stale use must be detectable. Rebuilding can be cheaper and safer than many complex incremental updates. Use query frequency and selectivity to justify each index. Low-selectivity queries returning most records gain little from indirect lookup. Cache keys must include every input that changes the result. Eviction policy should reflect bytes, recomputation cost, and access distribution. Avoid caching before identifying repeated expensive work in production traces. Prediction checkpoint: an immutable product catalog receives a new version nightly; rebuild indexes? Answer: often yes; build beside the old snapshot, validate, then atomically publish.

11. Compression, Quantization, and Level of Detail#

Compression represents the same information using fewer bytes, sometimes with decoding cost. Quantization maps values onto fewer representable levels and usually introduces error. Level of detail chooses a cheaper representation when full detail is unnecessary. Every lossy choice needs a semantic contract, not merely an acceptable file size. State units, range, maximum error, bias, overflow behavior, and exceptional values.

fn quantize_unit(value: f32) -> u16 {
	let clamped = value.clamp(0.0, 1.0);
	(clamped * u16::MAX as f32).round() as u16
}

fn dequantize_unit(value: u16) -> f32 {
	value as f32 / u16::MAX as f32
}

The contract says values outside zero through one clamp rather than wrap. Round-trip error is bounded approximately by half one quantization step. Telemetry timestamps might use delta encoding when samples are ordered and nearby. Missing samples, clock resets, and out-of-order arrival need explicit escape forms. Image thumbnails are level of detail: distant views avoid decoding full resolution. Audio previews may use fewer channels or lower sample rates with stated fidelity. Compression can reduce bandwidth enough to outweigh decode instructions. It can also block random access unless chunks provide independent decode boundaries. Measure compressed bytes, decode throughput, latency, and transient working memory. Never quantize identifiers, money, or categorical states as approximate measurements. Prediction checkpoint: is visually acceptable image error acceptable for medical imaging? Answer: not without a domain-specific safety contract, validation, and regulatory evidence.

12. Reshaping Loops in Plain English#

Loop interchange swaps which nested loop runs inside and which runs outside. Choose the inner loop so it walks nearby memory and performs regular work. Tiling processes bounded rectangular chunks instead of an entire dimension at once. Tiles keep reused data in a smaller working set before moving onward. Fusion combines adjacent loops that touch compatible data and share iteration order. Fission splits one complicated loop into simpler passes with narrower field needs.

fn brighten_rgb(pixels: &mut [[u8; 3]]) {
	for pixel in pixels {
		pixel[0] = pixel[0].saturating_add(8);
		pixel[1] = pixel[1].saturating_add(8);
		pixel[2] = pixel[2].saturating_add(8);
	}
}

fn sum_tiles(values: &[u32], tile_size: usize) -> u64 {
	values.chunks(tile_size).map(|tile| {
		tile.iter().map(|&value| value as u64).sum::<u64>()
	}).sum()
}

Fusion saves intermediate traffic but can enlarge code and worsen register pressure. Fission adds passes but may improve locality, branch predictability, and parallel scheduling. Interchange is legal only when dependencies permit the new execution order. Tiling adds boundary handling and requires choosing a size from evidence. Compilers may autovectorize regular loops, issuing one instruction over several lanes. Contiguous columns, simple bounds, and independent iterations can help that analysis. This is not a SIMD rulebook; inspect generated behavior and benchmark whole pipelines. Conversion into a vector-friendly layout may cost more than the accelerated loop saves. Prediction checkpoint: fuse parsing and every downstream transformation into one loop? Answer: rarely; ownership, diagnostics, reuse, and distinct filtering may favor boundaries.

13. Stable Typed IDs, Dense and Sparse Maps#

Memory addresses describe current storage locations, not durable logical identities. Moving vectors, compaction, serialization, and process boundaries invalidate address assumptions. Use typed IDs or handles so unrelated identifier domains cannot be mixed accidentally.

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct OrderId(u64);

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct ProductId(u64);

fn reserve(_order: OrderId, _product: ProductId) {
	// Resolve handles inside the owning storage API.
}

A dense-to-sparse mapping conceptually connects compact iteration positions to stable slots. The dense side stores active items tightly for efficient scans. The sparse side answers where a stable slot currently lives, if anywhere. Deleting by swap-remove moves the final dense item into the gap. The mapping for that moved item must change during the same operation. Iteration order therefore changes, which affects deterministic output and fairness. A generation counter distinguishes a reused slot from its previous occupant. A handle carries slot plus generation; mismatch means the handle is stale. Generation wraparound and concurrent access still require deliberate policy. Part III will implement these structures and prove their update invariants in code. For now, remember the conceptual invariant: every live mapping agrees both ways. Public APIs should resolve handles rather than exposing internal indexes as addresses. Prediction checkpoint: can a stable handle promise a stable iteration position? Answer: no; identity stability and physical-position stability are separate contracts.

14. End-to-End Redesign: Particle Simulation#

Start with evidence rather than replacing the particle struct immediately. There are 1.8 million typical particles and 3.2 million at peak. Integration runs sixty times per second and touches position, velocity, and age. Rendering runs sixty times per second for thirty-five percent visible particles. Color and material never mutate after spawn; collision exists on four percent. Particles live 0.7 seconds median, with a long twelve-second tail. The original AoS record occupies 80 bytes after alignment and optional payloads.

system/frame        pos  vel  age  color  material  collision  selected
integrate x60       RW   R    RW   -      -         -          100%
render x60          R    -    -    R      R         -           35%
collide x60         RW   RW   -    -      -         R            4%
debug x0.02         R    R    R    R      R         R          100%

Integration useful bytes are roughly twenty bytes per particle before alignment details. The original nominal scan is 144 MB per typical frame: 1.8 million times eighty. Useful integration data is about 36 MB, only one quarter of that scan. The model ignores write allocation and cache reuse, so it ranks candidates only. Choose hot columns for position, velocity, and age, indexed by one dense position. Keep immutable render attributes in paired compact records because rendering consumes both. Keep collision payload and membership in a separate four-percent component table. Build a visible command buffer containing dense handles grouped by material. Use reusable buffers because particle and command lifetimes repeat every frame. The representation invariants are precise and testable.

• Every hot column has identical length.
• Each dense position maps to one live generated handle.
• Render attributes exist for every live particle.
• Collision membership and payload existence agree.
• Swap-remove repairs mappings for the moved particle.
• Visible commands refer only to the current simulation generation.

The ownership boundary gives simulation current hot data and rendering an immutable snapshot. Double buffering is considered only if simulation and rendering overlap asynchronously. Conversion cost includes building visibility commands and gathering render pairs. The compiler may autovectorize integration because iterations are independent and contiguous. That possibility is supporting evidence, not the primary design justification. What evidence could reject this design? If visibility gathering dominates, direct AoS rendering might win overall. If almost every particle becomes collidable, sparse component separation loses selectivity. If particle counts stay below ten thousand, complexity may not repay itself. If creation and deletion dominate, parallel columns and mapping repair may cost too much. If profiling shows arithmetic rather than memory bandwidth dominates, layout changes may disappoint. Benchmark end-to-end frame time, memory peak, spawn cost, and tail latency. Prediction checkpoint: should debug serialization determine the hot representation? Answer: no; adapt at its rare boundary unless measurements show adaptation is costly.

15. Order and Inventory Case Study#

An order service reads inventory often, writes reservations, and audits every transition. Most orders have two lines; one percent have more than one hundred. Product descriptions change weekly, inventory counters change thousands of times per second.

Checkout selects a handful of products by identifier rather than scanning the catalog.

Warehouse picking later groups accepted lines by zone and shelf.

Keep immutable product metadata separate from hot inventory counters.

Use an identifier index for product lookup because queries are highly selective.

Store captured price on order lines to preserve historical financial semantics.

Batch reservation commands only within transaction and latency constraints.

After acceptance, build a denormalized pick record containing required warehouse fields.

Sort pick records by zone and shelf to reduce travel and group work.

This derived queue has a snapshot contract; later catalog edits do not rewrite history.

struct PickRecord {
	order: OrderId,
	product: ProductId,
	zone: u16,
	shelf: u32,
	quantity: u32,
}

fn group_for_picking(records: &mut [PickRecord]) {
	records.sort_unstable_by_key(|record| (record.zone, record.shelf));
}

Unstable sorting means equal keys may reorder, so fairness needs another key.

An audit stream preserves logical command order even when physical picking is reordered.

Giant global tables would couple checkout, catalog, auditing, and warehouse lifetimes.

Narrow owners make consistency and replacement boundaries clearer.

Excessive normalization would force warehouse workers to join catalogs for every line.

Excessive denormalization would copy mutable available counts into stale pick records.

Prediction checkpoint: should inventory availability be cached on every open order?

Answer: generally no; it changes rapidly and would create misleading stale snapshots.

16. State Machine and Parser Pipelines#

A connection state machine begins as records containing state plus every possible field.

Most fields are optional because each belongs to only one state.

The update loop repeatedly matches all connections even when only ready ones work.

Partition connections into connecting, ready, waiting, and closing collections.

Transition functions move generated handles and initialize state-specific payloads.

Ready processing now iterates existing ready payloads rather than testing global booleans.

This improves work proportionality but complicates globally ordered diagnostics.

Maintain a separate event sequence when observability requires total transition order.

For a text pipeline, observe bytes, token distribution, and consumer requirements.

Suppose ninety percent of lines are discarded by a cheap prefix test.

Filter prefixes before UTF-8 normalization, token allocation, and syntax analysis.

Retain source ranges instead of copying token strings when source ownership permits.

Classify tokens once, then bucket identifiers and numbers for specialized analysis.

input bytes
  -> cheap line filter
  -> validated source chunks
  -> token ranges + kinds
  -> grouped semantic work
  -> compact diagnostics/output

Ranges create an ownership contract: source bytes must outlive every range consumer.

Copying selected tokens may be cheaper than retaining a huge source allocation.

Scratch vectors can reuse token capacity across files processed by one worker.

Do not globally reuse scratch across concurrent parser calls.

Loop fusion between validation and scanning may reduce passes but weaken diagnostics.

Loop fission can isolate a rare escape-decoding path from ordinary tokens.

Prediction checkpoint: should discarded lines still receive full tokenization for consistency?

Answer: only if semantics or required diagnostics depend on tokens inside rejected lines.

17. Telemetry Tiles and Levels of Detail#

Consider sensors producing one thousand samples per second across ten thousand devices.

Recent dashboards show seconds; historical dashboards show months.

Raw samples are append-heavy, ordered usually, and occasionally arrive late.

Store recent raw chunks with timestamp deltas and quantized values where contracts permit.

Each chunk includes base time, scale, missing-value mask, and exceptional escape values.

Build minute summaries containing count, minimum, maximum, sum, and quality flags.

Build hour summaries from validated minute summaries rather than rereading all raw samples.

This is level of detail: query resolution determines which representation is sufficient.

range requested     representation        semantic error
last 30 seconds     raw samples           quantization bound
last 24 hours       minute summaries       timing/detail aggregation
last 12 months      hour summaries         wider aggregation

Averages must carry counts; averaging averages without weights is wrong whenever bucket counts differ, which is typical for real telemetry with gaps or partial windows.

Missing data must remain missing rather than silently becoming zero.

Late samples mark affected summaries dirty and schedule bounded rebuild work.

Summary indexes owe maintenance debt and expose a documented freshness watermark.

Chunking bounds decode work and permits targeted replacement after late arrival.

Very small chunks waste headers; very large chunks hurt random access and repair.

Double buffering can publish a complete summary snapshot while rebuilding the next.

Cache dashboard queries only with range, resolution, filters, and data version in keys.

Prediction checkpoint: can a monthly chart use one arbitrary sample per hour?

Answer: only under a stated sampling contract; extrema and missing periods may disappear.

18. Anti-Patterns and Their Repairs#

Cargo-cult SoA converts every record into columns without observing dominant loops.

Repair it by building an access matrix and including boundary conversion costs.

Giant global tables put unrelated lifetimes and ownership under one universal registry.

Repair them by assigning tables to coherent domains and explicit exchange boundaries.

Excessive normalization makes hot reads reconstruct obvious working sets repeatedly.

Repair it with measured, versioned derived views whose authority is documented.

Stale indexes occur when source mutations bypass index maintenance paths.

Repair them with encapsulated mutation, validation, versions, or deliberate rebuilding.

Batching everything increases latency, memory spikes, and semantic reordering hazards.

Repair it with bounded batches, deadlines, barriers, and direct paths for urgent work.

Premature bitsets add mapping complexity for tiny or very sparse domains.

Repair them by comparing set, vector, and chunked-bitset memory and query costs.

Address-based identity leaks physical layout into APIs and prevents safe compaction.

Repair it with typed generated handles resolved by the owning container.

One benchmark anti-pattern measures an isolated loop after excluding conversion overhead.

Repair it by reporting isolated diagnosis and end-to-end workload results together.

Another anti-pattern optimizes average input while p99 distributions cause failures.

Repair it with representative histograms, adversarial cases, and explicit capacity limits.

Finally, clever layouts without invariants become corruption mechanisms under mutation.

Repair them by writing invariants before code and testing every transition boundary.

19. Decision Tables and Reusable Redesign Worksheet#

Use this table to select experiments, not to replace measurement.

Copy this worksheet into a design note and fill every blank.

Goal and user-visible constraint:
Data quantities: minimum / typical / p95 / peak / hard limit:
Distributions and correlations:
Lifetimes and ownership:
Mutation frequency, fields, and range:
Optional fields and correlated capabilities:
Access order and dominant loops:
Selectivity after earlier filters:
Working set by phase:
Producers, consumers, and synchronization boundaries:
Access matrix with read/write and frequency:
Current useful bytes versus estimated moved bytes:
Candidate representations, including keeping the current one:
Conversion, allocation, ownership, and API costs:
Ordering, identity, and freshness contracts:
Invariants that every mutation must preserve:
Failure modes and capacity limits:
Benchmark dataset and end-to-end metric:
Evidence that would reject the proposal:
Rollback or migration plan:

Make at least two candidates and include the existing representation as a baseline.

Estimate before implementing so surprising measurements teach something specific.

State confidence ranges rather than presenting uncertain byte models as exact facts.

20. Exercises, Answer Sketches, and Practice Routine#

Exercise one: a million users have a rare suspended flag read hourly.

Compare record boolean, hash set membership, sorted IDs, and a bitset.

Answer sketch: use density, ID range, mutation frequency, and query shape.

An hourly full scan may favor a compact bitset with stable dense mapping.

Rare point lookups may favor a set without changing the user record layout.

Exercise two: an image filter touches RGB, while export needs metadata too.

Choose AoS, SoA, blocked layout, or a hot/cold split.

Answer sketch: benchmark pixel representation separately from cold image metadata.

Interleaved RGB can be excellent because each operation consumes all three channels.

Planar columns may win for channel-specific passes; blocks may balance both paths.

Exercise three: jobs are ninety-five percent waiting and five percent ready.

Answer sketch: a ready queue enables existence-based processing and removes global scans.

Transitions must prevent duplicate membership and preserve required scheduling fairness.

Exercise four: parser tokens reference a source buffer held for hours.

Answer sketch: copying selected long-lived lexemes may release a much larger source.

Measure retained bytes and copy cost, and document range lifetime contracts.

Exercise five: inventory queries use a stale product-to-zone index.

Answer sketch: centralize mutations, version the index, rebuild snapshots, or reject stale reads.

The correct choice depends on consistency promises and acceptable update latency.

Exercise six: particle removal uses swap-remove but replay output must be deterministic.

Answer sketch: sort output by stable ID, preserve stable order, or document nondeterminism.

Do not accidentally equate generated identity with physical dense ordering.

Exercise seven: telemetry values fit twelve bits with bounded sensor error.

Answer sketch: define unit, range, clamping, missing values, and total error budget.

Then compare saved bandwidth against packing, decoding, and random-access costs.

Exercise eight: a command buffer improves throughput but misses interaction deadlines.

Answer sketch: flush by deadline as well as size, and bound queued bytes.

Keep an immediate path only where ordering semantics remain understandable.

Prediction checkpoint: what is the first artifact in any redesign?

Answer: an observation sheet and access matrix, not a replacement container.

The practice routine is deliberately repetitive.

Observe quantities and distributions under realistic load.

Identify dominant work, useful bytes, moved bytes, and producer-consumer boundaries.

Propose the smallest reshaping that could remove measured waste.

Write identity, ordering, freshness, ownership, and error contracts.

List invariants and all mutations that owe maintenance work.

Include conversion costs and the possibility that the compiler already optimizes loops.

Benchmark the entire pipeline alongside focused diagnostic loops.

Reject the design when evidence contradicts its assumptions.

Keep it when it improves the chosen user-visible constraint without unacceptable debt.

Part III will turn these contracts into concrete Rust containers and operations.

Good redesign notes remain useful after their original benchmark expires. They record why a representation exists, which workload justified it, which contracts constrain it, and which measurements should trigger reconsideration. Future maintainers can then distinguish an essential invariant from an accidental implementation detail. That historical evidence also prevents a successful local optimization from becoming an unquestioned universal rule.

Until then, the craft is not memorizing layouts; it is learning to reshape responsibly.

Part III: Building Data-Oriented Structures in Stable Rust#

This part translates access models into safe, explicit Rust representations. By the end, you will be able to implement and test arenas, columns, sparse indexes, bitsets, and scratch storage.

1. Representation Is Part of the Design#

Data-oriented design starts by asking what bytes a computation reads, writes, and moves. Rust lets us answer many representation questions, but it deliberately leaves others unspecified. That distinction matters whenever a design depends on layout rather than merely on values.

std::mem::size_of::<T>() reports the stride of T in an array, including trailing padding. std::mem::align_of::<T>() reports the byte alignment required for a valid T location. Both are compile-time constants for sized types. A type with stronger alignment can force padding before a field and at the end of a structure.

use std::mem::{align_of, size_of};

#[derive(Debug)]
struct Example {
	flag: u8,
	count: u32,
}

fn main() {
	println!("u32: size={} align={}", size_of::<u32>(), align_of::<u32>());
	println!("Example: size={} align={}", size_of::<Example>(), align_of::<Example>());
}

Padding bytes are not fields. They need not be initialized merely because every field is initialized. Reading padding as bytes can therefore be undefined behavior in unsafe code. Do not hash or serialize a structure by viewing its complete storage as a byte slice. Serialize fields explicitly, which also defines byte order and format stability.

The default repr(Rust) optimizes for Rust's needs. It guarantees properly aligned, non-overlapping fields, but does not promise declaration order or stable offsets. Compiler versions and target architectures may choose different layouts. Never make a persistent format or foreign-function interface depend on default layout.

#[repr(C)] asks Rust to use the target's C-compatible aggregate layout rules. Its purpose is interoperability and, in suitable cases, documented field ordering. It does not make pointers portable, remove padding, define endianness, or create a versioned file format. Its fields must themselves have suitable foreign representations before crossing an FFI boundary. Rust enums and types such as String are not magically C-compatible when enclosed in a C structure.

#[repr(packed)] lowers alignment and can remove padding, but it is not a free compression switch. A packed field may be at an address invalid for a reference to its type. Creating such a reference is undefined behavior, even if a processor tolerates unaligned loads. Current Rust rejects many direct packed-field references, including safe-looking formatting expressions, but raw-pointer or unsafe code can still create an invalid reference if written incorrectly. Unaligned access requires raw-pointer operations and careful copying. Packed layouts also inhibit ordinary borrowing and can generate slower accesses. Prefer field reordering, separate arrays, narrower validated integers, or explicit encoding.

Use a measurement program for the exact target when layout affects capacity planning. Treat observed repr(Rust) offsets and enum sizes as observations, not promises. Rust documents some null-pointer optimizations for selected pointer-like types. Broader niche optimization is an implementation technique, not a general API contract. For example, do not persist an Option<MyEnum> by assuming its current in-memory bytes.

2. Owned Buffers, Views, and Pointer Stability#

An array [T; N] contains exactly N consecutive T values inline. Its length is part of its type, and its stride is size_of::<T>(). A slice [T] is a dynamically sized consecutive sequence. References &[T] and &mut [T] are borrowed views carrying a data address and length conceptually. Their exact ABI is not a serialization promise.

Box<T> owns one T in an allocation for ordinary non-zero-sized T. Moving a Box<T> moves the owning handle, not the allocation containing T. Consequently, the pointee address remains stable until ownership is converted, deallocated, or otherwise changed. This does not mean every address inside every boxed container is stable. A Box<Vec<T>> stabilizes the Vec header, not the vector's separate element allocation.

Vec<T> owns a contiguous sequence with a length and capacity. Length counts initialized elements available through indexing and slicing. Capacity is the number of elements that fit before growth is required. For non-zero-sized T, growth usually allocates a larger region, moves elements, and frees the old region. Therefore references and raw pointers into a vector cannot survive an operation that may reallocate. The standard library intentionally does not specify a growth factor. Zero-sized types have special capacity behavior and need no element storage.

Vec::with_capacity(n) requests room for at least n elements but leaves length zero. Indexing before pushing or otherwise initializing elements is invalid. reserve may over-allocate, whereas reserve_exact asks for the minimum while the allocator may still round. try_reserve and try_reserve_exact report allocation or capacity overflow instead of deliberately panicking. Production ingestion paths can use them before a mutation to provide a recoverable capacity error. Allocation can still fail in ways the process cannot recover from on every platform.

References express validity, alignment, lifetime, and aliasing requirements. An &mut T promises exclusive access for its active borrow. An &T permits shared reads but normally excludes mutation except through controlled interior mutability. Designing ownership so safe references suffice is usually simpler than proving raw-pointer obligations repeatedly.

Initialization is separate from allocation. Safe collections expose only initialized values and drop exactly those values. MaybeUninit<T> is useful in narrow low-level code, but its user must track initialization element by element. On panic, every initialized value must be dropped exactly once and every uninitialized slot must remain unread. Those obligations make a slightly redundant safe design attractive until profiling proves otherwise.

3. Parallel Structure-of-Arrays Vectors#

A structure of arrays, abbreviated SoA, stores each field in its own contiguous sequence. This helps a loop that reads positions without touching names, flags, or other cold fields. The main hazard is allowing field lengths to diverge. Private vectors and invariant-preserving methods turn that hazard into a local proof.

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Particle {
	pub x: f32,
	pub y: f32,
	pub vx: f32,
	pub vy: f32,
}

#[derive(Default)]
pub struct Particles {
	x: Vec<f32>,
	y: Vec<f32>,
	vx: Vec<f32>,
	vy: Vec<f32>,
}

impl Particles {
	pub fn new() -> Self { Self::default() }

	pub fn try_with_capacity(capacity: usize) -> Result<Self, std::collections::TryReserveError> {
		let mut result = Self::new();
		result.x.try_reserve(capacity)?;
		result.y.try_reserve(capacity)?;
		result.vx.try_reserve(capacity)?;
		result.vy.try_reserve(capacity)?;
		Ok(result)
	}

	pub fn len(&self) -> usize { self.x.len() }
	pub fn is_empty(&self) -> bool { self.x.is_empty() }

	pub fn push(&mut self, value: Particle) {
		self.x.push(value.x);
		self.y.push(value.y);
		self.vx.push(value.vx);
		self.vy.push(value.vy);
		debug_assert!(self.lengths_match());
	}

	pub fn get(&self, index: usize) -> Option<Particle> {
		Some(Particle {
			x: *self.x.get(index)?,
			y: *self.y.get(index)?,
			vx: *self.vx.get(index)?,
			vy: *self.vy.get(index)?,
		})
	}

	pub fn remove_swap(&mut self, index: usize) -> Option<Particle> {
		if index >= self.len() { return None; }
		let value = Particle {
			x: self.x.swap_remove(index),
			y: self.y.swap_remove(index),
			vx: self.vx.swap_remove(index),
			vy: self.vy.swap_remove(index),
		};
		debug_assert!(self.lengths_match());
		Some(value)
	}

	pub fn positions(&self) -> impl ExactSizeIterator<Item = (f32, f32)> + '_ {
		self.x.iter().copied().zip(self.y.iter().copied())
	}

	pub fn integrate(&mut self, dt: f32) {
		for (((x, y), vx), vy) in self.x.iter_mut()
			.zip(self.y.iter_mut()).zip(&self.vx).zip(&self.vy)
		{
			*x += *vx * dt;
			*y += *vy * dt;
		}
	}

	fn lengths_match(&self) -> bool {
		self.x.len() == self.y.len()
			&& self.x.len() == self.vx.len()
			&& self.x.len() == self.vy.len()
	}
}

zip stops at the shortest input, which can hide an invariant failure. Here private fields and every mutator maintain equal lengths, while debug assertions catch mistakes during development. For security-sensitive validation, use an ordinary assertion or return a corruption error at a trust boundary.

The simple push has a subtle failure characteristic. Any individual vector growth may abort on unrecoverable memory exhaustion. A recoverable transactional insertion can call try_reserve(1) on every field before pushing. After all reservations succeed, the pushes cannot need capacity growth and preserve equal lengths.

Returning four independent mutable slices can be valid because the vectors own disjoint allocations. Such a method is borrow-checker friendly and lets callers perform batch work without exposing vector-length mutation. Do not return &mut Vec<T>, because callers could push or truncate one field.

impl Particles {
	pub fn fields_mut(&mut self) -> (&mut [f32], &mut [f32], &mut [f32], &mut [f32]) {
		(&mut self.x, &mut self.y, &mut self.vx, &mut self.vy)
	}
}

4. One Allocation and Hot/Cold Splitting#

Four vectors can mean four allocations and four capacity decisions. A one-allocation SoA can reserve one byte region and place aligned columns at computed offsets. That design needs more machinery than adding field sizes. Each column start must be rounded up to its alignment. Multiplication and addition must be checked for overflow. The allocation layout must satisfy the maximum alignment. Growth must move initialized columns without reading padding or uninitialized storage. Panic cleanup must drop exactly the initialized elements in every column. Zero-sized fields and over-aligned fields need explicit policies.

No raw implementation is presented as copy-and-paste production code here. The standard Vec version is often fast enough and far easier to audit. Crates specializing in heterogeneous allocation can be appropriate when dependencies are permitted. A narrow unsafe implementation is justified only after measurements identify allocation count or locality as material.

Hot/cold splitting separates frequently traversed values from infrequently read metadata. An index or typed ID connects the two stores. The hot loop then consumes compact numeric arrays while diagnostics load names only on demand.

#[derive(Debug)]
pub struct BodyCold {
	pub name: String,
	pub description: String,
}

#[derive(Default)]
pub struct Bodies {
	hot: Particles,
	cold: Vec<BodyCold>,
}

impl Bodies {
	pub fn push(&mut self, hot: Particle, cold: BodyCold) {
		self.hot.push(hot);
		self.cold.push(cold);
		debug_assert_eq!(self.hot.len(), self.cold.len());
	}
}

This elementary store gives identity the same lifetime as dense position. Swap removal must update every associated structure, and external indices become invalid. Generational handles solve that identity problem.

5. Typed IDs and Handle Semantics#

A newtype wraps a primitive and prevents accidental mixing at compile time. Keep its fields private so callers cannot forge values that bypass validation. An arena handle needs a slot index and generation. The generation distinguishes a current occupant from a removed occupant that used the same slot.

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct EntityId {
	index: u32,
	generation: u32,
}

impl EntityId {
	pub fn index(self) -> usize { self.index as usize }
	pub fn generation(self) -> u32 { self.generation }
}

Using u32 halves handle width relative to two usize values on common 64-bit targets. It also imposes a maximum of u32::MAX + 1 representable slots. Insertion must reject capacity beyond that bound rather than truncate a usize cast. Typed IDs are values, not references, and carry no Rust lifetime. Every lookup must validate them.

6. A Generational Arena from Scratch#

The arena below uses one slot vector and a singly linked free list stored in vacant slots. Occupied slots contain values; vacant slots contain the next free index. Removing increments the generation before putting a slot on the free list. The implementation adopts a saturating retirement policy at u32::MAX. A slot removed at maximum generation is never reused, preventing an old handle from becoming valid after wraparound.

#[derive(Debug, PartialEq, Eq)]
pub enum InsertError {
	TooManySlots,
	Allocation(std::collections::TryReserveError),
}

#[derive(Debug)]
enum SlotState<T> {
	Occupied(T),
	Vacant { next: Option<u32> },
	Retired,
}

#[derive(Debug)]
struct Slot<T> {
	generation: u32,
	state: SlotState<T>,
}

#[derive(Debug, Default)]
pub struct Arena<T> {
	slots: Vec<Slot<T>>,
	free_head: Option<u32>,
	len: usize,
}

impl<T> Arena<T> {
	pub fn new() -> Self {
		Self { slots: Vec::new(), free_head: None, len: 0 }
	}

	pub fn len(&self) -> usize { self.len }
	pub fn is_empty(&self) -> bool { self.len == 0 }

	pub fn try_insert(&mut self, value: T) -> Result<EntityId, InsertError> {
		if let Some(index) = self.free_head {
			let slot = &mut self.slots[index as usize];
			let next = match slot.state {
				SlotState::Vacant { next } => next,
				_ => unreachable!("free list must contain vacant slots"),
			};
			self.free_head = next;
			slot.state = SlotState::Occupied(value);
			self.len += 1;
			return Ok(EntityId { index, generation: slot.generation });
		}

		let index = u32::try_from(self.slots.len()).map_err(|_| InsertError::TooManySlots)?;
		self.slots.try_reserve(1).map_err(InsertError::Allocation)?;
		self.slots.push(Slot { generation: 0, state: SlotState::Occupied(value) });
		self.len += 1;
		Ok(EntityId { index, generation: 0 })
	}

	pub fn insert(&mut self, value: T) -> EntityId {
		self.try_insert(value).unwrap_or_else(|error| panic!("arena insertion failed: {error:?}"))
	}

	pub fn get(&self, id: EntityId) -> Option<&T> {
		let slot = self.slots.get(id.index())?;
		if slot.generation != id.generation { return None; }
		match &slot.state {
			SlotState::Occupied(value) => Some(value),
			_ => None,
		}
	}

	pub fn get_mut(&mut self, id: EntityId) -> Option<&mut T> {
		let slot = self.slots.get_mut(id.index())?;
		if slot.generation != id.generation { return None; }
		match &mut slot.state {
			SlotState::Occupied(value) => Some(value),
			_ => None,
		}
	}

	pub fn remove(&mut self, id: EntityId) -> Option<T> {
		let slot = self.slots.get_mut(id.index())?;
		if slot.generation != id.generation { return None; }
		if !matches!(slot.state, SlotState::Occupied(_)) { return None; }

		let replacement = if slot.generation == u32::MAX {
			SlotState::Retired
		} else {
			slot.generation += 1;
			SlotState::Vacant { next: self.free_head }
		};
		let old = std::mem::replace(&mut slot.state, replacement);
		if !matches!(slot.state, SlotState::Retired) {
			self.free_head = Some(id.index);
		}
		self.len -= 1;
		match old {
			SlotState::Occupied(value) => Some(value),
			_ => unreachable!(),
		}
	}

	pub fn iter(&self) -> impl Iterator<Item = (EntityId, &T)> {
		self.slots.iter().enumerate().filter_map(|(index, slot)| {
			let SlotState::Occupied(value) = &slot.state else { return None };
			Some((EntityId { index: index as u32, generation: slot.generation }, value))
		})
	}
}

The invariants are explicit. Every free-list index is in bounds and names a vacant slot. Every vacant reusable slot occurs exactly once in the free list. No occupied or retired slot occurs there. len equals the occupied-slot count. An issued ID resolves only when index and generation match an occupied slot. Retirement trades bounded memory leakage of slots for permanent stale-handle rejection.

An alternative returns an error before removing an item whose generation cannot advance. That policy preserves reuse capacity but makes removal fallible at a rare boundary. Wrapping is unsafe at the semantic level because sufficiently old IDs can resurrect. A wider generation delays but does not logically eliminate wrap.

Multiple mutable lookups require care. Calling get_mut twice while retaining the first reference is rejected because the method borrows the arena. A get2_mut(a, b) API can reject equal indices, order indices, call split_at_mut, then validate generations. This safe split proves the returned slots are distinct. An iterator yielding &mut T can also be implemented safely from iter_mut, because each slot is visited once.

Entry APIs can avoid duplicate lookup and make insert-or-update intent explicit. An arena entry should retain an exclusive arena borrow and expose occupied or vacant operations. It must not expose free-list internals or permit changing a slot generation independently. Add such an API only when call sites benefit; it substantially enlarges the invariant surface.

7. Arena Tests and Differential Models#

Tests should attack transitions, not only happy-path values. A tiny standard-library model can map live IDs to values and compare every operation. Deterministic pseudo-random operations avoid external dependencies and make failures reproducible.

#[cfg(test)]
mod arena_tests {
	use super::*;
	use std::collections::HashMap;

	#[test]
	fn stale_handle_is_rejected_after_reuse() {
		let mut arena = Arena::new();
		let old = arena.insert("old");
		assert_eq!(arena.remove(old), Some("old"));
		assert_eq!(arena.get(old), None);
		let new = arena.insert("new");
		assert_eq!(old.index(), new.index());
		assert_ne!(old.generation(), new.generation());
		assert_eq!(arena.get(new), Some(&"new"));
	}

	#[test]
	fn empty_one_and_many_boundaries() {
		let mut arena = Arena::new();
		assert!(arena.is_empty());
		assert_eq!(arena.remove(EntityId { index: 0, generation: 0 }), None);
		let only = arena.insert(7);
		assert_eq!(arena.len(), 1);
		assert_eq!(arena.remove(only), Some(7));
		let ids: Vec<_> = (0..10_000).map(|n| arena.insert(n)).collect();
		for id in ids.iter().step_by(2) { assert!(arena.remove(*id).is_some()); }
		for id in ids.iter().step_by(2) { assert!(arena.get(*id).is_none()); }
		for id in ids.iter().skip(1).step_by(2) { assert!(arena.get(*id).is_some()); }
	}

	#[test]
	fn deterministic_differential_sequence() {
		let mut arena = Arena::new();
		let mut model = HashMap::new();
		let mut known = Vec::new();
		let mut state = 0x1234_5678_u32;
		for step in 0..20_000_i32 {
			state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
			if state % 3 != 0 || known.is_empty() {
				let id = arena.insert(step);
				model.insert(id, step);
				known.push(id);
			} else {
				let id = known[(state as usize) % known.len()];
				assert_eq!(arena.remove(id), model.remove(&id));
			}
			assert_eq!(arena.len(), model.len());
			for (&id, value) in &model { assert_eq!(arena.get(id), Some(value)); }
		}
	}

	#[test]
	fn maximum_generation_retires_slot() {
		let mut arena = Arena::new();
		arena.slots.push(Slot { generation: u32::MAX, state: SlotState::Occupied(1) });
		arena.len = 1;
		let id = EntityId { index: 0, generation: u32::MAX };
		assert_eq!(arena.remove(id), Some(1));
		assert!(matches!(arena.slots[0].state, SlotState::Retired));
		let next = arena.insert(2);
		assert_eq!(next.index(), 1);
	}
}

Tests inside the module may construct boundary states that public operations cannot reach promptly. That is appropriate for generation wrap policy, provided the crafted state satisfies all pre-operation invariants. Also test removing the free-list head, repeated removal, reinsertion order, invalid high indices, and mutable updates.

Drop safety needs a counter type whose Drop increments shared atomic state. Insert counters, remove some and drop returned values, then drop the arena. The final count must equal the constructed count exactly. Include a type that panics only under a controlled test if panic cleanup is being audited. Safe Vec and enum operations already provide strong foundations, but tests catch accidental duplication or leaks.

8. Dense Packed Storage with Stable IDs#

An arena leaves holes, which can make a full scan fetch unused slots. Packed storage keeps values dense and uses mappings to preserve external identity. For each live ID, id_to_dense[id.index] gives a dense index and expected generation. For each dense element, dense_to_id[dense] gives its owner ID. The two mappings must be inverses for all live elements.

#[derive(Clone, Copy, Debug)]
struct DenseLocation {
	generation: u32,
	dense: usize,
}

pub struct Packed<T> {
	ids: Arena<()>,
	values: Vec<T>,
	dense_to_id: Vec<EntityId>,
	id_to_dense: Vec<Option<DenseLocation>>,
}

impl<T> Packed<T> {
	pub fn new() -> Self {
		Self { ids: Arena::new(), values: Vec::new(), dense_to_id: Vec::new(), id_to_dense: Vec::new() }
	}

	pub fn insert(&mut self, value: T) -> EntityId {
		let id = self.ids.insert(());
		let dense = self.values.len();
		self.values.push(value);
		self.dense_to_id.push(id);
		if id.index() == self.id_to_dense.len() { self.id_to_dense.push(None); }
		self.id_to_dense[id.index()] = Some(DenseLocation { generation: id.generation(), dense });
		id
	}

	fn dense_index(&self, id: EntityId) -> Option<usize> {
		let location = self.id_to_dense.get(id.index())?.as_ref()?;
		(location.generation == id.generation()).then_some(location.dense)
	}

	pub fn get(&self, id: EntityId) -> Option<&T> {
		self.values.get(self.dense_index(id)?)
	}

	pub fn get_mut(&mut self, id: EntityId) -> Option<&mut T> {
		let dense = self.dense_index(id)?;
		self.values.get_mut(dense)
	}

	pub fn remove(&mut self, id: EntityId) -> Option<T> {
		let dense = self.dense_index(id)?;
		self.ids.remove(id)?;
		self.id_to_dense[id.index()] = None;
		let removed = self.values.swap_remove(dense);
		self.dense_to_id.swap_remove(dense);
		if dense < self.values.len() {
			let moved_id = self.dense_to_id[dense];
			let moved = self.id_to_dense[moved_id.index()].as_mut().expect("live reverse mapping");
			moved.dense = dense;
		}
		Some(removed)
	}

	pub fn iter(&self) -> impl Iterator<Item = (EntityId, &T)> {
		self.dense_to_id.iter().copied().zip(&self.values)
	}
}

The insertion shown is concise rather than allocation-transactional. A production fallible insertion reserves every growing vector before mutating the ID arena. Otherwise a recoverable allocation error after ID insertion would require rollback. Unrecoverable allocation failure may abort, but APIs should document which failures panic and which return errors.

Swap removal is constant time but changes iteration order. The fixup after swap_remove is essential: the last value moved into the hole now has a different dense index. Tests must remove the first, middle, last, and only values, then verify both mappings.

Stable order can use Vec::remove, shifting the suffix and updating every shifted reverse mapping. That costs linear time and moves values. Another alternative stores tombstones and compacts in a deliberate maintenance phase. Stable ordering is a requirement to state, not an accidental property to rely on.

9. Sparse-Set Component Storage#

A sparse set maps a bounded integer universe into a dense array. The dense array gives cache-friendly iteration. The sparse mapping answers membership and finds dense positions. Generations still need validation when entity indices can be reused.

The bounded form allocates one optional entry per possible or observed entity index. It is simple and fast when indices are compact.

#[derive(Clone, Copy)]
struct SparseEntry {
	generation: u32,
	dense: usize,
}

pub struct SparseSet<T> {
	sparse: Vec<Option<SparseEntry>>,
	entities: Vec<EntityId>,
	values: Vec<T>,
}

impl<T> SparseSet<T> {
	pub fn new() -> Self {
		Self { sparse: Vec::new(), entities: Vec::new(), values: Vec::new() }
	}

	fn index_of(&self, id: EntityId) -> Option<usize> {
		let entry = self.sparse.get(id.index())?.as_ref()?;
		if entry.generation != id.generation() { return None; }
		let dense_id = *self.entities.get(entry.dense)?;
		(dense_id == id).then_some(entry.dense)
	}

	pub fn contains(&self, id: EntityId) -> bool { self.index_of(id).is_some() }

	pub fn get(&self, id: EntityId) -> Option<&T> {
		self.values.get(self.index_of(id)?)
	}

	pub fn get_mut(&mut self, id: EntityId) -> Option<&mut T> {
		let dense = self.index_of(id)?;
		self.values.get_mut(dense)
	}

	pub fn insert(&mut self, id: EntityId, value: T) -> Option<T> {
		if let Some(dense) = self.index_of(id) {
			return Some(std::mem::replace(&mut self.values[dense], value));
		}
		if self.sparse.len() <= id.index() { self.sparse.resize(id.index() + 1, None); }
		let dense = self.values.len();
		self.entities.push(id);
		self.values.push(value);
		self.sparse[id.index()] = Some(SparseEntry { generation: id.generation(), dense });
		None
	}

	pub fn remove(&mut self, id: EntityId) -> Option<T> {
		let dense = self.index_of(id)?;
		self.sparse[id.index()] = None;
		let removed = self.values.swap_remove(dense);
		self.entities.swap_remove(dense);
		if dense < self.entities.len() {
			let moved = self.entities[dense];
			self.sparse[moved.index()] = Some(SparseEntry {
				generation: moved.generation(), dense
			});
		}
		Some(removed)
	}

	pub fn iter(&self) -> impl Iterator<Item = (EntityId, &T)> {
		self.entities.iter().copied().zip(&self.values)
	}
}

Replacing a stale generation at the same sparse index is allowed here. The old component remains densely stored unless explicitly removed, so the shown insert needs a policy correction in production. Before adding, inspect sparse[id.index()]; if it names another generation, remove that dense occupant or reject insertion as an entity-lifecycle error. Calling this out prevents a common leak in simplified sparse-set examples.

A paged sparse mapping avoids allocating up to one unexpectedly huge ID. Choose a page size such as 256 or 1024 entries. The page directory is indexed by id / PAGE, and each optional boxed page contains fixed entries indexed by id % PAGE. Only touched ranges allocate pages, though a far-out ID can still enlarge a vector directory. A tree map directory avoids that enlargement but adds logarithmic lookup and pointer chasing.

const PAGE: usize = 256;

struct SparsePages {
	pages: Vec<Option<Box<[Option<SparseEntry>; PAGE]>>>,
}

impl SparsePages {
	fn get(&self, index: usize) -> Option<SparseEntry> {
		self.pages.get(index / PAGE)?.as_ref()?[index % PAGE]
	}

	fn slot_mut(&mut self, index: usize) -> &mut Option<SparseEntry> {
		let page_index = index / PAGE;
		if self.pages.len() <= page_index { self.pages.resize_with(page_index + 1, || None); }
		let page = self.pages[page_index].get_or_insert_with(|| Box::new([None; PAGE]));
		&mut page[index % PAGE]
	}
}

The bounded vector costs O(max_id) sparse memory and provides direct predictable access. Paged storage costs O(touched_pages * page_size) plus a directory. Dense arrays cost O(live_components) and dominate query scanning. Choose with actual ID density and maximum-index constraints.

Sparse-set tests mirror packed-store tests and additionally use enormous separated IDs if the API permits them. Verify replacement, stale-generation insertion policy, membership after swaps, empty queries, and repeated remove. Differential testing can compare to HashMap<EntityId, T> after every deterministic operation.

10. Bitsets and Set Iteration#

A bitset stores one Boolean membership value per bit rather than per byte or enum. It is useful for bounded IDs, filters, dirty flags, and set intersections. Words enable testing many candidates with one machine operation.

#[derive(Default, Clone)]
pub struct BitSet {
	words: Vec<u64>,
}

impl BitSet {
	pub fn contains(&self, bit: usize) -> bool {
		self.words.get(bit / 64).is_some_and(|word| word & (1_u64 << (bit % 64)) != 0)
	}

	pub fn insert(&mut self, bit: usize) -> bool {
		let index = bit / 64;
		if self.words.len() <= index { self.words.resize(index + 1, 0); }
		let mask = 1_u64 << (bit % 64);
		let was_present = self.words[index] & mask != 0;
		self.words[index] |= mask;
		!was_present
	}

	pub fn remove(&mut self, bit: usize) -> bool {
		let Some(word) = self.words.get_mut(bit / 64) else { return false };
		let mask = 1_u64 << (bit % 64);
		let was_present = *word & mask != 0;
		*word &= !mask;
		was_present
	}

	pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
		self.words.iter().copied().enumerate().flat_map(|(word_index, mut word)| {
			std::iter::from_fn(move || {
				if word == 0 { return None; }
				let offset = word.trailing_zeros() as usize;
				word &= word - 1;
				Some(word_index * 64 + offset)
			})
		})
	}
}

Clearing the lowest set bit makes iteration proportional to set bits rather than bit capacity. Intersection zips words and applies &; union applies |; difference applies & !. Again, zip requires a stated length policy: missing words can be treated as zero. If generations matter, a bit by index alone cannot distinguish reused entities. Use it as a candidate filter, then validate generation through authoritative storage.

11. State Buckets and Deferred Transitions#

Branching on state for every element can disrupt a hot loop. State buckets keep active, sleeping, and disabled IDs in separate dense lists. Each state-specific loop then has less branching and reads only relevant data.

Changing buckets while iterating a bucket complicates borrows and may skip moved elements. Record transition commands first, then apply them at a synchronization point. This is deferred mutation: intent is collected separately from structural change.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum State { Active, Sleeping, Disabled }

#[derive(Clone, Copy, Debug)]
struct Transition { id: EntityId, to: State }

#[derive(Default)]
struct TransitionQueue { pending: Vec<Transition> }

impl TransitionQueue {
	fn request(&mut self, id: EntityId, to: State) {
		self.pending.push(Transition { id, to });
	}

	fn drain(&mut self) -> impl Iterator<Item = Transition> + '_ {
		self.pending.drain(..)
	}
}

Define duplicate-command semantics. “Last request wins” can compact commands by ID before application. “First request wins” can reject later commands. Sequential application is simplest but allows intermediate hooks to observe multiple transitions. Validate every ID when applying because an entity may have been removed after queuing.

Buckets can be sparse sets whose values are empty metadata. Moving an entity removes it from its old set and inserts it into the new one. To make the operation transactional under recoverable allocation failure, reserve destination capacity before removing source membership. Callbacks should run after invariants are restored, especially if they can panic or reenter the store.

12. Scratch Memory Without Leaking Lifetimes#

A bump allocator reserves a region and advances an offset for each allocation. Resetting the offset releases all allocations at once. This is excellent for phase-local temporary data when individual deallocation is unnecessary. Typed values with destructors make reset more complex because each live value must be dropped. Returned references must not outlive the reset or the backing allocation.

A raw allocator sketch would compute an aligned start as round_up(offset, align_of::<T>()), check multiplication and addition, ensure bounds, write initialized values, and record drop functions. That sketch is educational, not production copy/paste. Its unsafe core must prove initialization before reads, bounds within the allocated region, alignment for every T, no overlapping mutable aliases, lifetimes bounded by the arena borrow, and panic cleanup that drops each initialized value exactly once. Reallocation while references exist would invalidate them, so the backing allocation must remain fixed for a phase. Allocation and layout errors must be explicit.

Often the safe replacement is a reusable Vec<T> scratch buffer owned by the caller. The operation clears it, fills it, consumes a slice, and retains capacity for the next call.

#[derive(Default)]
pub struct Scratch<T> {
	items: Vec<T>,
}

impl<T> Scratch<T> {
	pub fn prepare<F>(&mut self, reserve: usize, fill: F) -> Result<&[T], std::collections::TryReserveError>
	where
		F: FnOnce(&mut Vec<T>),
	{
		self.items.clear();
		self.items.try_reserve(reserve)?;
		fill(&mut self.items);
		Ok(&self.items)
	}

	pub fn clear(&mut self) { self.items.clear(); }
}

clear drops old elements but preserves capacity. The returned slice borrows Scratch, so Rust prevents another preparation until the slice is no longer used. For several element types, keep several typed buffers in a phase context. For temporary bytes, use Vec<u8> but do not cast those bytes to arbitrary typed references.

An operation may instead accept &mut Vec<T> directly. That exposes capacity choices but keeps ownership obvious. Thread-local scratch avoids plumbing but introduces hidden retained memory, reentrancy questions, and interior mutability. Explicit per-worker contexts usually make memory budgets and Send boundaries clearer.

13. Blocked and Array-of-Structures-of-Arrays Layouts#

AoSoA means an array of small SoA blocks. It balances contiguous field scans with bounded grouping of related fields. A block size may match a SIMD width or cache consideration, but should be measured per workload. Stable Rust const generics express a fixed block length.

#[derive(Clone)]
struct ParticleBlock<const N: usize> {
	x: [f32; N],
	y: [f32; N],
	vx: [f32; N],
	vy: [f32; N],
	len: usize,
}

impl<const N: usize> ParticleBlock<N> {
	fn new() -> Self {
		assert!(N > 0, "block size must be nonzero");
		Self { x: [0.0; N], y: [0.0; N], vx: [0.0; N], vy: [0.0; N], len: 0 }
	}

	fn push(&mut self, p: Particle) -> Result<usize, Particle> {
		if self.len == N { return Err(p); }
		let i = self.len;
		self.x[i] = p.x;
		self.y[i] = p.y;
		self.vx[i] = p.vx;
		self.vy[i] = p.vy;
		self.len += 1;
		Ok(i)
	}

	fn integrate(&mut self, dt: f32) {
		for i in 0..self.len {
			self.x[i] += self.vx[i] * dt;
			self.y[i] += self.vy[i] * dt;
		}
	}
}

struct BlockedParticles<const N: usize> {
	blocks: Vec<ParticleBlock<N>>,
	len: usize,
}

Unused lanes in the final block are initialized zeros, avoiding unsafe partial initialization. The cost is at most N - 1 unused entries per field plus a block length. Removal can swap with the final live lane across blocks, then discard an empty final block. External block-and-lane positions are unstable, so map stable IDs as in packed storage.

Large N makes block moves expensive and may increase stack use when constructing blocks. Small N adds length metadata and more boundary handling. Const generics do not guarantee vectorization or a particular machine instruction width. They only make size available to type checking and optimization.

14. Slice-Based Batch Transforms#

Batch APIs expose simple contiguous loops to the optimizer. They also amortize validation and function-call overhead. Accept slices rather than collection types when the operation needs only a view.

pub fn integrate_xy(
	x: &mut [f32],
	y: &mut [f32],
	vx: &[f32],
	vy: &[f32],
	dt: f32,
) -> Result<(), LengthMismatch> {
	let len = x.len();
	if y.len() != len || vx.len() != len || vy.len() != len {
		return Err(LengthMismatch { x: len, y: y.len(), vx: vx.len(), vy: vy.len() });
	}
	for i in 0..len {
		x[i] += vx[i] * dt;
		y[i] += vy[i] * dt;
	}
	Ok(())
}

#[derive(Debug, PartialEq, Eq)]
pub struct LengthMismatch { x: usize, y: usize, vx: usize, vy: usize }

Checking lengths once prevents zip truncation and can help bounds-check elimination. Index loops and iterator loops can both optimize well; inspect generated behavior only after measuring a real bottleneck. Avoid forcing inlining everywhere. Keep exceptional branches outside the innermost loop when semantics permit.

Aliasing information is valuable. Separate &mut [f32] arguments promise that active mutable borrows do not overlap in invalid ways. When fields come from one struct, a method can split borrows by borrowing distinct fields directly. If data is interleaved, safe chunking methods such as split_at_mut establish disjoint regions.

Batch transforms should define floating-point semantics. Reassociation can change rounding and special-value behavior. Ordinary stable Rust does not silently grant arbitrary fast-math transformations. If deterministic simulation matters, document target and operation-order expectations and test tolerances carefully.

15. Borrow-Friendly Store Interfaces#

The borrow checker reasons from API structure, not domain promises hidden in comments. Expose disjoint columns as disjoint slices. Provide closures or query objects when a temporary compound borrow is easier than returning references. Use split_at_mut for two distinct indices after rejecting equality.

A query joining two sparse sets should iterate the smaller dense entity list and probe the larger sparse mapping. That avoids scanning absent combinations. Returning (&mut A, &mut B) is straightforward when components live in distinct store fields. Two components of the same type require distinctness checks and split borrowing.

Iterators should encode invariant assumptions. An immutable dense iterator can zip equal private vectors. A mutable iterator should originate from iter_mut, which guarantees each element appears at most once. Do not build a safe mutable iterator by repeatedly converting stored raw pointers unless a complete unsafe proof exists.

Interior mutability moves checks from compile time to runtime or hardware synchronization. Cell<T> supports copy-in/copy-out values without references to interiors. RefCell<T> dynamically checks shared and exclusive borrows and panics on violation; it is not Sync. Mutex<T> and RwLock<T> synchronize threads and can be poisoned after panic. Atomics support narrow operations with explicit ordering but are not a general replacement for invariants. Use these because mutation is genuinely shared, not merely to silence a design problem.

An entry API combines lookup and mutation under one exclusive borrow. It can return occupied and vacant variants whose methods preserve mappings. For sparse stores, an entry prevents doing contains followed by a second lookup. The vacant entry must either reserve before mutation or document panic-only allocation behavior.

16. Send, Sync, and Parallel Boundaries#

Send means ownership of a value may move to another thread safely. Sync means shared references to a value may be used from multiple threads safely. The compiler derives these auto traits from fields when possible. Raw pointers and interior-mutability choices can alter derivation and deserve deliberate review.

Plain stores built from Vec<T> are generally Send when T: Send and Sync when T: Sync. That does not make concurrent mutation automatically available. An exclusive &mut Store can be divided into disjoint slices and scoped across workers using the standard threading API. Cross-thread structural mutation is usually better represented as per-worker command queues merged at a phase boundary.

Generational IDs can be copied between threads, but validity still depends on synchronized access to the authoritative store. An ID alone grants no memory access and should not contain a naked pointer. Queues need a policy for commands racing with entity removal. Deterministic systems can sort merged commands by a stable sequence key before applying them.

Do not write unsafe impl Send or unsafe impl Sync merely because code appears race-free in tests. Such an implementation promises safety for every legal caller and future internal change. If a raw allocation core needs these implementations, document ownership transfer, synchronization, aliasing, destructor thread constraints, and pointee trait bounds beside them.

17. When a Narrow Unsafe Core Is Justified#

Unsafe Rust is appropriate when implementing an abstraction whose performance or interoperability cannot be obtained safely and whose contract can be proved. Examples include a measured one-allocation SoA, a custom fixed-capacity arena, or an FFI boundary. Keep unsafe operations in tiny functions with safe callers that establish preconditions. Enable the unsafe_op_in_unsafe_fn lint so each operation remains visibly scoped.

Every unsafe review must answer six classes of question. Initialization: which bytes contain valid T values at every point, including unwinding? Bounds: which checked arithmetic proves every offset and range lies in the allocation? Aliasing: can any shared and mutable references overlap while active? Alignment: how is every address rounded and validated for its pointee type? Lifetime: what owner keeps the allocation alive, and can growth or reset invalidate a reference? Panic and drop: which guard drops initialized values exactly once if construction or movement panics?

Also prove allocation layout validity, provenance-sensitive pointer derivation, zero-sized behavior, and thread traits. Use ptr::read_unaligned only when unaligned representation is truly required and no reference is formed. Do not casually use transmute; explicit conversion usually exposes assumptions better. Do not use packed structs as a substitute for serialization.

A safe baseline and differential tests should exist before introducing unsafe optimization. Run interpreter and sanitizer tooling where supported, while recognizing that tools supplement rather than replace proof. Document compiler-version and target assumptions if implementation details are unavoidable.

18. Errors, Capacity, and Memory Exhaustion#

Collection APIs need a consistent failure story. Lookup and removal naturally return Option for absent or stale IDs. Insertion can return a domain error for exhausted ID space and a reservation error for recoverable allocation failure. Index arithmetic uses checked_add and checked_mul before allocation calculations.

Do not mutate half of a multi-vector invariant before a fallible reservation. Reserve all required buffers first, then perform infallible logical updates. If later user code can panic, restore invariants before invoking it or use a rollback guard. Dropping a value can panic, although doing so during another unwind may abort the process. Library invariants should not depend on destructors behaving politely.

Memory budgets matter even when the allocator succeeds. A sparse vector expanded by an untrusted huge ID can become a denial of service. Bound IDs, use pages, or reject growth beyond configured limits. Scratch buffers retain their peak capacity, so provide trimming or phase-level destruction where peaks are exceptional. Retired generational slots consume index space and should be observable through metrics in very long-lived systems.

shrink_to_fit is a request and may not reduce capacity. Frequent shrinking and regrowing creates allocator churn. Capacity policies should derive from workload phases, not from an instinct that unused capacity is always waste.

19. Comprehensive Invariant Testing#

Example tests demonstrate intended use, while property-style tests explore operation sequences. No dependency is required: use a deterministic linear congruential generator and a standard collection as a model. Log the seed and operation index on failure so the sequence is reproducible.

For every arena sequence, compare live count, lookup result, removal result, and iteration contents against a HashMap model. Retain all historical IDs and periodically assert removed IDs remain invalid. Force immediate slot reuse, long free lists, alternating remove/insert, and complete drain/refill cycles. Craft maximum-generation states inside module tests and confirm the selected wrap policy exactly.

For packed storage, assert lengths of values and reverse IDs match. For every dense index, follow dense-to-ID then ID-to-dense and recover the original index. For every live ID, follow the inverse direction and compare values. Exercise swap removal at zero, middle, and final positions after every insertion count from one upward.

For sparse sets, compare with HashMap<EntityId, T>. Test replacement returns the old value, stale generations do not match, moved dense entries receive fixed sparse indices, and paging boundaries at PAGE - 1, PAGE, and PAGE + 1 work. Test sparse page absence without accidentally allocating during read-only lookup.

Bitset tests cover bits 0, 63, 64, 65, and a large configured boundary. Compare iteration with a BTreeSet<usize> to verify sorted unique output. Test empty intersections, unequal word lengths, and removal of absent bits.

Batch-transform tests cover empty slices, one element, a large vector, mismatched lengths, negative dt, infinities, and NaNs where semantics permit. AoSoA tests cross every block boundary and compare against a simple Vec<Particle> model. State-queue tests include duplicate transitions, stale IDs, removal before apply, and transitions requested during callbacks if callbacks are supported.

Drop tests use Arc<AtomicUsize> counters. Count construction and destruction across normal drop, explicit removal, replacement, swap removal, clear, and partial error paths. Values returned from removal remain the caller's responsibility and should not be counted as dropped until the caller drops them. Never intentionally trigger process-level allocation exhaustion in ordinary tests.

Large tests should be large enough to cross capacities and mapping pages, not merely large for appearance. Keep a slow model suite separate if it affects normal feedback time. When a failure appears, reduce the operation sequence manually or with a small in-house reducer before changing implementation.

20. Module Organization#

Organize by invariants rather than by fashionable labels. A practical crate might separate id, arena, packed, sparse_set, bit_set, scratch, and domain stores. Keep slot and mapping internals private to their modules. Re-export only stable user-facing handles and containers from the crate root.

The id module should define construction visibility and conversions. If IDs enter through a network or file, decode integers into a provisional representation and validate them against the current store. Deserialization cannot prove that a generation is still live. Avoid implementing an unchecked public conversion from a tuple when forged handles would confuse callers.

The arena module owns slot generations, retirement, and the free list. No neighboring module should edit those fields directly. It can expose iteration and capacity statistics without exposing a mutable slot slice. Useful statistics include occupied, vacant, retired, allocated slot capacity, and reusable free count. An invariant-checking method compiled for tests can walk the free list with a visited bitset and compare all counts.

The packed module composes identity with dense movement. Composition is preferable to duplicating generation logic, provided insertion rollback is designed explicitly. Keep mapping assertions close to every operation that moves a dense value. A private check_invariants method can verify inverses in linear time after each operation in small tests. Do not run that full scan in production hot paths unless diagnostic mode intentionally requests it.

The sparse_set module should state whether it trusts an external arena to establish entity liveness. If it does, inserting a component for a dead ID is a caller error and should return a defined error. If it does not, it needs access to an authority capable of validating handles. Silently accepting arbitrary handles leaves orphaned components that no entity lifecycle will remove.

Domain stores combine these primitives around actual access patterns. They decide which fields are hot, which components are optional, and which transitions are legal. Keeping domain policy above storage machinery prevents a generic container from accumulating unrelated callbacks and state rules. It also lets unit tests distinguish a broken mapping from a rejected domain transition.

src/
  lib.rs
  id.rs
  arena.rs
  packed.rs
  sparse_set.rs
  bit_set.rs
  scratch.rs
  body_store.rs
  tests/
    model_sequences.rs

Unit tests inside modules can inspect private invariants and construct generation-boundary states. Integration tests exercise only public behavior and protect encapsulation. Documentation examples should compile and show error handling, not just ideal inputs.

Public names should communicate stability. Call a position dense_index rather than id when swap removal can change it. Call a handle EntityId only when the application treats it as entity identity. Document whether cloning a store preserves handles, creates a separate identity universe, or is deliberately unsupported. Two arenas can issue numerically equal handles; a handle type alone does not identify its originating arena. Applications needing cross-store protection can include a store token, while recognizing the extra memory and comparison cost.

Version public behavior separately from physical representation. Changing from bounded sparse mapping to pages should not affect membership semantics. Changing generation width does affect serialization and foreign interfaces if raw handles cross those boundaries. Prefer explicit encoded handle formats with version tags over dumping native integer layouts.

Feature boundaries deserve similar care. Core containers can remain dependency-free and stable-Rust compatible. Optional persistence, parallel schedulers, or platform allocation policies can live in higher modules. This keeps foundational invariants reviewable and avoids forcing every consumer to accept unrelated machinery.

Avoid a generic “storage framework” until several concrete stores reveal genuinely shared behavior. Arena identity, packed order, sparse membership, and scratch lifetime have different contracts. Premature traits can erase useful slice access or force allocation behind abstractions. Small adapters at query boundaries are often enough.

21. Production API Review Checklist#

Representation: Are layout assumptions limited to documented guarantees? Representation: Are size_of and align_of measurements target-specific observations where appropriate? Representation: Is padding excluded from hashing, equality-by-bytes, serialization, and initialization assumptions? Representation: Does every repr(C) type have an actual interoperability reason? Representation: Has every packed representation been rejected unless unaligned storage is unavoidable?

Identity: Are integer domains separated by private newtypes? Identity: Can callers forge handles or bypass generation checks? Identity: Is generation wrap policy documented and tested? Identity: Is maximum slot count checked before narrowing conversions? Identity: Are stale IDs rejected by every read, write, removal, and queued command path?

Storage: Are parallel lengths private and changed transactionally? Storage: Are dense and reverse mappings exact inverses? Storage: Does swap removal repair every moved index? Storage: Is iteration-order stability explicitly promised or explicitly denied? Storage: Can an untrusted sparse index force unreasonable allocation? Storage: Are final partial blocks represented without reading uninitialized lanes?

Borrowing: Do APIs return slices instead of mutable collection internals? Borrowing: Are distinct mutable accesses proved with field splitting or split_at_mut? Borrowing: Can an iterator yield the same location mutably twice? Borrowing: Does any callback run while invariants are temporarily broken? Borrowing: Is interior mutability chosen for actual shared mutation rather than convenience?

Allocation: Are checked arithmetic and ID limits applied before allocation? Allocation: Are fallible reservations completed before multi-structure mutation? Allocation: Is retained scratch capacity observable and controllable? Allocation: Are error, panic, abort, and configured-limit behaviors documented? Allocation: Does rollback preserve values and generations after a recoverable failure?

Unsafe code: Is the safe baseline inadequate according to a measurement? Unsafe code: Is the unsafe core small, private, and surrounded by safe contracts? Unsafe code: Are initialization, bounds, aliasing, alignment, lifetime, and panic/drop proofs written down? Unsafe code: Are zero-sized, over-aligned, and destructor-bearing types handled? Unsafe code: Are Send and Sync derivations or implementations justified?

Testing: Do empty, one-element, boundary, and large cases run? Testing: Do remove/reinsert sequences retain and probe stale IDs? Testing: Is maximum generation reached through a valid crafted state? Testing: Does a standard-library model check randomized deterministic sequences? Testing: Do drop counters cover removal, replacement, errors, and container destruction?

Documentation: Is each jargon term defined near first use? Documentation: Are complexity and order guarantees stated? Documentation: Are invalid-input and memory-exhaustion outcomes stated? Documentation: Are conceptual sketches labeled so users do not copy incomplete unsafe code? Documentation: Are layout and niche observations kept out of persistent formats?

22. Closing Construction Principles#

Data-oriented Rust is not a contest to remove every byte or every bounds check. It is the practice of arranging ownership and representation around the work a program repeatedly performs. Start with safe vectors, slices, enums, and private invariants. They already provide contiguous storage, correct destruction, and strong aliasing information.

Separate identity from position when dense movement is useful. Use generations to reject stale handles and choose an explicit wrap policy. Use reverse mappings whenever swap removal can move an element. Use sparse mappings when membership probes accompany dense iteration. Use bitsets when Boolean sets and word-wise operations fit the ID universe.

Defer structural transitions to phase boundaries when immediate mutation conflicts with iteration. Reuse typed scratch vectors before building a raw bump allocator. Block data only when measured access patterns justify the extra boundary logic. Express hot work as validated slice transforms that expose simple loops.

Most importantly, make every optimization preserve a readable proof. The proof names initialized values, valid indices, current generations, disjoint borrows, stable owners, and defined failure behavior. When that proof no longer fits beside the code, the structure is not yet ready for production.

Benchmarking belongs mainly to the next part. For now, compare release builds, use representative data distributions, separate setup from the measured loop, warm up where appropriate, and confirm outputs so the optimizer cannot remove work. Measure whole-system effects as well as isolated throughput. A more compact layout is valuable only when it improves the workload that users actually run.

Part IV: ECS, Queries, Scheduling, and Production Architecture#

Data-oriented design (DOD) is broader than entity-component-system architecture. ECS is one useful consequence of arranging data around transformations and access patterns. It is not a synonym for DOD, nor a certificate of performance. This part derives ECS, examines its costs, and then moves beyond it. The recurring question is not “How do I use ECS?” It is “What data shape makes this workload simple and efficient?” By the end, you will understand ECS as one derived architecture and know when a simpler DOD structure is better.

1. From tables and set intersection to ECS#

Imagine a simulation represented by ordinary tables. One table stores positions, keyed by object identity. Another stores velocities, also keyed by identity. A third stores names, while a fourth stores health. Movement needs rows appearing in both position and velocity tables. That requirement is a set intersection over entity identities.

The movement set is {7, 19}. The damage set might be every identity in the health table. The render set could require position and sprite while excluding hidden. Queries merely name such membership constraints.

An entity is identity, not the object’s data. It is usually a compact handle used to correlate independent tables. A component is data associated with an entity. Components should describe state, not contain an inheritance hierarchy. A system is a transform over selected component rows. Its inputs, outputs, and access mode should be visible.

This vocabulary discourages object-shaped ownership. Position does not need a pointer to velocity. Movement does not ask each object to update itself. Instead, movement streams through relevant columns in a predictable loop.

fn integrate(dt: f32, positions: &mut [Position], velocities: &[Velocity]) {
	for (position, velocity) in positions.iter_mut().zip(velocities) {
		position.x += velocity.x * dt;
		position.y += velocity.y * dt;
	}
}

That loop assumes aligned rows, an especially favorable representation. General ECS storage must recover alignment through tables, indices, or joins. Every recovery mechanism has a cost worth measuring.

identities ──membership──> component tables
     │                         │
     └──── set intersection ───┘
                    │
                    v
             system row stream
                    │
                    v
              updated columns

ECS therefore follows from relational thinking. Identity behaves like a primary key. Component membership resembles a sparse relation. A query resembles a restricted join. A system resembles a batch update. The analogy is useful, although ECS engines are not databases. They usually optimize in-memory iteration rather than durable transactions.

2. Entity identity and generations#

A plain integer index can identify a slot. Unfortunately, deleted slots are eventually reused. An old handle could then silently refer to a different entity. This error is called the ABA problem in this context. The index changed from occupied, to free, to occupied again.

A generational ID pairs a slot index with a generation counter. Deleting an entity increments that slot’s generation. Lookup accepts a handle only when both fields match. Stale handles become detectable instead of aliasing new entities.

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct Entity {
	index: u32,
	generation: u32,
}

struct Slot {
	generation: u32,
	alive: bool,
}

fn is_alive(slots: &[Slot], entity: Entity) -> bool {
	slots.get(entity.index as usize).is_some_and(|slot| {
		slot.alive && slot.generation == entity.generation
	})
}

The index chooses storage; the generation validates identity. Free indices can be held in a stack or queue. A stack improves temporal reuse but may concentrate hot slots. A queue delays reuse and can make debugging histories clearer.

Generation width is an engineering decision. A wrapping 32-bit generation is not mathematically unique forever. Reusing one slot billions of times could validate ancient handles. Production designs document wrap behavior and expected churn. Wider identifiers trade memory and bandwidth for a larger safety horizon.

IDs may also encode a shard, world, or process namespace. Encoding helps routing but consumes bits and couples identity to topology. Random UUIDs travel well across services but cost more in hot arrays. A common design maps external durable IDs to compact internal IDs.

Never serialize an ephemeral slot ID as durable business identity accidentally. After loading, slot allocation order may differ. Persist stable keys and rebuild runtime handles explicitly.

Deleting an entity must invalidate all component membership consistently. Partial deletion creates ghosts visible to some queries. Deferred command application often centralizes this invariant. Debug builds should validate slot and storage agreement.

3. Sparse-set ECS from first principles#

A sparse set stores a dense entity array and dense component array. A sparse index maps an entity index to a dense position. Dense arrays permit compact iteration over one component type. Membership checks become expected constant-time indexed operations.

entity index:     0   1   2   3   4   5
sparse entry:     -   2   -   0   1   -

dense slot:       0       1       2
dense entity:     3       4       1
dense Position:  P3      P4      P1

To remove entity 4, swap the final dense row into its place. Update the moved entity’s sparse entry afterward. Dense order is unstable unless the implementation preserves or sorts it. References and row numbers may be invalidated by removal.

For a multi-component query, choose one dense set as join driver. Usually the smallest required set minimizes candidate entities. For every candidate, probe the other sparse sets. The result avoids scanning entities that lack the rare component.

query: Position & Velocity & !Sleeping
sizes: Position=1,000,000; Velocity=400,000; Sleeping=350,000
driver: Velocity
work: 400,000 candidates, two membership probes each

Optional components do not normally make good drivers. They do not restrict membership and may be absent. Excluded components can be tested as negative membership probes. Multiple sparse probes add random reads even when dense data is compact.

Sparse capacity commonly tracks the largest allocated entity index. Many component types can therefore multiply sparse-index memory. Paged sparse arrays avoid allocating untouched index ranges. Pages add another lookup and modest metadata.

Sparse sets handle frequent independent component insertion well. Adding one component changes only that component’s storage. Removing it likewise avoids moving unrelated components. This is attractive when entity shapes churn heavily.

Iteration across many common components is less naturally aligned. Each candidate can lead to scattered dense positions in other stores. Cache misses and branch behavior depend on membership distribution. Sorting stores into a shared entity order can help temporarily. Maintaining that order makes mutation more expensive.

Fragmentation appears across stores rather than inside one dense array. Components for one query may occupy unrelated pages. The ECS can still be fast when each system touches few columns. It can disappoint when wide joins dominate every frame.

4. Archetype and table ECS from first principles#

An archetype represents one exact component signature. Every entity in an archetype has the same component types. Each component type is stored as a column in that archetype’s table. Rows align across columns, making required-component iteration direct.

archetype signature: {Position, Velocity, Health}

row       entity       Position       Velocity       Health
0         E19          P19            V19            H19
1         E42          P42            V42            H42
2         E77          P77            V77            H77

A query finds archetypes whose signatures satisfy its constraints. It then streams matching columns without per-entity membership probes. Wide, stable queries can achieve excellent locality. Columnar storage also avoids fetching unrequested components.

Adding or removing a component changes an entity’s signature. The entity must move to another archetype table. Shared components are copied or moved between rows. The old row is removed, often by swap-remove. The new component is initialized in the destination. Entity location metadata must then be updated.

This operation is called a structural change. It can invalidate table-row references and disturb iteration order. Repeated toggling of tags may cause expensive table traffic. Batching identical transitions can amortize destination growth and bookkeeping.

Archetype counts can grow combinatorially in theory. With n independently combined component types, there are 2^n signatures. Real workloads usually realize far fewer combinations. Uncontrolled feature flags can nevertheless produce many tiny archetypes.

An empty archetype has no live rows but may retain metadata or capacity. Caching every observed signature can accumulate empty archetypes after churn. Reclaiming them complicates cached query and transition references. Engines choose different retention policies; inspect and measure them.

Fragmentation occurs when matching rows split among many small tables. Each table introduces metadata, allocations, and loop setup. Tiny tables reduce useful work per dispatch. Large tables provide better amortization and prefetch opportunities.

Archetype memory overhead includes signatures, type descriptors, columns, capacities, entity-location records, transition edges, and query match caches. The overhead can dominate worlds containing many tiny entity populations. Memory reports should separate component bytes from framework metadata.

Query caching maps a query shape to matching archetypes. When a new archetype appears, cached queries may need updating. Caching avoids repeating signature tests on every execution. It also creates lifecycle complexity and persistent metadata.

5. Comparing storage models by workload#

Neither sparse sets nor archetypes win universally. Start with mutation and query frequencies, not fashion. The following table summarizes tendencies, not guarantees.

A particle simulation with fixed Position, Velocity, and Lifetime favors tables. Its dominant work streams the same narrow columns repeatedly. A user-interface model with frequently attached transient behaviors may favor sparse sets. Its structural shape changes more than it performs wide numeric loops.

A compiler may use neither complete model. It could store expressions in typed Vec arenas, use side tables for inferred types, and maintain explicit worklists for changed functions. That simpler representation expresses the pipeline more directly.

Measure entity count distributions, not only totals. One million rows in one table differs from one million one-row tables. Measure component width and alignment. Copying a 512-byte component during table moves changes the decision.

Trace actual query combinations. If most queries touch one component, sparse probing is minimal. If hot queries require six components, aligned archetype columns may help. If membership is almost universal, plain parallel arrays can beat both.

Consider destruction bursts and snapshot frequency. Consider iteration-order requirements and serialization layout. Consider whether external IDs force a lookup anyway. Storage choice belongs in an architecture decision, with revisitable evidence.

6. A small educational Rust ECS#

The following ECS illustrates identities, stores, and joins. It resembles the typed stores developed in Part III. It deliberately omits ergonomic and production concerns. Do not treat it as a production ECS.

use std::any::{Any, TypeId};
use std::collections::HashMap;

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct Entity {
	index: u32,
	generation: u32,
}

struct Entities {
	generations: Vec<u32>,
	alive: Vec<bool>,
	free: Vec<u32>,
}

impl Entities {
	fn spawn(&mut self) -> Entity {
		if let Some(index) = self.free.pop() {
			self.alive[index as usize] = true;
			return Entity { index, generation: self.generations[index as usize] };
		}
		let index = self.generations.len() as u32;
		self.generations.push(0);
		self.alive.push(true);
		Entity { index, generation: 0 }
	}

	fn contains(&self, entity: Entity) -> bool {
		self.alive.get(entity.index as usize).copied().unwrap_or(false)
			&& self.generations[entity.index as usize] == entity.generation
	}

	fn despawn(&mut self, entity: Entity) -> bool {
		if !self.contains(entity) { return false; }
		let index = entity.index as usize;
		self.alive[index] = false;
		self.generations[index] = self.generations[index].wrapping_add(1);
		self.free.push(entity.index);
		true
	}
}

Each component store uses sparse indices and dense values. Comparing the generation in each dense entity prevents stale lookup confusion. A world-level despawn must remove the entity from every store before recycling its slot. The insertion code below also evicts an old-generation row at the same sparse index; without that repair, a leaked row could later be reconnected by swap_remove fixup.

struct Store<T> {
	sparse: Vec<Option<usize>>,
	entities: Vec<Entity>,
	values: Vec<T>,
}

impl<T> Store<T> {
	fn new() -> Self {
		Self { sparse: Vec::new(), entities: Vec::new(), values: Vec::new() }
	}

	fn insert(&mut self, entity: Entity, value: T) -> Option<T> {
		let index = entity.index as usize;
		if self.sparse.len() <= index { self.sparse.resize(index + 1, None); }
		if let Some(dense) = self.dense_index(entity) {
			return Some(std::mem::replace(&mut self.values[dense], value));
		}
		if let Some(stale_dense) = self.sparse[index] {
			let stale_entity = self.entities[stale_dense];
			debug_assert_eq!(stale_entity.index, entity.index);
			let _ = self.remove(stale_entity);
		}
		let dense = self.values.len();
		self.sparse[index] = Some(dense);
		self.entities.push(entity);
		self.values.push(value);
		None
	}

	fn dense_index(&self, entity: Entity) -> Option<usize> {
		let dense = self.sparse.get(entity.index as usize).copied().flatten()?;
		(self.entities.get(dense) == Some(&entity)).then_some(dense)
	}

	fn get(&self, entity: Entity) -> Option<&T> {
		self.dense_index(entity).map(|dense| &self.values[dense])
	}

	fn get_mut(&mut self, entity: Entity) -> Option<&mut T> {
		let dense = self.dense_index(entity)?;
		Some(&mut self.values[dense])
	}

	fn remove(&mut self, entity: Entity) -> Option<T> {
		let dense = self.dense_index(entity)?;
		self.sparse[entity.index as usize] = None;
		self.entities.swap_remove(dense);
		let removed = self.values.swap_remove(dense);
		if dense < self.entities.len() {
			let moved = self.entities[dense];
			self.sparse[moved.index as usize] = Some(dense);
		}
		Some(removed)
	}
}

A minimal world can type-erase stores behind Any. Production libraries need stronger invariants, diagnostics, and optimized access.

struct World {
	entities: Entities,
	stores: HashMap<TypeId, Box<dyn Any>>,
}

impl World {
	fn store<T: 'static>(&self) -> Option<&Store<T>> {
		self.stores.get(&TypeId::of::<T>())?.downcast_ref()
	}

	fn store_mut<T: 'static>(&mut self) -> &mut Store<T> {
		self.stores.entry(TypeId::of::<T>())
			.or_insert_with(|| Box::new(Store::<T>::new()))
			.downcast_mut().expect("TypeId and store type disagree")
	}
}

Borrowing two stores mutably through this map requires careful API design. One educational escape is temporarily removing one boxed store. That approach is clumsy and not panic-safe without a guard. Production ECS implementations centralize unsafe code or runtime borrow checks.

The join itself can remain straightforward.

#[derive(Clone, Copy)] struct Position { x: f32, y: f32 }
#[derive(Clone, Copy)] struct Velocity { x: f32, y: f32 }

fn move_entities(dt: f32, positions: &mut Store<Position>, velocities: &Store<Velocity>) {
	for dense in 0..positions.values.len() {
		let entity = positions.entities[dense];
		if let Some(velocity) = velocities.get(entity) {
			let position = &mut positions.values[dense];
			position.x += velocity.x * dt;
			position.y += velocity.y * dt;
		}
	}
}

This chooses Position as the driver even if Velocity is smaller. A planner could choose the smaller store and probe the other. Returning mutable references safely then needs disjointness guarantees.

Missing production features include panic-safe structural mutation, component destructors during despawn, query caching, parallel iteration, change ticks, command buffers, stable serialization, and good error reporting. The example teaches representation, not library design completeness.

7. Query semantics and planning#

A query is a declarative description of acceptable rows. Required components must be present. Optional components may be present and return an option. Excluded components must be absent.

(&mut Position, &Velocity, Option<&Acceleration>) without Sleeping
required: Position, Velocity
optional: Acceleration
excluded: Sleeping
access: write Position; read Velocity and Acceleration

Filters can also express changed, added, tags, or relations. Each filter affects candidate selection and tracking cost. Queries should make hidden work visible in profiles.

A sparse-set planner chooses a required component as join driver. The smallest dense store is a useful baseline heuristic. However, exclusion selectivity and cache locality may change the winner. A stable store with aligned ordering can beat a slightly smaller random join.

An archetype planner first tests table signatures. A signature may be a bit set indexed by registered component type. Required bits must all be set. Excluded bits must all be clear. Optional bits do not affect acceptance.

match(signature, required, excluded):
    (signature & required) == required
    and (signature & excluded) == 0

Large registries require multiword masks or sorted type lists. Masks make matching cheap but consume fixed metadata. Sorted lists save space for sparse signatures but require merge-like tests. Hybrid representations are possible and should be benchmarked.

Query caching stores the list of matching archetypes. The cache key includes component access and filter semantics. New archetypes must be tested against existing cached plans. Alternatively, caches can lazily refresh using an archetype generation.

Caching results by entity is usually harder. Structural changes invalidate membership continually. Caching table matches is cheaper because table signatures are stable.

Optional access can widen memory traffic unexpectedly. In archetypes, tables with and without the optional column require separate paths. In sparse sets, every candidate may perform another membership probe. Split hot paths when optional data is rare and expensive.

Excluded filters can avoid work but still cost tests. Represent common tags as signature bits when using archetypes. With sparse sets, a negative probe per candidate may be acceptable. Measure branch predictability when exclusion density is near fifty percent.

8. Change tracking, ticks, and temporal queries#

Systems often need rows added or changed since their last run. Scanning and comparing every value defeats the purpose. ECS implementations therefore attach change metadata to rows or columns.

An added tick records when a component became present. A changed tick records its latest mutable update. Each system remembers the tick of its previous execution. The query compares component ticks against that interval.

system last run          component changed          current world tick
      100 -------------------- 117 ------------------------ 130
                         included by Changed<T>

Merely obtaining mutable access may mark a component changed. This is conservative and can create false positives. Explicit mutation guards can mark only when dereferenced mutably. Exact value comparisons are more expensive and require equality semantics.

Tick counters eventually wrap. Naive changed_tick > last_tick fails across wraparound. Wrapping subtraction can compare ages within a bounded window. The implementation must define a maximum reliable age.

fn is_newer(change: u32, last: u32, now: u32) -> bool {
	let since_change = now.wrapping_sub(change);
	let since_last = now.wrapping_sub(last);
	since_change < since_last
}

This sketch assumes observations occur within half or another documented range. Long-sleeping systems can exceed the reliable window. An implementation may periodically clamp old ticks to preserve its documented comparison window. Read the chosen library’s exact semantics rather than copying this function.

Tracking per row improves selectivity but consumes metadata bandwidth. Tracking per column or table is cheaper but less precise. Hierarchical tracking can reject unchanged chunks before checking rows.

Change tracking is not an event log. It says that state changed, not how many times or why. Use events when every transition matters. Use snapshots when consumers need coherent historical state.

9. Deferred mutation, commands, stages, events, and resources#

Structural mutation during iteration can move or remove current rows. That invalidates iterators and complicates aliases. A command buffer records mutations for later application.

enum Command {
	Despawn(Entity),
	AddVelocity(Entity, Velocity),
	RemoveVelocity(Entity),
}

fn apply(commands: Vec<Command>, world: &mut World) {
	for command in commands {
		match command {
			Command::Despawn(entity) => { world.entities.despawn(entity); }
			Command::AddVelocity(entity, value) => {
				world.store_mut::<Velocity>().insert(entity, value);
			}
			Command::RemoveVelocity(entity) => {
				world.store_mut::<Velocity>().remove(entity);
			}
		}
	}
}

The sketch omits removal from every store during despawn. A real world needs a registry capable of complete cleanup. Commands should validate stale entities and report rejected operations.

Deferred commands create a visibility boundary. One system’s spawn may not appear until buffers flush. That delay must be documented in schedule semantics. Explicit flush points trade throughput for immediate visibility.

A stage groups systems around such boundaries. For example, input may precede simulation, simulation may precede command application, and extraction may precede rendering. Stages communicate temporal contracts, not merely code organization.

Events are append-only messages for a bounded period. They decouple producers from consumers and preserve repeated transitions. Readers need cursors so each event is observed at most as intended. Retention must handle readers that skip frames or fail.

Events are poor substitutes for durable queues. Process crashes usually erase in-memory event buffers. Business workflows may need transactional messaging or a database outbox.

A resource or singleton is one value shared by systems. Examples include configuration, clocks, and a network inbox. Resources avoid fake singleton entities and expose scheduler access. Too many mutable resources serialize an otherwise parallel schedule.

Global mutable resources can become architectural dumping grounds. Prefer narrow resources with clear ownership and update cadence. Snapshot frequently read configuration instead of locking it per row.

10. Relations, hierarchies, and irregular access#

A relation connects entities, such as parent, owner, or target. A hierarchy is usually a parent-child relation forming a forest. These structures are graphs, not simple independent columns.

The obvious representation stores Option<Entity> as Parent. Walking ancestors then follows entity handles through location maps. Each step may touch a different table and cache line. Parent pointers can therefore reintroduce irregular pointer-chasing access.

Children lists improve downward traversal but require synchronization. Changing a parent must remove one child edge and insert another. Cycles must be rejected if the relation promises a forest. Deleting a parent needs an explicit orphan or cascade policy.

transform table          parent lookup          transform table
[child row] -- Entity --> [location map] -----> [parent row]
     sequential             irregular              irregular

For frequent transform propagation, flatten hierarchy order. A depth-first ordered array places descendants near ancestors. Store subtree ranges or levels for batch processing. Reparenting then changes ordering and can become expensive.

Another design computes world transforms into a separate dense output. The hierarchy remains irregular during one propagation pass. Rendering then reads only flat world-transform arrays. This separates graph cost from the hotter render loop.

Relations with many edges need adjacency storage outside one component. A social graph or dependency graph is not naturally one-component-per-entity. Compressed sparse row layouts suit mostly static graphs. Chunked adjacency lists suit updates but fragment traversal.

Do not force every domain relation through an ECS relation API. Use a dedicated graph when graph algorithms dominate. Keep entity handles at subsystem boundaries if correlation is needed.

11. Runtime access metadata and Rust borrowing#

Rust statically prevents overlapping mutable references in ordinary code. Dynamic ECS queries are selected at runtime and cross type-erased storage. Libraries therefore combine static query types with runtime access metadata.

For each system, record component and resource reads and writes. Two systems conflict when one writes something the other reads or writes. Read-read overlap is safe under ordinary immutable access.

A: read Position, write Velocity
B: read Position, write Health
C: read Velocity, write Position

A with B: no conflict
A with C: conflict on Position and Velocity
B with C: conflict on Position

Filters can sometimes prove disjointness. With<Player> and Without<Player> cannot select the same entity. Exploiting such facts requires a sound disjointness model. Conservative conflict detection sacrifices parallelism but protects correctness.

Runtime borrow flags may guard direct world queries. Attempting two conflicting borrows then returns an error or panics. Scheduled systems can be prevalidated before execution. Unsafe internals must uphold aliasing even during panics and commands.

Component interior mutability changes the analysis. A Mutex<T> permits shared outer access but serializes internally. Cell and atomics have their own thread-safety contracts. Hiding mutation can prevent the scheduler from seeing real contention.

Audit escape hatches carefully. Raw world access or exclusive callbacks bypass normal conflict inference. They may be necessary for integration but should remain narrow.

12. Dependency graphs and parallel schedules#

A scheduler turns ordering constraints into a directed acyclic graph. Nodes are systems; edges mean one must complete before another. Edges arise from explicit ordering and unresolved access conflicts.

receive ──> normalize ──> simulate ──> snapshot
                    └──> metrics  ───────┘

Ready nodes with no unfinished predecessors can run concurrently. A parallel batch is a set of ready, nonconflicting systems. Completion releases successors until the graph is exhausted.

An exclusive system borrows the entire world or performs opaque work. It forms a barrier against ordinary systems. Use it for operations that genuinely require global control. Routine convenience is not a good reason to destroy parallelism.

Deterministic order means repeated inputs produce specified ordering effects. Parallel execution can change floating-point reduction order. Command buffers from simultaneous systems may merge nondeterministically. Hash iteration and work stealing can also vary order.

Determinism requires explicit policies. Sort commands by stable keys when order matters. Use fixed reduction trees for reproducible sums. Separate deterministic simulation from nondeterministic presentation work. Test replay hashes across thread counts and target machines.

Determinism is not automatically correctness. A consistently wrong order remains wrong. Conversely, many server tasks need invariants but not byte-identical replay.

Work granularity determines whether scheduling pays off. A ten-microsecond system can cost more to dispatch than execute. Fuse tiny transforms or process larger chunks. Split long uniform loops into cache-sized parallel ranges.

A thread pool reuses worker threads instead of spawning per task. Work stealing lets an idle worker take tasks from another worker’s deque. It balances irregular workloads but makes execution order less predictable. Stealing also moves task data and may reduce cache affinity.

False sharing occurs when threads update independent values on one cache line. The coherence protocol still transfers that line between cores. Per-thread counters should be padded or reduced after local accumulation. Chunk boundaries should avoid adjacent hot writes when practical.

13. Concurrency, parallelism, async I/O, and SIMD#

These terms solve different problems and should not be conflated. Concurrency means multiple tasks make progress during overlapping periods. They may time-slice on one core. Parallelism means work executes simultaneously on multiple cores or devices.

Async I/O suspends tasks while external operations wait. It is valuable for sockets, timers, and storage latency. It does not make CPU-heavy loops faster by itself. Blocking CPU work inside an async executor can starve unrelated tasks.

SIMD executes one instruction across multiple data lanes. It exploits regular loops within one core. SoA layouts often help the compiler vectorize numeric columns. Branches, pointer chasing, and alias uncertainty can inhibit vectorization.

async I/O: many waiting conversations, few active threads
threads:   several CPU tasks on several cores
SIMD:      several values in one core instruction
pipeline:  combinations are possible, but costs remain distinct

A server may use async I/O for connections, a bounded CPU pool for parsing or compression, and SIMD inside batch transforms. An ECS scheduler is not necessarily an async runtime. Bridging them needs cancellation, backpressure, and ownership rules.

Never hold ECS borrows across an .await without explicit support. The task can suspend indefinitely while retaining access. Copy or move request data into owned jobs instead. Apply completed results at a controlled ingestion boundary.

14. Production architecture beyond games#

DOD applies wherever batches of similar data undergo repeated transforms. Compilers, servers, simulations, renderers, and analytics all qualify sometimes. Their durability, latency, and correctness constraints differ substantially.

A robust high-level pipeline is deliberately boring.

ingestion -> validation -> normalized tables -> batch transforms -> output
                    |              |                   |
                 rejects       snapshots           metrics

Ingestion owns unstable external representations. Validation rejects malformed or unauthorized data early. Normalization maps strings and identifiers into compact internal forms. Batch transforms operate on owned, predictable tables. Output translates internal results into external protocols.

Subsystem boundaries should transfer values or immutable snapshots. Sharing a mutable world across every subsystem spreads coupling. An ECS can be an implementation detail inside one subsystem. It need not become the application’s universal service locator.

Ownership should answer who creates, mutates, publishes, and destroys data. Single-writer designs simplify consistency and snapshots. Readers can consume immutable published versions. Queues provide backpressure instead of surprise shared mutation.

Double buffering maintains a write buffer and a read buffer. At a boundary, roles swap after writes complete. Readers see a coherent previous state while producers build the next. Memory cost nearly doubles for buffered columns.

Copy-on-write snapshots can reduce copying when changes are sparse. They add reference counts, indirection, and worst-case copy spikes. Chunked snapshots balance granularity against metadata.

Serialization should use an explicit schema independent of memory layout. Rust struct layout and ECS table order are not stable wire formats. Persist type identifiers, field versions, and durable entity keys deliberately.

Schema migration transforms old serialized versions into current normalized data. Test migrations with fixtures from every supported version. Keep migrations deterministic and observable. Do not make loading depend on historical runtime registration order.

FFI boundaries need ownership, alignment, lifetime, and panic rules. Expose flat buffers and lengths rather than Rust-specific collections. Pin memory only when the foreign API requires stable addresses.

GPU boundaries reward large contiguous transfers and few submissions. Extract render or compute data into device-friendly staging buffers. Do not mirror an entire dynamic ECS world blindly. Track changed ranges when transfer bandwidth matters.

Observability belongs in the data flow. Record row counts, table counts, query durations, command volume, queue depth, snapshot age, allocation bytes, and rejected input counts. Trace identifiers should cross subsystem boundaries without entering every hot row.

15. Case study: telemetry normalization server#

Consider a service receiving telemetry from industrial sensors. Packets arrive asynchronously, include external device IDs, and vary by schema. The service validates, normalizes, enriches, aggregates, and exports records.

An async front end terminates connections and enforces byte limits. Validated packets enter a bounded queue. Backpressure rejects or delays senders before memory grows unbounded.

A normalization worker maps durable device IDs to compact session indices. Columns store timestamp, measurement kind, value, quality, and source. Strings are interned outside the hot numeric path. Invalid rows go to a bounded diagnostic stream.

Batch systems calibrate values, flag outliers, and compute windows. Required columns are explicit for each transform. Optional calibration metadata is resolved once per device batch. Output workers serialize completed immutable batches.

This design may resemble ECS queries without requiring entities that live forever. Arrow-like record batches or plain SoA vectors may fit better. Rows naturally flow forward and are discarded together.

A failed first version put every packet into a global ECS world. Each processing state was represented by adding and removing tag components. Archetype moves dominated CPU time under burst load. Millions of short-lived signatures accumulated metadata in diagnostics builds.

The repair used explicit stage queues and immutable batches. Only long-lived device state remained in indexed tables. Latency percentiles improved because queue limits exposed overload. The lesson was not that ECS is slow. The lesson was that a flow pipeline was the correct data model.

Failure modes still include skewed devices monopolizing batches, clock regressions corrupting windows, schema mismatches, and exporter stalls. Metrics partition hot-device skew and queue residence time. Replay fixtures exercise schema upgrades and out-of-order timestamps.

16. Case study: compiler analysis database#

A compiler receives source files and produces diagnostics and artifacts. Its identity domains include files, syntax nodes, symbols, and functions. These identities have different lifetimes and access patterns.

Syntax nodes fit compact typed arenas with child ranges. Symbols fit an intern table and scope indices. Function analyses fit side tables keyed by stable function IDs. Worklists contain functions invalidated by edits.

An ECS could model every syntax property as a component. That flexibility is tempting but may obscure phase invariants. Many compiler passes expect all nodes to possess a known typed shape. Typed arenas encode those expectations more directly.

Data-oriented techniques still matter. Separate rarely used source spans from hot opcode data. Batch type constraints by kind. Store control-flow successors contiguously. Use bit sets for liveness and reachability.

Incremental compilation needs change provenance, not only changed ticks. Dependencies identify which outputs an edit invalidates. A dedicated dependency graph is clearer than generic parent relations.

A failed design cloned rich AST objects into every pass. Pointer-heavy trees caused allocation pressure and poor locality. Replacing them with arenas and side tables reduced memory traffic. No ECS framework was necessary to obtain the DOD benefit.

Snapshot boundaries separate parsing from parallel semantic analysis. Diagnostics carry stable source IDs and ranges to output. Serialization caches use versioned compiler and schema fingerprints. Stale cache entries are rejected rather than partially interpreted.

17. Case study: deterministic traffic simulation#

A traffic simulation contains vehicles, lanes, signals, and incidents. Vehicles share position, speed, route, and behavior state. Most per-step operations are numerical and batch-friendly.

Stable vehicle columns support integration and collision candidate generation. Lane membership is partitioned spatially. Signals and incidents are smaller indexed tables. Route graphs live in dedicated compressed adjacency storage.

The scheduler divides each tick into explicit stages: input commands, route updates, movement proposals, conflict resolution, commit, metrics, and snapshot publication. Proposal and commit buffers prevent order-dependent in-place collisions.

Parallel movement processes disjoint spatial partitions. Boundary vehicles enter exchange buffers. Partitions merge exchanges in stable lane and vehicle order. This permits reproducible runs across thread counts.

Using parent pointers for route traversal performed poorly. Every vehicle chased nodes through a large graph independently. Grouping vehicles by next route segment improved locality. Caching short route windows reduced repeated graph access.

Change ticks were insufficient for audit logs. Regulators needed every signal transition and control command. The system emitted append-only versioned events alongside state snapshots.

Failure modes include dense intersections causing load imbalance, floating-point divergence, generation exhaustion in synthetic stress tests, and snapshot writers lagging behind simulation. The architecture bounds snapshot queues and drops optional visual frames, but never drops authoritative audit events.

18. Rendering and columnar analytics#

Rendering often uses ECS for scene extraction, not GPU execution itself. The simulation world contains rich dynamic state. An extraction stage builds compact render instances and material batches.

Visible instances are grouped by pipeline, mesh, and material. Transforms and bounds become contiguous upload buffers. Indirect draw arguments summarize groups. GPU synchronization is explicit at the extraction boundary.

Uploading per-entity objects individually wastes calls and bandwidth. Mirroring unused components wastes device memory. The renderer should consume a purpose-built frame snapshot.

Columnar analytics already embodies many DOD principles. Columns store one logical type, scans touch selected fields, and predicate masks feed vectorized operators. Record batches naturally define parallel work units.

An ECS entity is rarely needed for immutable analytical rows. Row numbers and key columns provide identity where required. Joins, group-by, null handling, and encoded columns need specialized algorithms. A generic ECS query language may be less expressive and slower.

Both domains benefit from separating logical schema from physical layout. Dictionary encoding can shrink repeated strings. Structure-of-arrays improves scans but may hurt whole-row serialization. Choose layouts at subsystem boundaries and transform deliberately.

19. When ECS is the wrong choice#

ECS is wrong when it makes the dominant operation less direct. A fixed homogeneous simulation may need only several aligned vectors. A graph workload may need adjacency arrays and frontier queues. A transactional service may need database records and explicit aggregates.

Use plain Vec<T> when every row has the same shape. Use SoA vectors when systems touch a few fields at a time. Use typed arenas when nodes need compact stable handles. Use hash or B-tree indexes when key lookup dominates. Use bit sets when membership and set algebra dominate.

ECS may be excessive when entity count is tiny. Framework metadata and dynamic dispatch can exceed useful work. It may be harmful when strict domain invariants span many components. Illegal partial states become easy to represent.

Frequent wide structural changes are another warning. So are requirements for stable memory addresses or stable iteration order. Distributed ownership does not map automatically to one in-memory world. Durability and transactions require more than deferred command buffers.

Ask these questions before adoption:

1. What are the three hottest transforms?
2. Which columns does each transform read and write?
3. How often does row shape change?
4. What identity must survive restart or migration?
5. Which ordering and consistency guarantees are required?
6. Can a simpler table or pipeline state them directly?

A small prototype with counters often answers better than architecture debate. Implement the baseline with vectors first when feasible. Keep it as a benchmark and correctness oracle.

20. Rust ecosystem evaluation guide#

Rust libraries evolve, so this section is intentionally version-sensitive. Names such as bevy_ecs, hecs, shipyard, slotmap, and rayon identify options to investigate, not claims about current internals.

An ECS library may provide worlds, queries, or scheduling. A slot-map library may provide generational handles without ECS. A data-parallel library may parallelize ordinary slices and iterators. Combining focused tools can be better than adopting one large framework.

Never assume a crate guarantees DOD or speed. An API cannot choose your data model or workload boundaries. Performance depends on versions, features, targets, and usage.

Start with current official documentation and release notes. Record the exact crate version and enabled features. Inspect examples for query syntax, deferred mutation, and scheduling semantics. Then inspect source around storage, access metadata, and unsafe blocks.

Use cargo tree to understand dependency and feature expansion. Use cargo metadata for machine-readable package information. Check the published MSRV policy and verify it in your toolchain matrix. Absence of a stated MSRV is itself migration risk.

cargo tree -e features
cargo metadata --format-version 1 > metadata.json
cargo test --all-targets
cargo bench

Assess unsafe surface rather than merely counting unsafe tokens. Read safety comments and identify invariant boundaries. Check whether optional features introduce FFI or platform code. Run Miri or sanitizers on your own integration where applicable.

Assess maintenance using recent releases, issue handling, and contributor breadth. Do not equate release frequency with quality automatically. Read changelogs for breaking query or schedule behavior. Check license compatibility and security advisory processes.

Benchmark your workload, including structural churn and worst-case shapes. Measure warm and cold query costs. Measure memory after creating and deleting many archetypes or entities. Measure single-thread latency and parallel scaling separately.

Test schedule semantics explicitly. When do commands become visible? How are ambiguous conflicts ordered? Can exclusive systems appear accidentally? What determinism is promised, if any? How are panics, cancellation, and nested parallelism handled?

Estimate migration cost before framework-specific types spread. Wrap durable IDs and external schemas in application-owned types. Keep domain transforms testable over plain slices where practical. Prototype export and import before committing production data.

21. Benchmarking and performance traces#

A useful benchmark states a hypothesis and controls confounders. “ECS A is faster” is not a useful hypothesis. “Archetype iteration lowers time for this six-column stable query” is testable.

Record CPU model, core count, memory, operating system, Rust version, crate versions, feature flags, optimization settings, and dataset seed. Pinning cores may reduce noise but can hide deployment variability.

Benchmark these phases separately: world construction, steady queries, structural changes, command application, snapshots, serialization, and teardown. Report throughput and latency distributions, not only means.

TRACE tick=420
  ingest             0.31 ms   rows=12,400
  command_flush      0.48 ms   commands=8,920
  movement           1.72 ms   matched=510,002 tables=14
  hierarchy          2.91 ms   edges=188,100
  extraction         0.83 ms   visible=91,440
  snapshot_swap      0.04 ms
critical_path        6.29 ms

The trace suggests hierarchy, not movement, deserves attention first. Table count contextualizes movement setup cost. Command volume may explain structural overhead. One trace is evidence for investigation, not proof.

Use hardware counters carefully to study cache misses and branches. Counters vary across processors and may multiplex. Allocation profiles reveal table churn and snapshot copies. Flame graphs reveal time, but not queue waiting by themselves.

Create adversarial datasets. Generate many tiny archetypes, skewed sparse IDs, deletion bursts, deep hierarchies, and fifty-percent exclusion filters. Production incidents often live outside average distributions.

Validate outputs during performance tests. Optimized code that skips work can look impressively fast. Use stable hashes or sampled invariants outside timed regions.

22. Failure patterns and diagnostic responses#

Archetype explosion: metadata and tiny-table iteration grow unexpectedly. Count live and empty archetypes by signature width and row count. Replace combinatorial tags with values or separate indices where appropriate.

Structural thrashing: entities toggle components every stage. Trace transitions by source and destination signature. Replace temporary membership with a state value or buffered worklist.

Sparse memory blowup: one high entity index expands many stores. Report sparse capacity separately from dense length. Use paged sparse storage or compact world-local IDs.

Hidden serialization: one mutable resource conflicts with every system. Print the scheduler graph and access sets. Split the resource or publish immutable snapshots.

False parallelism: dozens of tiny systems saturate scheduler overhead. Measure task duration and queue operations. Fuse work or schedule chunk-level jobs.

False sharing: scaling worsens despite independent logical writes. Inspect cache-line placement of counters and chunk boundaries. Use thread-local accumulation and a later reduction.

Stale handles: external code retains IDs after despawn. Log index and generation on validation failures. Separate durable external identity from ephemeral entity handles.

Missed changes: a system sleeps beyond the tick comparison window. Monitor system run age and tick distance. Use explicit dirty queues or full resynchronization when necessary.

Event loss: a slow reader falls behind bounded retention. Track reader cursors and oldest available sequence. Choose backpressure, durable storage, or documented loss.

Snapshot lag: readers retain old versions and prevent reclamation. Measure snapshot age and outstanding owners. Bound readers, copy critical output, or disconnect laggards.

Nondeterministic replay: hashes diverge across thread counts. Record merge order, random seeds, and floating reductions. Introduce stable ordering only where the contract requires it.

23. Architecture decision record template#

Use this template before selecting ECS or replacing an existing model.

# ADR: Data model and execution architecture for <subsystem>

Status: proposed | accepted | superseded
Date: YYYY-MM-DD
Owners: <team or people>

## Context
- Domain and subsystem boundary:
- Expected row/entity counts and distributions:
- Hot transforms and their read/write columns:
- Structural mutation frequency and patterns:
- Identity lifetime and persistence requirements:
- Ordering, determinism, latency, and durability requirements:
- Target platforms, MSRV, and memory budget:

## Options considered
1. Plain Vec/SoA plus explicit indexes
2. Sparse-set ECS
3. Archetype/table ECS
4. Domain-specific graph, database, or batch representation

## Evidence
- Prototype commit and exact dependency versions:
- Benchmark datasets and commands:
- Throughput, percentile latency, and memory results:
- Worst-case and churn results:
- Unsafe/FFI review:
- Operational and observability review:

## Decision
- Selected option:
- Data ownership and mutation authority:
- Snapshot and command visibility boundaries:
- Scheduling and determinism policy:
- Serialization schema and migration policy:

## Consequences
- Benefits:
- Costs and known failure modes:
- Migration and rollback plan:
- Metrics and alert thresholds:

## Revisit triggers
- Entity count or shape distribution changes by <threshold>
- Structural changes exceed <threshold>
- Critical-path latency exceeds <threshold>
- Required platform, MSRV, or schema changes

An ADR records assumptions so later teams can challenge them. It should link reproducible evidence rather than rely on adjectives. Superseding an ADR is healthy when workloads change.

24. Exercises#

1. Implement a generational allocator with a free queue.
2. Write tests proving stale handles fail after slot reuse.
3. Add generation-wrap documentation and a stress configuration.
4. Implement sparse-set insertion, lookup, and swap removal.
5. Property-test sparse and dense index consistency after random operations.
6. Implement a two-component join using the smaller driver.
7. Measure that join at membership densities of 1%, 50%, and 99%.
8. Model required, optional, and excluded query terms.
9. Explain why optional terms cannot restrict archetype matching.
10. Build bit-mask signature matching for 128 component types.
11. Compare mask matching with sorted type-list matching.
12. Simulate table moves when adding and removing one component.
13. Count bytes copied for small and large shared components.
14. Generate all observed signatures for ten independent tags.
15. Plot archetype row-count distribution after random churn.
16. Add changed ticks and test comparison across counter wrap.
17. Design a recovery for systems sleeping beyond tick limits.
18. Implement a command buffer and document visibility points.
19. Show a command order that creates nondeterministic output.
20. Repair it using a stable merge key.
21. Derive read and write sets for five example systems.
22. Build their conflict and dependency graph by hand.
23. Partition the graph into legal parallel batches.
24. Identify one unnecessary exclusive system and redesign it.
25. Benchmark per-thread counters with and without cache-line separation.
26. Compare sequential, thread-parallel, and SIMD-friendly integration loops.
27. Explain why async I/O does not accelerate those arithmetic loops.
28. Flatten a tree into depth-first order and compute subtree ranges.
29. Compare parent-pointer traversal with the flattened representation.
30. Design orphan, cascade, and cycle policies for reparenting.
31. Create a two-buffer snapshot publisher with one writer.
32. Specify behavior when a snapshot reader never releases data.
33. Define a versioned schema for three component-like records.
34. Write a migration from version one to version two.
35. Design an FFI buffer contract including ownership and alignment.
36. Extract only visible render data into a staging buffer.
37. Redesign the telemetry case study using plain record batches.
38. Identify where durable events differ from changed components.
39. Draft an ADR comparing ECS with typed arenas for a compiler.
40. Benchmark a library candidate using your workload, not its demo.

25. Review questions#

1. Why is DOD broader than ECS?
2. How does set intersection derive a component query?
3. Why should entity identity be separated from component data?
4. What stale-reference error do generations prevent?
5. What assumptions make generation wrap safe enough?
6. How does sparse-set swap removal preserve dense storage?
7. Why does the smallest required store often make a good join driver?
8. When might a different join driver perform better?
9. What makes add/remove operations structural in an archetype ECS?
10. Why can empty archetypes consume meaningful memory?
11. How does table fragmentation affect iteration?
12. What lifecycle work does query caching introduce?
13. How do required, optional, and excluded terms differ?
14. Why are negative filters not free?
15. What does a changed tick fail to record?
16. Why is ordinary integer ordering wrong after tick wrap?
17. What visibility semantics do deferred commands create?
18. When should events be durable rather than frame-local?
19. How can mutable resources serialize a schedule?
20. Why can parent pointers damage locality?
21. When is a dedicated graph better than ECS relations?
22. How does runtime access metadata support Rust aliasing rules?
23. Which combinations of read and write sets conflict?
24. What makes a system exclusive?
25. Why can deterministic ordering reduce parallel freedom?
26. How does work granularity affect scheduler overhead?
27. What is work stealing, and what trade-off does it introduce?
28. How can independent writes still cause false sharing?
29. How do concurrency and parallelism differ?
30. Why is async I/O unsuitable as a CPU speedup by itself?
31. What data properties help SIMD?
32. Why should ECS borrows generally not cross .await?
33. What belongs at an ingestion boundary?
34. How do snapshots clarify ownership?
35. Why is memory layout not a serialization schema?
36. What must an FFI contract state?
37. Why should GPU extraction be purpose-built?
38. Which telemetry failure suggested replacing ECS tags with queues?
39. Why did typed arenas suit the compiler case study?
40. Which simulation policies supported deterministic replay?
41. When is plain Vec preferable to ECS?
42. What should a crate evaluation record about versions?
43. Why is counting unsafe blocks an incomplete audit?
44. Which schedule semantics require explicit tests?
45. What evidence belongs in an architecture decision record?

26. Closing synthesis#

ECS begins with a modest observation: identity correlates independent data tables. Queries select intersections, and systems transform the resulting rows. Generations make reused identities safer. Storage then determines the shape and cost of those operations.

Sparse sets favor independent dense columns and cheap local membership changes. Archetype tables favor aligned iteration across stable component combinations. Both pay metadata, mutation, and query-planning costs in different places. Neither rescues an unsuitable domain model.

Scheduling adds another data problem. Read and write sets describe conflicts. Dependency edges describe required order. Parallel batches exploit remaining independence. Granularity, determinism, false sharing, and memory bandwidth bound the result.

Production systems extend beyond one world and one frame. They ingest untrusted data, normalize it, batch transforms, publish snapshots, migrate schemas, cross FFI or GPU boundaries, and expose enough telemetry to explain failure.

The strongest architecture makes ownership and transitions explicit. Sometimes that architecture contains an ECS. Sometimes it contains vectors, arenas, graphs, queues, or database tables. Data-oriented design asks us to choose from evidence, then preserve a simpler baseline against which complexity must justify itself.

Part V: Production Data-Oriented Systems Under Real Constraints#

Data-oriented design begins with work, not with a fashionable container. Production adds deadlines, hostile inputs, uneven machines, migrations, and exhausted operators. The useful question is which bytes each operation needs, when, and under whose ownership. The answer may justify columns, compact handles, batches, or an ordinary vector of records. Every representation also creates conversion, debugging, and lifecycle costs that benchmarks can hide. This part develops decisions from simple measurement toward deployment and incident response. By the end, you will be able to carry a DOD choice through capacity planning, rollout, failure, and recovery.

1. From business operation to access model#

An access model is a written account of operations over real populations. Start with verbs such as admit session, shade tile, scan predicate, or flush segment. For each verb, list fields read, fields changed, traversal order, frequency, and deadline. Also record cardinality because ten objects and ten million objects invite different engineering. Separate hot paths from paths that merely appear central in the type hierarchy. A field touched during configuration should not occupy every cache line used during execution. Conversely, splitting a six-field record can be wasteful when every request consumes all six.

Ownership belongs in the model rather than in a later concurrency appendix. Name the thread, task, partition, or epoch allowed to mutate each region. Identify publication points where readers acquire an immutable view. Write lifetimes beside ownership: packet, frame, query, connection, process, or durable generation. This often reveals that temporary columns can disappear immediately after a reduction. It can also reveal that an apparently local pointer must survive compaction and therefore needs identity.

Translate service objectives into budgets attached to units of work. A 16 millisecond frame budget is not a license for every subsystem to spend 16 milliseconds. Reserve slices for input, simulation, preparation, rendering, and scheduling variance. Memory accounting should distinguish live payload, allocator reservation, mapped pages, caches, and overlap. During migration, old and new representations may coexist and double the apparent steady-state estimate. Network buffers can add another burst-sized term that disappears in an idle heap profile.

Use checked arithmetic when untrusted counts become byte capacities. The following complete function rejects overflow and an explicit production ceiling.

fn checked_table_bytes(rows: usize, columns: usize, width: usize, limit: usize) -> Option<usize> {
    let cells = rows.checked_mul(columns)?;
    let bytes = cells.checked_mul(width)?;
    (bytes <= limit).then_some(bytes)
}

fn main() {
    assert_eq!(checked_table_bytes(100, 4, 8, 4096), Some(3200));
    assert_eq!(checked_table_bytes(usize::MAX, 2, 8, usize::MAX), None);
}

Keep the initial model falsifiable. Counters should report operation counts, touched records, selected records, and emitted bytes. Profiles should confirm whether predicted hot fields and loops actually dominate. When observations disagree, amend the model before rearranging structures. An AoS Vec<Job> is often ideal for a small scheduler that inspects every job completely. It offers one allocation, direct iteration, obvious invariants, and excellent debugger presentation. Columns become attractive only when important operations skip enough fields to repay synchronization costs.

Failure modes include optimizing a rare maintenance pass and omitting queue residence from latency. Another is counting payload bytes while ignoring indexes, spare capacity, and allocator metadata. Beware averages that combine cheap rejected work with expensive successful work. Document assumptions next to the benchmark and assign an owner to each limit. The access model is a revisable production artifact, not an ideological declaration.

2. Distributions, experiments, and honest latency#

Average input size describes almost no production workload adequately. Measurements need tiny, median, large, skewed, sparse, bursty, malformed, and cold populations. Preserve correlations: large tenants may also use uncommon features and arrive at peak hours. Uniform random generators erase those relationships and frequently flatter branch predictors and hash tables. Replay samples help, but scrubbed traces can remove adversarial names or timing structure. Combine captured distributions with constructed boundary cases and explain both sources.

Benchmark the named binary, compiler flags, CPU model, memory topology, and worker count. Warm and cold experiments answer different questions and should never be silently combined. A warm index measures steady service; a cold index exposes page faults after restart. Pinning may reduce noise but can conceal the scheduler behavior of the deployed service. Report enough repetitions to show spread, not only the best iteration. Compare outputs and error counts before comparing speed.

Throughput and latency are related but not interchangeable. Increasing batch size can improve records per second while making the oldest record miss its deadline. Publish p50, p90, p99, and a meaningful extreme percentile with sample counts. Break end-to-end latency into queue time, service time, retries, and downstream acknowledgment. Measure age at rejection so overload does not make dashboards look artificially fast.

Coordinated omission occurs when the load generator waits for a slow response before sending more work. The resulting quiet period removes precisely the arrivals that a real clock would have produced. Use an open-loop scheduled arrival stream for deadline services, recording intended send times. Closed-loop tests remain useful for interactive clients, but answer a different capacity question. Always graph offered load beside completed load and rejected load.

Histograms need ranges appropriate to the service and explicit overflow buckets. Logarithmic buckets preserve broad tails with bounded memory. Per-thread histograms avoid a contended global counter and can merge after an interval. The merge must include idle workers, otherwise disappearing shards distort rates. Reset through epoch exchange rather than racing readers against bucket clearing.

Representative experiments include degradation mechanisms. Inject allocator pressure, one slow shard, storage stalls, packet loss, and restart page faults. Run long enough to observe compaction, rotation, thermal throttling, and periodic maintenance. Separate initialization from the timed interval unless startup is itself the objective. Collect hardware counters cautiously; multiplexed events and virtualized hosts can mislead.

A scalar baseline is indispensable because it exposes conversion overhead and validates results. For short arrays, timer noise and setup can dwarf an optimized kernel. Use std::hint::black_box only to prevent benchmark elimination, never to imitate realistic consumption. Inspect generated assembly only after wall-clock and correctness evidence identifies a suspicious loop.

Operationally, retain benchmark inputs and machine metadata with results. Set regression thresholds wider than ordinary variance and investigate trends rather than single red builds. Canary metrics must use the same units and inclusion rules as laboratory metrics. A faster implementation that drops costly requests is a correctness regression, not an optimization.

3. Cache lines, tiles, and traversal choices#

Caches reward reuse within a limited working set, but tile size is not universal. A matrix operation should describe which dimensions advance together and which values are reused. Row-major traversal suits contiguous rows; column traversal may fetch a line for one element. Blocking retains a panel while combining it with several neighboring panels. Its benefit depends on element width, associativity, concurrent data, and the actual kernel.

Choose an initial tile from bytes, not folklore. Count input panels, output accumulators, metadata, and competing thread state. Leave headroom because a nominal cache capacity is neither fully associative nor private in practice. Sweep several sizes on target classes and watch both time and cache-miss counters. A sharp optimum may be fragile across CPU generations; a broad plateau is safer.

The following stable example sums image tiles while clipping edge tiles correctly. It is a complete program and intentionally keeps the inner traversal contiguous.

fn tiled_sum(pixels: &[u16], width: usize, height: usize, tile: usize) -> u64 {
    assert_eq!(pixels.len(), width.checked_mul(height).unwrap());
    assert!(tile > 0);
    let mut total = 0u64;
    for y0 in (0..height).step_by(tile) {
        for x0 in (0..width).step_by(tile) {
            let y1 = height.min(y0.saturating_add(tile));
            let x1 = width.min(x0.saturating_add(tile));
            for y in y0..y1 {
                for &pixel in &pixels[y * width + x0..y * width + x1] {
                    total += u64::from(pixel);
                }
            }
        }
    }
    total
}

fn main() {
    let image: Vec<u16> = (0..35).collect();
    assert_eq!(tiled_sum(&image, 7, 5, 4), image.iter().map(|&x| u64::from(x)).sum());
}

Cache-aware code fixes a tile size selected for known machines. Cache-oblivious code recursively divides a domain until small regions emerge naturally. Recursive traversal can serve several cache levels without embedding capacities. It also adds call structure, irregular edge handling, and sometimes worse vectorization. Use it when subdivisions preserve useful locality and recursion overhead is amortized.

Morton order can improve two-dimensional neighborhood locality but complicates coordinates and debugging. Explicitly copying a strided patch into a compact scratch buffer often wins instead. The copy is predictable, enables a simple inner loop, and isolates awkward boundaries. It loses when each element receives too little subsequent work or scratch allocation escapes control. Pool scratch space per worker and cap its maximum retained size.

No tiling is the right choice for a one-pass stream larger than cache with no reuse. Tiling such a scan adds loop machinery while every line still arrives once. Likewise, tiny grids already fit and benefit from direct readable loops. Counterexamples should remain in the benchmark suite to discourage universal transformations.

Watch for conflict misses when power-of-two strides map active rows to the same sets. Padding can help, but changes persistence formats if applied carelessly to serialized structs. Hardware counters can distinguish misses from bandwidth saturation only imperfectly. Confirm with size sweeps: cache effects often show knees, while streaming time scales linearly.

4. Instruction delivery, branches, and dispatch#

Data locality cannot compensate for an instruction working set that no longer fits. Inlining every specialized path duplicates loops and expands instruction-cache pressure. Generic monomorphization can produce one copy per type even when machine behavior is identical. Large match trees may be cheap for predictable values yet costly for mixed traffic. Measure text size, front-end stalls, and end-to-end latency together.

Split cold diagnostics, formatting, and unusual protocol handling away from hot loops. This does not require unsafe tricks; ordinary helper boundaries often suffice. Apply #[inline] sparingly because the compiler already has context and heuristics. #[inline(never)] is useful in experiments, not a substitute for evidence. Review binary-size changes during performance work, especially on shared hosts.

Branches are inexpensive when outcomes are strongly predictable. A bounds check in a regular loop may be removed or consistently predicted. An unpredictable filter over mixed records can waste pipeline work, but branchless arithmetic also executes both sides. Branchless transformations lose when one side is expensive and rare. Sort or partition by mode when doing so creates long homogeneous runs and amortizes movement.

Dispatch granularity matters more than dispatch existence. Choose a codec once per block instead of once per byte. Choose an entity behavior once per archetype chunk instead of through a virtual call per component. This preserves extensibility while keeping the inner kernel coherent. If blocks are tiny and heterogeneous, straightforward enum dispatch may remain superior.

The complete function below separates classification from aggregation. It can help mixed branches, but its extra buffers are deliberately visible.

fn sum_by_sign(values: &[i32]) -> (i64, i64) {
    let mut nonnegative = Vec::with_capacity(values.len());
    let mut negative = Vec::new();
    for &value in values {
        if value >= 0 { nonnegative.push(value); } else { negative.push(value); }
    }
    let positive_sum = nonnegative.into_iter().map(i64::from).sum();
    let negative_sum = negative.into_iter().map(i64::from).sum();
    (positive_sum, negative_sum)
}

fn main() {
    assert_eq!(sum_by_sign(&[3, -2, 5, -7]), (8, -9));
}

For one aggregation, that partition is probably slower than a direct branch. For twenty expensive passes over each class, it may repay allocation and copying. That contrast is the reason to state reuse counts in the access model. Production skew can also turn a laboratory fifty-fifty branch into a predictable ninety-nine-one branch.

Feature detection should happen outside the kernel. Stable Rust can use architecture detection macros where supported, but portable scalar code remains required. Keep variant count modest to avoid combinatorial code growth across format, CPU, and policy dimensions. Test every dispatched variant against the same oracle on boundary inputs. Record selected variants in diagnostics so incidents do not depend on disassembly.

5. Prefetching, bandwidth, and byte economics#

Hardware prefetchers excel at contiguous and simple-stride streams. They struggle with dependent pointer chains because the next address awaits the current load. As of this writing, stable portable Rust exposes no universal software-prefetch intrinsic. More importantly, fetching early consumes bandwidth and cache capacity whether useful or not. Reordering or batching addresses is often a more portable intervention.

Prefetch distance depends on memory latency divided by useful work per iteration. One fixed distance fails as CPU frequency, contention, and kernel cost change. Distances too short arrive late; distances too long evict data before use. Never prefetch beyond validated mappings merely because speculative hardware often suppresses faults. Measure on all supported architectures and retain a no-prefetch path.

Bandwidth-bound kernels improve by moving fewer bytes rather than issuing more instructions. Columns help when a predicate reads two fields from a twenty-field record. Smaller integer widths help only if conversion and range enforcement remain cheap and correct. Bit packing reduces traffic but can increase instruction work and complicate random updates. Compression wins when decompression is cheaper than transporting expanded bytes through memory or I/O.

Estimate a byte budget before tuning. Multiply bytes read and written per item by desired item rate. Include write allocation, temporary output, index probes, and repeated passes. Compare the estimate with sustained measured bandwidth, not advertised peak channels. Multiple sockets and cores share controllers, so a single-thread benchmark is not the ceiling. Scale thread counts until throughput flattens and latency or energy rises.

Non-temporal stores are architecture-specific and inappropriate for ordinary stable portable code. They can help large write-only outputs that will not be read soon. They can hurt when consumers immediately reuse the output or writes are partial. An explicit staging copy may provide better sequential traffic than scattered final writes. Copies are not automatically waste: they can replace many cache-line round trips with two streams.

Pointer-heavy structures multiply transferred bytes through nodes, allocator metadata, and poor spatial density. Indexes of u32 into a compact vector can reduce footprint where capacity is explicitly bounded. Do not narrow identities silently; reject growth before conversion overflows. Batch linked-list work into arrays when traversal dominates, but retain lists for constant-time splicing if measured.

Bandwidth incidents often appear as CPU utilization below one hundred percent. Track memory-controller counters where available, plus bytes processed per operation. Correlate regressions with representation changes and co-running tenants. Cloud instance classes may expose different effective bandwidth despite matching virtual CPU counts. Capacity tests should therefore include the deployment shapes actually purchased.

The right endpoint may be an uncomplicated scalar stream. It minimizes instruction footprint, lets hardware prefetch work, and is easy to audit. Stop optimizing when the byte minimum is reached and operational objectives are met.

6. Allocation, fragmentation, addresses, and identity#

Allocation policy should follow lifetime groups and release behavior. Per-request arenas make bulk destruction cheap and prevent long-lived objects trapping short-lived holes. Pools stabilize cost but retain their high-water memory and may retain secrets. Track requested, reserved, resident, reusable, and externally fragmented bytes separately. Reserve vectors from validated estimates, then cap growth rather than trusting attacker-provided counts. Small ordinary allocations remain sensible when populations are tiny and maintenance dominates.

Stable identity does not require a stable address. An index plus generation permits dense storage to move while rejecting stale references. The generation changes whenever a slot is reused; wrap policy must match lifetime and threat assumptions. External APIs should not expose raw indices without validating both components. Pinned boxes are appropriate for address-sensitive foreign interfaces, though indirection hurts scans.

#[derive(Clone, Copy)]
struct Handle { slot: u32, generation: u32 }
struct Entry<T> { generation: u32, value: Option<T> }

fn lookup<T>(entries: &[Entry<T>], handle: Handle) -> Option<&T> {
    let entry = entries.get(handle.slot as usize)?;
    if entry.generation != handle.generation { return None; }
    entry.value.as_ref()
}

fn main() {
    let entries = [Entry { generation: 7, value: Some("live") }];
    assert_eq!(lookup(&entries, Handle { slot: 0, generation: 7 }), Some(&"live"));
    assert_eq!(lookup(&entries, Handle { slot: 0, generation: 6 }), None);
}

Compaction needs an epoch where no borrowed references survive. Dense active arrays can map back to stable slots, paying one indirection only at boundaries. Measure churn, free-list length, generation failures, and compaction pause duration. Failure tests should remove and reuse slots while delayed messages remain in flight. Never serialize allocator addresses; persistence requires explicit IDs and versioned relations.

7. NUMA placement and partition ownership#

On a multisocket machine, memory access cost depends on where pages and threads reside. First-touch placement commonly associates newly faulted pages with the initializing processor's node. A single startup thread can therefore place every shard remotely from its eventual workers. Initialize large partitions through their owners, then verify placement with operating-system tooling. Containers and virtual machines may obscure topology, so treat affinity as measured configuration.

Shard keys should preserve ownership for enough work to amortize routing. Tenant, connection, spatial region, and hash range provide different balance and locality properties. Hot tenants require splitting or admission limits; a perfect hash distribution may destroy neighborhood reuse. Migration needs a handoff epoch, forwarding rule, bounded mailbox, and duplicate suppression. Record remote access, steal frequency, shard load, and migration age.

Work stealing is valuable when imbalance exceeds remote-memory cost. Steal coarse batches rather than individual records and prefer nearby workers before remote nodes. Immutable replicated lookup tables can beat repeated remote reads if update rate is low. Replication is wrong for large mutable state because publication traffic and memory multiply. A mutex-protected map can still win at low concurrency and offers a clean baseline.

Placement, handoff, and diagnosis#

A NUMA node is a group of processors with nearby memory controllers. Local memory is usually faster to reach than memory attached to another node. The operating system still presents one address space, so remote access is correct but can consume interconnect bandwidth and lengthen tail latency. That makes NUMA a placement concern rather than a different Rust memory model.

Partition construction should happen after worker affinity is established. Each owner allocates and writes its own arrays so first touch occurs locally. For restored state, readers can divide the file by final owner and decode into owner-local destinations instead of decoding centrally and scattering later. If affinity cannot be guaranteed, compare interleaving pages across nodes with natural placement; interleaving can reduce the worst case while sacrificing the best case.

A handoff starts by closing admission to the old owner's normal mailbox. New messages receive a monotonically increasing route sequence and enter a small forwarding mailbox. The old worker finishes through a recorded sequence, freezes mutable state, and sends one generation-tagged transfer package. The destination validates counts and limits before publishing its route. Only then may the source reclaim storage and remove its forwarding entry.

Timeouts need explicit outcomes. A destination that cannot reserve memory must reject before the source relinquishes authority. A lost acknowledgment causes the coordinator to query both generations rather than starting a second blind copy. Duplicate packages are harmless when destination installation is keyed by partition ID and transfer generation. A process crash falls back to the durable owner map plus replay of operations after its checkpoint sequence.

NUMA regressions often masquerade as lock contention or random slow requests. Compare per-node resident bytes, local and remote bandwidth, worker migrations, and latency grouped by owner node. Run a controlled test with one worker per node, then with all workers on one node, while retaining the same input trace. A throughput plateau accompanied by rising remote reads points toward placement; a plateau with balanced traffic may instead be a shared memory-controller cap.

Rebalancing should use hysteresis because moving state has a real byte cost. Estimate benefit from the recent load integral, not one hot interval. Limit concurrent transfers by both bytes and destination reserve. Small partitions can move whole; large ones need chunk checkpoints and a bounded change log. An operator must be able to pause movement without invalidating either owner.

8. False sharing, atomics, and memory ordering#

False sharing occurs when independent writers invalidate the same coherence line. Adjacent per-worker counters are a classic source despite having no logical sharing. Local aggregation followed by periodic merging usually beats padding every tiny field. Padding wastes cache and depends on machine line size, so validate before retaining it. Measure throughput scaling and coherence events while varying worker count.

Atomics provide indivisible operations, not automatic compound invariants. Relaxed ordering suits independent statistics where only eventual numeric accuracy matters. Publication requires a release operation paired with an acquire observation of the same synchronization chain. Sequential consistency simplifies reasoning but cannot fix a logically incomplete protocol. Document the value protected, legal transitions, and proof beside every nontrivial ordering.

use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};

struct Published { ready: AtomicBool, value: AtomicUsize }

fn publish(state: &Published, value: usize) {
    state.value.store(value, Ordering::Relaxed);
    state.ready.store(true, Ordering::Release);
}

fn read(state: &Published) -> Option<usize> {
    state.ready.load(Ordering::Acquire).then(|| state.value.load(Ordering::Relaxed))
}

fn main() {
    let state = Published { ready: AtomicBool::new(false), value: AtomicUsize::new(0) };
    publish(&state, 42);
    assert_eq!(read(&state), Some(42));
}

This one-shot example is not reusable publication; resetting introduces another protocol. Locks are preferable when several fields change together or contention is modest. Measure lock hold time, wait time, wakeups, retries, and fairness rather than rejecting mutexes categorically. Never infer safety from an x86-only test; weaker architectures expose missing ordering.

Coherence traffic and complete invariants#

A cache line is the fixed-size unit exchanged by core caches, commonly but not universally 64 bytes. Coherence is the protocol that makes writes from one core eventually visible to others. Two counters in one line therefore compete at the hardware level even when their values are logically unrelated. The symptom is ownership of the line bouncing between cores on every update.

Start with local counters owned by workers and merge outside the request path. If readers need a frequent approximate total, they can load one atomic counter per worker. Aligning every counter should be a later, measured choice because alignment expands arrays and increases scan traffic. Group read-mostly fields away from write-hot fields before adding architecture-dependent padding.

An atomic ordering constrains observations around an atomic operation. Relaxed guarantees atomicity and a modification order for that location but does not publish neighboring ordinary data. Release prevents earlier memory operations from moving after publication, while a matching Acquire prevents later memory operations from moving before observation. The matching edge must carry the value that proves which immutable object is ready; unrelated acquire loads do not help.

Reusable slots need more than toggling the one-shot ready flag above. One simple safe design publishes immutable values through an RwLock and puts the generation beside the value under the same lock. Readers clone an Arc, release the lock quickly, and then traverse without blocking the next build. The lock makes the compound root-and-generation invariant easy to audit.

use std::sync::{Arc, RwLock};

#[derive(Debug, PartialEq)]
struct View { generation: u64, values: Vec<u32> }

fn publish(root: &RwLock<Arc<View>>, next: View) {
    let mut guard = root.write().expect("publication lock poisoned");
    assert!(next.generation > guard.generation);
    *guard = Arc::new(next);
}

fn snapshot(root: &RwLock<Arc<View>>) -> Arc<View> {
    Arc::clone(&root.read().expect("snapshot lock poisoned"))
}

fn main() {
    let root = RwLock::new(Arc::new(View {
        generation: 1,
        values: vec![3, 5],
    }));
    let old = snapshot(&root);
    publish(&root, View { generation: 2, values: vec![8] });
    assert_eq!(old.values, vec![3, 5]);
    assert_eq!(snapshot(&root).generation, 2);
}

Poison handling is a policy decision in real services. Aborting may be right when a panic could have violated state construction. Recovery is reasonable only when the published root is known to remain coherent and the failed build was private. Never call an expensive formatter or callback while holding the publication lock, because incidental re-entry can deadlock the service.

For a contended atomic compare-and-swap loop, report attempts per success and time spent retrying. For a mutex, report blocked duration and critical-section duration separately. Compare both against a sharded owner-thread design. Atomics can reduce uncontended overhead yet behave worse under a synchronized burst; locks can sleep efficiently but expose convoying after a long holder.

9. Work queues, local buffers, and reductions#

Queues separate ownership domains but conceal waiting if only service time is measured. Attach enqueue timestamps and deadlines, and discard expired work before expensive processing. One bounded queue is often best for a small service because its overload policy is visible. Multiple priority queues become justified only when classes have materially different value or deadlines. Unbounded channels convert overload into memory exhaustion and delayed useless work.

Per-thread buffers remove allocator and lock traffic from hot production loops. Their total capacity equals worker count times retained high-water size, which can surprise memory budgets. Trim exceptional buffers at safe epochs and expose aggregate reserved capacity. Merge outputs in batches large enough to amortize synchronization but small enough for latency.

Reductions should use worker-local partials whenever the operation allows it. Integer sums need overflow policy; floating sums need an accepted order and error tolerance. Deterministic merge order helps replay but may cost parallel flexibility. Histograms merge naturally, while percentile values themselves do not. Skewed partitions demand weighted scheduling or finer chunks without abandoning locality entirely.

Local production and an ordered merge#

A queue stores ownership in transit: after a successful send, the producer no longer controls the item, and after receive the consumer does. Write that rule into the API by moving owned values rather than passing mutable shared handles. For borrowed input, copy the compact fields required by the consumer or retain an explicit reference-counted immutable batch with a bounded lifetime.

Workers should reserve local output from a trustworthy recent size, not from an unchecked request count. At a phase barrier, each worker transfers its vector to a merger. Concatenation is sufficient when output order has no meaning. If stable order matters, each item carries a partition and source sequence, and the merger performs a k-way merge over already sorted runs. This costs less than sorting all individual output when local work is ordered.

The following program shows deterministic local reduction without shared updates. Scoped threads borrow disjoint input chunks, and the parent merges partials in creation order. Checked addition turns overflow into a visible failure rather than wrapping a production total.

use std::thread;

fn parallel_checked_sum(values: &[u64], workers: usize) -> Option<u64> {
    if values.is_empty() { return Some(0); }
    let workers = workers.max(1);
    let width = values.len() / workers + usize::from(values.len() % workers != 0);
    thread::scope(|scope| {
        let jobs: Vec<_> = values.chunks(width)
            .map(|chunk| scope.spawn(move || {
                chunk.iter().try_fold(0u64, |sum, &x| sum.checked_add(x))
            }))
            .collect();
        jobs.into_iter().try_fold(0u64, |total, job| {
            total.checked_add(job.join().ok()??)
        })
    })
}

fn main() {
    assert_eq!(parallel_checked_sum(&[2, 3, 5, 7], 3), Some(17));
    assert_eq!(parallel_checked_sum(&[u64::MAX, 1], 2), None);
}

For floating point, the same fixed partition and merge tree makes runs stable, but not mathematically exact or invariant across partition counts. Specify an absolute and relative tolerance, or use integer fixed-point where the domain provides a safe scale. Compensated local summation can reduce error, though its additional operations need measurement in a throughput-sensitive kernel.

Queue metrics need occupancy distributions, oldest age, enqueue failures, batch size, and time from production to merge. A low mean occupancy can hide a full queue every minute. A high occupancy is harmless for bulk throughput if age remains within its objective; the same depth is unacceptable for control messages. Include item bytes because ten giant batches differ from ten IDs.

Worker termination must not strand a partial vector invisibly. At a normal barrier, either every expected worker contributes one generation or the merge fails as incomplete. During cancellation, discard partials only if the product is recomputable and no acknowledgment was issued. Otherwise persist progress or transfer the partial to a recovery owner with its exact sequence range.

10. Snapshots and double or triple buffering#

A snapshot gives readers a coherent generation without stopping every read. Build new immutable state privately, validate it, then publish one versioned root. Retain old generations until readers release them, and bound that retention explicitly. A slow reader can otherwise turn lock avoidance into unbounded memory. Snapshot age and outstanding-reader counts belong on dashboards.

Double buffering suits one producer and one consumer when each completes before reuse. Triple buffering permits producer and consumer cadence to drift and can drop intermediate visual states. It consumes another full buffer and may increase input-to-display latency. Audio cannot casually drop arbitrary blocks; its fallback must preserve sample cadence. Database readers may require every committed generation rather than newest-only semantics.

Copying a compact published view can outperform sharing a pointer-rich mutable world. The copy defines ownership, improves traversal, and makes rollback retainable. It loses when the entire state changes and memory overlap exceeds the budget. Dirty ranges or chunk-level copy-on-write help only when changes are genuinely sparse. Validate equality against a locked baseline during rollout.

Publication cadence and reclamation#

Readers call a snapshot coherent when all fields describe the same generation. Reading several atomics independently does not provide this property: a reader can observe a new length with an old pointer or mixed configuration versions. Publish one immutable root that owns every dependent array and index. Arc plus RwLock, as shown above, provides safe reclamation without unsafe code; old arrays disappear after the last reader drops its cloned root.

Double buffering assigns one buffer to construction and one to consumption. The producer cannot overwrite the old buffer until its consumer is finished. This works naturally at strict frame barriers. Triple buffering adds a spare, allowing the producer to finish another state while a reader holds the prior one, but selection must define whether the next or newest complete state wins. Newest-only display is not equivalent to a transaction log that forbids gaps.

Use generation numbers rather than buffer indices in diagnostics. Buffer zero is reused and says nothing about freshness. Record build start, publication, first consumption, final release, and bytes retained for each generation. An alert on oldest release age catches forgotten references before memory is exhausted. A hard generation-retention cap may reject a new build, disconnect an unhealthy reader, or copy its small required subset according to policy.

Incremental snapshots divide data into immutable chunks and replace only dirty chunks in a new root. The builder initially clones cheap Arc references, then allocates replacements for changed chunks. A write set records each chunk once, preventing two private copies in the same generation. Validation checks cross-chunk indexes after all replacements and before root publication.

Failure before publication simply drops the private root and replacement chunks. Failure after root publication is a consumer-visible generation and must follow normal rollback rather than mutating it. If external side effects depend on the snapshot, store their generation and idempotency key so retries cannot apply an old packet to a newer world.

Measure copied bytes per publication, dirty-chunk ratio, build duration, reader hold time, and peak overlap. A sparse synthetic update can exaggerate copy-on-write benefits if production changes cluster across most chunks. Conversely, a full-copy microbenchmark ignores the common case where only one tenant changes. Preserve both distributions and identify the crossover point.

11. Bounded queues, overload, and hard deadlines#

Capacity should derive from arrival rate, allowed waiting, and bytes per item. A queue of ten thousand is meaningless without those units. On saturation choose rejection, coalescing, sampling, lower-fidelity work, or upstream flow control. Retries need budgets and jitter because immediate retry amplifies the same bottleneck. Report offered, admitted, completed, rejected, expired, and retried work together.

Real-time paths prefer preallocated buffers and bounded algorithms over better average throughput. An audio callback should not allocate, block, fault pages, log synchronously, or await another thread. Warm required memory before entering the callback and provide silence or held-sample fallback deliberately. Frame systems can drop obsolete preparation while preserving authoritative simulation state. Operating-system scheduling means ordinary Rust cannot promise hard real-time behavior alone.

Memory limits must include queued payloads, snapshots, scratch, in-flight output, and migration overlap. Admission should reserve worst credible expansion before accepting compressed or nested input. When reservation fails, reject early with a bounded response. Overload drills should verify recovery after load subsides, not merely survival at peak.

Saturation transfers and deadline accounting#

A bounded queue has a finite number of slots or byte permits. Once full, the producer must make a decision instead of borrowing memory from the future. Blocking provides backpressure but can deadlock if the blocked producer owns a resource needed by the consumer. Immediate rejection keeps latency bounded; timed waits can be suitable for batch work with a real remaining deadline.

Rust's synchronous channel returns ownership on a failed nonblocking send. That detail permits the caller to retry elsewhere, degrade, or account exact dropped bytes without cloning the payload. The example is complete and makes saturation visible while returning ownership; disconnection likewise returns the job, although this small API intentionally does not distinguish the two failures.

use std::sync::mpsc::{sync_channel, SyncSender, TrySendError};

#[derive(Debug, PartialEq)]
struct Job { id: u64, bytes: Vec<u8> }

fn admit(sender: &SyncSender<Job>, job: Job) -> Result<(), Job> {
    match sender.try_send(job) {
        Ok(()) => Ok(()),
        Err(TrySendError::Full(returned)) => Err(returned),
        Err(TrySendError::Disconnected(returned)) => Err(returned),
    }
}

fn main() {
    let (sender, receiver) = sync_channel(1);
    assert!(admit(&sender, Job { id: 1, bytes: vec![0; 8] }).is_ok());
    let rejected = admit(&sender, Job { id: 2, bytes: vec![1; 4] })
        .expect_err("second job must retain ownership");
    assert_eq!(rejected.id, 2);
    assert_eq!(receiver.recv().unwrap().id, 1);
}

Slot bounds alone are insufficient when item sizes vary widely. Acquire a byte permit before constructing or decoding the full job, then return it when work is consumed or rejected. Reserve expansion using a validated upper bound for compressed data. Separate a small control queue so cancellation and health commands are not trapped behind giant payloads, while also rate-limiting it.

Each job carries arrival time, absolute deadline, class, and attempt count. Consumers check expiry before costly work and again before an irreversible side effect. Report queue residence for successful, rejected, and expired jobs. Otherwise early rejection can improve observed completion percentiles while users receive fewer answers. Load generators schedule arrivals independently to avoid coordinated omission during stalls.

Audio deadlines require another level of preparation. Lock sample buffers into the intended lifecycle where the platform permits, touch every page, and avoid lazy format initialization in the callback. If the producer misses, choose a precomputed silence block, a bounded crossfade, or the last valid block based on audible semantics. Count underruns out of band without formatting strings.

Recovery after overload has a shape worth measuring. Queues should drain, old deadlines should expire cheaply, retry rates should fall, and memory permits should return to their baseline. A leak in one rejection branch appears as permanent reduced capacity. Test repeated bursts because a single burst may not reveal retained vectors, exponential retries, or thermal degradation.

12. Generational publication and deterministic boundaries#

Production pipelines need explicit transitions from mutable building to immutable reading. Tag each published artifact with input generation, schema, configuration hash, and creation time. Consumers reject incompatible generations rather than quietly combining states. This principle applies to compiler facts, render packets, routing tables, and persisted indexes.

Determinism is easiest at boundaries, not inside every worker instruction. Allow parallel local work, then sort or merge by stable partition and sequence keys. Record nondeterministic inputs such as clocks, random seeds, external replies, and scheduler choices. Checkpoint hashes localize divergence without storing every intermediate byte. Beware hash iteration order and floating reduction order in supposedly identical replays.

Lifecycle tests should hold old readers while publishing several generations. They should crash between build, validation, publication, and reclamation. Metrics need current generation, oldest retained generation, build duration, and reclaimed bytes. If a simple read lock meets objectives, its smaller state space may be the safer implementation.

Event capture and replay checkpoints#

A deterministic boundary converts concurrent completion order into a stable logical order. Assign input sequence numbers at admission, process partitions independently, and merge by (generation, partition, sequence). Do not use wall clock timestamps as the sole order because clocks can repeat or move backward. Timestamps remain useful data but require a deterministic tie-breaking key.

Replay logs should contain accepted operations, not every rejected network byte by default. Include the decision inputs needed to reproduce admission, such as configuration generation and quota state. External service responses must be captured or replaced by a recorded deterministic adapter. Randomness comes from named streams with stored seeds so adding an unrelated random call does not perturb every subsequent choice.

Periodic state hashes narrow an incident to one interval. Hash canonical field encodings in stable ID order and exclude addresses, map iteration order, and diagnostic timestamps. A mismatch triggers finer checkpoints on replay rather than permanent verbose logging in production. Store the hash algorithm version because changing canonicalization otherwise resembles state corruption.

Backpressure affects replay semantics. If the original system dropped work at a capacity boundary, an unconstrained replay that admits everything models a different history. Capture admission outcomes or reproduce byte and slot limits with the same event schedule. For deadline decisions, replay uses the recorded logical arrival and service clock, not the workstation's current time.

Generation wrap must be considered even when it seems remote. A 32-bit frame counter can wrap during long service, and ordinary numeric comparison then misorders states. Use a sufficiently wide counter, reject exhausted persistent epochs, or define modular comparison within a bounded live window. Never reset identity generations while delayed commands or snapshots may survive.

13. Capacity planning across machine classes#

Production fleets rarely share one cache, bandwidth limit, core count, or storage latency. Define supported machine classes and benchmark each representative shape. Normalize results by completed useful work, not CPU percentage alone. A bandwidth-bound service may show low instruction utilization while already saturating memory controllers.

Capacity models combine per-item bytes, instructions, allocations, and downstream operations. Validate the model with load sweeps until throughput plateaus and queue age rises. Leave headroom for compaction, failover, noisy neighbors, and telemetry itself. Failover tests must place two normal shards on one host because steady tests miss that overlap.

Autoscaling based solely on CPU reacts poorly to queue-bound or memory-bandwidth-bound services. Use admitted rate, oldest age, saturation signals, and memory reserve alongside utilization. Scaling is slower than admission control, so immediate overload policy remains necessary. Document whether degraded hardware loses throughput, latency, or supported feature quality.

From a resource model to admission limits#

Build a table for each operation class with bytes read, bytes written, CPU time, temporary memory, durable output, and downstream requests. Multiply by the measured class distribution rather than one average operation. Then add burst envelopes and concurrent lifecycle work. The table will not predict an exact percentile, but it exposes impossible targets before expensive tuning.

Little's Law relates average in-flight work to arrival rate times average time in a stable system. It is useful for a first queue estimate, not permission to use averages for deadlines. Tail service times, retries, and burst correlation need simulation or trace replay. Capacity must be below the point where queue age grows without bound, with enough margin for a failed peer and maintenance.

Run step loads long enough for caches, allocators, compaction, and temperature to settle. At every step record offered, admitted, completed, and rejected rates. The sustainable point is where completed useful work remains stable and the oldest queue age returns after a burst. CPU saturation, memory bandwidth, lock contention, or downstream throttling will require different remedies.

Machine classes deserve separate configuration when their resource ratios differ. A many-core host with modest bandwidth may need fewer scan workers than its CPU count suggests. A small host may require smaller snapshot overlap and batch capacities. Prefer a few reviewed profiles over a formula based on reported core count, which is unreliable under quotas and virtual topology.

Failover planning includes correlated load. When one host fails, its peers receive state restoration traffic, client retries, and their own normal work. Benchmark restore while serving, with storage bandwidth and page cache in the same condition expected during an incident. Define which traffic is shed first and how quickly autoscaling can realistically produce initialized capacity.

Capacity alerts should be actionable. Oldest age near its deadline suggests admission or scaling; low byte permits identifies payload pressure; high remote NUMA traffic suggests placement; rising retries can identify a downstream limit. CPU percentage alone cannot distinguish useful computation from a spin loop, and low CPU does not imply spare memory or I/O bandwidth.

14. Memory budgets through the full lifecycle#

Steady-state heap size omits startup decoding, rebuild overlap, rollback state, and crash recovery. Write a phase table listing live sets for boot, normal service, migration, failover, and shutdown. Count allocator slack and page cache separately because both affect container pressure differently. Mapped virtual bytes are not resident bytes, yet touching them can create a sudden resident spike.

Set limits at domain boundaries such as sessions, syntax nodes, tags, tiles, or selected rows. Global byte caps alone permit one tenant to evict everyone else's useful state. Per-tenant quotas need a bounded shared reserve for small legitimate bursts. Eviction should prioritize recomputable and expired data before authoritative state.

Allocation failure paths deserve tests with partially built structures. Construct privately so failure can drop a consistent temporary value. Avoid updating parallel column lengths one allocation at a time without rollback. Metrics should expose live logical units and bytes per category to explain regressions.

Phases, pages, and accountable reserve#

Virtual memory is an address range promised to a process. Physical resident pages are the portions currently backed by RAM. The operating system may also keep file contents in a page cache, which accelerates rereads but competes for machine memory. Container accounting varies, so establish which categories its limit includes instead of assuming mapped bytes equal immediate consumption.

For every phase, sum authoritative data, indexes, allocator spare capacity, queues, scratch, snapshots, network buffers, code, thread stacks, and mapping residency. Migration adds old representation, new representation, conversion workspace, and rollback metadata. Recovery may add a read buffer and replay log while still serving the last good snapshot. Peak overlap, not normal heap, determines whether the process survives these transitions.

Fragmentation has internal and external forms. Internal waste is unused space inside allocated size classes or vector capacity. External fragmentation is free memory split into regions that cannot satisfy a large request or return pages efficiently. Long-lived allocations interspersed with transient objects are particularly troublesome. Group lifetimes in arenas and rebuild dense state at a controlled epoch rather than hoping an allocator can infer intent.

Page faults occur when an accessed virtual page lacks the needed mapping in the process page tables. Minor faults can install already available pages; major faults may wait for storage. Fault cost is invisible in a benchmark that touches all input before timing. Measure cold start separately, pre-fault only the critical bounded working set, and avoid touching a huge reserve merely to make a warm benchmark look predictable.

Memory reservation should be hierarchical. A global budget prevents process death, domain budgets protect queues from snapshots, and tenant budgets prevent one principal consuming the shared pool. Transfer permits with ownership: decoder reserve becomes batch storage, then queue reserve, then sealed segment bytes. A failed transition returns permits exactly once. Reconciliation metrics compare permit totals with category accounting to reveal leaks.

Shrinking requires safe epochs. A worker can replace an exceptional local buffer after its current request, while a snapshot cache evicts only roots with no semantic retention requirement. Never trim on the real-time callback or while holding a global lock. Rate-limit reclamation because page unmapping and destructors can create latency spikes as surely as allocation.

Test failures at each allocation boundary with tiny configured budgets rather than relying on actual machine exhaustion. Verify that parallel column lengths remain equal, temporary files are removed, queue permits return, and the last published generation remains readable. Out-of-memory abort behavior still requires admission far enough ahead that normal inputs do not reach it.

15. Case study: network sessions#

Packet handling repeatedly touches phase, sequence windows, deadlines, and buffer cursors. Certificates, user-agent text, and diagnostic history are cold after handshake. A worker-owned shard can keep hot columns dense while a slot table preserves session identity. Packets carry a slot and generation internally only after external identifiers are authenticated. Migration marks a session moving, drains its ordered mailbox, then publishes the new owner.

#[derive(Clone, Copy)]
struct SessionId { slot: usize, generation: u32 }
struct Sessions { generations: Vec<u32>, deadlines: Vec<u64>, received: Vec<u64> }

fn account(s: &mut Sessions, id: SessionId, now: u64, bytes: u64) -> bool {
    if s.generations.get(id.slot) != Some(&id.generation) { return false; }
    if s.deadlines[id.slot] < now { return false; }
    s.received[id.slot] = s.received[id.slot].saturating_add(bytes);
    true
}

fn main() {
    let mut s = Sessions { generations: vec![3], deadlines: vec![50], received: vec![0] };
    assert!(account(&mut s, SessionId { slot: 0, generation: 3 }, 40, 120));
    assert!(!account(&mut s, SessionId { slot: 0, generation: 2 }, 40, 1));
}

Validate packet lengths and sequence arithmetic before indexing receive windows. Cap bytes, outstanding packets, handshake work, and queued application messages per peer. Measure packets per session, migration rate, stale-handle rejects, deadline scans, and oldest mailbox age. Traffic distributions need idle keepalives, elephant transfers, reconnect storms, malformed packets, and loss. Lifecycle exercises must close sessions while delayed packets and timer entries remain.

An AoS record is better for a modest gateway that performs complete session logic per packet. Columns pay when timer scans cover millions of mostly idle sessions without touching cold state. A global mutex may be adequate for administration but should not serialize packet receipt. The counterexample is important: converting each packet into many column updates can cost more than locality saves.

Trace shape and ownership under reconnects#

A realistic trace is dominated by small packets and mostly idle connections, with a thin tail of bulk flows contributing most bytes. Timer sweeps touch expiry and phase for every live slot, while receive processing touches sequence state for only the active subset. This split justifies dense timer columns and separate cold handshake material only at a sufficiently large session count.

The shard worker owns receive windows, retransmit state, and application queue for its generation. Authentication maps an external token to an internal ID; it never trusts a peer-supplied slot. Closing first marks the generation dead, removes routing, and only then recycles buffers. Delayed timer entries compare the complete ID, so they cannot close a new occupant of the same slot.

During a reconnect storm, handshake CPU rather than packet bytes can saturate. Use separate bounded admission for unauthenticated work, cache only validated results within short limits, and issue retry tokens before allocating session state where the protocol permits. Existing sessions may receive reserved queue and CPU shares. Metrics distinguish cryptographic rejects, quota rejects, expired packets, application backpressure, and stale-generation traffic.

Workloads should include median packet and connection distributions plus an elephant-byte tail, NAT-correlated reconnects, reordered bursts, and slow consumers. Report p99 packet residence per traffic class, useful bytes per CPU second, active and half-open sessions, timer scan duration, and shard imbalance. A packet-per-second result without handshake and rejection costs is incomplete.

The concrete baseline is one HashMap<ConnectionId, Session> behind a mutex, with full record processing for each packet and a simple timer heap. It often wins below tens of thousands of sessions because lookup dominates and the whole record is warm. The column design must beat that implementation on the target idle-to-active ratio while preserving more complex migration behavior.

Rollout can shadow timer expiry decisions and byte accounting before moving packet authority. Compare session close reason and final sequence state, not raw internal order. On rollback, stop new column-owned sessions, drain existing generations, and route fresh handshakes to the old path. Recovery rebuilds the route table from authenticated durable identifiers; ephemeral retransmit state is either reconstructed by protocol exchange or explicitly lost.

16. Case study: compiler analysis tables#

Compiler passes have sharply different field demand. Parsing creates node kind, span, and child ranges; type analysis emphasizes symbols and inferred facts. Typed integer IDs let compact tables move while preventing accidental mixing of node and symbol namespaces. Phase arenas release temporary constraints together, while revision-tagged facts support incremental builds.

#[derive(Clone, Copy)]
struct NodeId(usize);
struct Nodes { kind: Vec<u8>, first_child: Vec<u32>, child_count: Vec<u16> }

fn leaf_count(nodes: &Nodes, ids: &[NodeId]) -> usize {
    ids.iter().filter(|id| nodes.child_count[id.0] == 0).count()
}

fn main() {
    let nodes = Nodes { kind: vec![1, 2], first_child: vec![1, 0], child_count: vec![1, 0] };
    assert_eq!(leaf_count(&nodes, &[NodeId(0), NodeId(1)]), 1);
    assert_eq!(nodes.kind.len(), nodes.first_child.len());
}

Every constructor must preserve equal column lengths and valid edge ranges. Malformed source can create deep nesting, enormous identifiers, and diagnostic explosions, so bound them. Measure nodes per file, edge density, cache hit rate, invalidation fanout, peak arena bytes, and diagnostic count. Use real repositories plus generated depth, wide expressions, error cascades, and tiny interactive edits.

Rich AoS nodes are excellent for a small interpreter where each visitor uses nearly every field. Columns excel when broad passes inspect only kind or fact state across large modules. Incremental IDs must never silently refer to a new revision after deletion. Dump tools should reconstruct readable nodes with source spans rather than exposing anonymous arrays.

Revisions, invalidation, and pathological source#

The access trace changes by phase and by edit size. A full build performs long kind and edge scans, while an editor repeatedly changes one file and requests facts near the cursor. Type checking follows symbol edges with locality based on modules, not allocation time. Store syntax rows by file and revision, and place cross-file symbol relations in a separate index whose rebuild cost is visible rather than mixing all nodes into one global arena.

A fact is valid only for the node revision and dependency generations used to derive it. Publication installs a complete analysis snapshot after diagnostics and indexes agree. Cancellation drops the private revision; it must not leave half-updated columns discoverable. Source spans refer to an immutable text snapshot, so edits cannot make old diagnostics index into a new buffer.

Adversarial source includes deeply nested types, broad union combinations, macro expansion growth, and thousands of errors caused by one missing token. Depth counters replace uncontrolled recursion where necessary. Budgets cap generated nodes, constraint steps, interned bytes, and diagnostics per source region. When exceeded, emit one stable bounded diagnostic and keep the server responsive for unrelated files.

Benchmark tiny keystrokes, clean full builds, dependency-wide API changes, generated million-node files, and code with high error density. Useful metrics include p95 answer latency after edit, reparsed nodes, invalidated facts, dependency visits, bytes per node, arena high-water, and cancellation waste. Cache hit rate needs a denominator by fact kind because cheap hits can hide repeated misses in expensive inference.

An ordinary tree of boxed or vector-owned rich nodes remains the comparison for a command-line compiler that walks complete declarations once. It provides natural recursive debugging and cheap construction. Tables earn their cost when selective repeated analyses and incremental retention outweigh ID lookup, parallel-array invariants, and reconstruction tools.

Deploy table changes by writing both fact hashes in development and a sampled production shadow. Persisted caches carry compiler build, target, options, schema, and source digest; any mismatch causes discard rather than creative migration of derived data. A crash loses only the private revision. Recovery loads validated cache segments, rebuilds missing indexes, and republishes one generation before accepting queries that require cross-file coherence.

17. Case study: log and telemetry ingestion#

Telemetry arrives burstily, with tenant skew and attacker-controlled tag cardinality. Validate envelope sizes before decoding, intern only within quotas, and retain original tenant attribution. Batches can store timestamp deltas, metric IDs, values, and validity separately for compression and scans. Flush IDs make retries idempotent across network uncertainty.

struct Batch { times: Vec<u64>, metrics: Vec<u32>, values: Vec<i64> }

fn push(batch: &mut Batch, time: u64, metric: u32, value: i64, cap: usize) -> bool {
    if batch.times.len() >= cap { return false; }
    batch.times.push(time); batch.metrics.push(metric); batch.values.push(value);
    true
}

fn main() {
    let mut b = Batch { times: vec![], metrics: vec![], values: vec![] };
    assert!(push(&mut b, 10, 7, 99, 1));
    assert!(!push(&mut b, 11, 8, 100, 1));
}

The production constructor should reserve all columns before committing a row to preserve equal lengths. Acknowledgment occurs only after the documented durability boundary, not merely after enqueue. Overload policy may preserve control metrics, sample noisy tenants, and reject excessive unique tags. Measure offered bytes, decoded rows, compression ratio, flush age, cardinality, drops by reason, and replay duplicates.

Test quiet trickles, full batches, synchronized agent reconnects, corrupt frames, and one dominant tenant. Row records remain simpler when logs are immediately forwarded without analytical projection. Column batches win when filters and compression repeatedly operate on selected fields. The lifecycle includes segment sealing, retry, retention deletion, schema evolution, and recovery after partial flush.

Bursts, durable acceptance, and tenant isolation#

The ingestion trace alternates between quiet partial batches and aligned flush bursts from thousands of agents. Values are dense, while tags are repeated but highly skewed across tenants. Dictionary encoding within a tenant or sealed segment improves scans without granting one global intern table to an attacker. Keep raw envelope ownership until decode validation succeeds, then transfer a compact batch to the flush queue under a byte permit.

Equal column length is a commit invariant. Decode into private temporary columns, validate timestamp bounds and dictionary references, then append the whole batch or none. A flush ID combines tenant, source epoch, and sequence. The durable deduplication index and segment acknowledgment advance together, so a retry after an ambiguous network failure cannot create duplicate rows.

When storage stalls, partial batches first fill and age. The service may flush smaller batches to reduce latency, but doing so increases metadata and write amplification. Once byte permits run out, reject low-priority telemetry or apply per-tenant deterministic sampling before expensive tag work. Audit and control events require a reserved path with its own strict bound, not an unbounded promise to accept everything important.

Replay synchronized reconnects with compressed and uncompressed envelopes, clock skew, duplicate flush IDs, one tenant generating millions of unique tag sets, and storage pauses longer than normal queue tolerance. Plot accepted and durable rows, oldest unflushed age, bytes per encoded row, dictionary growth, segment fsync latency, dedup hits, and drops by tenant and policy.

The domain-specific alternative is a row-oriented append log that forwards each validated event immediately. It minimizes latency and representation machinery for a relay service that rarely filters locally. Column batches are justified when compression, predicate routing, and local aggregation reuse the projection before storage. Compare end-to-end durable latency, not only decode throughput, because waiting to fill a batch is part of the design.

Sealing writes data and indexes to a temporary segment, verifies checksums and row counts, synchronizes according to the durability contract, then publishes the manifest entry. Recovery removes unreferenced incomplete files or resumes only from a validated checkpoint. Rollout dual-reads sampled sealed segments and compares canonical rows. Retention deletes a segment only after no query, replication task, rollback reader, or legal hold references its generation.

18. Case study: image and audio processing#

Images favor tiles when filters reuse neighborhoods; audio favors fixed blocks constrained by callback deadlines. Planar channels suit per-channel transforms, while interleaved samples suit devices and whole-frame operations. Conversion is worthwhile only when enough stages reuse the chosen layout. Worker-owned scratch buffers should be allocated and faulted before real-time execution.

fn gain_interleaved(samples: &mut [i16], numerator: i32, denominator: i32) {
    assert!(denominator != 0);
    for sample in samples {
        let scaled = i64::from(*sample) * i64::from(numerator) / i64::from(denominator);
        *sample = scaled.clamp(i64::from(i16::MIN), i64::from(i16::MAX)) as i16;
    }
}

fn main() {
    let mut audio = [1000i16, -1000, 2000, -2000];
    gain_interleaved(&mut audio, 3, 2);
    assert_eq!(audio, [1500, -1500, 3000, -3000]);
}

Image edge tiles need clipped halos and defined border policy. Audio arithmetic needs clipping, denormal policy where relevant, and a deterministic fallback for missed work. Measure cycles per pixel or frame, conversion bytes, scratch high-water, deadline misses, and end-to-end delay. Include odd dimensions, one-pixel images, silence, peaks, many channels, and cold startup.

A scalar interleaved loop often beats SIMD setup for short device blocks. Untiled streaming wins for a single brightness pass with no neighborhood reuse. GPU execution loses for small images when transfer and command latency dominate. Lifecycle work covers device format changes, buffer renegotiation, dropped frames, and safe callback shutdown.

Neighborhood reuse and audible failure#

An image pipeline usually reads each tile through several filters and may reuse halo pixels at tile edges. Its trace rewards tiled intermediate storage when multiple stages stay near the same region. Audio arrives in fixed cadence: each callback consumes the next interleaved device block even if upstream work is late. Planar conversion helps long per-channel chains, but a single gain and device write should remain interleaved to avoid two extra full-memory passes.

Pixels require declared color space, alpha convention, dimensions, stride, and border rule. Audio blocks require sample rate, channel order, frame count, timestamp, and discontinuity status. These properties travel with a generation of the format, not as loosely updated globals. On device renegotiation, build new converters and buffers privately, then switch at a safe block boundary.

An image worker can reject an oversized dimension before multiplying stride and height. Decode bombs need limits on expanded pixels and metadata. The audio callback never waits for image or control work and draws only from preallocated single-owner rings. If its input is absent, a short ramp to silence avoids a click; replaying an arbitrary stale block could produce a tone and is not a neutral fallback.

Evaluate 1-by-1 and odd-edge images, common photographs, huge panoramas, flat compressible inputs, noisy frames, mono speech, multichannel audio, silence, full-scale clipping, and rapid format switches. Record end-to-end frame age, cycles per output pixel, halo copy bytes, conversion passes, audio callback maximum duration, underruns, and scratch residency. Average audio throughput is irrelevant if one callback exceeds its period.

A direct scalar row loop is the image baseline for color conversion without neighborhood reuse. A direct interleaved callback is the audio baseline for a short chain. Tiling or planar columns must repay edge copying, format shuffles, and more complex shutdown. GPU comparison includes upload, dispatch, download, and synchronization; it cannot quote the convolution kernel alone.

Image jobs can be retried from immutable source after a worker crash. Live audio cannot replay elapsed wall-clock samples, so recovery reopens the device, primes bounded rings, resets filter continuity deliberately, and resumes at a new stream epoch. Canary rollout compares pixels within format-specific rules and records audio offline through both paths before enabling live callbacks.

19. Case study: simulation and render preparation#

Simulation mutates authoritative components; rendering consumes a coherent read-only frame description. Component columns support systems that touch position and velocity without loading names or scripts. Compact visible-ID lists narrow later work, and immutable draw packets sever renderer ownership from simulation. Triple buffering can discard an obsolete visual packet but must never tear authoritative state.

struct Motion { x: Vec<f32>, y: Vec<f32>, vx: Vec<f32>, vy: Vec<f32> }

fn step(m: &mut Motion, dt: f32) {
    assert!(m.x.len() == m.y.len() && m.x.len() == m.vx.len() && m.x.len() == m.vy.len());
    for i in 0..m.x.len() { m.x[i] += m.vx[i] * dt; m.y[i] += m.vy[i] * dt; }
}

fn main() {
    let mut m = Motion { x: vec![0.0], y: vec![1.0], vx: vec![2.0], vy: vec![-1.0] };
    step(&mut m, 0.5);
    assert_eq!((m.x[0], m.y[0]), (1.0, 0.5));
}

Entity generations reject stale commands after destruction and slot reuse. Moving between archetypes must update all indexes atomically at a safe phase boundary. Measure entities per archetype, migrations, visible fraction, packet bytes, frame percentiles, and stale commands. Replays capture inputs, seeds, fixed timesteps, asset versions, and stable merge order.

AoS is preferable for a small game where one loop updates every property of every entity. CPU render preparation wins when batches are small or GPU synchronization would extend latency. Failure tests kill producers mid-frame and hold consumers across several publications. Debug views should map entity IDs to coherent generation-tagged component snapshots.

Phase access and frame recovery#

The simulation trace consists of systems over different entity subsets: physics streams position and velocity, animation touches pose and time, while render preparation reads transforms and visible mesh IDs. Archetype chunks group entities sharing component sets, giving each system dense relevant runs. Render packets then copy only camera-visible immutable values in draw-friendly order, preventing the renderer from following mutable simulation references.

An entity belongs to exactly one archetype at a phase boundary. Moving it allocates its destination row, copies shared components, initializes additions, updates the stable slot mapping, and removes the source row with any moved-row mapping repair. Expose none of these intermediate states. Commands generated during a phase carry entity generation and execute in stable command order at the boundary, where stale targets are rejected.

Overload policies differ by subsystem. Simulation may reduce fidelity only through an explicit deterministic level, never by silently skipping random authoritative entities. Render preparation can drop an unpublished obsolete packet and proceed to the newest completed simulation snapshot. If rendering stalls, cap retained packets and release old assets only after their final GPU fence or CPU consumer acknowledgment.

Workloads need empty scenes, many identical static entities, highly dynamic archetype churn, visibility from near zero to all objects, particle bursts, and asset streaming during camera movement. Measure system bytes per entity, chunk occupancy, migrations, commands rejected by generation, culling ratio, packet build time, retained frame bytes, and input-to-present latency. Frame rate alone hides queues and can improve by displaying older frames.

The baseline is a vector of complete entity records updated and immediately converted to draw calls in one thread. It is compelling for small tools and games because all state is visible and phase machinery is absent. Archetypes must show gains on actual component sparsity and system reuse; a benchmark with one component combination unfairly removes migration and lookup costs.

Replay stores input commands, fixed timestep decisions, seeds, and asset versions, then compares canonical state hashes at every phase. A producer crash before publication leaves the prior coherent frame usable. Rollout shadows packet generation and compares stable draw keys and transforms, allowing only documented floating tolerance. Rollback drains GPU references before deleting new packet codecs or chunk layouts from the asset pipeline.

20. Case study: database-like column scanning#

Analytical scans read projected columns, evaluate predicates, and delay row materialization. Zone metadata can skip pages whose minima and maxima cannot match. Validity bitmaps separate nullness from values, while selection vectors carry surviving positions. Predicate order depends on cost, selectivity, encoding, and reuse rather than source order alone.

fn qualifying_rows(age: &[u16], active: &[bool], minimum: u16) -> Vec<usize> {
    assert_eq!(age.len(), active.len());
    age.iter().zip(active).enumerate()
        .filter_map(|(i, (&age, &active))| (active && age >= minimum).then_some(i))
        .collect()
}

fn main() {
    assert_eq!(qualifying_rows(&[18, 42, 70], &[true, false, true], 21), vec![2]);
}

Measure rows scanned, pages skipped, selected fraction, decoded bytes, null density, and materialized output. Datasets need all-match, no-match, clustered matches, random matches, cold pages, and corrupt metadata. Selection vectors lose when nearly every row survives because writing and rereading positions adds traffic. An index loses when probes are random and the predicate is broad.

Row layout remains ideal for point lookup returning most fields. Scalar scans can beat vector machinery on short tails or highly selective early branches. Snapshots pin segment generations while compaction writes replacements and atomically publishes metadata. Crash recovery must distinguish complete sealed segments from abandoned temporary output.

Selectivity, snapshot pins, and corrupt metadata#

Query access begins with a small projected set, scans page metadata, decodes candidate pages, writes a selection, and materializes surviving rows late. Skew matters: dates and tenant IDs cluster, while hashes may be uniform. Sort order and page boundaries should reflect common pruning predicates rather than an abstract desire for perfectly balanced values. Keep original row identity when clients require stable result references across late materialization.

Validity has one authoritative bit per logical row, and every encoded page declares row count, value bounds, codec, and checksum. Metadata is only a hint after validation; corrupt minima must not cause false-negative skipping. Readers pin a manifest generation before choosing segments. Compaction reads those immutable inputs and publishes replacements atomically, leaving pinned queries able to finish against the old files.

Under broad queries, memory for selection vectors and materialized output can dominate scan bandwidth. Stream bounded result batches with downstream backpressure rather than collecting all matches. Expensive queries receive work and byte budgets; cancellation checks occur between pages. Storage faults or a corrupt page fail according to query semantics instead of returning an apparently complete subset. Background compaction yields I/O permits to urgent cold reads.

Evaluate no-match and all-match predicates, one clustered range, random one percent selection, high null density, short tail pages, repeated warm scans, cold mapped scans, and concurrent compaction. Track physical and decoded bytes, minor and major faults, pages pruned, rows tested, selection bytes, output stall time, and snapshot pin age. Report time to first batch as well as completion.

The explicit counter-model is a row store with a B-tree lookup returning full records. It wins point queries and narrow ranges that require most fields. The column scanner wins broad analytical projections only after including decode and materialization. A scalar fused predicate remains a necessary competitor to staged selection, especially when the first condition is highly selective and later columns would otherwise stay untouched.

New encodings roll out per segment while readers support a bounded version set. A sampled verifier decodes old and new segments to canonical rows and compares aggregate checksums. Recovery reads only manifest-referenced sealed files, validates their roots, and quarantines corrupt segments without deleting evidence. Old codecs disappear after every retained snapshot, backup, replica, and rollback version is known to have crossed the compatibility boundary.

21. SIMD, GPUs, and acceleration boundaries#

SIMD rewards regular independent lanes with compatible arithmetic and contiguous inputs. Tails, masks, gathers, overflow, NaNs, and reduction order are semantic issues, not cleanup details. Stable portable scalar Rust provides the reference and lets compiler autovectorization work. Architecture-specific variants need runtime detection outside loops and equivalence tests.

GPUs require enough parallel work to repay transfer, command submission, synchronization, and format conversion. Keep data resident across multiple kernels when possible and batch dispatches. Divergent control, tiny workloads, and immediate CPU consumption favor CPU execution. GPU memory budgets include staging, device copies, pipelines, and overlapping frames.

Observe total pipeline latency, energy where relevant, transfer bytes, occupancy, and fallback frequency. Do not report kernel time alone while excluding preparation and synchronization. Canaries must compare outputs within documented floating tolerances. Code-size and maintenance costs justify limiting specialized variants.

Semantic contracts before dispatch#

Vectorization performs one instruction over several lanes. It is beneficial when lanes do equivalent work and memory is contiguous; masked lanes and gathers can spend much of that advantage. Define scalar semantics first: integer overflow, saturation, shift counts, NaN propagation, signed zero, rounding, and reduction order. An accelerated path is incorrect if it changes a security decision merely because its comparison handles NaN differently.

Dispatch once per substantial batch. Detect supported CPU features at process initialization or a cold call boundary, select a function, and record the choice in diagnostics. Avoid one compiled variant for every combination of codec, precision, filter, and CPU feature. Such cross-products expand code size, increase instruction-cache misses, slow builds, and leave rare variants poorly tested. Compose a small decode stage with a small kernel family instead.

Alignment is a property to check, not an excuse for undefined behavior. Portable scalar slices remain valid for odd starts and tails. Specialized code can peel a prefix and handle a scalar suffix, while tests cover lengths around every lane boundary. Tiny inputs stay on scalar code because dispatch, packing, and cleanup may exceed useful arithmetic. Benchmark crossover by input size.

GPU submission transfers ownership of buffers until a fence or completion event. A staging allocator cannot recycle a range merely because the CPU call returned. Track generation and in-flight bytes, cap queued submissions, and define device-loss behavior. Recomputable image work can return to the CPU; an acknowledged durable update cannot be silently rerun with changed numeric semantics. Fallback must use the same validated input and output contract.

Device memory exhaustion should reject before half a graph is submitted. Reserve outputs, scratch, descriptors, and overlap for the chosen graph, then release on completion or cancellation acknowledgment. A timeout does not prove the device stopped using memory. Device loss requires abandoning that context, failing affected promises once, and rebuilding immutable resources from known CPU or durable copies.

Compare scalar, compiler-autovectorized, explicit CPU, and GPU paths using the same corpus and oracle. Include transfer, format conversion, queue residence, warm-up, shader compilation, and synchronization. Report fallback counts and why they occurred. Canary comparisons sample whole outputs and adversarial edges, not only aggregate sums that can hide lane permutations.

22. Persistence, schemas, mapping, and crash boundaries#

Persistent bytes require explicit widths, signedness, endianness, alignment rules, and version semantics. Rust structure layout is not a durable schema. Decode with checked offsets and canonical byte conversions, validating structure before allocation.

fn read_le_u32(input: &[u8], offset: usize) -> Option<u32> {
    let end = offset.checked_add(4)?;
    Some(u32::from_le_bytes(input.get(offset..end)?.try_into().ok()?))
}

fn main() {
    assert_eq!(read_le_u32(&[1, 0, 0, 0], 0), Some(1));
    assert_eq!(read_le_u32(&[1, 2], 0), None);
}

Writers should emit one current version while readers support a bounded migration window. Migrations need restartable progress, rate limits, old-plus-new disk budget, verification, and rollback. Generated codecs can centralize limits and golden fixtures when schemas are reviewed inputs. Unknown fields need an intentional preserve, reject, or discard policy.

Zero-copy borrows source lifetime and alignment; it does not eliminate cache traffic. Memory mapping avoids an explicit read copy but introduces page faults and residency uncertainty. Cold random mapping can be slower and less predictable than buffered sequential reads. Explicit copies are safer when input lifetime is short or canonicalization is required.

Crash consistency defines valid states after interruption. Write new content, validate checksums and semantic counts, synchronize as promised, then publish a small root. Acknowledgment must correspond to the documented durability point. Recovery tests cut power conceptually after every step and verify idempotent replay.

Evolution without layout guesses#

A schema names fields and their meaning independently of an in-memory struct. Fixed-width integers specify byte order; variable fields specify length encoding and maximum size; references specify whether unknown targets are errors. A reader first validates header, version, declared lengths, and checksum ranges, then reserves bounded destinations. It never casts arbitrary mapped bytes to a Rust struct whose padding and alignment are compiler choices.

Endianness is the order of bytes within a multibyte value. Choose one canonical wire order and decode with from_le_bytes or from_be_bytes. Byte swapping is usually cheaper than maintaining native-order file variants. Golden fixtures include boundary signed values and are generated independently enough to catch a codec that writes and reads the same wrong convention.

Migration should be a resumable state machine: discover an old object, reserve new capacity, convert privately, validate semantic equivalence, publish the new reference, and record completion. Checkpoints identify source generation and destination checksum. Restart either recognizes a complete idempotent result or safely rebuilds it. Rate limits cover I/O, CPU, and overlap bytes so normal service retains headroom.

Readers often support versions N and N-1 while writers emit only N. Mixed clusters require capability negotiation before a writer uses new required fields. Unknown optional fields can be preserved as bounded opaque bytes when forwarding requires it, but doing so must not bypass size limits. Removing old readers waits for replicas, backups, rollback binaries, and offline repair tools, not merely the active server fleet.

Mapping, acknowledgment, and repair#

Memory mapping lets the operating system populate file-backed pages on access. It is called zero-copy because an explicit user-space read buffer may vanish, not because bytes avoid storage, memory, caches, or decoding. A mapped slice also borrows the file generation: truncation or replacement by another actor can invalidate assumptions. Keep immutable files and publish new names or roots rather than modifying mappings beneath readers.

Sequential buffered reads provide controllable readahead and bounded buffers. Mappings are attractive for random shared reads and natural snapshot lifetime, but page faults can occur at surprising instructions. Test after dropping page cache in a representative environment where allowed, and report major faults, resident growth, and latency. Prefaulting an entire giant index can cause an outage by evicting the currently useful working set.

Crash consistency is a sequence of ownership claims. Temporary output is not discoverable, a validated sealed object is immutable, and a published manifest is the sole authority for readers. Synchronization calls and directory entry durability vary by platform and filesystem, so the service contract must state what has actually been verified. A checksum detects damage but does not make an unsynchronized acknowledgment durable.

Acknowledge a write only at the promised point: accepted in volatile memory, replicated to a peer, or synchronized to durable media are distinct products. Recovery starts from the last valid root, scans bounded journal records with checksums and sequence continuity, and replays idempotently. It retains corrupt bytes for diagnosis while quarantining them from normal readers. Repair never guesses missing authoritative values from page metadata.

Generated codecs should emit checked decoders, size calculators, validators, and field-name diagnostics from a reviewed schema. Fuzz generated readers and cross-test them with independent fixtures. Keep generation deterministic so a schema change produces reviewable diffs. Hand-written policy remains around resource quotas, migrations, authorization, and durable publication; generated syntax alone cannot decide those semantics.

23. Security, APIs, and maintainable representations#

Safe memory access does not bound computational or memory cost. Limit lengths, nesting, graph expansion, decompression ratios, unique keys, and expensive diagnostics. Apply quotas before interning or reserving attacker-provided cardinalities. Hash flooding, sparse huge IDs, and retry amplification deserve dedicated adversarial tests.

Domain APIs should expose operations such as append batch or publish generation, not mutable columns. Constructors enforce equal lengths, sorted ranges, generation validity, and ownership phase. Internal layouts can then evolve without infecting callers. Generated code is useful when one schema produces validators, codecs, fixtures, and readable documentation.

Debug views reconstruct bounded, redacted records from compact storage. Dumps include schema, build identity, configuration, generation, checksum, and snapshot age. Deterministic replay captures accepted inputs and nondeterministic dependencies, not private secrets indiscriminately. Sampling and dump limits prevent observability from becoming an outage mechanism.

Cost is part of input validation#

An input can be memory-safe and still consume quadratic time. Duplicate-name checks implemented by scanning prior names, recursive graph expansion without a visited set, and repeated insertion into the front of a vector are common examples. State complexity expectations for public operations and test them on growing adversarial inputs. A ratio graph reveals whether doubling input makes work roughly double, quadruple, or worse.

Hash maps need a denial-of-service-resistant default for attacker-controlled keys, plus cardinality quotas. Replacing the hasher for benchmark speed changes the threat model. Sorting bounded batches can offer deterministic behavior and predictable worst-case complexity. Sparse external IDs must map through a bounded dictionary rather than resize a vector to the largest observed number.

Decompression and expansion reserve from declared and policy-limited output, then verify actual production. Nested formats carry a shared recursion and byte budget through every decoder. Errors are concise and rate-limited because formatting one diagnostic per malformed child can become the dominant attack. Authorization happens before expensive cold-field hydration whenever enough authenticated envelope data is available.

Interfaces, dumps, and reproducible incidents#

Public methods should consume validated domain values and preserve ownership. For example, append_batch can guarantee equal columns, while exposing three mutable vectors lets callers violate the invariant between pushes. Iterators can yield read-only reconstructed rows without promising that rows exist in memory. Stable IDs cross API boundaries; offsets and pointers remain private.

Generated APIs are valuable for repetitive field validation and codec wiring, provided generated names remain domain-readable. A schema compiler can produce builders that require mandatory fields, checked size estimates, and versioned decoders. Human review should reject a schema that permits unbounded repeated fields even if code generation handles its syntax perfectly.

Observability has its own capacity plan. Use per-worker bounded counters and histograms, merge on intervals, and cap unique labels. A debug dump takes one coherent snapshot, limits records and bytes, redacts secrets before writing, and includes truncation markers. It must not hold a global mutation lock while performing disk or network I/O. Operators need category totals even when row details are sampled.

Deterministic replay captures the minimum authorized evidence: accepted event bytes or canonical operations, ordering keys, schema and configuration hashes, clock decisions, seeds, and external responses. Encrypt and expire sensitive captures, and audit access. A bounded ring can preserve the seconds preceding an invariant failure, freezing only on trigger. If overwritten history is required for compliance, it belongs in a durable audit subsystem instead.

Fuzzing targets parsers and operation sequences; property tests compare compact representations with a simple model. Include stale handles, cancellation, duplicate retries, generation publication, and quota release. Security review must cover recovery tools too, because they often parse damaged bytes with elevated privileges and weaker operational monitoring.

24. Rollout, rollback, and incident playbooks#

Ship representation changes behind a reversible selection boundary. Shadow execution compares outputs without serving them, but doubles compute and sometimes memory. Canaries should include machine classes and workload shapes likely to expose the change. Success criteria cover correctness, tails, errors, memory, queue age, and recovery behavior.

Rollback remains possible only while formats and acknowledgments are backward compatible. Define deletion criteria before launch: confidence period, minimum versions, and migration completion. Then remove obsolete codecs, dual writes, flags, dashboards, and retained state deliberately. Permanent dual paths expand code size and incident ambiguity.

Incident playbooks begin with containment: disable the path, shed work, stop migration, or isolate shards. Preserve triggering inputs, build identity, distributions, counters, profiles, and generation metadata. For memory spikes inspect category high-water marks; for latency separate queue from service. For stale identities quarantine reuse; for corruption stop writers and retain original bytes.

Recovery steps must be rehearsed and have named owners. Restarting can erase queue and allocation evidence, so capture bounded diagnostics first. After containment, reproduce against the scalar or old-layout oracle. The permanent repair should tighten an invariant, limit, measurement, or transition rather than add folklore.

Compatibility gates and eventual deletion#

Define a compatibility matrix before the first canary. Rows are writer, reader, persisted schema, replay tool, and rollback binary versions; cells say whether interaction is supported. A new writer remains disabled until every reader that may receive its output advertises support. Mixed-version tests include failover and restore, not just normal request exchange.

Shadowing can compare canonical outputs without changing authority. Bound its CPU and memory, sample by stable request key, and drop shadow work first under load. Dual writing is riskier because two side effects can diverge. If needed, choose one authoritative acknowledgment and reconcile the secondary with idempotent sequence keys. Never tell clients both copies are durable when only one completion was observed.

Canary cohorts should represent NUMA hosts, smaller memory classes, cold restarts, high-cardinality tenants, broad scans, and bursty clients. Compare distributions rather than fleet-wide averages. Automatic rollback triggers use correctness mismatches, queue age, memory reserve, rejection reasons, and crash loops, with enough persistence to avoid toggling paths repeatedly.

Deletion begins only after the confidence window, fleet capability, persistent migration, backup expiry, and rollback policy all agree. Remove old writes first when no rollback depends on them, then readers after old bytes disappear. Delete feature flags, conversion buffers, metrics, alerts, repair branches, and documentation together. Leaving dormant variants increases binary text, instruction-cache pressure, attack surface, and on-call uncertainty.

Diagnosis by symptom and safe recovery#

For a latency incident, first graph intended arrivals, admitted work, queue age, service time, completion, and rejection. Rising queue age with stable service points to insufficient capacity or an arrival burst. Rising service time only on one shard suggests skew, remote NUMA placement, a lock holder, or cold pages. Capture bounded profiles and placement evidence before restarting.

For memory growth, compare logical item counts with reserved, resident, mapped, snapshot, queue, scratch, and migration bytes. Stable logical counts with old snapshot generations implicate a held reader; growing reserved but not live bytes suggests retained capacity or fragmentation. Stop migrations and shadow paths, lower admission safely, and preserve category high-water evidence.

For corrupt persisted data, stop writers that could overwrite evidence and record the active manifest, file identities, schema versions, checksums, and acknowledgment frontier. Restore the last independently validated root, replay only continuous checked journal records, and quarantine the first failure. Do not run a destructive repair tool against the sole remaining copy.

For stale identities or divergent simulation, freeze slot reuse if capacity allows, capture generation mappings and triggering commands, and replay from the nearest matching checkpoint. Compare canonical hashes by partition to narrow the first divergence. Recovery publishes a newly identified generation; it does not mutate the suspect snapshot and pretend history remained unchanged.

For audio underruns or missed frame deadlines, disable optional processing, switch to the rehearsed bounded fallback, and inspect maximum callback time, page faults, queue readiness, and device format epoch. Synchronous logging or allocation in the callback is removed before adding larger latency buffers. A larger buffer may mask jitter but changes user-visible delay and is a product decision, not a universally safe incident fix.

Every playbook names decision authority, evidence location, traffic controls, rollback command, compatibility preconditions, and communication channel. Exercises inject one failure at a time and verify the system returns permits, drains retries, reclaims old generations, and restores alert baselines. Post-incident tests preserve the exact distribution and transition that failed, while sensitive captures follow their retention and access policy.

25. Production decision checklist#

State the operation, population, field accesses, traversal, owner, lifetime, and deadline. Name the baseline, including AoS, scalar code, explicit copy, mutex, or simple queue where appropriate. Account for live, reserved, resident, mapped, queued, scratch, snapshot, migration, and recovery memory. Reject overflow and untrusted expansion before allocation or indexing.

Measure representative size, skew, sparsity, burst, malformed, cold, and failover distributions. Report offered and completed throughput with queue, service, end-to-end percentiles, errors, and drops. Check coordinated omission, output equivalence, benchmark metadata, and startup effects. Estimate bytes moved and verify whether cache, instructions, bandwidth, or synchronization limits progress.

Choose tiling only where reuse repays edges and traversal machinery. Keep branches when predictable or when the rare path is expensive. Prefer local ownership, coarse partitions, worker buffers, and deterministic reductions before shared atomics. Document every lock scope and every atomic ordering argument.

Bound queues, retries, snapshot retention, debug output, cardinality, and per-tenant consumption. Define overload semantics and real-time fallback before saturation. Version persistent and wire bytes with canonical endianness and restartable migrations. Test page faults, partial writes, crashes, restore, stale generations, and delayed readers.

Validate adversarial computational cost as well as structural safety. Provide domain operations, invariant checks, readable views, bounded dumps, and replay inputs. Roll out with shadows or canaries, compatible rollback, and explicit deletion milestones. Maintain an incident playbook with containment, evidence, recovery, ownership, and communication.

Finally, revisit the access model after production evidence arrives. Remove transformations whose conversion or maintenance cost exceeds their measured benefit. Retain simple implementations when they satisfy budgets and reduce operational state space. Data orientation is disciplined attention to work and bytes, never allegiance to one layout.

Part VI: Measurement, Verification, Open Source, and Mastery#

This part teaches the evidence and communication skills that turn a promising layout into trustworthy engineering. By the end, you will be ready to benchmark, review, contribute, and explain DOD work in public.

1. Evidence Is the Production Skill#

Data-oriented design is not a contest for the cleverest memory layout. It is a discipline for connecting representation to observable outcomes. Production work starts with a user or business outcome, not a profiler screenshot. A checkout service might care about completed orders per minute. A game might care about frames delivered before a 16.7 millisecond deadline. A database might care about durable writes and tail latency under recovery load. These are outcome metrics: measurements that describe value or harm to users. Engineering metrics such as cycles, allocations, and cache misses explain outcomes. They are means, not ends.

Write the decision before gathering evidence. For example: reduce import p95 latency without increasing memory beyond its budget. The decision defines which measurements can change the next action. It also prevents collecting attractive but irrelevant charts. State a guardrail beside the primary metric. Guardrails include correctness, memory, power, fairness, and operational complexity. A faster result that corrupts records has failed. A faster result that doubles cloud cost may also have failed.

Define the workload as carefully as the metric. A workload is the operations, inputs, concurrency, and environment being measured. Record data sizes, value distributions, request mixtures, and read/write ratios. Record whether data begins in memory, page cache, or durable storage. Record thread count, affinity policy, runtime settings, and backpressure behavior. Record steady-state duration and startup behavior separately. Real traffic traces are useful after removing secrets and preserving distributions. Synthetic inputs are useful when they isolate one mechanism. Neither is automatically representative.

Use this evidence loop:

outcome and guardrails
        -> representative workload
        -> baseline and profile
        -> hypothesis about one limiting resource
        -> smallest relevant change
        -> correctness verification
        -> repeated measurement
        -> ship, revise, or revert

Keep an evidence log under version control or attached to the issue. Include commands, commit identifiers, machine details, raw results, and interpretation. Separate observations from explanations. “Samples cluster in lookup” is an observation. “Hashing dominates because keys are long” is a hypothesis until tested. This distinction makes failed hypotheses useful rather than embarrassing.

2. Start With a Reproducible Baseline#

Build the exact artifact users run whenever practical. Rust debug builds optimize for compilation and debugging, not realistic throughput. Use cargo build --release or a project-specific production profile. Check that assertions, features, logging, panic strategy, and link settings match deployment. Profile-guided optimization and link-time optimization can change code shape substantially. Document whether they are enabled instead of silently mixing configurations.

A baseline is a repeatable measurement before the proposed change. It should include correctness checks and operating conditions. Pin versions with the lockfile and capture the compiler version. Keep the machine mostly idle and connect laptops to stable power. Disable automatic updates, indexing, and thermal surprises when possible. Do not claim laboratory precision from a shared continuous-integration runner. Shared runners can still catch large regressions with conservative thresholds.

Begin with the standard library when building a small harness. This exposes timing, setup, and statistics rather than hiding them.

use std::hint::black_box;
use std::time::{Duration, Instant};

fn measure<F, T>(iterations: u64, mut operation: F) -> Duration
where
    F: FnMut() -> T,
{
    let start = Instant::now();
    for _ in 0..iterations {
        black_box(operation());
    }
    start.elapsed()
}

fn main() {
    let input: Vec<u32> = (0..100_000).map(|x| x % 97).collect();
    let elapsed = measure(500, || {
        black_box(input.as_slice()).iter().copied().map(u64::from).sum::<u64>()
    });
    println!("elapsed={elapsed:?}");
}

black_box discourages the optimizer from deleting an apparently unused computation. It is a barrier to some optimization, not a magical realism switch. Opaquify inputs as well as outputs when repeated inputs are otherwise loop-invariant; without the input barrier, the optimizer may move a pure computation outside the timed loop. Inspect whether the harness still measures the intended work. Time a batch when one operation is shorter than clock resolution. Divide only after retaining the batch duration and iteration count.

Run a warmup before recording samples. Warmup allows code pages, allocators, branch predictors, and caches to settle. It also exposes lazy initialization that belongs either inside or outside the workload. Keep setup outside the timed region unless setup is part of the user operation. Parsing an input once is setup when benchmarking repeated queries. Parsing is measured work when benchmarking end-to-end request ingestion. State that boundary explicitly.

Never publish a single duration as a universal truth. Collect independent samples, preserve raw values, and inspect their distribution. Report machine, operating system, compiler, configuration, and workload definition. Report throughput for capacity questions and latency for responsiveness questions. Avoid invented benchmark numbers in design documents. If measurement is unavailable, label estimates as estimates and show assumptions.

3. Diagnose the Kind of Limit#

Profiling asks where resources go while benchmarking asks how much time passes. Profile before redesigning because intuition overweights visible and recently edited code. Start broad, then choose tools that match the observed symptom.

A CPU symptom shows busy cores and substantial on-CPU samples. Look for expensive instructions, repeated computation, poor vectorization, or large traversals. High CPU does not necessarily mean the CPU is the root cause. Spin loops and lock contention can consume CPU while making no useful progress.

An allocation symptom includes many allocation calls, allocator contention, or heap growth. Count allocations and bytes, because one million tiny allocations differs from one huge buffer. Check ownership design, temporary collections, formatting, and repeated capacity growth. Removing allocations can reduce latency without changing algorithmic complexity. Pooling can retain excessive memory and complicate lifecycle correctness.

An I/O symptom includes blocked tasks, low CPU utilization, and storage or network waits. Measure bytes, operations, queue depth, and service time. Changing an array layout cannot fix a synchronous remote call. Batching might improve throughput while worsening latency, so consult the outcome metric.

A lock symptom includes blocked threads, futex activity, long critical sections, or convoying. Measure wait time separately from hold time when tooling permits. Sharding may reduce contention but can complicate snapshots and memory use. Replacing a mutex with atomics is not automatically safer or faster.

A branch symptom appears when unpredictable decisions dominate a hot loop. Sorted or skewed inputs may train predictors differently from random inputs. Branchless code can execute extra work and sometimes loses. Measure realistic distributions before transforming control flow.

A memory symptom appears when cores wait for data rather than instructions. Clues include sensitivity to working-set size, layout, stride, and cache state. Bandwidth saturation and latency stalls require different remedies. Structure-of-arrays can help scans that touch a few fields. Array-of-structures can help operations that consume every field together.

Symptoms can overlap. Allocation touches memory, locks allocator state, and may trigger operating-system work. I/O completion can awaken contending threads and disturb caches. Form a resource hypothesis, then seek a prediction unique to that hypothesis. If locality is the cause, performance should change near cache-size boundaries. If locking is the cause, performance should change with thread count and contention.

4. Sampling, Flame Graphs, and Linux perf#

A sampling profiler periodically records where execution is occurring. It observes a fraction of execution rather than instrumenting every function call. Sampling usually has manageable overhead and works well for production-like workloads. Short functions can still dominate if they execute often enough. Very short runs produce too few samples for stable conclusions.

A stack sample records the current function and its callers. A flame graph aggregates stack samples into horizontal widths. Width represents sample share, not elapsed order and not call count. Vertical position represents call-stack depth. A wide plateau identifies a stack path worth investigation. Color usually has no semantic meaning unless the generator says otherwise.

Compile with symbols and enough frame information for readable stacks. Inlining means source functions may merge or disappear in profiles. Missing frames can result from unwinding configuration rather than absent work. Kernel, runtime, and native dependency frames may matter as much as Rust frames. Compare an on-CPU profile with wall-clock or off-CPU evidence for blocking services.

Linux perf is a family of kernel performance-observation tools. Conceptually, perf record samples events and call stacks during a command. perf report aggregates the captured data by symbol and stack. perf stat counts selected hardware or software events for a whole run. Permissions, kernel settings, virtualization, and hardware determine available events.

cargo build --release
perf record -g -- ./target/release/my-workload representative-input
perf report
perf stat -r 10 -- ./target/release/my-workload representative-input

Treat these commands as starting points, not universally portable recipes. Select a consistent stack-unwinding method appropriate to the build. Avoid recording confidential payloads or exposing symbols carelessly in production. Measure profiler overhead by comparing profiled and unprofiled runs.

Hardware counters estimate events such as cycles, instructions, cache misses, and branches. Instructions per cycle can reveal changing machine utilization. Cache-miss rates can suggest a working-set or access-pattern problem. Branch-miss rates can suggest input-dependent control-flow cost. Counters are clues, not proof of a source-level cause. Speculation, prefetching, event multiplexing, and microarchitecture complicate interpretation. Virtual machines may expose incomplete or noisy counters.

Use counter comparisons only for equivalent useful work. A version doing less work naturally executes fewer instructions. A version doing more instructions can still finish sooner through parallelism. Normalize bytes and operations alongside machine events. Confirm the suspected mechanism with a controlled workload change.

5. Cost Models, Amdahl's Law, and Bytes per Work#

A cost model is a simplified account of work and resource movement. It predicts direction and scale before implementation. Useful models are explicit enough to be disproved.

Amdahl's law says total speedup is limited by the unchanged part. If only a small fraction of time is improved, total improvement stays small. Making five percent of execution infinitely fast saves at most five percent overall. The exact formula matters less than the habit of measuring the improvable fraction. Optimization can also shift the bottleneck into previously minor code.

Write the baseline as shares rather than guesses about entire speedup.

total time = parsing + lookup + allocation + waiting + output
candidate change affects only lookup and some allocation
maximum plausible gain is bounded by those measured shares

Parallel Amdahl reasoning includes serial coordination and communication overhead. Adding threads cannot accelerate a serial stage. It may slow that stage through contention and cache interference. Measure scaling at one, two, four, and more workers rather than extrapolating.

A bytes-per-work model is often illuminating for data-oriented code. Define one unit of useful work, such as updating one active entity. List bytes read, bytes written, metadata touched, and temporary bytes created. Include index arrays and indirection, not just payload fields. Multiply by operation rate to estimate required bandwidth. Compare the estimate cautiously with sustainable measured bandwidth, not marketing peak.

bytes per entity update
  position read:         size_of(Position)
  velocity read:         size_of(Velocity)
  position write:        size_of(Position)
  alive metadata:        one amortized fraction of its storage
  sparse lookup:         index plus generation, if required
  write allocation:      architecture-dependent and measured separately

Alignment and padding can invalidate source-level size intuition. Use std::mem::size_of and inspect representative container capacity. Cache lines transfer neighboring bytes whether the algorithm requests them or not. Prefetchers favor regular access but cannot rescue every random dependency chain.

Count algorithmic work too: comparisons, hashes, probes, branches, and synchronization. Model best, typical, and adversarial distributions. A cost model chooses experiments; it does not replace them. After measurement, revise the model and preserve what was learned.

6. Designing Benchmark Harnesses#

A benchmark is an experiment with controlled variables. Name the question in its function or report title. “dense_scan_by_size” is more useful than “new_vs_old.” The name remains meaningful after implementations change.

First establish a standard-library harness you fully understand. Add warmup iterations and multiple independently timed samples. Store durations for later analysis instead of averaging immediately. Randomize implementation order when drift could favor the first or second candidate. Confirm outputs outside timing so optimized-away or incorrect work fails loudly.

Criterion and divan are optional Rust benchmark crates. They can provide sampling, statistics, plots, parameterization, and convenient reports. Use the harness already accepted by the project. Do not add a dependency merely to decorate a tiny experiment. Read each crate's current documentation because APIs and defaults evolve. Understand what its reported interval and outlier policy mean.

Separate setup into intentional layers. Global setup creates immutable source data once. Per-sample setup restores mutable state without entering the timed region. Per-iteration setup belongs inside timing only when users pay that cost. Teardown may cause deferred drops; decide whether those drops are part of work. Large clones outside timing can still perturb cache state before measurement.

Input distributions define branch behavior and memory locality. Test uniform random, skewed, sorted, clustered, and adversarial inputs when relevant. Use deterministic seeds and record the generator. Never use an all-zero vector merely because it is convenient. Include absent-key frequency for lookup benchmarks. Include mutation frequency for indexes whose maintenance has a cost.

Test warm-cache and cold-cache questions separately. A warm-cache benchmark repeats over a working set likely to remain resident. A cold-cache approximation rotates through data larger than relevant caches. Flushing caches perfectly is difficult and usually privileged or intrusive. Describe the approximation rather than claiming literal coldness. Production often lies between both extremes.

Build a size matrix around meaningful boundaries. Include empty, one, small, typical, large, and capacity-stressing cases. Include values near vectorization chunks, page sizes, and expected cache transitions. Build an alignment matrix only where alignment is a plausible mechanism. Test naturally aligned, offset, and padded layouts without introducing undefined behavior. Do not infer a universal threshold from one processor.

Throughput is useful work completed per time unit. Report items per second, requests per second, or bytes per second with clear semantics. Latency is elapsed time for one operation or request. Report p50, p95, and p99 when tails affect users. The p99 is the value at or below which 99 percent of observations fall. Percentiles require enough observations and a stated aggregation method. Never average percentiles from separate machines as if they were raw samples.

Noise is variation unrelated to the candidate change. Sources include scheduling, frequency scaling, temperature, interrupts, and background work. Increase sample duration, reduce interference, and repeat across process launches. An interval quantifies uncertainty under assumptions; it does not guarantee truth. Effect size describes how large the difference is, not merely whether detected. A statistically detectable tiny change may have no operational value. A large but noisy change deserves more investigation, not automatic dismissal.

Preserve distributions instead of only means. Plot or list sample summaries and inspect multimodal results. Two modes can reveal thermal states, allocator phases, or competing workloads. Use robust summaries such as medians while retaining tails. Set regression thresholds from historical noise and business relevance.

7. Inspecting Assembly and LLVM IR#

Source code expresses intent; generated code reveals one compiler's chosen implementation. Inspect assembly only after a profile and hypothesis point to a hot region. Otherwise it becomes an absorbing search for aesthetically pleasing instructions.

Assembly inspection can answer focused questions. Was a bounds check removed from the inner loop? Was the loop vectorized? Did an abstraction inline? Did an accidental copy remain? Are calls to allocation or panic paths present?

LLVM intermediate representation, or LLVM IR, sits below Rust source and above assembly. It can make vector operations, alias assumptions, and control flow easier to compare. Neither assembly nor IR proves runtime performance. Instruction scheduling, cache behavior, and input distributions remain dynamic.

Use release settings and the same target features as deployment. Generic local builds may omit instructions enabled in production. Native-target builds may create artifacts that cannot run on older machines. Compare functions by semantic role, not by unstable symbol spelling. Compiler upgrades can change output without changing source.

Tools such as cargo asm, compiler emission flags, and Compiler Explorer can help. Optional tools should not become required production dependencies. A direct compiler command can emit LLVM IR for a suitably isolated crate.

cargo rustc --release -- --emit=llvm-ir
objdump -d -C target/release/my-binary | less

Exact artifact paths and flags vary with crate type and toolchain. Keep a tiny reproducer when investigating optimizer behavior. Return to end-to-end measurement after understanding generated code.

8. Verification Begins With a Reference Model#

Optimization changes representation while promising the same observable behavior. A simple scalar reference model makes that promise executable. “Scalar” here means straightforward element-by-element code, not necessarily one CPU instruction. Prefer clarity over speed in the reference. Keep it independent enough that optimized and reference versions do not share the same bug.

Differential testing feeds identical operations to two implementations and compares results. It is especially effective for dense/sparse sets, generation tables, and batched transforms. Compare externally visible state after every operation when sequences are short. For long sequences, compare checkpoints and final state to control test cost.

Property-style testing checks general rules across generated inputs. Dependencies are optional; a tiny deterministic generator is enough to begin.

fn next(seed: &mut u64) -> u64 {
    *seed ^= *seed << 13;
    *seed ^= *seed >> 7;
    *seed ^= *seed << 17;
    *seed
}

#[test]
fn optimized_matches_reference() {
    for initial_seed in 1..=200 {
        let mut seed = initial_seed;
        let mut reference = ReferenceSet::new();
        let mut optimized = DenseSet::new();

        for _ in 0..1_000 {
            let id = (next(&mut seed) % 128) as u32;
            if next(&mut seed) & 1 == 0 {
                assert_eq!(optimized.insert(id), reference.insert(id));
            } else {
                assert_eq!(optimized.remove(id), reference.remove(id));
            }
            assert_eq!(optimized.sorted_values(), reference.sorted_values());
        }
    }
}

Store the seed when a generated case fails. Shrink a failure manually by deleting operations or reducing values. A minimized sequence turns a mysterious failure into a regression test. Exercise empty states, duplicates, maximum sizes, repeated removal, and wraparound policies.

Fuzzing is an optional extension that mutates inputs and explores surprising paths. Define an oracle: no panic, model equivalence, parser round-trip, or invariant preservation. A fuzzer without a meaningful oracle finds fewer semantic bugs. Save the corpus and minimized failures where maintainers can rerun them. Fuzzing finds examples; it does not prove all inputs correct.

9. Unsafe Code and Specialized Verification Tools#

Unsafe Rust creates obligations that ordinary type checking cannot enforce. Write each obligation next to the unsafe block. Cover pointer validity, alignment, initialization, aliasing, lifetimes, and drop behavior. Then test the safe API that maintains those obligations.

Miri interprets Rust with checks for many forms of undefined behavior. It can catch invalid pointer use, some aliasing violations, and uninitialized reads. Run focused tests because interpretation is much slower than native execution. Miri does not model every platform behavior, external function, or concurrency reality. Passing Miri is evidence, not a proof that all unsafe code is valid.

Sanitizers instrument native programs to detect classes of memory and thread errors. AddressSanitizer targets many out-of-bounds and use-after-free bugs. ThreadSanitizer targets data races, with platform and runtime limitations. MemorySanitizer targets uninitialized reads but requires compatible instrumented dependencies. Sanitizer support and commands depend on toolchain and target. Run representative integration tests, not only tiny unit tests.

Loom is an optional Rust crate for exploring concurrent operation interleavings conceptually. It substitutes modeled synchronization primitives and systematically schedules small scenarios. Keep models tiny because the state space grows explosively. Model ordering assumptions and failure cases, not production throughput. Loom cannot establish performance and does not model every operating-system behavior.

Tests do not prove performance. A benchmark that passes assertions does not prove all unsafe validity. A sanitizer-clean run does not cover paths it never executed. Use layered evidence because tools have different blind spots.

10. Invariants, Generations, and Stale Identifiers#

An invariant is a condition that must hold at every public boundary. Data-oriented structures often distribute one logical fact across several arrays. Write those relationships mathematically or in plain assertions.

For a sparse set, every dense entity has one matching dense component. Its sparse slot must point back to the same dense index. Every occupied sparse slot must point within dense bounds. Removal by swapping must repair the moved entity's sparse entry. Debug-only full checks can validate these rules after randomized operations.

Generational identifiers distinguish a reused slot from an old handle. An identifier commonly contains a slot index and generation counter. Lookup succeeds only when both the occupancy state and generation match. Increment the generation according to an explicitly documented overflow policy. Never let a stale identifier silently access a new occupant.

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Id {
    slot: u32,
    generation: u32,
}

fn is_live(id: Id, generations: &[u32], occupied: &[bool]) -> bool {
    let slot = id.slot as usize;
    occupied.get(slot).copied().unwrap_or(false)
        && generations.get(slot) == Some(&id.generation)
}

Test remove-then-reuse sequences directly. Keep old identifiers and attempt every operation through them. Test serialization boundaries so generations are not accidentally discarded. Test counter wrap behavior with a reduced-width model rather than billions of operations.

Schema migration changes persistent representation while preserving intended meaning. Version serialized data and define supported upgrade paths. Test old fixtures produced by released versions. Validate before converting and keep migration transactional when partial writes are dangerous. Never reinterpret raw persisted struct bytes after changing layout.

11. Deterministic Replay and Cross-Platform CI#

Deterministic replay records enough inputs to reproduce a failure. Record operation order, random seeds, logical time, configuration, and relevant responses. Avoid depending on wall-clock timestamps when a logical clock suffices. Normalize nondeterministic map iteration before comparing outputs. Version the replay format so old incidents remain useful.

Concurrency makes exact replay difficult because scheduler choices are inputs too. Capture high-level event ordering where practical. Use model checking for small ordering questions and stress tests for broader behavior. Do not promise deterministic replay if external services remain uncontrolled.

Cross-platform continuous integration exposes assumptions hidden by one development machine. Include major supported operating systems and architectures when resources allow. Test 32-bit targets if index narrowing or address size matters. Test endianness-sensitive serialization through portable fixtures. Test minimum supported Rust versions only if the project declares one.

Separate correctness CI from performance monitoring. Correctness should be deterministic enough to gate every merge. Performance on noisy runners may produce trends or alerts requiring confirmation. Use dedicated machines for sensitive regression gates when the cost is justified. Store compiler, hardware, and configuration metadata with each result.

12. Open-Source Integration Workflow#

Begin with an issue, trace, or profile tied to user pain. Do not arrive with a preferred layout and search for a reason to install it. Reproduce the hotspot at the current main commit. Ask whether maintainers can share representative workloads without private data.

Understand maintainers' constraints before changing code. Constraints include API stability, minimum compiler version, binary size, portability, and dependencies. They also include review capacity, contributor familiarity, and maintenance burden. A five-percent gain may not justify unsafe code in a rarely used path. Read contribution guidelines, prior discussions, and accepted benchmark practices.

Read data flow before editing layout. Trace creation, mutation, lookup, iteration, serialization, and destruction. Find ownership boundaries and extension points. Search for downstream assumptions about ordering and stable addresses. Map cold paths as well as the profiled hot path.

Create a baseline reproduction that maintainers can run. Reduce private traces to a deterministic generator where possible. Verify the baseline shows both the symptom and correct output. Attach commands and environment, not only screenshots. Confirm the benchmark itself does not dominate the measured operation.

Make the smallest semantic-preserving commit. Separate mechanical refactoring from behavior changes. Separate both from the performance change when practical. This lets reviewers identify which diff creates risk and which creates benefit. Avoid drive-by formatting that obscures ownership history.

Use the project's benchmark harness and naming conventions. Measure the supported feature set, not a stripped private build. Document processor, memory, operating system, compiler, power mode, and commit IDs. Describe scope: inputs, cache state, concurrency, and excluded setup. Provide raw artifacts or machine-readable summaries when appropriate.

Offer a feature and fallback plan when compatibility is uncertain. A feature flag can stage an implementation but creates testing obligations. A runtime fallback can preserve old hardware support but increases code paths. Prefer one robust implementation when the evidence does not justify variants. State removal criteria for temporary fallback code.

13. Worked Hypothetical Contribution#

Imagine an open-source telemetry processor with an issue about high ingestion latency. The issue includes a sanitized trace and reports allocation spikes under tag-heavy events. A release profile shows repeated linear searches in per-event tag vectors. Allocation samples also point to temporary lowercase strings during lookup. The contributor first builds the tagged-event generator already used by maintainers. They add no new benchmark framework. They confirm output equality against fixture files. They record event-size and tag-count distributions from the sanitized trace. They establish warm and rotating-data benchmark modes. Reading data flow reveals that tags preserve insertion order in serialized output. Several users also hold stable numeric tag positions through a plugin API. Replacing the vector with a hash map would silently break both assumptions. The contributor rejects that tempting redesign. The new hypothesis is narrower: cache normalized tag keys once at schema creation. Events then compare prevalidated identifiers instead of allocating lowercase strings. Unknown dynamic tags retain the old string fallback. The representation adds one identifier array owned by the immutable schema. Commit one extracts normalization into a named helper with unchanged behavior. Commit two adds differential tests across known and unknown tags. Commit three introduces cached identifiers and the fallback. Commit four extends the existing benchmark matrix. Each commit builds and explains one decision. The pull request describes the user metric and guardrail. It links the reproduction command and profile artifact. It reports no fabricated universal speedup. Instead it provides raw local samples and asks maintainers to confirm on their machine. It notes a small schema-memory increase and measures bytes per registered tag. A reviewer writes:

Review: Does normalization still handle non-ASCII keys exactly as before?
Response: Yes. Both paths call the extracted helper. I added old fixture cases
for composed and decomposed forms, plus differential generated strings.
Review: Why keep the fallback branch in the event loop?
Response: Plugins can introduce tags after schema creation. Removing fallback would
change the public contract. The benchmark matrix reports known-tag and mixed-tag cases.
Review: This unsafe indexed access appears unnecessary.
Response: Agreed. The checked access has no measured penalty in the project harness,
so I removed unsafe rather than asking maintainers to carry its proof obligation.
Review: Can the benchmark include serialization to reflect user latency?
Response: Added a separate end-to-end group. The lookup microbenchmark remains because
it tests the mechanism, while the end-to-end group tests the outcome.

After merge, a different architecture reports worse mixed-tag latency. The contributor requests its command, compiler, and raw samples. They reproduce using a mixed distribution that stresses fallback branches. The regression is real, so they restore the old lookup for highly dynamic schemas. They add that distribution to monitoring and document the dispatch rule. Ownership means responding after celebration, not merely landing a patch.

14. Review, Regression, and Maintenance Ownership#

A performance review should begin with semantic risk. Can ordering change? Can integer conversion truncate? Can stale identifiers become valid? Can panic, cancellation, or partial initialization violate invariants? Can serialization or public API behavior drift? Then review evidence quality. Is the workload connected to user behavior? Is setup separated correctly? Are release settings and commit IDs recorded? Are input distributions and cache conditions named? Are raw samples available? Is the observed effect larger than ordinary noise? Then review the mechanism. Does the profile show the changed code matters? Does a cost model predict the direction? Do counters support, rather than dictate, the explanation? Does generated-code inspection answer a specific unresolved question? Could a simpler change achieve the same outcome? Plan regression response before shipping. Define dashboards or benchmark alerts and an accountable owner. Prefer a clean revert when harm is urgent and diagnosis is incomplete. Preserve the failing workload as a test or benchmark. Write a short incident note distinguishing cause from contributing conditions. Maintenance ownership includes dependency updates, compiler changes, and hardware diversity. Delete obsolete specialized paths when their benefit disappears. Keep comments focused on enduring constraints and evidence. Do not freeze measured numbers into source comments without environment and date.

15. Debugging Playbook#

Step 1: state the failure in user-visible terms. Include what happened, what should happen, and the smallest known trigger. Classify it as correctness, latency, throughput, memory, availability, or several. Step 2: freeze evidence before changing code. Capture logs, replay inputs, profile data, versions, and machine state. Protect confidential information while retaining useful distributions. Step 3: reproduce under controlled conditions. Start with the production configuration and reduce one variable at a time. If reproduction fails, compare environment and workload rather than guessing. Step 4: check correctness invariants. Enable expensive debug validation around the suspected boundary. Compare with the reference implementation and replay operation prefixes. Step 5: classify resource symptoms. Check on-CPU activity, allocations, I/O waits, lock waits, working set, and branches. Choose one profiling tool that answers the next question. Step 6: bisect dimensions before commits. Vary input size, distribution, thread count, cache state, and feature flags. A threshold often points toward capacity, overflow, or contention. Step 7: write competing hypotheses. For each, state a predicted observation that differs from alternatives. Run the cheapest discriminating experiment first. Step 8: inspect the smallest relevant code path. Trace data ownership and lifecycle, not just the hottest function body. Check generated code only when source and profile leave a compiler question. Step 9: patch with a rollback path. Add a regression test or workload before changing behavior when feasible. Keep unrelated refactors out of the patch. Step 10: verify in layers. Run unit, differential, randomized, integration, and appropriate unsafe checks. Repeat performance measurements and inspect guardrails. Step 11: validate in a production-like canary. Watch tails, errors, memory, and workload shifts. Do not extrapolate one quiet interval into long-term safety. Step 12: preserve the lesson. Record the trigger, mechanism, fix, and monitoring gap. Remove temporary diagnostics and private captured data.

16. Production Readiness Checklist#

Outcome: the primary user or business metric is named. Outcome: correctness and resource guardrails are named. Workload: operations, distributions, sizes, and concurrency are documented. Workload: cold start and steady state are separated. Baseline: release configuration and commit identifier are recorded. Baseline: machine, compiler, operating system, and features are recorded. Profile: the relevant resource symptom was observed before redesign. Profile: flame-graph widths are interpreted as sample shares. Counters: cache and branch events are treated as clues, not conclusions. Model: Amdahl's unchanged fraction limits the expected outcome. Model: bytes and useful operations are estimated per work unit. Harness: setup and measured work boundaries match user semantics. Harness: output is consumed and correctness is checked. Harness: warmup and independent samples are included. Harness: realistic and adversarial distributions are represented. Harness: warm and cold-cache claims are accurately qualified. Harness: size and alignment matrices test the proposed mechanism. Statistics: throughput and relevant latency percentiles are reported. Statistics: uncertainty, noise, and effect size are discussed. Verification: an independent scalar or reference model exists where practical. Verification: generated operation sequences preserve failing seeds. Verification: structure invariants run in tests or debug mode. Verification: stale identifiers and generation reuse are tested. Verification: migrations use released fixtures and versioned formats. Unsafe: every unsafe block states validity obligations. Unsafe: Miri or sanitizers are used where applicable, with limits acknowledged. Concurrency: ordering assumptions have focused tests or a Loom model where justified. Replay: incidents can preserve deterministic inputs without secrets. CI: supported platforms and compiler policies are represented. Integration: refactor, semantic change, and optimization are separable. Integration: maintainers' compatibility and maintenance constraints are respected. Rollout: feature fallback, canary, and revert plans are documented. Ownership: an owner will inspect regressions and maintain specialized paths. Ethics: claims are bounded by measured hardware, workload, and dates.

17. Thirty-Day Learning Plan#

Day 1: choose one Rust loop and write its user outcome and guardrails. Artifact: a one-page measurement charter with a falsifiable decision. Day 2: define three realistic input distributions for that loop. Artifact: deterministic generators with documented seeds and assumptions. Day 3: build a standard-library timing harness in release mode. Artifact: source, exact command, and raw duration samples. Day 4: separate setup, warmup, measured work, and validation. Artifact: an annotated harness explaining every timing boundary. Day 5: measure empty, small, typical, and large inputs. Artifact: a size table and a paragraph explaining scaling shape. Day 6: collect a sampling profile of the typical workload. Artifact: a flame graph with three correctly interpreted observations. Day 7: classify CPU, allocation, I/O, lock, branch, and memory clues. Artifact: a symptom matrix marking evidence, uncertainty, and next experiment. Day 8: write an Amdahl breakdown from profile shares. Artifact: an upper-bound argument without promising a speedup. Day 9: create a bytes-per-work cost model. Artifact: a field-level table including indexes, padding, and writes. Day 10: compare warm repeated data with rotating oversized data. Artifact: raw samples and carefully qualified cache-state conclusions. Day 11: test sorted, skewed, and randomized input order. Artifact: one explanation linking distributions to branches or locality. Day 12: inspect assembly for one focused compiler question. Artifact: a short note quoting relevant instructions and avoiding performance claims. Day 13: inspect LLVM IR for the same function. Artifact: a source-to-IR map identifying loop and bounds behavior. Day 14: repeat measurements across fresh process launches. Artifact: a noise diary listing thermal, scheduler, and frequency controls. Day 15: implement a deliberately clear reference model. Artifact: tests showing its behavior at boundary cases. Day 16: implement differential generated-operation testing without dependencies. Artifact: a reproducible failing seed from an intentionally inserted bug. Day 17: minimize that failing operation sequence. Artifact: a compact regression test and a description of the invariant violated. Day 18: add full internal invariant checking in debug tests. Artifact: one checker relating every index structure to payload storage. Day 19: model slot reuse with generations. Artifact: stale-handle tests including reduced-width wrap policy. Day 20: run Miri on a focused unsafe or collection test. Artifact: a report stating coverage and explicit limitations. Day 21: design a sanitizer or concurrency-modeling plan. Artifact: commands or pseudocode plus the bug classes not covered. Day 22: select a real open-source performance issue. Artifact: an issue brief summarizing user pain and maintainer constraints. Day 23: trace the project's data flow end to end. Artifact: a diagram of creation, mutation, lookup, serialization, and destruction. Day 24: reproduce its baseline without changing implementation. Artifact: a script or documented command maintainers can run. Day 25: propose two competing hypotheses. Artifact: discriminating predictions and cheapest experiments for each. Day 26: draft the smallest semantic-preserving change. Artifact: a commit plan separating refactor, tests, behavior, and benchmarks. Day 27: conduct a mock review using the production checklist. Artifact: review comments covering semantics, evidence, fallback, and ownership. Day 28: prepare a rollback and regression-monitoring plan. Artifact: trigger thresholds, owner, canary scope, and revert command. Day 29: assemble a six-slide technical talk. Artifact: problem, workload, profile, model, verification, and limits slides. Day 30: publish a bounded case study. Artifact: a repository note with raw evidence, reproducibility, and next questions.

18. Mastery Ladder#

The beginner can distinguish a benchmark from a profile. They use release builds, black_box, and explicit timing boundaries. They avoid claiming causation from one duration. Promotion evidence is a reproducible harness reviewed by another person. The advanced beginner can classify likely resource symptoms. They read flame graphs, vary input distributions, and preserve raw samples. They understand throughput, p50, p95, and p99. Promotion evidence is a diagnosis confirmed by a discriminating experiment. The competent practitioner builds cost models before redesigning. They use Amdahl's law, bytes per work, and size matrices. They create reference models, differential tests, and invariant checkers. Promotion evidence is a semantic-preserving optimization with bounded claims. The proficient engineer connects local mechanisms to production outcomes. They handle noise, tail latency, portability, migration, and rollout. They choose Miri, sanitizers, fuzzing, or Loom according to risk. Promotion evidence is a safely operated change across multiple environments. The expert shapes systems and teams, not merely loops. They recognize when no optimization is needed. They make evidence cheap to collect and failures easy to replay. They teach tradeoffs, delete obsolete complexity, and own regressions. Expertise is demonstrated by durable judgment, not exotic syntax.

19. Substantial Exercises I: Measurement#

Exercise 1: Write a measurement charter for a batch image service. Include a user metric, business metric, correctness guardrail, and memory guardrail. Answer sketch: use completed valid images per cost-hour and p99 job latency. Reject “make conversion faster” because it lacks workload and decision boundaries. Exercise 2: Design workloads for a sparse component scan. Include occupancy, entity order, component size, and mutation frequency. Evaluation: the matrix must contain realistic, boundary, and adversarial cases. It must explain which production observation motivates each distribution. Exercise 3: Repair a harness that allocates input inside every timed iteration. Decide whether allocation belongs to the user operation before moving it. Answer sketch: provide separate core-loop and end-to-end benchmark groups. Validate identical outputs outside both timed regions. Exercise 4: Explain a wide flame-graph frame under a narrow caller. Answer sketch: width is aggregate sample share for stacks containing that frame. It does not show chronological duration or number of calls. Request enough samples and verify stack unwinding before acting. Exercise 5: A cache-miss counter rises after a change while runtime falls. Offer at least three explanations and one follow-up experiment each. Evaluation: answers must not call the change a regression from the counter alone. Consider fewer instructions, more parallelism, event normalization, and changed useful work. Exercise 6: Build an Amdahl model from measured stage shares. Do not calculate with invented times; use symbolic fractions from a supplied profile. Answer sketch: bound total gain by the changed fraction and include new overhead. State that stage shares can shift after optimization. Exercise 7: Make a bytes-per-work model for particle integration. Include position, velocity, optional acceleration, alive metadata, and write traffic. Evaluation: distinguish logical bytes from actual transferred bytes and padding. Identify which fields a structure-of-arrays scan can omit. Exercise 8: Design a warm/cold-cache comparison without claiming perfect flushing. Answer sketch: repeat one working set, then rotate through a larger backing set. Record working-set sizes and randomization seeds. Describe both as approximations and monitor page-fault differences. Exercise 9: Create an alignment and size matrix for a SIMD candidate. Include scalar tails and values around vector-width boundaries. Evaluation: all pointer construction must remain valid and aligned as required. The conclusion must be scoped to tested targets. Exercise 10: Interpret latency samples with a stable median and unstable p99. Propose collection and investigation steps without manufacturing certainty. Answer sketch: gather more independent tail observations and correlate pauses or queues. Report throughput alongside tails to detect hidden batching.

20. Substantial Exercises II: Verification#

Exercise 11: Write a reference model for a generational arena. Use a simple vector of optional values and explicit generations. Evaluation: clarity and externally equivalent semantics matter more than speed. Document generation overflow behavior. Exercise 12: Generate dependency-free operation sequences for that arena. Operations must include insert, get, mutate, remove, and stale get. Answer sketch: use a deterministic small generator and retain historical handles. Compare complete visible state after every short sequence. Exercise 13: Minimize a failing random sequence manually. Evaluation: repeatedly delete chunks, then simplify IDs and values. The final regression should fail for one understandable invariant violation. Preserve the original seed in an incident note. Exercise 14: Specify sparse-set invariants after swap removal. Answer sketch: dense lengths match; each dense entity maps back to its index. Every occupied sparse index lies in bounds and names the same entity. Check invariants after every generated mutation in debug tests. Exercise 15: Design wraparound tests for an eight-bit generation model. Evaluation: state whether exhausted slots retire, wider epochs intervene, or reuse risk remains. Do not silently declare wraparound impossible. Explain how the production-width policy relates to the reduced model. Exercise 16: Create a schema migration plan from row records to column arrays. Answer sketch: version formats, validate old fixtures, transform transactionally, and checksum output. Maintain ordering and unknown-field policy explicitly. Include rollback before destructive replacement. Exercise 17: Select Miri, a sanitizer, fuzzing, or Loom for four bugs. Use aliasing, native buffer overflow, parser panic, and atomic ordering as cases. Answer sketch: Miri, AddressSanitizer, fuzzing, and Loom are plausible primary choices. Explain overlap and every tool's coverage limits. Exercise 18: Design deterministic replay for a simulated scheduler. Record commands, logical ticks, seeds, and external responses. Evaluation: replay format is versioned and excludes secrets. State which real thread scheduling decisions remain unreproduced. Exercise 19: Build a cross-platform CI matrix for a serialization crate. Answer sketch: major supported systems, endian fixture tests, and declared Rust versions. Use performance jobs separately on controlled hardware. Explain cost-driven omissions honestly. Exercise 20: Review an unsafe unchecked-index optimization. Evaluation: demand a profile, benchmark, validity proof, and safe comparison. Reject unsafe if checked indexing has no relevant measured cost. State that passing tests cannot prove all validity obligations.

21. Substantial Exercises III: Integration and Leadership#

Exercise 21: Turn a vague open-source “slow” issue into a reproduction plan. Ask for workload shape, version, configuration, profile, and user impact. Evaluation: the plan protects private data and produces deterministic shareable inputs. It must establish correctness before timing. Exercise 22: Split a hypothetical 2,000-line optimization patch into commits. Answer sketch: mechanical extraction, baseline tests, representation change, and benchmark extension. Keep formatting separate and make each commit build where practical. Explain any unavoidable coupling. Exercise 23: Write review comments for a faster hash-based replacement. Challenge iteration order, stable references, denial-of-service behavior, and memory. Evaluation: comments ask questions and cite contracts rather than asserting taste. Request fallback or migration only where evidence supports it. Exercise 24: Document benchmark evidence for an open-source pull request. Include hardware, software, commits, commands, workload, raw samples, and limitations. Answer sketch: report no universal percentage and separate mechanism from outcome tests. Mention noise and guardrail results. Exercise 25: Plan response to a post-merge architecture-specific regression. Evaluation: collect a reproducible report, confirm, mitigate, preserve workload, and communicate. Prefer revert when user harm is ongoing. Assign maintenance ownership after the immediate fix. Exercise 26: Evaluate a resume claim saying “made the engine 10x faster.” Answer sketch: require operation, workload, baseline, hardware, commits, and correctness guardrails. Rewrite as a bounded claim supported by linked evidence. Remove the multiplier if it cannot be reproduced. Exercise 27: Design a feature/fallback plan for target-specific vectorization. Evaluation: cover detection, old hardware, CI, binary size, and deletion criteria. Compare against compiler autovectorization before accepting complexity. Specify semantic equivalence tests across paths. Exercise 28: Conduct a mock production readiness review. Assign participants to semantics, measurement, operations, and maintenance. Answer sketch: each role records blocking evidence and explicit accepted risks. The decision log includes owner and revisit date. Exercise 29: Prepare a seven-minute technical explanation of one optimization. Evaluation: begin with user pain, then workload, profile, model, change, verification, limits. Use one readable chart and one data-flow diagram. Reserve time for what would falsify the conclusion. Exercise 30: Decide not to optimize. Given a cold path, noisy tiny effect, and substantial unsafe complexity, write the decision. Answer sketch: retain the simple implementation and archive the reproducible evidence. Describe the workload change that would justify revisiting.

22. Portfolio and Capstone Projects#

Capstone A is a generational sparse-set library with an evidence notebook. Implement a clear reference and an optimized dense representation. Add generated differential tests, full invariants, stale-ID tests, and serialization fixtures. Benchmark scans, inserts, removals, and lookups across occupancy and size matrices. Profile one workload and connect a layout change to bytes per work. Deliver raw samples, commands, limitations, and a maintenance plan. Capstone B is a log analytics pipeline using columnar batches. Define throughput and p99 query latency under a realistic mixed workload. Compare row and column layouts without changing parser semantics. Include allocation, I/O, and warm/rotating-data profiles. Test schema evolution with fixtures and deterministic replay of malformed inputs. Deliver a decision explaining where columnar storage does and does not help. Capstone C is a small entity simulation with fixed frame deadlines. Model component bytes touched by movement, collision, and rendering extraction. Measure frame p50, p95, and p99 as entity count and occupancy change. Preserve deterministic seeds and state hashes for replay. Use a scalar collision reference to verify any batched implementation. Deliver a regression dashboard design and rollback thresholds. Capstone D is a contribution to an existing open-source Rust project. Begin from a maintainer-recognized issue and reproduce current behavior. Map data flow and public constraints before proposing representation changes. Submit the smallest reviewable semantic-preserving improvement. Use the project's tests and benchmark conventions. Deliver a retrospective including review changes and post-merge ownership. Assess every capstone on five dimensions. Correctness asks whether models, invariants, and boundaries are convincing. Measurement asks whether workload, raw evidence, and uncertainty are reproducible. Mechanism asks whether profiles and cost models explain the change. Integration asks whether compatibility, fallback, rollout, and maintenance are credible. Communication asks whether claims remain precise, ethical, and understandable.

23. Preparing a Technical Talk#

Start with one sentence describing audience and decision. An internal operations audience needs rollout implications. A Rust conference audience may need representation and validity details. Remove material that does not help that audience make the decision. Build the narrative around an evidence chain. Slide 1 names user pain and guardrails. Slide 2 defines workload and baseline environment. Slide 3 shows the profile and distinguishes observation from hypothesis. Slide 4 presents Amdahl or bytes-per-work reasoning. Slide 5 shows the smallest representation change with a data-flow diagram. Slide 6 explains reference models, invariants, and specialized checks. Slide 7 reports distributions, tails, noise, and limits. Slide 8 closes with rollout, ownership, and open questions. Use charts with units, sample counts, and environment labels. Do not truncate axes to exaggerate small effects. Do not animate a flame graph as though horizontal position were time. Show raw points when summaries could hide modes. Use color and text together so meaning survives color-vision differences. Prepare three levels of explanation. The thirty-second version states outcome, mechanism, evidence, and limit. The five-minute version adds workload and verification. The full version adds alternatives, failed hypotheses, and operational details. This layering improves both hallway answers and deep review. Rehearse hostile but fair questions. What work was excluded? How representative are inputs? Could correctness have changed? Why not use a simpler algorithm? What happens on another processor? What evidence would make you revert? Publish a reproducibility appendix when licensing and privacy allow. Link code, commit IDs, commands, raw measurements, and generated fixtures. Redact secrets and explain unavailable production data. A strong talk teaches the investigation, not merely the victory.

24. Ethical Evidence and Resume Claims#

Performance claims influence architecture, budgets, careers, and environmental cost. Treat them with the same care as correctness claims. Never choose only the best run and hide the distribution. Never compare your release build against another implementation's debug build. Never change semantics silently to win a benchmark. Bound every claim by operation, workload, environment, and baseline. Say “reduced allocations in tagged ingestion on the recorded workload” when that is known. Do not say “made Rust ingestion universally faster.” Include dates because compilers and dependencies evolve. Link evidence where confidentiality permits. Resume bullets should describe responsibility and verification. A credible format is action, scoped outcome, method, and evidence. For example, say you redesigned a hot index identified by sampling. Then state that project-harness measurements and differential tests supported deployment. Use a numeric result only if the underlying comparison remains available and honest. Credit collaborators, reviewers, and prior work. An optimization adopted from a paper remains valuable engineering when attributed. Do not imply sole ownership of a team result. Discuss regressions you found and repaired; that demonstrates maturity. Ethical reporting includes negative results. A layout that failed on mixed traffic can save others weeks of effort. Archive enough context to explain why it failed. Do not shame contributors for hypotheses disproved by good experiments. Reward accurate retraction and clean reverts.

25. Final Synthesis#

Mastery begins by refusing to optimize an undefined problem. Define the user outcome, business consequence, workload, and guardrails. Build the production artifact and preserve a reproducible baseline. Profile before selecting a representation. Distinguish CPU, allocation, I/O, lock, branch, and memory symptoms. Use sampling and flame graphs to locate important stack paths. Use Linux perf and hardware counters as observational instruments. Treat cache and branch counters as clues requiring controlled confirmation. Use Amdahl's law to respect unchanged work. Use bytes-per-work models to expose bandwidth and locality pressure. Design benchmark harnesses with warmup, setup separation, and realistic distributions. Report throughput and p50, p95, and p99 latency according to user needs. Discuss noise, uncertainty, and effect size without manufacturing benchmark numbers. Inspect assembly or LLVM IR only to answer a focused compiler question. Return from generated code to runtime evidence. Verify optimized representations against simple reference models. Generate operations, preserve seeds, minimize failures, and check invariants. Use fuzzing, Miri, sanitizers, and Loom for the bug classes they can address. State their limits plainly. Test generations, stale identifiers, schema migration, and deterministic replay. Run correctness across supported platforms while isolating noisy performance monitoring. In open source, understand constraints and data flow before editing layout. Reproduce the baseline, make the smallest semantic-preserving commits, and use project harnesses. Document hardware, scope, fallback, review decisions, and regression plans. Own the result after merge. The expert's product is not a fast benchmark. It is a trustworthy decision that survives new inputs, reviewers, machines, and time.

Part VII: The Art and Philosophy of Data-Oriented Design#

This part makes the reasoning behind the techniques explicit. By the end, you will be able to critique, teach, and extend DOD rather than merely repeat its patterns.

1. Programs, Data, and Disciplined Judgment#

A program transforms data. It receives observations, preserves some distinctions, discards others, and produces new observations. Even a program that seems to “manage customers” actually reads bytes, interprets them as facts, and emits bytes, pixels, requests, or actuator commands. This claim does not deny people, purposes, or domains. It gives design a concrete starting point: what information arrives, what must remain true, and what questions must become answers?

Data-oriented design, abbreviated DOD, chooses representations by examining the transformations and their costs. Representation means the concrete way facts are encoded: fields, tables, arrays, bit sets, indexes, handles, and ownership rules. A representation makes some questions cheap, some expensive, some obvious, and some nearly impossible to ask. Choosing it is therefore a choice about the program's practical vocabulary.

The art in this title is not mysticism, taste without evidence, or clever bit tricks. Art means disciplined judgment when goals conflict and evidence is incomplete. A designer balances latency, throughput, memory, correctness, change, team skill, debugging, and delivery time. No formula supplies every weight. Good judgment states assumptions, measures consequences, and keeps an affordable path to revision.

A useful first equation is deliberately plain: design quality equals fitness for a stated workload under stated constraints. A workload is the collection of operations the system actually performs, including how often, on how much data, and with what deadlines. A constraint is a limit such as memory, power, response time, compatibility, or engineer attention. Without workload and constraints, “fast” and “clean” are incomplete claims.

DOD is not an identity or a club. It is a lens. Use it when representation, scale, or repeated transformation matters enough to study. A tiny configuration script may need no special layout. A payroll rule may benefit more from clear domain types than packed arrays. Refusing needless DOD is itself data-oriented judgment because engineering time is a scarce quantity.

2. Observations Before Nouns#

Domain conversations naturally use nouns: Player, Invoice, Tree, Message. Nouns help people coordinate, but they can hide what was observed. “The player has a position” might mean a sampled controller estimate, an authoritative simulation coordinate, a rendered interpolation point, or a stale network report. These values share a noun and differ in source, time, certainty, and permitted use.

Treat data first as observations. An observation has a source, a time, a unit, a precision, and often an uncertainty. Saying “sensor 12 reported 21.4 degrees Celsius at tick 880, within 0.2 degrees” preserves more useful meaning than creating a generic Temperature object. The richer statement makes filtering, reconciliation, and error handling visible.

This does not require storing provenance beside every scalar. It requires deciding which distinctions matter. If the source never affects behavior, omit it. If late readings trigger corrections, time is essential. If two units can meet, encode the unit or normalize at a boundary. Representation begins by asking which lost distinction could change an answer.

Nouns remain useful summaries. A Customer record can be an excellent stable interface for business policy. The warning is against mistaking a grammatical noun for a natural memory unit. Shipping labels may need addresses in one pass, credit review may need balances in another, and analytics may need events by date. One “real-world object” does not dictate one physical layout.

Ask of every domain noun: which observations justify its existence, which transformations consume it, and which facts change together? If the answers differ across uses, keep the meaning but permit several representations. Stable meaning and replaceable representation can coexist when conversion boundaries are explicit.

3. Schema as Hypothesis, Layout as Ontology#

A schema names fields, types, relationships, and allowed states. It is a hypothesis about the distinctions future work will need. Like any hypothesis, it can be useful, falsified, or too broad to test. Calling a schema a hypothesis encourages migration plans and measurement; calling it reality encourages brittle certainty.

An ontology is an account of what kinds of things exist and how they relate. Layout becomes an operational ontology because allocated bytes declare what can exist cheaply. A dense array says that many values of one kind deserve contiguous space. An optional pointer says absence is expected. A bit set says existence can be reduced to membership in a bounded universe.

Consider health stored inside every entity record. That layout says health is a universal or near-universal property. A separate health table says health belongs only to members of a set. Neither statement is metaphysically true. Each is a useful ontology for particular queries, lifetimes, and densities.

Schemas also hide negative space. A table with died_at: Option<Tick> can express living and dead records together. Separate live and death-event tables express current membership and historical transition. The second design may make “iterate the living” cheaper while making “reconstruct one biography” require a join. The schema chooses which story is direct.

Do not demand that one schema serve every stage. Input schemas preserve external meaning. Working schemas support computation. Output schemas support consumers. Archival schemas preserve evidence. Conversion costs are real, but forcing one universal representation often charges every operation forever to avoid a visible boundary once.

4. Access Patterns Are Narratives#

An access pattern is the order and frequency with which code reads or writes data. It is also a narrative: first select active accounts, then read balances, then apply interest, then record changes. Writing that narrative before choosing structs reveals the working set, sequence, reuse, and boundaries.

Quantities give the narrative weight. “We update particles” is weak. “At 120 hertz, update positions and velocities for 200,000 live particles; render 40,000 visible particles; spawn 300; retire 250” is design evidence. Values say what exists now. Quantities say how much. Frequencies say how often. Change rates say how quickly membership or values churn.

Probabilities matter when paths differ. If 99.9 percent of messages are valid, optimize the valid scan while preserving a clear error path. If a branch is evenly split, a branchless or grouped representation might help. Probability is not permission to ignore rare correctness. It helps assign space, latency, and testing effort.

Narratives expose reuse. If acceleration is read once, velocity twice, and decorative metadata never during simulation, colocating all three may waste traffic. If every operation reads all fields together, splitting them may add indirection without benefit. “Structure of arrays is always faster” is therefore a slogan, not a design rule.

Record traces when possible. Count rows touched, bytes moved, allocations, cache misses, lock waits, and tail latency. A trace is not the whole truth: tomorrow's workload may differ, and instrumentation perturbs execution. It is still stronger evidence than a diagram built only from nouns.

5. Information, Entropy, and Compression#

Information is a distinction that can affect an answer. If a flag never changes any output or future decision, it carries no useful information for that program, though it may matter to another. This operational definition keeps philosophy tied to observable behavior.

Entropy is a measure of uncertainty before a value is known. A fair coin has more entropy than a flag that is almost always false. In simple terms, predictable data needs fewer bits to describe than unpredictable data. Entropy is not disorder, evil, or a synonym for randomness in casual speech.

Compression removes repeated description. Run-length encoding stores “false repeated 10,000 times” instead of 10,000 independent false values. A dictionary stores a common string once and refers to it by a small number. Normalization, indexes, batches, and shared defaults are also forms of avoiding repeated description, although their goals differ.

Compression can improve speed when fewer bytes move through memory, even if decoding costs instructions. It can also hurt random access, mutation, simplicity, and worst-case latency. The question is not whether compression is clever. It is whether saved bandwidth and space exceed decode and maintenance costs for the measured access pattern.

Information has semantic compression too. A type such as NonZeroU32 states an invariant once rather than checking zero at every use. A batch header states a timestamp once for many samples. Good designs share descriptions that truly are shared; bad designs force unlike cases under one description and recover exceptions with flags.

6. Existence, Membership, and Sparse Reality#

Existence in software is represented, not discovered. An entity “exists” because a slot is occupied, an identifier resolves, a row is present, or a membership bit is set. Different definitions support different questions. A tombstoned row exists historically but not operationally. A reserved handle may exist as an identity without having components.

Set membership is often the cleanest model for optional capability. Instead of asking whether every entity contains a nullable Velocity, define the moving set as entities with velocity rows. Iteration then visits members directly. This is especially valuable when the set is sparse, meaning only a small fraction of possible members are present.

Density is the fraction of possible members that are present. Dense sets favor bitmaps and arrays; sparse sets favor lists, hash tables, or sorted identifiers. Change rate matters too. A sorted vector is compact and searchable but costly under constant insertion. A hash set accepts churn but spends space and loses ordered traversal.

Absence has meanings that should not collapse accidentally: unknown, not applicable, not yet loaded, deleted, redacted, and truly zero are different observations. One nullable field may erase those distinctions. Sometimes that is correct compression. Sometimes it creates bugs that no layout benchmark will reveal.

Rust enums can make absence explicit. enum Reading { Missing, Pending, Value(f32), Fault(Code) } costs more than a sentinel float but states the cases. If millions of values make that cost material, split case tags from payloads or group cases. Begin with meaning, then optimize its representation without deleting required states.

7. Time and Lifetime Are Dimensions#

Time is not merely another field. It orders observations, determines validity, and creates versions. A current-state table answers “what is true now?” An event log answers “what changed?” A snapshot answers “what was believed at a chosen boundary?” These are different products of time.

Lifetime is the interval during which data is valid or needed. Temporary scratch values may live for one loop. Frame data lives until presentation. Session data survives requests. Reference data may survive deployments. Grouping data by lifetime can simplify allocation, cleanup, ownership, and reasoning.

Arena allocation reserves a region and frees many values together. It is excellent when lifetimes align and dangerous when one long-lived reference pins an entire region. The philosophical lesson is that shared lifetime is another shared description. Batch destruction is valid only if the members truly expire together.

Mutation is change through time. A mutable cell hides a sequence of states behind one address. An append-only log exposes the sequence but requires reconstruction. Neither is inherently honest. Choose based on questions: current response favors mutation; auditing and replay favor events; many systems deliberately keep both.

Rates of change guide separation. Cold data changes rarely; hot data changes often. Mixing them can rewrite, replicate, lock, or invalidate cold bytes whenever hot values move. Splitting by change rate can improve cache behavior and operational clarity, provided the join does not dominate the workload.

8. Identity Is Not Location#

Identity answers “is this the same logical thing?” Location answers “where are its bytes now?” A raw pointer often combines both answers. That is convenient until compaction, migration, replication, or deletion makes location unstable.

A handle separates identity from location. A common handle contains an index and a generation. The index selects a slot; the generation detects reuse. If slot 7 is deleted and reused, an old (7, 3) handle cannot silently name new (7, 4) data.

Stable identity has costs: lookup, metadata, failure cases, and policies for exhaustion. Do not add global IDs when a short lexical borrow is enough. Conversely, do not expose addresses as durable identity when storage must move. Stability should match the promised lifetime.

IDs also define equality. Is an imported customer with a new database key the same customer? The machine cannot answer without policy. Content hashes identify equal bytes, not necessarily equal people or events. Names identify according to a naming authority. Every identity scheme encodes a social or domain decision.

Location remains valuable. Dense slot indices make arrays and bit sets cheap. The design move is to expose stable meaning at boundaries while allowing replaceable location internally. A resolver, version check, or table join pays for that freedom explicitly.

9. Stable Meaning and Replaceable Representation#

An interface should stabilize promises, not accidents. “Iterate active orders in priority order” is a semantic promise. “Orders live in a Vec and indexes never change” is a representation promise. Promise the latter only when clients truly need it because every promise narrows future layouts.

Objects can provide excellent stable boundaries. An object may guard invariants, hide storage, coordinate side effects, and give callers a durable vocabulary. DOD does not require exposing parallel arrays to every module. It asks whether the object's internal representation and call pattern serve the workload.

A danger appears when a method boundary hides cost. world.entity(id).inventory().items() may perform several hash lookups and allocations while looking like field access. Good abstraction hides irrelevant mechanism but signals meaningful cost through names, iterators, borrowing, batch APIs, documentation, and types.

Versioned schemas make replacement explicit. A decoder converts old records into a canonical meaning; computation uses a current layout; an encoder writes a chosen version. This costs code and tests. It buys the ability to evolve evidence without pretending old bytes already mean the new thing.

Replaceability needs seams. A seam is a place where one representation can be exchanged for another. Useful seams align with phase boundaries, ownership changes, or external protocols. Too many seams produce conversion noise; too few produce a monolith. Their placement is an architectural judgment backed by expected change.

10. Transformations and Boundaries#

A transformation maps input data to output data. Parsing maps bytes to validated records. Selection maps records to a subset. Aggregation maps many values to summaries. Simulation maps one state and inputs to a next state. Naming these verbs often reveals design more clearly than naming managers and services.

A boundary is where representation, trust, owner, lifetime, or rate changes. Validate at untrusted boundaries. Convert units at unit boundaries. Compact at storage boundaries. Batch at transport boundaries. A good boundary makes a change explicit once instead of scattering adaptation through every consumer.

Boundaries are not automatically layers. A layer can become ceremonial forwarding with no semantic work. Keep a boundary when it enforces a policy, changes representation, owns a resource, or protects change. Remove it when it merely renames identical data and hides the path.

Pure functions, which return outputs determined only by inputs and have no hidden effects, make transformations easy to test and compose. Functional design therefore pairs well with DOD. Mutation can still be the right mechanism for large working sets. Isolate mutation and describe its before-and-after contract.

A pipeline makes sequence visible but can materialize too many intermediate collections. Fusion combines adjacent transformations into one pass. Fusion saves traffic and may reduce clarity or reuse. Keep the semantic steps named even if implementation fuses them, and verify that fusion changes no ordering, error, or precision rule.

11. Normalization and Denormalization#

Normalization stores a fact once and refers to it. In relational databases it reduces contradictory copies and clarifies dependencies. If a product name belongs to a product, order lines can store product IDs rather than repeated names. This supports consistent updates.

Denormalization stores derived or repeated facts near their use. An order may preserve the product name shown at purchase time because historical truth differs from the current catalog. A cached total may avoid summing thousands of lines on every read. Denormalization is not sloppy when its source, refresh rule, and failure behavior are explicit.

Every duplicate creates a consistency obligation. State which copy is authoritative, meaning accepted as the source of truth for a decision. State when derived copies update: synchronously, eventually, periodically, or on demand. State what readers may observe while copies disagree.

Normalization can over-centralize. A universal lookup table may turn a local calculation into random joins and make availability depend on one service. Denormalization can over-distribute. Copies can drift and migrations can become impossible to coordinate. Measure read-to-write ratios and assess the cost of stale answers.

The right unit is often a bounded snapshot. Copy exactly the facts needed to make an event self-explanatory, while keeping mutable reference data normalized. This is a semantic choice before it is a speed choice: decide whether a record describes what was known then or what is known now.

12. Locality as Geometry#

Locality means that data used near each other in time is placed near each other in an address space or storage hierarchy. Spatial locality concerns nearby addresses. Temporal locality concerns reusing the same data soon. Hardware rewards both through caches, pages, prefetchers, and block transfers.

Think of layout as geometry. A query traces a path through bytes. A dense array gives it a straight path. Pointer-linked nodes produce scattered jumps. Column storage gives one field a straight path and a whole-record query several parallel paths. Geometry turns “cache friendly” into a question about distance and route.

There are many geometries: CPU virtual memory, NUMA nodes, GPU memory, disks, network regions, compressed blocks, and database partitions. Improving one can harm another. Packing bytes tightly may complicate vector alignment. Co-locating writes may create cache-line contention between cores, called false sharing.

Locality is not merely physical adjacency. Logical locality groups values under one lock, transaction, permission, or failure domain. A data set can be physically close and operationally distant because every access requires synchronization. Cost models should include coordination as well as nanoseconds.

Do not freeze a design to one cache line size without evidence. Use broad principles—contiguous scans, bounded working sets, fewer transfers—then isolate machine-specific tuning. Hardware-aware is not hardware-captive. Benchmark on representative machines and retain a readable fallback.

13. Batching and Shared Description#

A batch applies one description to many values. One function call names an operation for a slice. One packet header describes many records. One lock acquisition protects many updates. One vector instruction describes several arithmetic lanes. Batching saves repeated control and metadata.

Batching also exposes quantity. update(&mut [Position], &[Velocity], dt) tells the caller that work scales with slice length. A per-object update() can hide the same loop behind dynamic dispatch and repeated calls. Neither syntax determines speed, but the batch form makes the shared transformation inspectable.

Batch size balances amortization and delay. Large batches spread setup cost but make early items wait, consume memory, and enlarge failure scope. Small batches respond quickly but repeat overhead. Choose with arrival rate, deadline, memory limit, and error policy, not with a universal magic number.

Items belong in one batch only when their description is truly shared. Mixing currencies under one unmarked arithmetic loop is wrong. Mixing exceptional rows can add branches that defeat the common path. Partitioning by state or operation can make both meaning and execution simpler.

A batch boundary is a proof boundary. Validate shape and units once, then let an inner loop rely on them. Rust slices prove contiguous extent and borrowing rules, but not equal lengths or matching IDs. A constructor can check those semantic invariants before creating a batch view.

14. Indexes Are Saved Answers#

An index is a saved partial answer to a future query. A map from email to user ID precomputes “which user has this email?” A sorted time column precomputes an order useful for ranges. A spatial grid precomputes approximate neighborhood. This framing prevents indexes from seeming free.

Every saved answer incurs maintenance debt. Inserts, deletes, and updates must keep it correct. Memory holds keys and links. Recovery must rebuild or restore it. Tests must compare it with authoritative data. A rarely used index may make every common write slower.

An index has a scope. It may be exact or approximate, current or delayed, complete or partial. A Bloom filter is a compact probabilistic membership index: it can say “possibly present” or “definitely absent,” with some false positives but no false negatives under its stated construction. Callers must understand that contract.

Index soup occurs when many ad hoc indexes overlap, no owner knows which query needs each one, and updates touch them all. Prevent it with an index inventory: query served, observed frequency, build cost, update cost, memory, freshness promise, and deletion criterion.

Sometimes recomputation is cheaper and safer. Scanning 500 contiguous rows may beat maintaining a hash map. The crossover depends on size and frequency. Prototype both. Delete saved answers when their questions disappear.

15. DOD as Empirical and Epistemic Practice#

Empirical means grounded in observation or experiment. Epistemic concerns what we know and how we know it. DOD is both when it starts from traces, forms layout hypotheses, predicts effects, measures results, and records the limits of each conclusion.

A performance claim is scoped knowledge. “Layout B is 1.8 times faster” must include operation, data size and distribution, machine, compiler, build mode, warm-up, sample count, statistic, and version. Without scope, the claim becomes folklore. With scope, another person can test whether it transfers.

Measurement has error. Clocks have resolution, operating systems interrupt, caches warm, branch predictors learn, and benchmarks accidentally omit real work. Report distributions or at least median and a tail percentile, not only the best run. Inspect generated work when surprising results matter.

A benchmark can answer the wrong question precisely. A tight loop over synthetic uniform data may not represent production skew, allocation, synchronization, parsing, or output. Use microbenchmarks to isolate mechanisms and end-to-end tests to verify relevance. Agreement between both is stronger evidence.

Knowledge expires. Workloads shift, compilers improve, hardware changes, and invariants grow. Keep the evidence next to the decision: a benchmark, trace, design note, and date. Revisit expensive complexity when its premise no longer holds.

16. Safety and Invariants as Proof#

An invariant is a statement that must remain true at a defined boundary. Examples include equal column lengths, unique live IDs, sorted timestamps, nonnegative balances, and references pointing only to matching generations. Safety comes from preserving the invariants required to interpret bytes correctly.

A proof need not be formal mathematics. It can be a Rust type that excludes invalid states, a constructor that validates once, a loop argument, a database constraint, or a property test over many generated cases. Strong designs state what establishes each invariant and what operations preserve it.

Rust memory safety proves important facts about references, aliasing, and lifetimes, but it does not prove domain truth. A u32 can still hold the wrong account ID. Two safe vectors can have mismatched lengths. DOD often separates related columns, so semantic checks become especially important.

Unsafe Rust asks the programmer to supply proofs the compiler cannot check. Keep unsafe code small, document preconditions, test edge cases, and expose a safe API. A speedup is not evidence of soundness. Undefined behavior means the language places no requirements on the result, including results that appear correct today.

Redundancy can aid proof. Storing a generation duplicates lifecycle information but detects stale handles. Storing a checksum detects corruption. The goal is not minimum bits at any cost; it is sufficient information to establish required claims with acceptable cost.

17. Readability Is a Resource#

Human attention is finite and expensive. Readability affects defect rate, review speed, onboarding, and willingness to change a layout. It belongs in the cost model beside bytes and cycles. Code that nobody can safely modify has severe maintenance latency.

Readable DOD names sets, units, phases, and invariants. active_particle_indices says more than dense. MetersPerSecond says more than f32. A short comment should explain why columns align or why an index exists, not narrate obvious syntax.

Parallel arrays become unreadable when position in one vector silently corresponds to position in several others. Wrap them in a table type, centralize row creation and removal, expose checked iterators, and test length agreement. Keep data-oriented internals without exporting accidental coupling.

Generic abstraction can be valuable. A well-designed table, arena, iterator, or query combinator can remove repeated correctness work while preserving cost visibility. Reject genericity only when it forces poor layout, unpredictable allocation, or obscure control flow. Concrete and generic are tools, not moral categories.

Diagrams and cost tables are executable understanding only when updated. Prefer small diagrams near the owning code and tests that assert structural promises. Delete misleading documentation. Readability includes the ability to see when the explanation and mechanism diverge.

18. Balance the Design Lenses#

Problem-oriented design begins with the task and user outcome. It prevents optimization of irrelevant machinery. Domain-driven design develops a shared language and protects business distinctions. Object-oriented design can bind state to behavior behind stable boundaries. Functional design clarifies transformations and controls effects.

Relational design treats facts as tuples in sets and derives answers through selection, projection, and joins. It offers deep tools for normalization, constraints, and query independence. Data-oriented design studies representation and access cost. These perspectives answer different questions and can inhabit one system.

A payment service might use domain types for money and authorization, objects for a gateway boundary, pure functions for fee rules, relational tables for durable facts, and columnar batches for reconciliation. Declaring one winner would discard useful reasoning. The architecture should reveal where each lens earns its cost.

Conflicts require explicit priority. A compact enum may weaken domain extensibility. A stable object API may prevent batch access. A normalized schema may miss a latency target. State the affected stakeholder and evidence, then adapt the boundary rather than arguing from school loyalty.

Not every program needs DOD. Small data, infrequent execution, dominant network waits, or rapidly changing requirements may make a straightforward model best. Start simple when failure is cheap. Introduce specialized representation where measured pain or a firm bound justifies it.

19. Failure Modes and Fair Counterpoints#

A DOD system can become a giant global database: every subsystem reaches shared tables, ownership disappears, tests require a whole world, and changes ripple everywhere. Data visibility is not permission for global mutation. Partition ownership, pass narrow views, and make phases explicit.

Schemas can become brittle when many algorithms depend on exact columns and ordering. Preserve semantic APIs, version persisted forms, and isolate layout-dependent kernels. A fast layout that cannot evolve may lose more time in migration than it saves in execution.

Index soup and premature machine coupling are related failures: both save answers before proving the questions. Hundreds of lookup structures or hand-coded SIMD paths create maintenance work. Keep an evidence threshold and deletion plan for each specialization.

Unreadable parallel arrays replace one object with positional folklore. If engineers cannot tell which indices align, the design has lost. Table wrappers, typed IDs, iterators, and invariant checks make relationships explicit without surrendering contiguous storage.

Objects deserve a fair counterpoint. They provide excellent stable boundaries when behavior and invariants belong together, especially around files, devices, transactions, and external services. The problem is not an object. It is assuming that one object graph must also be the optimal representation for every bulk transformation.

20. Counterfactual Laboratory#

Suppose memory were free but transfer still took time. We would stop caring about capacity, yet locality, bandwidth, initialization, backup, and human comprehension would remain. Duplication might save computation, but moving limitless data would still be costly. Free capacity does not make representation irrelevant.

Suppose computation were free but memory movement were not. We would recompute aggressively, compress richly, and avoid stored indexes whose maintenance moves bytes. Representation would become even more central because the scarce act would be fetching descriptions, not transforming them.

Suppose all data had the same size. Padding and variable-length allocation would vanish, but access frequency, relationships, lifetime, and ordering would remain. Arrays could still beat graphs for scans, and sparse membership could still beat universal rows. Size is only one axis.

Suppose there were no cache and every memory access had equal cost. Spatial locality would lose one hardware benefit, but fewer accesses, compact transfer to disks or networks, batch control, and understandable traversal would still matter. Some array-of-struct versus structure-of-arrays choices would become semantically neutral.

Suppose mutation were impossible. We would represent change as new values, persistent structures, or event streams. DOD would still choose chunk sizes, sharing, indexes, and traversal. Immutability removes in-place updates, not workload or representation.

Suppose a perfect compiler always found the fastest equivalent representation and transformation. We would focus on semantics and invariants, but must still tell it which outputs, timing, memory limits, identities, and failure behavior are equivalent. A perfect mechanism optimizer cannot invent policy.

Suppose bandwidth were infinite. Latency, synchronization, capacity, energy, contention, and correctness would remain. Remote data could move freely but coordinating simultaneous changes would still require ordering. Infinite bandwidth does not create one coherent truth.

Suppose IDs were never recycled. Generation counters for reuse could disappear, but deletion, authorization, unbounded identifier size, stale expectations, and mistaken cross-system identity would remain. Permanent names simplify one proof and complicate retention.

Suppose all queries were known forever. We could tailor layouts and indexes precisely, perhaps generating one representation per query family. Updates and storage would still trade off against reads. In reality queries evolve, so replaceability has option value.

Suppose hardware changed yearly. It already does in milder form. Isolate kernels, retain semantic tests, benchmark representative targets, and prefer transformations that map to several layouts. Freeze promises about meaning; keep mechanism negotiable.

21. Workshop One: Infer a Model from Work#

We begin without domain classes. Observation A: each frame reads position and velocity for 80,000 moving items. Observation B: only 6,000 items have names, read by an editor twice per second. Observation C: 2,000 items spawn and die per second. Observation D: collisions need a spatial neighborhood index rebuilt every frame.

The first hypothesis is separate dense motion columns, a sparse name table keyed by handle, and generation-checked slots. The spatial index is derived and replaceable. We do not place names in motion rows because the hot scan never reads them. We do not make the index authoritative because it is a saved answer to current positions.

Now challenge the hypothesis. Do position and velocity always travel together? Integration reads both and writes position; rendering reads only position. Two columns permit both scans, but two independent vectors risk length mismatch. A MotionTable owns both and exposes phase-specific borrowed views.

Spawn and death threaten dense order. Swap removal keeps arrays dense by moving the last row into the hole. Therefore identity cannot equal row location. Maintain slot_to_row, row_to_slot, and generation per slot. Assert that both mappings are inverses after every lifecycle operation.

The model is not finished until costs are estimated. Count bytes per motion row, index rebuild operations, name lookup frequency, and removal traffic. Prototype at realistic density and churn. If mapping overhead dominates, test stable holes plus a free list. Let evidence choose between two explicit hypotheses.

The lesson is method: observations become quantities; quantities suggest sets and phases; sets suggest layouts; layouts create invariants; invariants demand APIs and tests. No noun alone yielded the answer.

22. Workshop Two: A Tiny Runtime and Table#

Design a tiny runtime with three phases: ingest commands, simulate motion, and publish snapshots. Commands may spawn, accelerate, or remove entities. Simulation touches only live motion rows. Publication copies positions into an immutable snapshot so readers never observe half a phase.

The authoritative tables are slots and motion. A command queue is temporary input, and the published snapshot is derived output. Ownership follows phase order. This avoids locks inside the hot loop and makes the visible time boundary explicit.

A minimal layout can be pictured as follows.

Handle(index,generation)
        |
        v
slots:  [ generation | row? ]
                         |
                         v
rows:   position[] velocity[] row_to_slot[]
             |
             +--> immutable published_position[]

Insertion allocates a free slot or extends slots, appends every row column, and installs both mappings. Removal validates generation, swap-removes each column, repairs the moved slot mapping, clears the removed slot, and increments generation. All steps happen behind one mutable table borrow.

The runtime should not offer arbitrary mutation during simulation. It records structural commands and applies them at a phase boundary. That is deferred mutation: requests occur now, structural change occurs later. The delay is part of semantics and must be documented.

Adversarial tests remove the first, middle, and last rows; remove twice; use stale handles; spawn after deletion; issue conflicting commands; publish empty and full tables; and run random command sequences while comparing with a simple reference map.

23. Workshop Three: Rust API, Hidden Layout, Visible Cost#

The API should hide mapping arrays and preserve freedom to replace them. It should reveal bulk work, possible failure, and allocation. Types and names can communicate those costs without exposing bytes.

The next block is an interface sketch rather than a complete Rust implementation. Its semicolons intentionally show the promised operations while hiding their bodies. Part III develops the mappings and removal repair that those bodies must preserve.

#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct EntityId {
    slot: u32,
    generation: u32,
}

pub struct MotionTable {
    positions: Vec<[f32; 3]>,
    velocities: Vec<[f32; 3]>,
    row_to_slot: Vec<u32>,
    slots: Vec<Slot>,
    free_slots: Vec<u32>,
}

pub struct MotionView<'a> {
    pub positions: &'a [[f32; 3]],
    pub velocities: &'a [[f32; 3]],
}

impl MotionTable {
    pub fn view(&self) -> MotionView<'_>;
    pub fn reserve(&mut self, additional: usize);
    pub fn spawn(&mut self, p: [f32; 3], v: [f32; 3]) -> EntityId;
    pub fn remove(&mut self, id: EntityId) -> bool;
    pub fn row_of(&self, id: EntityId) -> Option<usize>;
}

view exposes slices because contiguous iteration is a useful promise for kernels. It does not expose row identity as stable. reserve lets callers move allocation outside a deadline. remove documents relocation. row_of names a lookup rather than pretending to return a field.

A safer integration method could borrow matching slices internally and use zip, which stops at the shorter slice. Because silent truncation would hide corruption, first assert equal lengths or construct the table so no external operation can separate them. Safety includes semantic completeness.

If callers need one entity occasionally, provide get(id). If they repeatedly call it inside a large loop, offer a batch query and profile both. An abstraction should make the good path available, not attempt to forbid every locally reasonable use.

24. Workshop Four: Reject Seductive Optimizations#

Proposal: pack positions into sixteen-bit integers immediately. Reject for now because required world range, precision, accumulation error, and conversion frequency are unknown. First measure bandwidth pressure and specify an error budget. Compactness without numerical meaning is corruption with good marketing.

Proposal: add hash indexes for every component combination. Reject because no observed query needs them and every structural change would maintain them. Build one index only after recording a repeated expensive question and compare against a dense scan.

Proposal: hand-write SIMD for integration. SIMD means one instruction operates on several lanes. Defer because the scalar loop is not yet a measured bottleneck and compiler vectorization has not been inspected. Keep columns aligned enough to leave the option open.

Proposal: sort rows by spatial cell every frame. Test rather than accept. It may improve collision locality but costs a permutation of several columns and destabilizes publication order. Compare rebuilding a separate cell index, sorting handles, and sorting authoritative rows under actual churn.

Proposal: replace all IDs with pointers for one fewer lookup. Reject because swap removal moves rows and snapshots cross phases. The optimization breaks identity promises. A pointer can be used inside a narrowly borrowed kernel if Rust proves the table cannot structurally change.

Proposal: combine all tables into one global world for easy queries. Reject because ease of arbitrary access destroys ownership and phase proofs. Add explicit query views instead. Convenience is a real value, but global mutability spends too much safety and evolution budget.

25. Workshop Five: Improve Through Evidence and Migration#

Imagine version one uses Vec<EntityRecord>. Production traces show simulation consumes 62 percent of frame time, with high cache misses; rendering consumes 12 percent; editor access is negligible. Hypothesis: separating motion fields reduces transferred bytes enough to lower simulation time by 25 percent.

Build a prototype converter and motion kernel, not a total rewrite. Feed captured distributions, including dead slots and exceptional entities. Compare optimized builds on two target machines. Use adversarial tests for NaNs, maximum counts, rapid churn, and deterministic replay.

Suppose the prototype lowers kernel time 35 percent but whole-frame time only 9 percent because publication now copies more. The hypothesis about the kernel is supported; the product claim needs revision. Measure whether double-buffered snapshots, chunked dirty copies, or accepting 9 percent has the best total cost.

Migration uses dual representation briefly. Keep the old record authoritative, derive the new table, and compare outputs. Then make the new table authoritative and derive compatibility views. Finally remove the old path after consumers migrate. Each phase has one declared authority to avoid split truth.

Rollout metrics include result mismatches, frame percentiles, allocation peaks, command backlog, and stale-handle failures. Keep a rollback path until representative load passes. Migration is part of design, not clerical work after the clever layout.

Document what would reverse the choice: much smaller entity counts, editor queries becoming dominant, or hardware with different transfer costs. A reversible conclusion is more honest and often more durable than a triumphant one.

26. Aesthetic Principles of Good DOD#

Good DOD has economy: each stored distinction earns its place, and each duplicate has an owner. Economy is not minimal byte count. It is absence of unexplained mechanism.

It has legible flow: data enters, changes representation at named boundaries, passes through phases, and leaves. A reader can point to authority and time. Hidden cycles and arbitrary callbacks weaken this quality.

It has proportion: common work receives straight paths; rare work remains correct without dominating the common representation. The design does not sacrifice an entire system for a five-line microbenchmark.

It has honest surfaces: expensive operations look expensive, invalid states have names, and machine-specific assumptions are visible. Beauty that depends on concealed cost is decoration.

It has rhythm: batches, phases, and lifetimes align so setup and cleanup occur at understandable intervals. This rhythm helps hardware and humans predict what happens next.

It has tension without confusion. Meaning may remain rich while representation is compact. Stable APIs may surround replaceable tables. Generic tools may support specialized kernels. Good design does not erase tradeoffs; it arranges them so they can be inspected.

It has an exit. Every index, cache, compressed form, and unsafe kernel has a way to be rebuilt, validated, or removed. Evolution is an aesthetic property because a design that can change preserves coherence over time.

27. Mental Models to Keep and Discard#

Keep: data is evidence encoded for a purpose. Discard: data structures are neutral containers. A container changes which evidence is easy to combine and which mistakes are easy to make.

Keep: a layout is a wager on future questions. Discard: there is one natural in-memory image of the domain. Domains supply meaning; workloads and machines influence physical form.

Keep: hot paths are stories with quantities. Discard: one impressive operation per second is a hot path. Frequency multiplied by cost and deadline determines importance.

Keep: an index is a maintained answer. Discard: lookup is free after an index exists. Writes, memory, recovery, and staleness pay the bill.

Keep: boundaries convert meaning and establish proof. Discard: more abstraction layers always improve architecture. Boundaries without policy become fog.

Keep: types can carry proof. Discard: type safety proves the business is correct. Units, identities, and lifecycle rules still need semantic design.

Keep: contiguous data often gives simple geometry. Discard: structure of arrays always wins. Fields used together, mutation patterns, and data size can favor other layouts.

Keep: measurement narrows uncertainty. Discard: a benchmark is universal truth. Its result belongs to its scope.

Keep: readability consumes and restores human capacity. Discard: comments make any clever layout maintainable. Prefer mechanisms whose invariants can be locally checked.

Keep: evolution is another workload. Discard: migration can be designed later. Persisted bytes and public IDs become long-lived promises quickly.

28. Philosophical Glossary#

Abstraction: a chosen omission of detail. A good abstraction omits mechanism irrelevant to callers while preserving costs and distinctions they need.

Authority: the representation accepted as decisive when copies disagree. Authority is a policy, not necessarily the oldest or most central table.

Composition: building a larger transformation from smaller transformations whose contracts fit. Cheap composition depends on compatible representations and explicit boundaries.

Constraint: a limit the design must respect, such as memory, time, precision, law, or available attention.

Cost model: an explicit estimate of resources used by an operation. It may count bytes, instructions, allocations, locks, network trips, or engineer work.

Evidence: observations that can support or challenge a claim. Traces, benchmarks, incidents, proofs, and user requirements are different kinds of evidence.

Invariant: a statement required to stay true at a named boundary. Invariants let code interpret compact representation safely.

Mechanism: the process that produces an effect, such as hashing, scanning, sorting, borrowing, or copying.

Meaning: the distinctions a value is intended to preserve for decisions. Meaning comes from contracts and use, not bits alone.

Ontology: a model of what kinds of things exist and relate. A layout acts as an ontology by making some entities and relations direct.

Representation: a concrete encoding of meaning in data structures, bytes, and relationships.

Schema: a declared structure and set of constraints for data. It is a testable hypothesis about needed distinctions.

Workload: operations together with sizes, distributions, frequencies, order, and deadlines. A list of features is not yet a workload.

Locality: closeness of related accesses in time, address, or operational domain. It reduces transfer and coordination when aligned with work.

Entropy: uncertainty in a value before observation. Lower uncertainty often permits a shorter description.

Normalization: storing a fact once under clear dependencies. Denormalization intentionally stores copies or derived answers for another goal.

Identity: the rule by which two references are judged to denote the same logical thing. Identity need not equal address or contents.

Proof: a justified argument that a claim follows under assumptions. Types, tests, checks, and mathematics provide proofs of different strength.

29. Socratic and Adversarial Questions#

Question: “Isn't everything data, making DOD meaningless?” Answer: the useful claim is not the vocabulary but the method: quantify transformations and choose representation around observed access. A lens can be broad and still produce specific tests.

Question: “Why not trust the compiler?” Answer: trust it to optimize within semantics it can see. It usually cannot change public identity, storage contracts, network schemas, ownership, or acceptable precision. Inspect before doing its job manually.

Question: “Does exposing slices leak layout?” Answer: yes, intentionally, if contiguous bulk access is a stable useful promise. Expose an iterator or query view when replacement matters more. Leakage is a tradeoff, not automatically a defect.

Question: “Can an object be data-oriented?” Answer: yes. An object can own a columnar table and offer batch methods. DOD concerns decisions and costs, not syntax.

Question: “Why preserve rare states if they slow the common path?” Answer: correctness requirements define whether they may be discarded. Partitioning can keep rare states out of a hot loop without pretending they do not exist.

Question: “Is a cache just denormalization?” Answer: it is a derived copy with a reuse policy, so often yes. The term cache emphasizes eviction and recomputation; denormalization emphasizes schema duplication. Both need authority and freshness rules.

Question: “What if measurement is too expensive?” Answer: use bounded estimates, counters, representative samples, and reversible decisions. Lack of perfect data is not license for unscoped certainty.

Question: “Should every cost appear in a type?” Answer: no. Types can become unusable. Signal major semantic costs through API shape and names, and document measured constants. Judgment chooses the resolution.

Question: “Are relational databases already DOD?” Answer: they embody strong data-centered ideas and sophisticated physical planning. DOD adds a general workload-and-representation lens across memory, devices, and application code. Neither label owns the truths.

Question: “When is elegance evidence?” Answer: elegance can suggest fewer invariants and easier proof, but it does not establish throughput or correctness. Treat taste as a hypothesis generator, then test consequences.

30. Exercises That Require Arguments#

Exercise 1: A million devices report temperature once a minute; one percent report ten times per second during alarms. Propose layouts for ingest, current state, and history. Argue from frequency, lifetime, compression, and late arrival. State what evidence could overturn your choice.

Exercise 2: Compare nullable fields, a tagged enum, and sparse component tables for optional medical observations. Discuss meanings of absence and safety before memory. Then estimate density at which each layout becomes attractive.

Exercise 3: Design identity for documents that move between offline devices and a server. Explain collision, deletion, merge, privacy, and recycling. Reject at least one simpler identity scheme with a concrete failure.

Exercise 4: Given a read-heavy catalog and an update-heavy inventory, choose normalization boundaries. Define authority and stale-read policy. Explain which snapshot should preserve historical product descriptions.

Exercise 5: An index saves 4 milliseconds on a query run hourly but adds 20 microseconds to 10,000 writes per second. Calculate daily costs, then include user deadline and recovery complexity. Decide with an argument, not arithmetic alone.

Exercise 6: Rewrite an object-per-particle design as a table, then defend keeping one object boundary around the table. Identify what layout remains hidden and what cost remains visible.

Exercise 7: A benchmark improves by 3 percent with large variance. Specify sample size, statistics, machines, and an acceptance threshold. Explain why shipping or rejecting it is rational.

Exercise 8: Build an invariant inventory for swap removal. For each invariant, name the operation that establishes it, operations that preserve it, and an adversarial test.

Exercise 9: Choose a batch size for network inference given arrival rate, a 20-millisecond deadline, and limited memory. Draw the queueing narrative and discuss tail latency.

Exercise 10: Critique a system with thirty parallel vectors and raw integer IDs. Preserve its locality while improving readability and proof. Estimate added overhead.

Exercise 11: Argue whether an event log or mutable table should be authoritative for a game match. Include replay, live latency, cheating disputes, and storage.

Exercise 12: Hardware will move from CPU to GPU next year. Identify semantic APIs that can survive, layouts likely to change, and evidence needed before coupling to GPU constraints.

31. A Stage Talk for Thousands, Without Hype#

Minute 0–5, open with one transformation: update many positions. Show object records and columns, but do not announce a winner. Ask which fields the loop reads. The audience discovers that representation follows a question.

Minute 5–12, add quantities, frequency, and a cache diagram. Define locality in plain language as shortening the path through needed bytes. Run or show a reproducible benchmark with scope printed on the slide.

Minute 12–20, break the easy story. Add editor names, sparse health, spawn churn, and stable IDs. Show that a fastest loop can create broken identity and unreadable arrays. Introduce table ownership and generation handles.

Minute 20–28, connect to meaning. Present observations versus nouns, absence cases, units, and time. Explain schema as a hypothesis. This prevents the talk becoming a hardware trick demonstration.

Minute 28–35, compare lenses fairly. Use one payment example with domain types, an object boundary, pure rules, relational storage, and a batch reconciler. The point is cooperation, not conquest.

Minute 35–42, conduct the counterfactuals: free computation, no cache, and perfect compiler. Invite predictions before answers. The exercise isolates which principles depend on which constraints.

Minute 42–50, show the empirical loop: trace, hypothesis, prototype, adversarial test, scoped benchmark, migration, and rollback. Include a failed optimization. Trust grows when evidence can say no.

Minute 50–56, cover safety and readability. Display an invariant table and a Rust API with batch views. Say explicitly that safe Rust does not prove matching column meaning.

Minute 56–60, close with seven words on one slide: meaning, measurement, representation, mechanism, proof, evidence, evolution. Give the audience questions to take to Monday's code, not a demand to rewrite it.

Avoid claims that DOD makes software “blazingly fast,” that objects are dead, or that one cache diagram explains every machine. Publish code, input, compiler flags, and negative results. A talk teaches judgment by showing uncertainty handled well.

32. Further Reading and Historical Placement#

Mike Acton's 2014 CppCon talk, “Data-Oriented Design and C++,” is a durable historical statement of the modern DOD movement. It is valuable for its insistence on knowing data and hardware. Its rhetoric and examples are framing, not timeless proof; retest claims on current tools and workloads.

Richard Fabian's Data-Oriented Design develops practical transformations, layouts, and software architecture from a DOD perspective. Read it as a rich design vocabulary. No book can supply measurements for a particular application.

Scott Meyers's 2014 talk “CPU Caches and Why You Care” and Ulrich Drepper's “What Every Programmer Should Know About Memory” explain memory hierarchy historically. Details age; the method of understanding transfer costs remains useful. Consult current vendor manuals for current machines.

Martin Thompson's Mechanical Sympathy writings connect hardware behavior and software design. The phrase means designing with mechanisms rather than against them. Examples are evidence from contexts, not laws that overrule local benchmarks.

The Rust Reference and The Rustonomicon are primary durable sources for Rust semantics and unsafe obligations. They establish language rules, not domain invariants or performance guarantees.

Database literature on relational algebra, normalization, indexes, column stores, and query optimization predates the DOD label and supplies essential theory. C. J. Date is a durable relational source; research on MonetDB and C-Store explains column-oriented tradeoffs. Historical priority does not make every old mechanism optimal.

Leslie Lamport's work on time and ordering in distributed systems, especially “Time, Clocks, and the Ordering of Events in a Distributed System,” clarifies that observed order requires rules. It is foundational reasoning, not a ready-made application schema.

Claude Shannon's “A Mathematical Theory of Communication” defines information entropy precisely. This chapter used only a plain operational introduction. Do not borrow entropy as a decorative synonym for mess.

John Ousterhout's A Philosophy of Software Design and works on domain-driven, functional, and object-oriented design offer complementary lenses. Read opposing schools to discover hidden assumptions. Their examples are arguments to examine, not votes in a winner-take-all contest.

33. Conclusion: One Discipline, Seven Commitments#

Meaning asks which distinctions matter and to whom. Without meaning, optimized bytes can produce the wrong answer faster. Begin with observations, units, identity, absence, time, and authority.

Measurement gives scale to meaning. Quantities, frequencies, probabilities, and change rates turn feature names into workloads. Measurements are imperfect, so preserve their scope and error.

Representation chooses which questions become cheap, visible, and composable. Arrays, tables, enums, logs, indexes, and compressed blocks are arguments about expected use. Layout is an ontology, but a revisable one.

Mechanism explains how the cost occurs. Cache lines, vector lanes, locks, allocators, network trips, and maintenance writes are mechanisms rather than magic words. Understanding them permits prediction; experiments correct prediction.

Proof protects interpretation. Types, constructors, ownership, constraints, assertions, property tests, and carefully bounded unsafe code establish invariants at different strengths. Performance without valid meaning is failure.

Evidence disciplines confidence. Traces, prototypes, benchmarks, incidents, and adversarial tests support scoped claims. A negative result saves complexity. A result without context should not harden into folklore.

Evolution treats tomorrow as part of the workload. Stable meaning, replaceable representation, versioned boundaries, migrations, deletion plans, and readable code preserve the option to learn.

The art of data-oriented design is the practiced movement among these commitments. It is neither worship of data nor hostility to objects. It is disciplined judgment under constraints: observe the work, preserve the meaning, shape the representation, expose the cost, prove the invariants, test the claim, and leave the system able to change.

34. Design Review Cards#

Card 1: Meaning#

What decision changes if this field changes? If none can be named, why store it? Separate “unknown” from “empty” whenever a later action differs.

Card 2: Quantity#

How many values exist at median, peak, and hard limit? A design for median load may fail exactly when the system is most valuable.

Card 3: Frequency#

Which operations repeat per item, frame, request, or day? Multiply frequency by cost before celebrating a locally expensive rare path.

Card 4: Probability#

What distribution drives branches, compression, and index selectivity? Test skew and adversarial concentration, not only uniform random input.

Card 5: Change rate#

Which values and memberships churn? Separate hot updates from cold facts when the join is cheaper than moving or locking cold bytes.

Card 6: Time#

Is the value current state, an event, or a belief at a past boundary? Never update historical truth with a current lookup by accident.

Card 7: Identity#

What makes two references the same, and for how long? State reuse, deletion, collision, and cross-system policies before choosing integer width.

Card 8: Authority#

When copies disagree, which wins, and how is disagreement detected? “Eventually consistent” names a timing model, not a resolution policy.

Card 9: Geometry#

Draw the byte path of the common query. Count unrelated bytes, jumps, transfers, locks, and conversions rather than merely naming a cache.

Card 10: Batch#

Which description is shared by every member? Choose batch limits from deadline and failure scope as well as throughput.

Card 11: Index#

Name the exact saved question, its frequency, and update tax. Include a date or metric that would justify deleting the index.

Card 12: Boundary#

What changes here: trust, owner, lifetime, representation, unit, or rate? If nothing changes, the boundary may be ceremony.

Card 13: Invariant#

Write the statement in a testable form. Name who establishes it and list every operation allowed to threaten it.

Card 14: Evidence#

Could another engineer reproduce this claim? Preserve data distribution, machine, compiler, flags, statistic, and end-to-end consequence.

Card 15: Readability#

Can a reviewer trace one row through creation, movement, lookup, and deletion? If not, improve names and ownership before adding speed.

Card 16: Evolution#

How would this schema migrate under live traffic? A design with no route from old bytes to new meaning is incomplete.

35. Final Audit Checklist#

1. List every authoritative table and the decision for which it is

authoritative.

1. List every derived copy and its freshness, rebuild, validation, and

deletion rule.

1. Write units beside every physical quantity and conversion beside every

boundary.

1. Record peak count, ordinary count, and growth assumption for every major

set.

1. Record operation frequency and deadline rather than calling code simply

hot.

1. State whether IDs survive deletion, restart, replication, export, and

migration.

1. Test empty, singleton, maximum, sparse, dense, skewed, and rapidly

changing data.

1. Compare a specialized representation with the simplest correct baseline.

1. Include conversion and maintenance work in every end-to-end performance

claim.

1. Inspect whether a generic abstraction allocates, dispatches, copies, or

obscures order.

1. Keep unsafe code behind one safe boundary with documented proof

obligations.

1. Explain every parallel array relationship in one owning type and

invariant test.

1. Name each index by the question it saves rather than the structure it

uses.

1. Put machine-specific constants behind a seam and benchmark every

supported target.

1. Preserve a migration path before persisted data or public callers depend

on layout.

1. Ask whether removing an optimization improves total engineering

throughput.

1. Ask whether an object boundary protects meaning even when storage

becomes columnar.

1. Ask whether normalization prevents contradiction or merely forces

repeated joins.

1. Ask whether denormalization preserves historical meaning or creates

accidental copies.

1. Ask whether batching increases waiting beyond the user-visible latency

budget.

1. Ask whether locality improved in CPU memory while worsening network or

lock geometry.

1. Ask whether compression preserves random access and numerical error

requirements.

1. Ask whether benchmark inputs contain production skew, churn, and

exceptional states.

1. Publish failed hypotheses so future engineers do not repeat unsupported

optimizations.

1. Date every workload assumption likely to change as products or hardware

evolve.