Computer Science from First Principles

Interactive foundations for high-performance, low-latency systems.

Data structures Version 1.0Current part Algorithms

Low latency is not one trick. It emerges from choices made across algorithms, memory layout, scheduling, synchronization, networking, measurement, and the application itself.

This book builds those ideas from the ground up. Each chapter begins with a concrete problem and an interactive model, establishes a language-independent invariant, and then uses straightforward Rust to make the costs explicit. It assumes you can read basic Rust without making Rust syntax the subject.

Every field note answers the same questions:

• What problem does this idea solve?
• What is the smallest complete example?
• What mental model predicts its behavior?
• Which costs become visible on real machines?
• When should you choose something else?

Start with VecDeque when work must enter and leave a collection in order, continue to binary search to see how an invariant becomes an algorithm, or browse the curriculum to see the path toward complete low-latency systems.

Curriculum

The destination is the ability to reason about a complete low-latency system: from the shape of an algorithm, through cache lines and scheduler behavior, to packets, latency distributions, risk checks, and production failure modes.

This is not a survey of every computer-science topic. Material earns a place when it helps explain, construct, or measure high-performance systems. HFT is a later application of those foundations, not required context for learning them.

The concepts are language-independent. Rust is the primary reference language because it makes ownership, memory, and concurrency decisions visible. Modern C++ is a first-class implementation track where its object model, allocators, atomics, compiler toolchain, and low-latency ecosystem teach something distinct.

The book will not mechanically translate every listing. An experiment appears in both languages when the comparison exposes a real tradeoff: layout, lifetime, allocation, abstraction cost, synchronization, generated code, or tooling.

Part I — Data structures

Status: version 1.0 complete.

Sequences, queues, maps, sets, trees, graphs, heaps, arenas, probabilistic membership, rolling windows, fixed-capacity buffers, and choosing among them.

These chapters establish the vocabulary used throughout the rest of the book.

Part II — Essential algorithms

Status: in progress.

• Binary search and boundary finding
• Sorting, selection, and top-k problems
• Linear scans, two pointers, and sliding windows
• Prefix aggregates and incremental computation
• Graph traversal and dependency ordering
• Greedy scheduling and queueing decisions
• Streaming and online algorithms
• Parsing and state machines

The goal is not broad interview-problem coverage. It is to identify invariants, prove that progress occurs, and connect asymptotic analysis with actual memory access and data movement.

Part III — The machine

• Integer and floating-point representation
• Virtual memory, pages, and translation lookaside buffers
• Cache lines, cache hierarchy, and locality
• Branch prediction and speculative execution
• Data-oriented layouts
• SIMD and vectorization
• Allocation, fragmentation, pools, and arenas
• NUMA topology and memory placement
• Hardware clocks and timestamp counters

This part explains why two programs with the same big-O complexity can have very different latency.

Part IV — Operating systems and execution

• Processes, threads, privilege levels, and system calls
• Scheduling, preemption, context switches, and jitter
• CPU affinity, CPU pinning, and isolation
• Page faults, memory locking, and huge pages
• Signals, timers, and clock sources
• Files, memory mapping, and asynchronous I/O
• Interrupts, polling, and busy waiting

The objective is to understand what the operating system can do between the start and end timestamps of an otherwise small operation.

Part V — Concurrency

• Threads, ownership transfer, and shared state
• Mutexes, reader-writer locks, and condition variables
• Atomics and memory ordering
• False sharing and cache coherence
• Bounded queues and backpressure
• Lock-free single-producer/single-consumer rings
• The LMAX Disruptor and sequence-gated pipelines
• Multi-producer algorithms and contention
• Read-copy-update, epochs, and reclamation
• Async runtimes versus dedicated threads

Correctness comes first; predictability and throughput follow from measuring the resulting contention and coordination.

Part VI — Networking and I/O

• Ethernet, IP, UDP, TCP, and multicast
• Socket buffers, batching, and packet timestamps
• NIC queues, receive-side scaling, and flow steering
• Interrupt moderation and busy polling
• Zero-copy techniques
• io_uring, AF_XDP, and kernel-bypass architectures
• DPDK-style poll-mode processing
• Protocol parsing and sequence recovery

The emphasis is the complete path from a byte on the wire to application state, including where copies, queues, interrupts, and scheduling enter that path.

Part VII — Latency measurement and performance engineering

• Throughput versus latency
• Latency distributions, percentiles, and tail behavior
• Histograms and coordinated omission
• Warm-up, cache state, and benchmark design
• Profiling CPU, allocation, locks, and I/O
• Jitter budgets and critical-path analysis
• Load generation, replay, and deterministic tests
• Capacity, overload behavior, and graceful degradation

Averages are rarely enough. This part teaches how to produce measurements that remain meaningful when the system is busy or occasionally slow.

Applied track — High-performance C++

• Cost models, value categories, RAII, and object lifetime
• Object layout, containers, iterators, and invalidation
• Allocation, std::pmr, arenas, and object pools
• Templates, inlining, generated code, and instruction-cache cost
• Atomics and the C++ memory model
• Build modes, sanitizers, compiler inspection, and benchmarking

This is an applied track, not a second introductory programming course. It uses the machine, operating-system, concurrency, and measurement models established above to explain how high-performance C++ actually behaves.

Part VIII — Storage and database internals

• Pages, B-trees, log-structured storage, and write-ahead logs
• Buffer pools and caching
• Transactions, isolation, and recovery
• Columnar layouts, compression, and vectorized execution
• Time-series storage and append-only logs
• Index design and query execution

Storage systems provide durable examples of the same locality, batching, contention, and recovery tradeoffs found in trading infrastructure.

Part IX — Market and trading systems

• Market data, feeds, sequence numbers, and gap recovery
• Limit order books and price-time priority
• Matching engines and deterministic replay
• Order gateways, acknowledgements, and state machines
• Pre-trade risk checks and kill switches
• Position, P&L, and exposure tracking
• Simulation, backtesting, and avoiding look-ahead bias
• Clock synchronization and latency attribution
• Failure recovery and operational controls

Finance appears here as an application of the earlier foundations rather than a collection of unexplained low-latency tricks.

Chapter rule

A topic graduates into the book only when it has a concrete motivating problem, an interactive model where motion clarifies the idea, a predictive invariant, a straightforward reference implementation, honest alternatives, sharp edges, and a focused exercise.

Performance Systems Reading Map

Purpose Sources and laboratoriesScope CPU to NIC

This book is the curriculum and experiment notebook. It should not pretend to replace processor manuals, kernel documentation, language standards, or the people who developed the tools being studied.

Use four kinds of material differently:

Pin the version or commit used in an experiment. Record the CPU, kernel, compiler, flags, NIC, driver, firmware, topology, power policy, and relevant operating-system configuration. “Faster” without that context is not a reusable finding.

If you are buying books

The strongest first purchases for this curriculum are:

1. Systems Performance, second edition, for a disciplined whole-system method.
2. Understanding Software Dynamics, for explaining intermittent delay, queues, waiting, and long-tail latency with low-overhead tracing.
3. The Art of Writing Efficient Programs, for hardware-aware measurement and optimization through C++ experiments.

Then buy according to the layer you are actively studying:

• C++ concurrency: C++ Concurrency in Action, second edition.
• Linux APIs: The Linux Programming Interface.
• Production observability: BPF Performance Tools.
• Deep processor architecture: Computer Architecture: A Quantitative Approach, seventh edition.

Two books are unusually direct about low-latency trading systems:

• Building Low Latency Applications with C++
• Developing High-Frequency Trading Systems

Use those as architecture tours and implementation prompts, not as the final authority for processor behavior, Linux APIs, venue semantics, or benchmark claims. They connect the layers conveniently; the specialist books and current official documentation establish the details.

A deliberate reading order

1. Learn the modern CPU cost model

Start with Denis Bakhvalov’s open Performance Analysis and Tuning on Modern CPUs. Pair each concept with an exercise from Perf-Ninja: caches, branches, vectorization, memory-level parallelism, and hardware counters become useful only after you predict and measure them.

Agner Fog’s Optimizing software in C++ is a dense reference for compiler behavior and low-level C++ optimization. Treat its advice as hypotheses to verify on the compilers and processors named in your own report.

2. Learn whole-system performance

Brendan Gregg’s Systems Performance, second edition provides the broader method: workloads, CPUs, memory, filesystems, networking, profiling, tracing, and latency outliers. Its most durable lesson is to form a system model before reaching for a favorite tool.

Use BPF Performance Tools and its companion repository when the question requires kernel visibility rather than another application timer.

3. Learn Linux interfaces before bypassing them

Michael Kerrisk’s The Linux Programming Interface is the comprehensive reference. The newer open Linux System Programming Essentials is a shorter practical route through file descriptors, processes, memory, signals, and I/O.

You should be able to explain the normal syscall, scheduler, socket-buffer, and network-stack path before deciding which part to avoid.

4. Learn C++ concurrency as a correctness model

Anthony Williams’s C++ Concurrency in Action, second edition is a useful structured treatment of threads, futures, atomics, the memory model, and lock-free structures. Pair it with current compiler and standard-library documentation: the book targets C++17, while the implementation track here also uses later C++ features.

The objective is not memorizing memory-order names. It is being able to state ownership, invariants, publication edges, and reclamation rules before optimizing a concurrent structure.

5. Move down the network path one layer at a time

“Kernel bypass” is not one feature, and these mechanisms are not substitutes in every workload:

ordinary sockets
    ↓ batching, affinity, busy polling, steering
io_uring: asynchronous kernel I/O through shared submission/completion rings
    ↓
XDP / AF_XDP: early packet processing plus shared user/kernel packet rings
    ↓
DPDK poll-mode drivers: userspace polling and direct NIC descriptor management

• The liburing repository supplies the reference userspace library and examples for io_uring. io_uring reduces submission and completion overhead; it is not general kernel bypass.
• The Linux kernel’s AF_XDP documentation defines its rings, UMEM ownership, copy modes, and socket behavior.
• XDP Tutorial and BPF examples are laboratories. Follow their own version caveats and use kernel documentation as the current contract.
• The DPDK Programmer’s Guide and poll-mode driver documentation explain a substantially different ownership and operational model.
• Seastar is a valuable C++ laboratory for shared-nothing, one-thread-per-core design. Its tutorial makes futures, sharding, and reactor-style execution concrete.

Do not start with DPDK because it sounds fastest. First measure ordinary sockets, batching, queue placement, and scheduler effects. Every lower-level path trades generality and operational simplicity for more explicit ownership and control.

6. Make the measurements honest

Google Benchmark is a useful C++ harness, not a substitute for experimental design. Use HdrHistogram_c for wide-range latency recording and study its coordinated-omission correction before trusting load-test percentiles.

Final evidence should include distributions, not only averages; warm and cold conditions when both matter; throughput at the reported latency; compiler and binary inspection; and explicit treatment of queueing and coordinated omission.

How the sources map to this book

The repositories are laboratories, not a giant checklist. A good study cycle is:

1. Predict the result from a model.
2. Write the smallest experiment that could disprove the prediction.
3. Record enough environment detail to reproduce it.
4. Inspect counters, traces, or generated code when wall time cannot explain why.
5. Change one important variable and repeat.
6. Write what would make the conclusion stop being true.

Data Structures

Status Version 1.0 complete

This part develops the structures used throughout the rest of the book: contiguous and linked sequences, queues, maps, sets, trees, graphs, stable-handle storage, probabilistic membership, caches, rolling windows, and bounded buffers.

The goal is not memorizing APIs. It is learning to choose a representation from required operations, memory layout, ownership, capacity, and worst-case behavior.

VecDeque — A Double-Ended Queue

A double-ended queue, often abbreviated to “deque” (pronounced “deck”), is an abstract data type that generalizes a queue, allowing elements to be added to or removed from both the front and the back.

VecDeque<T> is Rust’s growable double-ended queue.

Its defining property is:

It supports efficient insertion and removal at both the front and the back.

Use the controls below. Watch how head moves while the logical order remains normal.

When to use VecDeque

Use VecDeque when values remain in an ordered sequence and operations at the front are routine—not exceptional.

Common cases include:

• FIFO queues: add new work at the back and process the oldest work from the front.
• Worklists and breadth-first search: visit items in discovery order while adding newly discovered items at the back.
• Rolling or sliding windows: append new observations and discard expired ones from the front.
• Bounded histories and stream buffers: retain recent values while evicting the oldest.
• Algorithms that use both ends deliberately: for example, 0–1 BFS adds zero-cost edges at the front and one-cost edges at the back.

The simplest decision rule is:

Use VecDeque when the ends are active—especially when removing from the front is routine.

Choose another structure when the access pattern is different:

• Use Vec when you mainly add and remove at the back or need one contiguous slice.
• Use BinaryHeap when the highest-priority value should come out first.
• Use HashMap when values are found by key rather than position.
• Use a channel when concurrent producers and consumers must wait for and wake one another.
• Consider another representation when arbitrary searches, insertions, or removals from the middle dominate the workload.

1. The essential mental model

A Vec<T> is conceptually:

• One contiguous allocation.
• The first element lives at physical slot 0.
• Adding or removing at the back is cheap.
• Removing from the front requires shifting every remaining element.

A VecDeque<T> is also backed by an array-like allocation, but it treats that allocation as a circle.

Conceptually, it tracks:

buffer: allocation containing capacity slots
head:   physical slot containing the logical front
len:    number of initialized elements

The exact private implementation is not guaranteed, but this is the correct conceptual model.

For logical index i:

physical_index = (head + i) % capacity

Therefore:

deque[0]         // element at physical slot head
deque[1]         // element at (head + 1) % capacity
deque[len - 1]   // logical back

The user of VecDeque sees logical order. The wraparound is hidden.

2. Why the circular buffer matters

Suppose the front is in physical slot 6 of an eight-slot allocation, and the logical contents are:

[10, 20, 30, 40]

They can physically occupy:

The sequence wraps from the end of the allocation back to its beginning.

Yet these all operate in logical order:

deque.front();     // Some(&10)
deque.back();      // Some(&40)
deque.get(2);      // Some(&30)
deque.iter();      // 10, 20, 30, 40

Physical layout and logical order are different concepts.

3. How the four central operations work

Assuming available capacity:

push_back(value)

The next back slot is conceptually:

tail_next = (head + len) % capacity

Write there and increment len.

pop_back()

Find:

back = (head + len - 1) % capacity

Move the value out and decrement len.

push_front(value)

Move the head one slot backward, wrapping if necessary:

head = previous_slot(head)

Write the value at the new head and increment len.

pop_front()

Move the value out of head, advance head, and decrement len.

None of these operations needs to shift all the other elements.

That is the entire reason VecDeque exists.

4. The basic Rust API

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();

    deque.push_back(20);
    deque.push_back(30);
    deque.push_front(10);

    assert_eq!(deque.front(), Some(&10));
    assert_eq!(deque.back(), Some(&30));
    assert_eq!(deque[1], 20);

    assert_eq!(deque.pop_front(), Some(10));
    assert_eq!(deque.pop_back(), Some(30));
    assert_eq!(deque.pop_front(), Some(20));
    assert_eq!(deque.pop_front(), None);
}

Notice the ownership behavior:

deque.push_back(value);

moves value into the deque.

deque.pop_front()

returns Option<T>, moving the element back out.

Reading without removing uses references:

deque.front()      // Option<&T>
deque.front_mut()  // Option<&mut T>
deque.get(i)       // Option<&T>
deque.get_mut(i)   // Option<&mut T>

Indexing panics when out of bounds:

let x = deque[100]; // panic if len <= 100

Prefer get() when the index might be invalid.

5. Complexity

“Amortized O(1)” means most pushes are constant time, but a push into a full deque may require:

1. Allocating a larger buffer.
2. Moving the existing elements.
3. Freeing the old buffer.

That individual push is O(n), but spread across many pushes, the average cost is constant.

You can reduce reallocations:

use std::collections::VecDeque;

fn main() {
    let queue: VecDeque<i32> = VecDeque::with_capacity(10_000);
    assert!(queue.capacity() >= 10_000);
    assert!(queue.is_empty());
}

This reserves space for at least that many elements. It does not create or initialize 10,000 values.

6. The full-versus-empty problem

Consider:

tail_next = (head + len) % capacity

When the deque is empty:

len == 0
tail_next == head

When the deque is completely full:

len == capacity
tail_next == head

Therefore, head == tail_next alone cannot distinguish empty from full.

The deque also needs len, or an equivalent piece of state. This is one of the fundamental invariants:

0 <= len <= capacity

The occupied elements are exactly the len slots encountered by walking forward from head, wrapping at the allocation boundary.

7. It may not be one contiguous slice

Because the sequence can wrap, a VecDeque cannot always expose all its elements as one &[T].

Instead, as_slices() returns the contents as two slices:

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([10, 20, 30, 40]);
    let (first, second) = deque.as_slices();

    let logical: Vec<_> = first.iter().chain(second).copied().collect();
    assert_eq!(logical, vec![10, 20, 30, 40]);
}

If the deque does not wrap, second will be empty. If it does wrap, both slices may contain elements. Their chained order is always the deque’s logical order.

If an operation requires one contiguous slice:

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([30, 10, 20]);
    let slice: &mut [i32] = deque.make_contiguous();
    slice.sort();

    assert_eq!(deque, VecDeque::from([10, 20, 30]));
}

make_contiguous() may rotate or move elements, so it can cost O(n). Do not call it repeatedly in a hot loop without measuring.

8. Why it is generally faster than LinkedList

Both structures provide efficient operations at their ends, but their memory layouts differ.

A linked list usually stores every element in a separate node containing pointers. This causes:

• One or more pointers of overhead per element.
• More allocations.
• Pointer chasing.
• Poor CPU cache locality.
• No constant-time indexing.

A VecDeque stores elements densely in one allocation, possibly divided into two physical regions by wraparound. It therefore normally has much better cache behavior and supports O(1) indexing.

In Rust, LinkedList is rarely the default answer. VecDeque is usually preferable for queues and worklists.

9. Vec versus VecDeque

Use Vec<T> when:

• You mainly push and pop at the back.
• You want the simplest contiguous representation.
• You frequently pass the contents as a slice.
• Front removal is rare.
• Slightly lower overhead matters.

Use VecDeque<T> when:

• You regularly remove from the front.
• You insert at both ends.
• You need FIFO queue behavior.
• You need a rolling window.
• You need a BFS or scheduler work queue.

The classic mistake is implementing a queue with:

let item = vec.remove(0);

That shifts everything left and costs O(n) per removal. Processing an entire queue this way can become O(n²).

With VecDeque:

let item = deque.pop_front();

each removal is O(1).

10. Canonical queue pattern

use std::collections::VecDeque;

fn main() {
    let mut jobs = VecDeque::new();

    jobs.push_back("job-a");
    jobs.push_back("job-b");
    jobs.push_back("job-c");

    while let Some(job) = jobs.pop_front() {
        println!("processing {job}");
    }
}

This is FIFO:

first in → first out

For a stack, you normally use Vec, but VecDeque can also behave like one by pairing push_back with pop_back.

11. Breadth-first search

A deque is the standard structure for BFS:

use std::collections::{HashSet, VecDeque};

fn bfs(start: usize, graph: &[Vec<usize>]) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    visited.insert(start);
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);

        for &neighbor in &graph[node] {
            if visited.insert(neighbor) {
                queue.push_back(neighbor);
            }
        }
    }

    order
}

fn main() {
    let graph = vec![vec![1, 2], vec![3], vec![3], vec![]];
    assert_eq!(bfs(0, &graph), vec![0, 1, 2, 3]);
}

Nodes are processed in the order they are discovered.

A deque is also used for algorithms such as 0–1 BFS, where zero-cost edges go to the front and one-cost edges go to the back.

12. Rolling windows

Suppose you retain only the last 1,000 market-data ticks:

use std::collections::VecDeque;

fn add_tick<T>(ticks: &mut VecDeque<T>, tick: T, max_len: usize) {
    if max_len == 0 {
        return;
    }

    if ticks.len() == max_len {
        ticks.pop_front();
    }

    ticks.push_back(tick);
}

fn main() {
    let mut ticks = VecDeque::new();

    for tick in [10, 20, 30, 40] {
        add_tick(&mut ticks, tick, 3);
    }

    assert_eq!(ticks, VecDeque::from([20, 30, 40]));
}

For a time-based window, add the new event and evict expired events from the front:

events.push_back(new_event);

while events
    .front()
    .is_some_and(|event| event.timestamp < cutoff)
{
    events.pop_front();
}

Although one update might evict several old events, each event enters once and leaves once. Across the entire stream, eviction is amortized O(1) per event.

This is a strong use of VecDeque.

13. The LRU-cache trap

For a strict O(1) least-recently-used cache, VecDeque is usually the wrong recency structure—but that does not make every deque-based cache a bad design.

The simple design

A small dependency-free cache might use:

HashMap: key → value
VecDeque: least-recent key → ... → most-recent key

When a key is accessed, the cache finds it in the deque, removes it, and pushes it onto the most-recent end:

let position = deque.iter().position(|key| key == wanted); // O(n)
deque.remove(position);                                    // O(n) in general
deque.push_back(wanted);

The lookup in the hash map is expected O(1), but refreshing recency is O(n). This is not a strict constant-time LRU.

It can still be a sensible implementation:

• It uses only safe standard-library types.
• It is short and easy to verify.
• The keys are stored densely with good cache locality.
• It has no node handles or pointer relationships to maintain.
• A linear scan over 32 or 100 entries may be extremely cheap.

Big-O describes how cost grows; it does not describe every constant factor. A simple contiguous scan can outperform a more elaborate linked structure at small capacities.

What strict O(1) requires

A genuinely O(1) LRU normally needs:

• A hash map for key lookup.
• A doubly linked recency structure.
• Stable node handles or indices connecting the two.

The map finds a node in expected O(1). The linked structure then detaches that node and moves it to the most-recent end in O(1).

This relationship is awkward to express with ordinary Rust references. Moving values can invalidate references, multiple mutable links need careful control, and LinkedList does not expose convenient persistent handles for arbitrary nodes. Safe custom implementations commonly use stable integer IDs into an arena or slab rather than references between nodes.

That design offers stronger asymptotic guarantees, but it is substantially more code than a map and a deque.

A deque of stale access records

Another design avoids middle removal by treating the deque as an append-only recency log. Each access receives a new generation:

map:
A → generation 9
B → generation 4

deque, oldest to newest:
(A, 7), (B, 4), (A, 8), (A, 9)

Accessing A appends (A, 9) without searching for its older records. During eviction, the cache pops from the front until it finds a record whose generation still matches the map:

while let Some((key, generation)) = order.pop_front() {
    if map[key].generation == generation {
        evict(key);
        break;
    }

    // An old access record: discard it and continue.
}

Each record is appended once and eventually removed once, giving amortized O(1) queue work. The tradeoff moves from time to space: repeated hits create stale records, so the implementation needs a bound or periodic compaction.

This is a particularly natural use of VecDeque. The design needs efficient append-at-back and discard-from-front operations—the deque’s exact strengths.

Approximate recency

Strict LRU turns every cache hit into a metadata write. Large or concurrent caches often relax the policy to reduce work and contention. They may:

• Record access events and apply them in batches.
• Refresh recency only after a time threshold.
• Divide entries into generations or segments.
• Sample several candidates and evict the oldest sample.
• Use policies such as CLOCK rather than exact LRU.

A VecDeque can hold access events, generations, or FIFO membership within a segment even when it is not the structure used to find arbitrary cache entries.

Seeing a deque in cache code therefore does not prove that hits scan and reorder it. The deque might instead manage expiration, deferred cleanup, free nodes, admission, or stale access records. Follow the cache-hit path before judging its complexity.

The real decision

The useful conclusion is:

People use VecDeque because it is simple, safe, cache-friendly, and often fast enough—not because it provides the theoretically optimal strict LRU.

14. Middle operations are possible, but not its strength

deque.insert(index, value);
let removed = deque.remove(index);

VecDeque can shift whichever side is closer:

cost ≈ min(distance to front, distance to back)

This is better than always shifting the entire suffix, but it is still linear in the general case.

For an order-book price level, for example, a VecDeque is excellent for FIFO execution at the front. But if arbitrary orders are constantly cancelled from the middle by ID, repeatedly searching and removing them becomes expensive. You may need stable handles, a slab, linked nodes, or lazy cancellation.

15. Memory safety underneath

Internally, capacity slots are not all necessarily initialized T values.

Only the logical len occupied slots contain live elements. The unused slots are conceptually uninitialized storage.

When you call:

let item = deque.pop_front();

Rust moves the value out. That slot must no longer be treated as containing a valid T.

When the deque is dropped, the standard library drops exactly the remaining live elements—not every capacity slot. The implementation uses carefully audited unsafe machinery internally, while the public API keeps this safe.

This distinction explains why capacity != len and why reserving capacity does not construct extra values.

16. Concurrency

VecDeque does not make queue operations atomic. If multiple threads mutate one queue, it needs synchronization:

use std::collections::VecDeque;
use std::sync::{Arc, Mutex};

let queue = Arc::new(Mutex::new(VecDeque::<Job>::new()));

Keep the critical section short:

let job = {
    let mut queue = queue.lock().unwrap();
    queue.pop_front()
};

// Do slow or async work after releasing the lock.
process(job).await;

Do not hold a synchronous mutex guard across .await.

For high-throughput producer/consumer systems, a channel or specialized concurrent queue may be better than Mutex<VecDeque<T>>.

17. What you should internalize

The durable model is:

1. VecDeque is a growable circular buffer.
2. head identifies the physical location of logical index zero.
3. Logical index i maps around the allocation boundary.
4. Moving either end generally changes metadata, not all the elements.
5. End operations are O(1) unless a push triggers growth.
6. Logical order may occupy two physical slices.
7. Random access is O(1), but searching and middle removal are still linear.
8. It is ideal for FIFO queues, BFS, worklists, and rolling windows.
9. It does not solve strict O(1) LRU recency updates.

Exercise

With capacity 8, head = 6, and len = 4, determine the physical slot used by push_back, then by push_front. Draw the physical buffer after both operations and write the resulting logical order.

LinkedList — A Doubly Linked List

A linked list is a linear data structure whose elements live in separate nodes. Pointers connect each node to the next node in the sequence. The list keeps track of its first node, called the head, and often its last node, called the tail.

Rust’s std::collections::LinkedList<T> is a growable, doubly linked list.

When to use LinkedList

Use a linked list when its node-based structure is itself useful—not merely because the collection must grow.

Possible cases include:

• You frequently push and pop values at both ends.
• You need to join two whole lists in constant time with append.
• Sequential traversal is sufficient and random access is unimportant.
• Moving elements in one contiguous allocation would be unusually expensive, and profiling shows that a linked representation performs better.

In ordinary Rust programs, start with Vec or VecDeque. They store elements densely, require fewer allocations, and usually benefit much more from the CPU cache. Choose LinkedList because measurements or a specific operation justify it, not as the default representation for a growable collection.

The simplest decision rule is:

Use LinkedList only when you need linked-list behavior; use VecDeque for an ordinary queue.

1. The essential mental model

A linked list stores a value and its connections together in a node.

A singly linked list node contains:

value | next

Each node points to the following node. The final node’s next link is empty. Traversal moves only from front to back.

A doubly linked list node contains:

previous | value | next

The extra link permits traversal in both directions. Rust’s standard LinkedList uses this doubly linked structure and tracks both ends:

head                                                   tail
  ↓                                                       ↓
None ← [ A ] ⇄ [ B ] ⇄ [ C ] ⇄ [ D ] → None

The diagram shows logical connections, not adjacent memory. Nodes may occupy unrelated addresses in the heap.

2. What the links buy you

Removing the first node does not shift the other values. The list changes its head and repairs a small number of links:

before: None ← [ A ] ⇄ [ B ] ⇄ [ C ] → None
after:         None ← [ B ] ⇄ [ C ] → None

The same principle applies at the back. Given direct access to a node, a traditional doubly linked list can also unlink it by updating its two neighbors.

This leads to the familiar claim that linked lists support O(1) insertion and deletion. The qualification matters:

The operation is O(1) only after you already know the node or insertion point.

Finding the node by value or logical position still requires walking through the list and costs O(n). Rust’s ordinary stable LinkedList interface is centered on operations at the ends, iteration, and operations on whole lists; it does not behave like an indexable collection of public node handles.

3. The basic Rust API

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();

    list.push_back(20);
    list.push_back(30);
    list.push_front(10);

    assert_eq!(list.front(), Some(&10));
    assert_eq!(list.back(), Some(&30));

    assert_eq!(list.pop_front(), Some(10));
    assert_eq!(list.pop_back(), Some(30));
    assert_eq!(list.pop_front(), Some(20));
    assert_eq!(list.pop_front(), None);
}

The end operations mirror VecDeque:

Pushing moves a value into the list. Popping returns Option<T>, moving a value back out. Inspecting returns a reference because the value stays inside the list.

Unlike Vec and VecDeque, LinkedList does not support indexing:

list[3] // not supported

An index would suggest cheap random access, but reaching the fourth element requires following links through the preceding nodes.

4. A complete example

This example demonstrates construction, traversal, removal, search, and clearing:

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<u32> = LinkedList::new();

    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    list.push_front(5);

    println!("Linked list after insertions:");
    for element in &list {
        println!("{element}");
    }

    list.pop_front();
    list.pop_back();

    println!("\nLinked list after removals:");
    for element in &list {
        println!("{element}");
    }

    if list.contains(&20) {
        println!("\n20 exists in the list!");
    }

    list.clear();
    println!("\nLinked list after clearing: {list:?}");
}

The program prints:

Linked list after insertions:
5
10
20
30

Linked list after removals:
10
20

20 exists in the list!

Linked list after clearing: []

contains reads naturally, but it performs a sequential search. It may inspect every node.

5. Complexity

The table describes asymptotic growth, not real-world speed. An O(n) scan over a contiguous Vec can outperform an O(n) linked-list traversal by a large margin because the vector has better locality.

6. Joining whole lists

append is one operation that exposes the value of explicit links. It moves all nodes from one list onto the back of another without copying each element:

use std::collections::LinkedList;

fn main() {
    let mut first = LinkedList::from([1, 2]);
    let mut second = LinkedList::from([3, 4]);

    first.append(&mut second);

    assert_eq!(first, LinkedList::from([1, 2, 3, 4]));
    assert!(second.is_empty());
}

The second list is empty afterward because ownership of its nodes moves into the first list.

7. Dynamic size does not distinguish it from Vec

Linked lists are often introduced as “dynamic,” but that description is not a reason to choose one in Rust. Vec, VecDeque, HashMap, and many other collections also grow and shrink dynamically.

The meaningful distinction is how they grow:

• Vec keeps elements in one contiguous allocation and occasionally moves them when that allocation grows.
• VecDeque keeps elements in a growable ring buffer that may wrap into two contiguous regions.
• LinkedList allocates and connects separate nodes.

Ask which memory layout and access pattern the program needs, not merely whether the number of elements changes.

8. The memory cost of nodes

Each doubly linked node needs space for:

previous pointer + value + next pointer

It also normally requires a separate allocation. Compared with a dense collection, this introduces:

• Two links per element.
• Allocation metadata and allocator work.
• More addresses for the CPU to load.
• Less useful data per cache line.
• Pointer chasing during traversal.

For small values, the links may consume more space than the values themselves. This is why theoretical O(1) end operations do not automatically make a linked list faster than VecDeque.

9. Vec, VecDeque, or LinkedList?

For a FIFO queue, both VecDeque and LinkedList have constant-time end operations. Prefer VecDeque unless a benchmark or a linked-list-specific operation demonstrates a reason not to.

10. Ownership and mutation

Mutable iteration can change values without changing the links:

use std::collections::LinkedList;

fn main() {
    let mut values = LinkedList::from([1, 2, 3]);

    for value in &mut values {
        *value *= 10;
    }

    assert_eq!(values, LinkedList::from([10, 20, 30]));
}

Rust’s borrowing rules prevent structural mutation through the list while an iterator is borrowing it. This keeps iterators and references from silently pointing at removed nodes.

11. What you should internalize

The durable model is:

1. A linked list stores values in separate connected nodes.
2. Rust’s LinkedList is doubly linked and tracks both ends.
3. Pushes and pops at either end are O(1).
4. Search and positional access are O(n).
5. Arbitrary deletion is only O(1) after the node is already known.
6. Nodes add pointer, allocation, and cache-locality costs.
7. Dynamic size alone is not a reason to choose a linked list.
8. VecDeque is normally the better queue.
9. LinkedList earns its place when linked-list-specific operations or measurements justify it.

Exercise

Create two lists, keep references to their first values, append the second list to the first, and confirm the resulting order. Then write the equivalent using VecDeque and compare which operations each version expresses naturally.

BinaryHeap — A Priority Queue

A priority queue stores values according to importance rather than arrival order. Rust’s BinaryHeap<T> is a max-heap: peek and pop expose the greatest value first.

When to use BinaryHeap

Use it when the next value is determined by priority:

• Schedulers that run the most important job next.
• Top-k and streaming-selection problems.
• Graph algorithms such as Dijkstra’s shortest path.
• Merging sorted streams.
• Simulations driven by the next scheduled event.

The decision rule is:

Use BinaryHeap when you repeatedly need the current greatest—or smallest—value without keeping the entire collection sorted.

Use VecDeque when arrival order matters, BTreeMap when every value must be traversable in sorted order, and HashMap when lookup happens by key.

1. The essential mental model

A binary heap is a complete binary tree stored inside a contiguous array. In a max-heap, every parent is at least as large as its children:

        90
      /    \
    70      80
   /  \    /
 20   40  30

The same tree can occupy an array without node pointers:

[90, 70, 80, 20, 40, 30]

For a node at index i, its children are conceptually at 2i + 1 and 2i + 2. The heap guarantees only the parent-child ordering. Siblings and separate branches are not globally sorted.

2. Push and pop

Pushing adds a value at the end, then moves it upward until the heap property is restored. Popping removes the root, moves the final value into its place, then moves that value downward.

use std::collections::BinaryHeap;

fn main() {
    let mut priorities = BinaryHeap::new();
    priorities.push(20);
    priorities.push(90);
    priorities.push(40);

    assert_eq!(priorities.peek(), Some(&90));
    assert_eq!(priorities.pop(), Some(90));
    assert_eq!(priorities.pop(), Some(40));
    assert_eq!(priorities.pop(), Some(20));
    assert_eq!(priorities.pop(), None);
}

peek borrows the greatest value. pop moves it out.

3. A minimum-priority heap

Wrap values in Reverse when the smallest value should come out first:

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut deadlines = BinaryHeap::new();
    deadlines.push(Reverse(30));
    deadlines.push(Reverse(10));
    deadlines.push(Reverse(20));

    assert_eq!(deadlines.pop(), Some(Reverse(10)));
    assert_eq!(deadlines.pop(), Some(Reverse(20)));
    assert_eq!(deadlines.pop(), Some(Reverse(30)));
}

The heap is still a max-heap; Reverse<T> reverses the ordering of T.

4. Priority scheduler

Include a sequence number when equal-priority jobs must remain in arrival order:

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug, Eq, PartialEq)]
struct Job {
    priority: u8,
    sequence: u64,
    name: &'static str,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority)
            .then_with(|| other.sequence.cmp(&self.sequence))
            .then_with(|| self.name.cmp(other.name))
    }
}

impl PartialOrd for Job {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut jobs = BinaryHeap::from([
        Job { priority: 2, sequence: 0, name: "compile" },
        Job { priority: 3, sequence: 1, name: "deploy" },
        Job { priority: 3, sequence: 2, name: "notify" },
    ]);

    assert_eq!(jobs.pop().unwrap().name, "deploy");
    assert_eq!(jobs.pop().unwrap().name, "notify");
    assert_eq!(jobs.pop().unwrap().name, "compile");
}

The comparison makes higher priority greater while making an earlier sequence greater among ties.

5. Complexity

Iteration does not produce sorted order. Repeatedly call pop, or consume the heap with into_sorted_vec, when sorted output is required.

6. Sharp edges

• Equal values have no automatic FIFO guarantee; encode a tie-breaker when it matters.
• Changing a value so its ordering changes while it is inside the heap is a logic error. Use the APIs rather than interior mutation that changes priority.
• A heap is excellent at exposing one extreme value, not at searching for or deleting an arbitrary item.
• BinaryHeap requires Ord. Floating-point values need a deliberate ordering policy because ordinary floats do not implement total ordering.

7. What you should internalize

1. BinaryHeap is a max-priority queue.
2. Reverse<T> turns it into a min-priority queue.
3. Only the root is guaranteed to be the current extreme.
4. Push and pop repair a partial tree ordering in O(log n).
5. Use a sequence number when equal priorities must remain FIFO.

Exercise

Build a task queue whose larger priority runs first while equal priorities run in insertion order. Push five tasks, including three with the same priority, and assert the complete pop order.

Vec — A Growable Array

Vec<T> stores values in a growable contiguous allocation. It is Rust’s default general-purpose sequence and the collection to try first when values are primarily added and removed at the back.

When to use Vec

Use Vec when:

• You need fast indexing by position.
• You append values and iterate over them.
• You use the collection as a stack.
• You sort, search, or pass the contents as a slice.
• Dense storage and cache locality matter.

The decision rule is:

Start with Vec for an ordered sequence; switch only when another access pattern clearly dominates.

Use VecDeque when front removal is routine, a map when lookup is by key, and BinaryHeap when removal is by priority.

1. The essential mental model

A vector tracks three pieces of state:

pointer   address of the allocation
length    number of initialized elements
capacity  number of elements that fit before growth

allocation: [ A | B | C | unused | unused ]
length:       3
capacity:     5

Elements occupy the first length slots contiguously. The unused capacity does not contain initialized T values.

2. The basic API

fn main() {
    let mut values = Vec::new();

    values.push(10);
    values.push(20);
    values.push(30);

    assert_eq!(values.first(), Some(&10));
    assert_eq!(values.last(), Some(&30));
    assert_eq!(values.get(1), Some(&20));
    assert_eq!(values[1], 20);

    assert_eq!(values.pop(), Some(30));
    assert_eq!(values, vec![10, 20]);
}

Indexing panics when the index is out of bounds. get returns Option<&T> and is appropriate when absence is possible.

3. Growth and capacity

When len == capacity, a push may allocate a larger region and move every element into it. This invalidates pointers into the old allocation.

fn main() {
    let mut samples = Vec::with_capacity(1_000);
    assert!(samples.capacity() >= 1_000);
    assert_eq!(samples.len(), 0);

    samples.extend(0..1_000);
    assert_eq!(samples.len(), 1_000);
}

Reserve when a useful size estimate is known. Do not reserve enormous capacity without evidence; unused capacity still consumes memory.

4. Vec as a stack

The back of a vector provides last-in, first-out behavior:

fn main() {
    let mut stack = Vec::new();
    stack.push("first");
    stack.push("second");

    assert_eq!(stack.pop(), Some("second"));
    assert_eq!(stack.pop(), Some("first"));
}

Rust needs no separate standard-library stack type because Vec already has the right operations and representation.

5. Slices are borrowed views

A slice, &[T], borrows a contiguous region without owning its allocation:

fn sum(values: &[i32]) -> i32 {
    values.iter().sum()
}

fn main() {
    let values = vec![10, 20, 30, 40];
    assert_eq!(sum(&values), 100);
    assert_eq!(sum(&values[1..3]), 50);
}

Accepting a slice instead of &Vec<T> makes a function work with vectors, arrays, and subranges.

6. Complexity

Removing index zero shifts every later element. Repeating remove(0) to drain a queue can become O(n²); use VecDeque::pop_front instead.

7. Useful transformations

fn main() {
    let mut values = vec![4, 1, 4, 2, 3, 2];

    values.sort();
    values.dedup();
    values.retain(|value| value % 2 == 0);

    assert_eq!(values, vec![2, 4]);
}

sort establishes order, dedup removes adjacent duplicates, and retain keeps values matching a predicate.

8. What you should internalize

1. Vec is a growable contiguous array.
2. Length counts live values; capacity counts available slots.
3. Indexing and back operations are cheap.
4. Middle and front changes shift elements.
5. Slices expose borrowed contiguous views.
6. Vec is the default ordered collection and the standard stack.

Exercise

Implement a stack with Vec using only push, pop, and last. Then remove values repeatedly from index zero and explain why the total work is quadratic.

HashMap — Key-Value Lookup

HashMap<K, V> associates unique keys with values. It uses a key’s hash to locate the region where that key should be stored.

When to use HashMap

Use it for:

• Looking up records by ID or name.
• Counting occurrences.
• Grouping values by a derived key.
• Caches and indexes.
• Representing sparse relationships.

The decision rule is:

Use HashMap when the question is “what value belongs to this key?” and key order is unimportant.

Use BTreeMap when sorted keys or range queries matter, and a sequence when position rather than identity determines access.

1. The essential mental model

A hash function converts a key into a number. The map uses that number to find a bucket or probe sequence, then uses equality to identify the exact key.

key ──hash──▶ candidate location ──equality──▶ matching entry

Different keys can produce the same candidate location. This is a collision, and a correct hash map resolves it. Keys must obey one invariant: equal keys must produce equal hashes.

2. The basic API

use std::collections::HashMap;

fn main() {
    let mut ports = HashMap::new();
    ports.insert("http", 80);
    ports.insert("https", 443);

    assert_eq!(ports.get("https"), Some(&443));
    assert!(ports.contains_key("http"));
    assert_eq!(ports.remove("http"), Some(80));
    assert_eq!(ports.get("http"), None);
}

insert returns the previous value when the key already exists. get borrows the value; remove moves it out.

3. The entry API

entry performs one lookup and then lets code modify or create the value:

use std::collections::HashMap;

fn main() {
    let mut counts = HashMap::new();

    for word in "red blue red green red blue".split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }

    assert_eq!(counts["red"], 3);
    assert_eq!(counts["blue"], 2);
    assert_eq!(counts["green"], 1);
}

This is clearer and avoids a redundant lookup compared with checking first and inserting later.

4. Grouping by key

use std::collections::HashMap;

fn main() {
    let records = [("error", 10), ("info", 20), ("error", 30)];
    let mut grouped: HashMap<&str, Vec<i32>> = HashMap::new();

    for (level, value) in records {
        grouped.entry(level).or_default().push(value);
    }

    assert_eq!(grouped["error"], vec![10, 30]);
    assert_eq!(grouped["info"], vec![20]);
}

The map provides keyed access; each value can itself be another collection.

5. Complexity

Constant-time lookup is an expected property under a well-distributed hash, not an unconditional guarantee. Growth may also allocate and reorganize entries.

6. Keys and ownership

Owned keys make the map independent of its input:

use std::collections::HashMap;

fn main() {
    let mut users = HashMap::new();
    users.insert(String::from("alice"), 42);

    // A borrowed `&str` can look up an owned `String` key.
    assert_eq!(users.get("alice"), Some(&42));
}

A map can store borrowed keys, but then it cannot outlive the data those keys reference. Owned keys are often the simpler API boundary.

7. Iteration order

HashMap does not promise insertion order or sorted order. Do not write logic or tests that depend on the order produced by iteration.

When deterministic sorted output is needed, sort the collected keys or use a BTreeMap. When insertion order is part of the requirement, use a collection that explicitly guarantees it.

8. Sharp edges

• Keys require Eq + Hash.
• Mutating a key so its hash or equality changes while stored in the map is a logic error.
• map[key] panics when the key is absent; get returns Option<&V>.
• A hash map does not preserve ordering.
• Reserving capacity does not insert entries.

9. What you should internalize

1. A hash map associates unique keys with values.
2. Hashing finds candidates; equality confirms the key.
3. Lookup is expected O(1), not ordered.
4. entry is the central tool for update-or-insert logic.
5. Choose BTreeMap when order and ranges are requirements.

Exercise

Build a frequency map for a stream of instrument IDs using entry. Then produce deterministic output without changing the map type.

BTreeMap — An Ordered Map

BTreeMap<K, V> associates unique keys with values while keeping the keys in sorted order. It is implemented as a balanced search tree with nodes containing multiple entries.

When to use BTreeMap

Use it when:

• Iteration must follow key order.
• You need all entries within a key range.
• You need the first or last key efficiently.
• Deterministic traversal is part of the program’s behavior.
• Keys implement Ord but are inconvenient to hash.

The decision rule is:

Use BTreeMap when ordering is a required operation, not merely a preferred appearance in debug output.

Use HashMap for general key lookup when order is irrelevant.

1. The essential mental model

A B-tree is a balanced search tree whose nodes hold several sorted keys:

                 [ 20 | 50 ]
                /     |     \
       [ 5 | 10 ] [30 | 40] [60 | 80]

Each comparison chooses a child containing the requested key range. All leaves remain at the same depth, so operations do not degrade into walking a long, one-sided chain.

Storing several keys per node improves locality and reduces tree height compared with a one-key-per-node binary search tree.

2. The basic API

use std::collections::BTreeMap;

fn main() {
    let mut scores = BTreeMap::new();
    scores.insert("carol", 30);
    scores.insert("alice", 10);
    scores.insert("bob", 20);

    assert_eq!(scores.get("bob"), Some(&20));

    let names: Vec<_> = scores.keys().copied().collect();
    assert_eq!(names, vec!["alice", "bob", "carol"]);
}

Insertion order does not affect traversal order. Keys are yielded according to Ord.

3. Range queries

Ranges are the defining advantage over a hash map:

use std::collections::BTreeMap;

fn main() {
    let temperatures = BTreeMap::from([
        (8, 14.0),
        (9, 15.5),
        (10, 17.0),
        (11, 18.5),
        (12, 20.0),
    ]);

    let morning: Vec<_> = temperatures
        .range(9..=11)
        .map(|(&hour, &temperature)| (hour, temperature))
        .collect();

    assert_eq!(morning, vec![(9, 15.5), (10, 17.0), (11, 18.5)]);
}

The map finds the range boundary, then walks only the matching entries.

4. Extremes and neighboring keys

use std::collections::BTreeMap;

fn main() {
    let prices = BTreeMap::from([(101, "one"), (103, "three"), (107, "seven")]);

    assert_eq!(prices.first_key_value(), Some((&101, &"one")));
    assert_eq!(prices.last_key_value(), Some((&107, &"seven")));

    let at_or_below_105 = prices.range(..=105).next_back();
    assert_eq!(at_or_below_105, Some((&103, &"three")));
}

This pattern is useful for timelines, price levels, interval boundaries, and configuration that changes at ordered thresholds.

5. Complexity

Although HashMap offers expected O(1) lookup, BTreeMap may still perform well because its nodes group entries and traversal has predictable locality. Choose based on required behavior and measurements.

6. BTreeMap versus HashMap

Do not select BTreeMap solely to make a snapshot test deterministic if order has no semantic meaning; sorting only at the output boundary may express the requirement more accurately.

7. What you should internalize

1. BTreeMap stores key-value pairs in key order.
2. Lookup and updates are O(log n).
3. Range queries and ordered traversal are its central strengths.
4. It requires Ord, while HashMap requires Eq + Hash.
5. Choose it when ordering is part of the problem.

Exercise

Represent price levels as BTreeMap<i64, u64>. Find the best ask, best bid, and every level within five ticks of a supplied price without scanning the entire map.

HashSet — Membership and Uniqueness

HashSet<T> stores unique values and answers whether a value is present. It is conceptually a HashMap<T, ()>: the keys matter, but there is no separate value associated with each key.

When to use HashSet

Use it for:

• Removing duplicates.
• Tracking visited nodes or processed IDs.
• Fast membership checks.
• Comparing groups with union, intersection, and difference.
• Enforcing uniqueness in memory.

The decision rule is:

Use HashSet when presence is the information you need.

Use HashMap when each key needs associated data, BTreeSet when sorted order or ranges matter, and a bit set when the universe is small and densely numbered.

1. The basic API

use std::collections::HashSet;

fn main() {
    let mut active = HashSet::new();

    assert!(active.insert("alice"));
    assert!(!active.insert("alice"));
    assert!(active.contains("alice"));
    assert!(active.remove("alice"));
    assert!(!active.contains("alice"));
}

insert returns true only when the value was not already present. remove returns whether a value was found.

2. Deduplication

use std::collections::HashSet;

fn main() {
    let events = ["login", "trade", "login", "logout", "trade"];
    let unique: HashSet<_> = events.into_iter().collect();

    assert_eq!(unique.len(), 3);
    assert!(unique.contains("login"));
    assert!(unique.contains("trade"));
    assert!(unique.contains("logout"));
}

Iteration order is unspecified. If first-occurrence order must be preserved, collecting directly into HashSet is not sufficient by itself.

3. Tracking visited values

The return value from insert combines “check” and “mark” into one lookup:

use std::collections::HashSet;

fn main() {
    let stream = [4, 2, 4, 1, 2, 3];
    let mut seen = HashSet::new();
    let mut first_occurrences = Vec::new();

    for value in stream {
        if seen.insert(value) {
            first_occurrences.push(value);
        }
    }

    assert_eq!(first_occurrences, vec![4, 2, 1, 3]);
}

This pattern appears in graph traversal, event processing, and cycle detection.

4. Set operations

use std::collections::HashSet;

fn main() {
    let left = HashSet::from([1, 2, 3]);
    let right = HashSet::from([3, 4, 5]);

    let intersection: HashSet<_> = left.intersection(&right).copied().collect();
    let union: HashSet<_> = left.union(&right).copied().collect();
    let difference: HashSet<_> = left.difference(&right).copied().collect();

    assert_eq!(intersection, HashSet::from([3]));
    assert_eq!(union, HashSet::from([1, 2, 3, 4, 5]));
    assert_eq!(difference, HashSet::from([1, 2]));
}

The iterators borrow the original sets. Collect only when an owned result is needed.

5. Complexity

As with HashMap, expected constant-time behavior depends on hash distribution.

6. Set relationships

use std::collections::HashSet;

fn main() {
    let required = HashSet::from(["read", "write"]);
    let granted = HashSet::from(["read", "write", "admin"]);

    assert!(required.is_subset(&granted));
    assert!(granted.is_superset(&required));
    assert!(!required.is_disjoint(&granted));
}

These methods often communicate authorization, feature, or classification logic more directly than nested membership checks.

7. Sharp edges

• Values require Eq + Hash.
• Iteration order is not stable or sorted.
• Mutating a stored value so its hash or equality changes is a logic error.
• A set answers presence, not multiplicity. Use HashMap<T, usize> for counts.
• Hash-based uniqueness follows Eq, which may differ from domain-level ideas such as case-insensitive equality unless the type encodes them.

8. What you should internalize

1. HashSet stores unique values without associated data.
2. Membership is expected O(1).
3. insert conveniently reports whether a value was new.
4. Set operations express comparisons between groups.
5. Use BTreeSet when sorted traversal or ranges matter.

Exercise

Given yesterday’s and today’s active symbol sets, compute added, removed, and unchanged symbols. Assert the three groups for a small example.

Slabs and Arenas — Stable Handles

Slabs and arenas store many values in one managed region and identify them with small handles. They are useful when values refer to one another, must be found quickly by ID, or need identities that survive ordinary collection growth.

When to use slabs and arenas

Use this family of structures when:

• Graph nodes refer to other graph nodes.
• A hash map must point directly to nodes in another structure.
• Orders, tasks, entities, or sessions need compact stable IDs.
• A linked structure is easier to express with indices than Rust references.
• You allocate many related values and want to release them together.
• You need to reuse vacant storage without moving every live value.

The decision rule is:

Use handles when identity must outlive a borrow, and use generations when a reused slot must not revive an old identity.

Use an ordinary Vec when position already is identity and elements are not removed individually. Use HashMap when an existing domain key is sufficient.

1. Why ordinary references are difficult here

Consider a doubly linked cache node:

previous ← [ key | value ] → next

If previous and next were ordinary Rust references into a growable Vec, a reallocation could move the nodes and invalidate those references. Long-lived mutable references between nodes also conflict with Rust’s requirement that a value have only one active mutable reference.

A handle changes the relationship:

node.previous = Some(Handle { index: 7, generation: 3 })
node.next     = Some(Handle { index: 2, generation: 8 })

The handle is data, not a borrow. Code resolves it through the arena each time it needs the value.

Growing the arena may move its internal allocation, but index 7 still means slot 7. No pointer into the old allocation is retained.

2. Arena, slab, and generational arena

The names overlap, but these models are useful:

• Arena: allocates many related values in a shared region, often releasing them all together.
• Slab: stores values in indexed slots and maintains a free list so removed slots can be reused individually.
• Generational arena: pairs each slot index with a version number so stale handles are rejected after reuse.

A simple slab might look like:

slots: [ A | empty | C | D | empty ]
free:  [ 1, 4 ]

Inserting can pop an index from free rather than growing slots.

3. The stale-handle problem

Suppose handle 1 refers to an order in slot 1:

handle 1 ──▶ order A

The order is removed, and the slab later reuses slot 1:

handle 1 ──▶ order B

An old handle for order A now appears to identify order B. This is sometimes called an ABA problem: the slot changed from A to empty to B, but the numeric index looks unchanged.

A generation distinguishes the identities:

old handle: Handle { index: 1, generation: 4 }
new handle: Handle { index: 1, generation: 5 }

Lookup succeeds only when both the index and generation match.

4. A small generational arena

This complete implementation uses only the standard library:

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct Handle {
    index: usize,
    generation: u64,
}

#[derive(Debug)]
struct Slot<T> {
    generation: u64,
    value: Option<T>,
}

#[derive(Debug)]
struct Arena<T> {
    slots: Vec<Slot<T>>,
    free: Vec<usize>,
}

impl<T> Arena<T> {
    fn new() -> Self {
        Self {
            slots: Vec::new(),
            free: Vec::new(),
        }
    }

    fn insert(&mut self, value: T) -> Handle {
        if let Some(index) = self.free.pop() {
            let slot = &mut self.slots[index];
            debug_assert!(slot.value.is_none());
            slot.value = Some(value);

            Handle {
                index,
                generation: slot.generation,
            }
        } else {
            let index = self.slots.len();
            self.slots.push(Slot {
                generation: 0,
                value: Some(value),
            });

            Handle {
                index,
                generation: 0,
            }
        }
    }

    fn get(&self, handle: Handle) -> Option<&T> {
        let slot = self.slots.get(handle.index)?;

        if slot.generation != handle.generation {
            return None;
        }

        slot.value.as_ref()
    }

    fn get_mut(&mut self, handle: Handle) -> Option<&mut T> {
        let slot = self.slots.get_mut(handle.index)?;

        if slot.generation != handle.generation {
            return None;
        }

        slot.value.as_mut()
    }

    fn remove(&mut self, handle: Handle) -> Option<T> {
        let slot = self.slots.get_mut(handle.index)?;

        if slot.generation != handle.generation {
            return None;
        }

        let value = slot.value.take()?;
        slot.generation = slot
            .generation
            .checked_add(1)
            .expect("arena generation exhausted");
        self.free.push(handle.index);
        Some(value)
    }
}

fn main() {
    let mut arena = Arena::new();

    let old = arena.insert(String::from("order-a"));
    arena.get_mut(old).unwrap().push_str("-updated");
    assert_eq!(arena.get(old).map(String::as_str), Some("order-a-updated"));

    assert_eq!(arena.remove(old), Some(String::from("order-a-updated")));
    assert_eq!(arena.get(old), None);

    let new = arena.insert(String::from("order-b"));
    assert_eq!(new.index, old.index);
    assert_ne!(new.generation, old.generation);

    // Reusing the slot did not make the old handle valid again.
    assert_eq!(arena.get(old), None);
    assert_eq!(arena.get(new).map(String::as_str), Some("order-b"));
}

The free list makes reuse constant time. The generation check turns a stale handle into None rather than silently selecting a different value.

5. Complexity

The arena may contain holes, so its slot capacity can be larger than its number of live values. Compacting those holes would change indices and invalidate handles unless the arena also maintains a layer of indirection.

6. Building linked structures with handles

A strict LRU cache can store links as handles:

HashMap<K, Handle>

Node<K, V> {
    key: K,
    value: V,
    previous: Option<Handle>,
    next: Option<Handle>,
}

Arena<Node<K, V>>

The map finds a node in expected O(1). The cache uses its previous and next handles to detach and reattach it in O(1).

The same representation is useful for:

• Order management: HashMap<OrderId, Handle> finds an order for cancellation while price-level links preserve execution order.
• Graphs: nodes store handles for neighboring nodes.
• Schedulers: a public task ID resolves to mutable task state.
• Entity systems: components refer to entities without holding Rust references into a moving allocation.

7. Handles are not references

A handle does not keep its target alive. Removal can invalidate it, so lookup returns Option.

A handle also does not carry borrowing rules by itself. The arena still controls access:

arena.get(handle)      → Option<&T>
arena.get_mut(handle)  → Option<&mut T>

When an operation must modify two nodes, code cannot simply call get_mut twice while retaining the first mutable reference. Common approaches include:

• Copy the neighboring handles, end the first borrow, then mutate each node in separate steps.
• Use split_at_mut internally after proving the indices differ.
• Provide a carefully designed get_many_mut operation that rejects duplicate handles.
• Move the multi-node operation inside the arena so it can enforce the invariant centrally.

This friction is useful: it forces aliasing assumptions to become explicit.

8. Generation policy

The sample uses a u64 generation and refuses to wrap. A production arena must choose a policy deliberately:

• Use a sufficiently wide generation counter.
• Treat exhaustion as an unrecoverable invariant failure.
• Retire a slot permanently before its generation wraps.
• Document whether handles may cross process, persistence, or network boundaries.

Serializing a raw handle is dangerous when the arena may be rebuilt. An index and generation identify a slot within a particular arena instance, not a universal domain entity.

9. Arena allocation without individual removal

Not every arena needs reusable slots. Parsers, compilers, and request-scoped work often allocate many objects that all share one lifetime. A bump-style arena advances an allocation cursor for each value and releases the entire region at once.

That design trades individual removal for extremely cheap allocation and bulk cleanup. It is a different answer to the same question: which lifetime and identity operations does the workload actually require?

10. Sharp edges

• A bare index is vulnerable to stale-handle aliasing after slot reuse.
• Generations reduce that risk only while they do not wrap.
• Handles are meaningful only with the arena that created them.
• Removing values creates holes and can retain unused capacity.
• Compacting storage normally invalidates handles.
• A custom arena is easy to get subtly wrong; prefer a well-tested implementation when the design becomes infrastructure.
• Stable handles do not imply stable memory addresses.

11. What you should internalize

1. Handles replace long-lived internal references with resolvable IDs.
2. A slab reuses indexed slots through a free list.
3. A generation prevents an old handle from naming a new occupant.
4. Insert, lookup, and removal can all be constant time.
5. Holes trade memory density for stable identity.
6. Handle-based links make graphs, LRUs, and order structures easier to express safely in Rust.
7. The arena remains responsible for borrowing, lifetime, and generation invariants.

Exercise

Insert a value, remove it, and reuse its slot. Prove with assertions that the old handle is rejected while the new handle resolves, even though both handles contain the same slot index.

BTreeSet — Ordered Membership

BTreeSet<T> stores unique values in sorted order. It answers membership questions like a HashSet, while also supporting ordered traversal, range queries, and efficient access to the smallest and greatest values.

When to use BTreeSet

Use it when:

• Values must remain unique and sorted.
• You need every value within a range.
• You need the smallest, greatest, predecessor, or successor value.
• Deterministic traversal is part of the program’s behavior.
• Values implement Ord but are inconvenient to hash.

The decision rule is:

Use BTreeSet when presence and order both matter.

Use HashSet when you only need membership and expected constant-time lookup. Use a sorted Vec when updates are rare and compact storage or fast sequential scans matter more than insertion cost.

1. The essential mental model

A BTreeSet<T> is conceptually a BTreeMap<T, ()>: each stored value acts as a key, and there is no separate associated value.

The values live in a balanced B-tree whose nodes contain several sorted values:

                    [ 20 | 50 ]
                   /     |     \
          [ 5 | 10 ] [30 | 40] [60 | 80]

Each comparison chooses the child containing the relevant range. All leaves stay at the same depth, preventing the structure from degrading into a long one-sided chain.

The exact node layout is private, but three properties define the useful model:

1. Every value is unique.
2. Traversal follows Ord.
3. The tree remains balanced as values are inserted and removed.

2. The basic API

use std::collections::BTreeSet;

fn main() {
    let mut prices = BTreeSet::new();

    assert!(prices.insert(103));
    assert!(prices.insert(101));
    assert!(prices.insert(107));
    assert!(!prices.insert(103));

    assert!(prices.contains(&101));
    assert!(prices.remove(&103));
    assert!(!prices.contains(&103));

    let ordered: Vec<_> = prices.into_iter().collect();
    assert_eq!(ordered, vec![101, 107]);
}

insert returns true only when the value was new. remove returns whether a matching value existed.

3. Ordered traversal

Insertion order does not affect iteration order:

use std::collections::BTreeSet;

fn main() {
    let values = BTreeSet::from([40, 10, 30, 20]);
    let ordered: Vec<_> = values.iter().copied().collect();

    assert_eq!(ordered, vec![10, 20, 30, 40]);
    assert_eq!(values.first(), Some(&10));
    assert_eq!(values.last(), Some(&40));
}

This makes BTreeSet useful for timelines, price levels, ordered IDs, and deterministic output.

4. Range queries

A range begins near its lower boundary and visits only matching values:

use std::collections::BTreeSet;

fn main() {
    let prices = BTreeSet::from([95, 100, 101, 103, 108, 110]);

    let nearby: Vec<_> = prices.range(100..=108).copied().collect();
    assert_eq!(nearby, vec![100, 101, 103, 108]);
}

A HashSet cannot answer this query without examining every value.

5. Predecessors and successors

Range iterators can locate the nearest stored value on either side of a target:

use std::collections::BTreeSet;

fn main() {
    let levels = BTreeSet::from([100, 103, 107, 112]);

    let at_or_below = levels.range(..=105).next_back();
    let at_or_above = levels.range(105..).next();

    assert_eq!(at_or_below, Some(&103));
    assert_eq!(at_or_above, Some(&107));
}

This is useful for price ladders, schedules, thresholds, and sparse numeric domains.

6. Set operations

use std::collections::BTreeSet;

fn main() {
    let left = BTreeSet::from([1, 2, 3]);
    let right = BTreeSet::from([3, 4, 5]);

    let intersection: Vec<_> = left.intersection(&right).copied().collect();
    let union: Vec<_> = left.union(&right).copied().collect();
    let difference: Vec<_> = left.difference(&right).copied().collect();
    let symmetric: Vec<_> = left.symmetric_difference(&right).copied().collect();

    assert_eq!(intersection, vec![3]);
    assert_eq!(union, vec![1, 2, 3, 4, 5]);
    assert_eq!(difference, vec![1, 2]);
    assert_eq!(symmetric, vec![1, 2, 4, 5]);
}

The results arrive in sorted order. The operations return borrowing iterators, so collecting is unnecessary when values can be processed immediately.

7. Set relationships

use std::collections::BTreeSet;

fn main() {
    let required = BTreeSet::from(["read", "write"]);
    let granted = BTreeSet::from(["admin", "read", "write"]);

    assert!(required.is_subset(&granted));
    assert!(granted.is_superset(&required));
    assert!(!required.is_disjoint(&granted));
}

These relationships express permissions, capabilities, classifications, and dependency requirements directly.

8. Taking ownership of a stored value

take removes and returns the value equal to a borrowed lookup key:

use std::collections::BTreeSet;

#[derive(Debug, Eq, Ord, PartialEq, PartialOrd)]
struct Session {
    id: u32,
}

fn main() {
    let mut sessions = BTreeSet::from([
        Session { id: 10 },
        Session { id: 20 },
    ]);

    let removed = sessions.take(&Session { id: 10 });
    assert_eq!(removed, Some(Session { id: 10 }));
    assert_eq!(sessions.len(), 1);
}

For richer records, ensure the implemented ordering represents identity correctly. If comparison includes every field, a lookup value must match every field—not merely an ID.

9. Complexity

The asymptotic comparison with HashSet is only part of the decision. Tree operations provide deterministic order and range behavior that a hash table does not provide at all.

10. BTreeSet, HashSet, or sorted Vec?

A sorted vector supports binary-search membership in O(log n) and has excellent locality, but insertion and removal shift elements. It can beat a tree when the collection is built once and queried many times.

11. Ordering defines uniqueness

BTreeSet considers two values duplicates when Ord::cmp returns Equal. Ordering and equality must agree.

This matters for records with custom comparison. If comparison uses only a timestamp, two distinct events with the same timestamp will be treated as one set value. Add a sequence number or unique ID when ties must remain distinct.

Values must not change their relative ordering while stored in the set. Doing so through interior mutability is a logic error that can produce incorrect results, even though Rust’s memory safety remains intact.

12. Sharp edges

• BTreeSet requires Ord; ordinary floating-point types do not implement a total order suitable for it.
• There is no positional indexing. A B-tree is ordered by value, not array position.
• Deterministic traversal is useful only when order has meaning. Sorting at an output boundary may be clearer when it does not.
• Tree nodes and comparisons add overhead; benchmark against a sorted vector for read-heavy, mostly static data.
• A set records presence, not multiplicity. Use a map from value to count when duplicates must be counted.

13. What you should internalize

1. BTreeSet stores unique values in sorted order.
2. It provides O(log n) membership and updates.
3. Range, predecessor, successor, first, and last queries are its strengths.
4. Ordering defines both traversal and uniqueness.
5. HashSet is the default when order is irrelevant.
6. A sorted Vec can be better when updates are rare.

Exercise

Store a set of timestamps, then implement queries for the nearest timestamp at or before a target and the nearest timestamp at or after it. Include targets below and above every stored value.

Graphs — Choosing a Representation

A graph contains vertices connected by edges. The representation is not an implementation detail: it determines which graph operations are cheap.

When to use a graph

Use a graph for networks, dependencies, routes, state transitions, ownership relationships, or any domain where arbitrary entities connect to one another.

Choose the representation from the queries: neighbor traversal, edge lookup, global edge processing, or dense connectivity.

1. Adjacency list

An adjacency list stores each vertex’s outgoing neighbors:

use std::collections::VecDeque;

fn bfs(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut seen = vec![false; graph.len()];
    let mut queue = VecDeque::from([start]);
    let mut order = Vec::new();
    seen[start] = true;

    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &next in &graph[node] {
            if !seen[next] {
                seen[next] = true;
                queue.push_back(next);
            }
        }
    }
    order
}

fn main() {
    let graph = vec![vec![1, 2], vec![3], vec![3], vec![]];
    assert_eq!(bfs(&graph, 0), vec![0, 1, 2, 3]);
}

For V vertices and E edges, storage is O(V + E). Traversing a vertex’s neighbors costs O(degree). This is the default for sparse graphs.

2. Other representations

An undirected edge normally appears in both adjacency lists. A weighted graph stores (neighbor, weight) rather than only the neighbor.

3. Identity and deletion

Dense integer IDs make Vec<Vec<usize>> simple and fast. If nodes are removed and slots reused, bare indices can become stale. Generational arena handles prevent an old edge from silently pointing to a new occupant.

4. Core algorithms

• BFS uses a queue and finds shortest paths in unweighted graphs.
• DFS uses a stack or recursion and explores reachability and structure.
• Dijkstra uses a min-priority queue for nonnegative weighted edges.
• Topological sorting orders a directed acyclic graph.
• Minimum-spanning-tree algorithms use sorted edges or a priority queue.

5. What you should internalize

Graphs have no single best storage type. Start with an adjacency list for sparse graphs, then change representation only when edge lookup, density, identity, or mutation demands it.

Exercise

Modify the BFS example to return the shortest path from start to a target, not merely visitation order. Return None when the target is unreachable.

Disjoint Set — Dynamic Connectivity

A disjoint-set union structure—also called union-find—maintains a partition of elements into non-overlapping groups.

When to use it

Use union-find when edges are added and you repeatedly ask whether two elements are connected. It appears in Kruskal’s minimum spanning tree, clustering, network connectivity, and cycle detection in undirected graphs.

It does not support efficient arbitrary edge deletion or shortest paths.

1. The essential mental model

Each group is a tree whose root represents the group:

0 ← 1 ← 3       2 ← 4

find(x) follows parents to a root. union(a, b) connects two roots.

Two optimizations make it extremely fast:

• Union by size: attach the smaller tree beneath the larger.
• Path compression: make visited nodes point directly to the root.

2. Complete implementation

struct DisjointSet {
    parent: Vec<usize>,
    size: Vec<usize>,
}

impl DisjointSet {
    fn new(len: usize) -> Self {
        Self {
            parent: (0..len).collect(),
            size: vec![1; len],
        }
    }

    fn find(&mut self, value: usize) -> usize {
        if self.parent[value] != value {
            self.parent[value] = self.find(self.parent[value]);
        }
        self.parent[value]
    }

    fn union(&mut self, left: usize, right: usize) -> bool {
        let mut a = self.find(left);
        let mut b = self.find(right);
        if a == b {
            return false;
        }
        if self.size[a] < self.size[b] {
            std::mem::swap(&mut a, &mut b);
        }
        self.parent[b] = a;
        self.size[a] += self.size[b];
        true
    }

    fn connected(&mut self, left: usize, right: usize) -> bool {
        self.find(left) == self.find(right)
    }
}

fn main() {
    let mut sets = DisjointSet::new(6);
    assert!(sets.union(0, 1));
    assert!(sets.union(1, 2));
    assert!(sets.connected(0, 2));
    assert!(!sets.connected(0, 5));
    assert!(!sets.union(0, 2));
}

With both optimizations, operations take amortized O(α(n)), where the inverse Ackermann function grows so slowly that it is effectively constant for realistic inputs.

3. Invariants

• Every parent is a valid index.
• A root is its own parent.
• Only a root’s size is authoritative.
• union changes parents only at roots.

Union-find answers connectivity, not the actual path connecting two elements.

4. What you should internalize

Union-find is specialized and exceptionally efficient: it maintains connected components under additions. Path compression speeds future queries; union by size prevents tall trees.

Exercise

Extend the implementation with component_size(x) and a count of current components. Verify that redundant unions change neither result.

Tries — Prefix Lookup

A trie stores keys one symbol at a time. Keys with a common prefix share the same path.

When to use a trie

Use one for prefix search, autocomplete, routing tables, dictionaries, and longest-prefix matching. Use a hash map when only complete-key lookup matters; tries often consume substantially more memory.

1. Mental model

root
 └─ c
    ├─ a ─ t*       "cat"
    └─ o ─ w*       "cow"

The terminal marker distinguishes a stored word from a prefix.

2. A character trie

use std::collections::HashMap;

#[derive(Default)]
struct Node {
    terminal: bool,
    children: HashMap<char, Node>,
}

#[derive(Default)]
struct Trie {
    root: Node,
}

impl Trie {
    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for character in word.chars() {
            node = node.children.entry(character).or_default();
        }
        node.terminal = true;
    }

    fn contains(&self, word: &str) -> bool {
        self.find(word).is_some_and(|node| node.terminal)
    }

    fn has_prefix(&self, prefix: &str) -> bool {
        self.find(prefix).is_some()
    }

    fn find(&self, text: &str) -> Option<&Node> {
        let mut node = &self.root;
        for character in text.chars() {
            node = node.children.get(&character)?;
        }
        Some(node)
    }
}

fn main() {
    let mut trie = Trie::default();
    trie.insert("cat");
    trie.insert("car");

    assert!(trie.contains("cat"));
    assert!(!trie.contains("ca"));
    assert!(trie.has_prefix("ca"));
    assert!(!trie.has_prefix("dog"));
}

Lookup costs O(k) for a key of k symbols, independent of the number of stored keys. The constant cost depends heavily on child representation.

3. Representation choices

• HashMap<char, Node> handles sparse alphabets flexibly.
• A fixed child array is faster but wastes space for sparse nodes.
• Radix trees compress chains of single-child nodes.
• Byte tries operate on encodings; character tries operate on Unicode scalar values, which are not necessarily user-perceived characters.

4. What you should internalize

Tries exchange memory for prefix-oriented operations. The alphabet and child representation usually matter more than the high-level algorithm.

Exercise

Add words_with_prefix(prefix) and return results in deterministic order. Test a prefix that is itself a stored word as well as a prefix with no matches.

Bit Sets — Dense Membership

A bit set represents membership with one bit per possible integer value.

When to use it

Use a bit set when the universe is bounded and densely numbered: permissions, CPU sets, feature flags, graph visitation, instrument IDs, or compact set algebra. Use HashSet for sparse or non-integer keys.

1. Representation

One u64 stores membership for 64 values:

word = value / 64
bit  = value % 64
mask = 1 << bit

2. Small implementation

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

impl BitSet {
    fn with_capacity(bits: usize) -> Self {
        Self { words: vec![0; bits.div_ceil(64)] }
    }

    fn insert(&mut self, value: usize) {
        let (word, bit) = (value / 64, value % 64);
        self.words[word] |= 1_u64 << bit;
    }

    fn remove(&mut self, value: usize) {
        let (word, bit) = (value / 64, value % 64);
        self.words[word] &= !(1_u64 << bit);
    }

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

    fn intersection(&self, other: &Self) -> Self {
        Self {
            words: self.words.iter().zip(&other.words)
                .map(|(left, right)| left & right).collect(),
        }
    }

    fn len(&self) -> u32 {
        self.words.iter().map(|word| word.count_ones()).sum()
    }
}

fn main() {
    let mut left = BitSet::with_capacity(128);
    left.insert(3);
    left.insert(70);

    let mut right = BitSet::with_capacity(128);
    right.insert(3);
    right.insert(90);

    assert!(left.contains(70));
    assert_eq!(left.intersection(&right).len(), 1);
    left.remove(3);
    assert!(!left.contains(3));
}

Membership updates are O(1). Union and intersection process one machine word at a time in O(universe / word_size) and are often vectorizable.

3. Tradeoffs

A million possible IDs require about 125 KB regardless of how many are present. That is excellent when many IDs occur and wasteful when only a handful do. Bounds policy is part of the API: the example panics when inserting beyond its declared capacity but safely returns false for an out-of-range lookup.

4. What you should internalize

Bit sets are arrays of membership bits. They provide compact dense membership and extremely fast bulk set operations, but require a bounded integer domain.

Exercise

Add union, difference, and count operations to the example. Test values on both sides of a word boundary, such as 63, 64, and 65.

Bloom Filters — Probabilistic Membership

A Bloom filter is a compact probabilistic set. It can prove that a value is definitely absent or report that it is possibly present.

When to use it

Use a Bloom filter to avoid expensive negative lookups—for example, before disk, network, or database access. Do not use it when false positives are unacceptable or when stored values must be retrieved.

“Not present” is definitive; “possibly present” requires confirmation.

1. Mental model

Insertion hashes a value several ways and sets several bits. Lookup checks the same positions:

insert(x): set bits h1(x), h2(x), h3(x)
lookup(x): if any bit is zero → definitely absent
           if all are one    → possibly present

Collisions can make an absent value appear present. A standard Bloom filter has no false negatives as long as bits are never cleared.

2. Small implementation

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

struct BloomFilter {
    bits: Vec<bool>,
    hashes: u64,
}

impl BloomFilter {
    fn new(bit_count: usize, hashes: u64) -> Self {
        assert!(bit_count > 0 && hashes > 0);
        Self { bits: vec![false; bit_count], hashes }
    }

    fn index<T: Hash>(&self, value: &T, seed: u64) -> usize {
        let mut hasher = DefaultHasher::new();
        seed.hash(&mut hasher);
        value.hash(&mut hasher);
        hasher.finish() as usize % self.bits.len()
    }

    fn insert<T: Hash>(&mut self, value: &T) {
        for seed in 0..self.hashes {
            let index = self.index(value, seed);
            self.bits[index] = true;
        }
    }

    fn might_contain<T: Hash>(&self, value: &T) -> bool {
        (0..self.hashes).all(|seed| self.bits[self.index(value, seed)])
    }
}

fn main() {
    let mut filter = BloomFilter::new(1_024, 4);
    filter.insert(&"alice");
    filter.insert(&"bob");

    assert!(filter.might_contain(&"alice"));
    // A false positive is possible, so do not assert that an absent key is false.
}

The example teaches the structure; production implementations use carefully chosen hash derivation and bit storage.

3. Sizing

False positives increase when too many values share too few bits. For n expected values and desired false-positive probability p, common estimates are:

bits ≈ -n ln(p) / (ln 2)²
hashes ≈ (bits / n) ln 2

Measure the realized rate with representative data.

4. Limitations

• It does not store or return the original values.
• Ordinary deletion can create false negatives; counting Bloom filters replace bits with counters when deletion is required.
• Capacity mistakes degrade accuracy rather than producing an obvious error.
• The hash scheme and parameters are part of persisted-format compatibility.

5. What you should internalize

A Bloom filter is a fast negative filter, not a source of truth. It trades a controlled false-positive rate for compact storage and cheap membership tests.

Exercise

Insert 1,000 values, test 10,000 different values, and measure the observed false-positive rate. Repeat with twice as many bits while keeping the number of hashes fixed.

LRU Cache — Lookup Plus Recency

An LRU cache evicts the least recently used entry when capacity is full. It combines keyed lookup with an ordering that changes on every hit.

When to use it

Use LRU when recent access predicts future access and storage is bounded. Avoid it when entries have explicit expiration, frequency matters more than recency, or every read becoming a metadata write creates too much contention.

1. Two structures, two questions

HashMap:  where is key K?
Recency:  which key is oldest?

A simple safe implementation uses HashMap<K, V> plus VecDeque<K>. Hits scan the deque, so they are O(n), but the design is often excellent for small caches.

use std::collections::{HashMap, VecDeque};
use std::hash::Hash;

struct Lru<K, V> {
    capacity: usize,
    values: HashMap<K, V>,
    order: VecDeque<K>,
}

impl<K: Clone + Eq + Hash, V> Lru<K, V> {
    fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        Self { capacity, values: HashMap::new(), order: VecDeque::new() }
    }

    fn get(&mut self, key: &K) -> Option<&V> {
        let position = self.order.iter().position(|stored| stored == key)?;
        let key = self.order.remove(position).unwrap();
        self.order.push_back(key.clone());
        self.values.get(&key)
    }

    fn insert(&mut self, key: K, value: V) {
        if let Some(position) = self.order.iter().position(|stored| stored == &key) {
            self.order.remove(position);
        } else if self.values.len() == self.capacity {
            let oldest = self.order.pop_front().unwrap();
            self.values.remove(&oldest);
        }
        self.order.push_back(key.clone());
        self.values.insert(key, value);
    }
}

fn main() {
    let mut cache = Lru::new(2);
    cache.insert("a", 1);
    cache.insert("b", 2);
    assert_eq!(cache.get(&"a"), Some(&1));
    cache.insert("c", 3);
    assert_eq!(cache.get(&"b"), None);
    assert_eq!(cache.get(&"a"), Some(&1));
}

2. Strict constant time

Strict expected O(1) operations require a hash map pointing to nodes in a doubly linked recency list. In safe Rust, generational arena handles are a natural representation. The map resolves a node; handles unlink and relink it without searching.

3. Alternatives

• A stale-generation deque log gives amortized O(1) but needs compaction.
• CLOCK approximates recency with a reference bit.
• Segmented policies protect frequently reused entries.
• TTL caches order by expiration rather than access.

4. What you should internalize

LRU is a composition, not one container. “Best” depends on capacity, contention, memory bounds, and whether strict recency is actually required.

Exercise

Trace a capacity-three cache through A, B, C, A, D, C. Record the recency order after each access, then update the example to count hits, misses, and evictions.

Monotonic Deque — Rolling Extremes

A monotonic deque keeps candidates ordered so the minimum or maximum of every sliding window can be produced in linear time.

When to use it

Use it for rolling highs and lows, streaming thresholds, windowed telemetry, and algorithms that repeatedly need an extreme over adjacent ranges.

Use a heap or range-query structure when windows are not contiguous or do not advance in one direction.

1. Invariant

For a rolling maximum, stored values decrease from front to back. Before adding a new value, remove smaller values from the back: they can never win again while the new, later value remains in the window. Remove expired indices from the front.

use std::collections::VecDeque;

fn rolling_max(values: &[i32], width: usize) -> Vec<i32> {
    assert!(width > 0);
    let mut candidates = VecDeque::new();
    let mut result = Vec::new();

    for index in 0..values.len() {
        while candidates.front().is_some_and(|&old| old + width <= index) {
            candidates.pop_front();
        }
        while candidates.back().is_some_and(|&old| values[old] <= values[index]) {
            candidates.pop_back();
        }
        candidates.push_back(index);
        if index + 1 >= width {
            result.push(values[*candidates.front().unwrap()]);
        }
    }
    result
}

fn main() {
    assert_eq!(rolling_max(&[1, 3, -1, -3, 5, 3, 6, 7], 3),
               vec![3, 3, 5, 5, 6, 7]);
}

Each index enters once and leaves once, so total work is O(n) rather than O(n × width). Store indices, not only values, so expiration is detectable.

2. What you should internalize

The deque contains only values that can still become the answer. Its ordering invariant converts repeated window scans into amortized constant work per item.

Exercise

Adapt rolling_max into rolling_min, then test both functions on increasing, decreasing, constant, and duplicate-heavy inputs.

Ring Buffer — Fixed-Capacity Streaming

A fixed-capacity ring buffer reuses a bounded allocation by wrapping its read and write positions around the end.

When to use it

Use one for bounded histories, audio or network buffers, telemetry, and producer/consumer pipelines where allocation after initialization is unwanted.

Use VecDeque when the collection should grow rather than enforce a capacity.

1. Overwriting implementation

struct RingBuffer<T> {
    slots: Vec<Option<T>>,
    head: usize,
    len: usize,
}

impl<T> RingBuffer<T> {
    fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        Self {
            slots: (0..capacity).map(|_| None).collect(),
            head: 0,
            len: 0,
        }
    }

    fn push(&mut self, value: T) -> Option<T> {
        let capacity = self.slots.len();
        let index = (self.head + self.len) % capacity;
        if self.len < capacity {
            self.slots[index] = Some(value);
            self.len += 1;
            None
        } else {
            let replaced = self.slots[self.head].replace(value);
            self.head = (self.head + 1) % capacity;
            replaced
        }
    }

    fn pop(&mut self) -> Option<T> {
        if self.len == 0 { return None; }
        let value = self.slots[self.head].take();
        self.head = (self.head + 1) % self.slots.len();
        self.len -= 1;
        value
    }
}

fn main() {
    let mut ring = RingBuffer::new(3);
    assert_eq!(ring.push(10), None);
    ring.push(20);
    ring.push(30);
    assert_eq!(ring.push(40), Some(10));
    assert_eq!(ring.pop(), Some(20));
}

This policy overwrites the oldest value. Other APIs reject new values or block the producer when full. That policy is part of the data structure’s contract.

2. Ring buffer versus VecDeque

VecDeque grows and offers a rich collection API. A fixed ring buffer promises bounded memory and makes overflow behavior explicit. Concurrent lock-free rings also require atomic ordering and ownership protocols; circular indexing alone does not make a queue thread-safe.

3. What you should internalize

Ring buffers trade growth for predictable capacity. Define what full and empty mean, what happens on overflow, and who owns each slot.

Exercise

Change the example’s overwrite policy into a reject-new-value policy. Make the return type distinguish a full buffer from an accepted value, and test the wraparound boundary.

Indexed Priority Queue — Mutable Priorities

An indexed priority queue combines a heap with a map from item identity to heap position. It supports changing or removing an arbitrary item’s priority without scanning the entire heap.

When to use it

Use it for schedulers with cancellation, Dijkstra variants with decrease-key, order queues with priority updates, and simulations whose future events change.

Use an ordinary BinaryHeap when priorities never change after insertion.

1. Invariant

heap[index].key = K  ⇔  positions[K] = index

Every heap swap must update both position entries. After a priority change, bubble the item upward or downward to restore heap order.

use std::collections::HashMap;

struct IndexedHeap {
    heap: Vec<(String, i32)>,
    positions: HashMap<String, usize>,
}

impl IndexedHeap {
    fn new() -> Self { Self { heap: Vec::new(), positions: HashMap::new() } }

    fn swap(&mut self, a: usize, b: usize) {
        self.heap.swap(a, b);
        self.positions.insert(self.heap[a].0.clone(), a);
        self.positions.insert(self.heap[b].0.clone(), b);
    }

    fn push(&mut self, key: String, priority: i32) {
        assert!(!self.positions.contains_key(&key));
        let mut index = self.heap.len();
        self.heap.push((key.clone(), priority));
        self.positions.insert(key, index);
        while index > 0 {
            let parent = (index - 1) / 2;
            if self.heap[parent].1 >= self.heap[index].1 { break; }
            self.swap(parent, index);
            index = parent;
        }
    }

    fn update(&mut self, key: &str, priority: i32) {
        let mut index = self.positions[key];
        let old = self.heap[index].1;
        self.heap[index].1 = priority;
        if priority > old {
            while index > 0 {
                let parent = (index - 1) / 2;
                if self.heap[parent].1 >= self.heap[index].1 { break; }
                self.swap(parent, index);
                index = parent;
            }
        } else {
            loop {
                let left = index * 2 + 1;
                if left >= self.heap.len() { break; }
                let right = left + 1;
                let child = if right < self.heap.len()
                    && self.heap[right].1 > self.heap[left].1 { right } else { left };
                if self.heap[index].1 >= self.heap[child].1 { break; }
                self.swap(index, child);
                index = child;
            }
        }
    }
}

fn main() {
    let mut queue = IndexedHeap::new();
    queue.push("compile".into(), 2);
    queue.push("deploy".into(), 5);
    queue.update("compile", 8);
    assert_eq!(queue.heap[0], ("compile".into(), 8));
}

Lookup is expected O(1); insertion and priority change are O(log n). The map/heap synchronization invariant is the structure’s main source of bugs.

2. What you should internalize

An ordinary heap exposes only its root. Adding an index map makes arbitrary items addressable, but every structural change must maintain two coordinated representations.

Exercise

Implement removal by key. After every swap and removal, assert that each heap entry’s index agrees with positions and that the heap-order invariant holds.

Interval Structures — Overlap and Range Queries

An interval represents a range such as [start, end). Interval problems ask which ranges overlap a point or another range, or how ranges can be merged.

When to use them

Use interval structures for schedules, reservations, time windows, memory ranges, genomic regions, and price validity periods.

Start with a sorted Vec; add an augmented tree only when frequent dynamic overlap queries justify the additional invariants.

1. The overlap rule

For half-open intervals, two ranges overlap exactly when:

left.start < right.end && right.start < left.end

Half-open ranges make adjacent intervals non-overlapping and avoid double counting their shared boundary.

2. Merge sorted intervals

fn merge(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    intervals.sort_unstable();
    let mut merged: Vec<(i32, i32)> = Vec::new();

    for (start, end) in intervals {
        assert!(start <= end);
        match merged.last_mut() {
            Some(last) if start < last.1 => last.1 = last.1.max(end),
            _ => merged.push((start, end)),
        }
    }
    merged
}

fn main() {
    assert_eq!(merge(vec![(5, 8), (1, 3), (2, 6), (10, 12)]),
               vec![(1, 8), (10, 12)]);
}

Sorting costs O(n log n); the merge scan is O(n).

3. Choosing a structure

An interval tree augments each search-tree node with the greatest endpoint in its subtree. That summary lets a query skip branches that cannot overlap.

4. Sharp edges

Choose closed, open, or half-open boundaries once and encode the choice consistently. Decide whether empty intervals and touching ranges count as overlap. Many interval bugs are contract bugs, not tree bugs.

5. What you should internalize

Start with sorted intervals and binary search. Reach for an augmented tree only when dynamic overlap queries justify its invariants and memory cost.

Exercise

Test the merge function with empty intervals, nested intervals, and the half-open neighbors [1, 3) and [3, 5). Decide explicitly whether touching ranges should remain separate, then make the implementation match that rule.

Data-Structure Selection Guide

Choose a data structure from the operation that must be cheap, not from its name or theoretical reputation.

Ordered sequences

Keys, membership, and order

Priority, identity, and relationships

Questions to ask

1. Is access by position, key, priority, range, prefix, identity, or recency?
2. Which operations dominate, and what are their required bounds?
3. Is order semantic or merely convenient for display?
4. Is the domain dense or sparse?
5. Are identities stable across removal and reuse?
6. Must memory be bounded?
7. Does contiguous layout outweigh asymptotic differences?
8. What invariant must every mutation preserve?
9. Can a simpler structure meet the measured workload?

Final rule

Prefer the simplest representation whose invariants make the required operations cheap enough—and verify the decision with realistic measurements.

Essential Algorithms

Status In progress

This part studies the small set of algorithmic patterns repeatedly used in systems: boundary finding, selection, scans, incremental state, graph frontiers, scheduling, streaming, and parsers.

Each chapter connects a correctness invariant and asymptotic cost to data movement and machine behavior.

Binary Search — Finding the Boundary

Binary search repeatedly removes half of a sorted search space. Its durable form is not “look for the target”; it is “find the first position where a condition becomes true.”

When to use binary search

Use binary search when:

• Values are sorted and indexable.
• A yes/no condition changes from false to true at one boundary.
• Each comparison can discard an entire half of the remaining candidates.
• Repeated queries justify establishing or maintaining order.

Typical questions include:

• Is this value present?
• Where should this value be inserted?
• Where does a run of equal values begin or end?
• What is the first timestamp at or after a cutoff?
• What is the smallest capacity that satisfies a feasibility test?

Do not sort a one-off input merely to perform one binary search: sorting costs O(n log n), while a linear scan costs O(n). Binary search also requires random access or another way to reach the middle efficiently.

1. The invariant

Use a half-open interval:

[low, high)

At every step, the boundary is somewhere in that interval. Everything before low is known to be too small. Everything at or after high is already known to satisfy the condition.

The interval begins as:

low = 0
high = len

It ends when:

low == high

That single remaining position is the boundary. Keeping high exclusive makes the empty input and an insertion after the final element ordinary cases rather than exceptions.

2. Lower bound in Rust

The lower bound is the first index whose value is greater than or equal to the target:

fn lower_bound(values: &[i32], target: i32) -> usize {
    let mut low = 0;
    let mut high = values.len();

    while low < high {
        let middle = low + (high - low) / 2;

        if values[middle] < target {
            low = middle + 1;
        } else {
            high = middle;
        }
    }

    low
}

fn main() {
    let values = [3, 7, 11, 18, 24, 24, 42, 57, 68];

    assert_eq!(lower_bound(&values, 2), 0);
    assert_eq!(lower_bound(&values, 24), 4);
    assert_eq!(lower_bound(&values, 25), 6);
    assert_eq!(lower_bound(&values, 70), values.len());
}

Every branch preserves the invariant:

• If values[middle] < target, the boundary must be after middle.
• Otherwise, middle might be the boundary, so it remains included by setting high = middle.

Both branches shrink the interval. That progress argument is what prevents an infinite loop.

3. Exact lookup is a boundary plus a check

Once the lower bound is known, exact membership requires one safe comparison:

fn lower_bound(values: &[i32], target: i32) -> usize {
    let (mut low, mut high) = (0, values.len());
    while low < high {
        let middle = low + (high - low) / 2;
        if values[middle] < target { low = middle + 1; } else { high = middle; }
    }
    low
}
fn find(values: &[i32], target: i32) -> Option<usize> {
    let index = lower_bound(values, target);
    values.get(index).is_some_and(|&value| value == target).then_some(index)
}

fn main() {
    let values = [10, 20, 20, 30];
    assert_eq!(find(&values, 20), Some(1));
    assert_eq!(find(&values, 25), None);
}

This deliberately finds the first duplicate rather than merely any matching position.

4. Why it is logarithmic

After each comparison, at most half of the candidates remain:

n → n/2 → n/4 → n/8 → ... → 1

The number of halvings is O(log n). Searching one billion sorted values needs only about 30 comparisons.

The complete cost is:

Binary search makes lookup cheap; it does not make maintaining sorted storage cheap.

5. Common failure modes

• Mixing inclusive and exclusive bounds in one implementation.
• Updating low = middle when middle can equal low, preventing progress.
• Subtracting one from an unsigned zero index.
• Returning immediately on equality when the first duplicate is required.
• Forgetting that a valid insertion position can equal len.
• Applying the algorithm to a predicate that does not change monotonically.

Writing the invariant before writing the loop makes these bugs much easier to see.

6. Big-O is not the whole machine

Binary search jumps through memory and contains a data-dependent branch. A linear scan touches adjacent values and can be friendly to caches, prefetching, and SIMD. For a small collection, a scan can therefore beat binary search even though it performs more comparisons.

The practical rule is:

Use complexity to choose plausible algorithms, then measure representative sizes and data on the target machine.

This relationship between an abstract cost model and actual hardware is the bridge into the later machine-model and performance parts of the book.

7. What you should internalize

1. Binary search locates a boundary in a monotonic search space.
2. [low, high) contains every position that could still be the answer.
3. Every iteration must preserve the invariant and shrink the interval.
4. Lower bound turns exact search, insertion points, and duplicate handling into the same operation.
5. O(log n) comparisons do not guarantee the fastest result for tiny inputs.

Exercise

Implement upper_bound, the first index whose value is strictly greater than the target. Combine it with lower_bound to return the complete half-open range containing every duplicate. Test empty input, missing values, all-equal values, and targets before and after the stored range.

Sorting, Selection, and Top-K

Status Draft outlineSection Essential Algorithms

Ordering everything is often unnecessary. This chapter will compare full sorting, partial selection, and bounded top-k maintenance by the work and data movement each performs.

Planned model

Animate the same stream through a sort, quickselect-style partition, heap, and fixed-size insertion buffer. Track comparisons, swaps, allocations, and cache-line touches.

Questions

• When is sort_unstable preferable to preserving equal-item order?
• When does a heap beat sorting the whole input?
• How do nearly sorted, duplicated, or adversarial inputs change behavior?
• Which result is required: exact order, one rank, or an unordered top-k set?

Exercise

Choose an algorithm for retaining the ten largest values from an unbounded stream and defend its memory bound and update cost.

Scans, Two Pointers, and Sliding Windows

Status Draft outlineSection Essential Algorithms

Many linear-looking problems become truly linear once each boundary moves in only one direction.

Planned model

Move left and right cursors over one array while displaying the active invariant, elements entering or leaving the window, and the number of visits per element.

Questions

• What condition lets a pointer advance without later retreating?
• When does a window need a deque, counter map, or running aggregate?
• How do time-based windows differ from fixed-length windows?

Exercise

Maintain the maximum and total of the most recent n samples without rescanning the window after every arrival.

Prefix Aggregates and Incremental Computation

Status Draft outlineSection Essential Algorithms

Precomputed prefixes and incremental state exchange repeated work for stored summaries and carefully maintained invariants.

Planned model

Compare rescanning a range with prefix sums, a difference array, and a rolling update. Show build cost, query cost, update cost, and invalidated state.

Questions

• Which operations have inverses and can be removed from a running aggregate?
• When do Fenwick or segment trees become necessary?
• How can numerical error accumulate in floating-point running totals?

Exercise

Design a rolling volume calculation that supports arrivals, expirations, and occasional corrections.

Graph Traversal and Dependency Ordering

Status Draft outlineSection Essential Algorithms

Graphs model reachability, dependencies, routes, and state transitions. The representation and traversal frontier usually matter as much as the abstract algorithm.

Planned model

Run BFS, DFS, Dijkstra, and topological sorting over the same small graph while exposing the frontier, visited state, and adjacency reads.

Questions

• When is a queue, stack, or priority queue the correct frontier?
• What invariant makes a node final?
• How do dense and sparse representations change traversal cost?

Exercise

Detect a dependency cycle and produce a valid processing order when no cycle exists.

Greedy Scheduling and Queueing

Status Draft outlineSection Essential Algorithms

Greedy algorithms make an irreversible local choice. Their value comes from the invariant proving that the choice cannot make the final answer worse.

Planned model

Schedule the same jobs by arrival time, duration, deadline, and priority. Display queue growth, completed work, lateness, and counterexamples.

Questions

• What exchange argument justifies the local choice?
• When does priority create starvation?
• How do fairness, throughput, and latency goals conflict?

Exercise

Choose a policy for a bounded worker queue and construct a workload on which a plausible alternative fails.

Streaming and Online Algorithms

Status Draft outlineSection Essential Algorithms

An online algorithm must act before the full input is known; a streaming algorithm must usually do so with bounded memory.

Planned model

Feed an adjustable stream into exact counters, reservoir sampling, sketches, and online statistics. Show memory use and approximation error as data arrives.

Questions

• Which exact state must grow with the number of distinct values?
• What error guarantee does an approximation provide?
• How do event time, arrival time, and late data affect the result?

Exercise

Estimate a percentile or distinct count under a fixed memory budget and state precisely what accuracy is sacrificed.

Parsing and State Machines

Status Draft outlineSection Essential Algorithms

Protocol parsers turn bytes into state transitions while preserving framing, validation, and recovery invariants.

Planned model

Step through a fragmented byte stream. Display parser state, buffered bytes, completed messages, rejected input, and resynchronization points.

Questions

• How is a complete frame recognized across arbitrary chunk boundaries?
• Which lengths and offsets must be validated before slicing?
• Can parsing proceed without copying the payload?

Exercise

Implement an incremental length-prefixed parser that accepts partial frames and rejects oversized messages.

The Machine

Status In progress

This part builds the hardware model needed to explain real execution cost: representations, caches, layout, prediction, address translation, allocation, vector execution, topology, and clocks.

It explains why two programs with the same big-O complexity can have dramatically different latency.

Integer and Floating-Point Representation

Status Draft outlineSection The Machine

Bits acquire meaning only through an agreed representation. That choice determines range, rounding, overflow, exceptional values, and comparison behavior.

Planned model

Let the reader edit a bit pattern and interpret it as unsigned, two’s-complement, fixed-point, and IEEE-754 data. Expose sign, exponent, fraction, rounding, and overflow.

Questions

• Why is decimal money commonly represented with scaled integers?
• When does wrapping, checked, saturating, or overflowing arithmetic fit?
• Why are NaN, signed zero, and non-associativity operational concerns?

Exercise

Choose a representation for prices and quantities, including scale, maximum range, rounding policy, and overflow handling.

Memory Hierarchy — Where Data Becomes Time

The cost of reading a value depends on where its cache line is, what arrived beside it, and whether the processor can find useful work while it waits.

Section The MachineModel Cache lines and localityGoal Predict data movement

Start with a packed sequential scan and press Run. Then change only storage to Scattered nodes. Both experiments visit the same logical records and do the same O(n) work; their physical line traffic is very different.

The lab uses 16-byte useful records and 64-byte cache lines. A packed line holds four adjacent records. A scattered node occupies a different conceptual line, leaving the other 48 bytes unused. Real allocators and nodes have more varied layouts, but this contrast isolates spatial locality.

A latency ladder

The hierarchy exists because no single storage technology is simultaneously the smallest, fastest, cheapest, and largest. Capacity increases as we move away from the execution units; latency usually increases with it.

These are intentionally broad orientation ranges. A reported cache latency must name the processor and clarify whether it is load-to-use latency, sustained throughput, dependent access, or an overlapped stream. DRAM depends on memory frequency, controllers, queueing, row state, and NUMA placement. Persistent storage is included to show scale; it is not a CPU cache level.

At 3 GHz, one cycle is about one third of a nanosecond. A 4-cycle L1 hit and a 90-nanosecond DRAM access therefore differ by roughly two orders of magnitude. The processor may overlap independent misses, so latency is not the same as achievable bandwidth.

What the levels mean

“L3” and “last-level cache” are often the same level on a server CPU, but not universally. Cache topology, private/shared boundaries, and inclusivity vary. Query the target machine and consult its processor documentation instead of building software around this representative table.

CPU caches are generally built from fast on-chip SRAM-like structures. Main memory uses denser DRAM located beyond the core and usually beyond the CPU die. An SSD is storage, not slower DRAM: ordinary CPU loads do not directly fetch its bytes into registers. Data travels through an I/O and operating-system path before the processor can consume it as memory.

When this matters

Memory locality matters whenever a hot loop performs little arithmetic compared with the data it touches. Common examples include:

• Feed handlers parsing large buffers.
• Order books, indexes, graphs, and lookup tables.
• Queues and progress counters shared between cores.
• Batch calculations over many records.
• Any latency-sensitive path whose working set does not remain in the nearest cache.

The first question should not be “which clever instruction should I use?” It is:

Which cache lines must move for this operation, and how much useful work does each transferred line enable?

1. Memory is a hierarchy

A core can access several storage levels. Names and topology vary by processor, but the durable relationship is:

registers
    ↓
small per-core caches
    ↓
larger private or shared caches
    ↓
main memory

Levels nearer the core are smaller and generally faster. When a required line is absent, hardware obtains it from a farther level. Independent instructions may overlap some of that delay; a dependent instruction must wait for its input.

That is why “one array access” is not a stable unit of time.

2. The transfer unit is a line

Processors normally move aligned blocks called cache lines between cache levels. A 64-byte line is common on contemporary general-purpose processors, but it is not a universal language-level guarantee.

Requesting one 8-byte field can fetch the surrounding line. This produces two possible outcomes:

• Nearby values are used soon, amortizing the transfer.
• The program jumps elsewhere and most transferred bytes are wasted.

The lab’s fetched-line use metric counts how many distinct 16-byte records are used from each line load. Re-reading the same hot record can produce cache hits, but it does not retroactively make unused neighboring bytes useful. Hit rate and line utilization describe different properties.

3. Spatial and temporal locality

Spatial locality means accessing nearby addresses. A packed sequential scan misses on the first record of a line, then can hit on the next three.

Temporal locality means reusing the same data soon. Select Repeat four hot records. If the cache can retain the required lines, later passes hit even when the broader data set is large.

These properties can work independently:

4. Logical order is not physical layout

A language-level sequence describes logical order. Hardware observes addresses.

packed array:
line 0: [record 0][record 1][record 2][record 3]
line 1: [record 4][record 5][record 6][record 7]

scattered nodes:
line 0: [record 7][unused........................]
line 1: [record 2][unused........................]
line 2: [record 11][unused.......................]

Walking logical records 0, 1, 2, 3 can therefore touch one line or four unrelated lines. The algorithm has not changed; its representation has.

5. Working-set size determines whether reuse survives

A working set is the data needed over a relevant interval. Temporal locality helps only while the reused lines remain close enough to the core.

The lab uses a tiny fully associative cache with least-recently-used replacement:

1. A hit moves the line to the most-recently-used end.
2. A miss inserts the new line.
3. If capacity is full, the least-recently-used line is evicted.

Real caches are divided into sets and ways, so addresses can conflict even when the total number of lines appears to fit. The simplified model demonstrates capacity pressure without pretending to model a specific CPU.

Three broad causes are useful when reasoning about misses:

• Compulsory: the line has not been loaded yet.
• Capacity: the active data exceeds available cache space.
• Conflict: limited placement choices evict lines that could fit in a fully associative cache of the same size.

6. Pointer chasing adds a dependency chain

A pointer-linked traversal conceptually performs:

load node
    → discover address of next node
        → load next node

The processor cannot know the next address until the current node arrives. A sequential array exposes future addresses immediately, allowing hardware prefetchers and out-of-order execution to look ahead.

The lab changes access order when Pointer chase is selected, but it cannot model elapsed cycles or memory-level parallelism. Its miss count shows only one part of the disadvantage; the dependency chain can make the same misses harder to overlap.

7. Same big-O, different traversal

These functions both visit every matrix element and perform O(rows × columns) work. The matrix is stored in row-major order:

#![allow(unused)]
fn main() {
fn row_major_sum(values: &[u64], rows: usize, columns: usize) -> u64 {
    let mut total = 0;
    for row in 0..rows {
        for column in 0..columns {
            total += values[row * columns + column];
        }
    }
    total
}

fn column_major_sum(values: &[u64], rows: usize, columns: usize) -> u64 {
    let mut total = 0;
    for column in 0..columns {
        for row in 0..rows {
            total += values[row * columns + column];
        }
    }
    total
}
}

The first consumes adjacent values. The second jumps by an entire row. Their asymptotic complexity is identical; line traffic, prefetch behavior, and observed latency can differ substantially.

Do not infer a universal speed ratio. Matrix dimensions, cache geometry, compiler optimization, prefetching, and surrounding work all affect the result.

8. Representation is a performance decision

Contiguous storage usually offers:

• Fewer allocations and less metadata.
• Predictable addresses.
• More useful values per transferred line.
• Easier batching, prefetching, and vectorization.

Node-, handle-, and pointer-based structures still earn their place when stable identity, structural mutation, or another required operation outweighs traversal cost. “Arrays are faster” is not a complete design argument. State the workload, invariants, mutation costs, and evidence.

This also explains why a VecDeque frequently traverses faster than a linked list, why an arena can improve both stable identity and locality, and why order book implementations often separate stable handles from densely stored fields.

9. What the lab deliberately omits

Real memory behavior also depends on:

• Several cache levels and inclusive or exclusive policies.
• Set associativity and address-to-set mapping.
• Hardware and software prefetching.
• Translation lookaside buffers and page walks.
• Store buffers, write allocation, and coherence.
• Memory-level parallelism and outstanding misses.
• NUMA placement and remote memory.
• Other threads, interrupts, migrations, and power state.
• Compiler reordering, vectorization, and dead-code elimination.

Later chapters isolate those mechanisms. A useful model is small enough to predict and explicit about what it cannot conclude.

10. How to measure this on real hardware

A defensible experiment should:

1. Generate identical useful results for each layout.
2. Prevent the optimizer from deleting the work.
3. Sweep working-set size across expected cache boundaries.
4. Separate cold-start behavior from steady state.
5. Record traversal order, element size, alignment, and allocation method.
6. Inspect elapsed time together with relevant hardware counters.
7. Repeat under realistic contention and CPU placement.

Counter names and interpretations are processor-specific. Begin with the vendor’s current optimization and performance-monitoring documentation, then confirm what your profiler actually programs.

11. What you should internalize

1. A load is cheap or expensive depending on where its line currently resides.
2. Hardware transfers lines, not isolated language-level fields.
3. Spatial locality reuses neighboring bytes from one transfer.
4. Temporal locality helps only while the working set remains resident.
5. Logical order does not determine physical layout.
6. Pointer chasing can combine poor locality with serialized address discovery.
7. Equal big-O complexity does not imply equal data movement or latency.
8. Hit rate and fetched-line utilization answer different questions.
9. Compact predictable representations are strong defaults, not universal laws.
10. Hardware counters and controlled experiments decide whether the model explains the real workload.

Retrieval drill

Assume 64-byte lines, 16-byte packed records, and an initially empty cache:

1. How many compulsory line misses occur while scanning records 0..12?
2. After reading record 4, which other records arrived in the same line?
3. Why can four scattered nodes require four transfers even if their payloads total only 64 bytes?
4. With a three-line cache, what happens while repeatedly accessing four lines in strict rotation?
5. Why can a pointer chase be slower than an array scan even when both report the same number of last-level cache misses?

Sources

• Denis Bakhvalov et al., Performance Analysis and Tuning on Modern CPUs
• Intel 64 and IA-32 Architectures Optimization Reference Manual
• AMD performance-tuning documentation

Vendor manuals describe particular processors. The chapter’s claims remain conceptual unless an experiment names the target CPU, counters, software, and configuration.

Data Layout — Which Bytes Move Together?

The same logical records can place hot fields together, scatter them across columns, or carry cold bytes through every cache line.

Section The MachineModel AoS, SoA, and hot/cold splittingGoal Match representation to access

Run a Price-only scan with each layout. Then select Matching path, which reads price, quantity, and order ID. The useful computation is unchanged; only the physical grouping of bytes changes.

The model contains eight logical orders. Each order has 56 useful bytes:

price 8 | quantity 8 | timestamp 8 | order ID 8 | metadata 24

The AoS layout can use a 56-byte packed stride or an explicitly 64-byte-aligned stride with 8 bytes of tail padding. The SoA layout groups equal fields. The hot/cold layout keeps four 8-byte hot fields together and moves the 24-byte metadata into a separate region.

When layout becomes a design decision

Layout deserves attention when:

• Hot loops process large batches.
• Most operations read only a subset of each record.
• The working set competes for cache capacity or memory bandwidth.
• SIMD-friendly homogeneous inputs matter.
• Cold metadata inflates critical-path records.
• Separate threads write different fields and may false-share lines.
• Profiling attributes meaningful time to loads, misses, or stalled execution.

A specialized layout adds API and mutation invariants. It should earn that cost through a known access pattern and measurement.

1. Array of structures keeps records together

An array of structures stores one complete record after another:

[P0 Q0 T0 I0 M0...] [P1 Q1 T1 I1 M1...] ...

The direct Rust representation is a Vec<Order>:

#![allow(unused)]
fn main() {
#[derive(Clone)]
struct Order {
    price: u64,
    quantity: u64,
    timestamp: u64,
    id: u64,
    metadata: [u64; 3],
}

fn matching_checksum(orders: &[Order]) -> u64 {
    orders
        .iter()
        .map(|order| order.price ^ order.quantity ^ order.id)
        .sum()
}
}

AoS is natural when an operation consumes or transfers one complete record. The type system keeps the fields together, and insertion or removal changes one collection.

A narrow scan may fetch mostly irrelevant bytes. With a 64-byte-aligned record, reading an 8-byte price uses one eighth of every transferred line.

2. Structure of arrays keeps fields together

A structure of arrays stores each field in a separate contiguous sequence:

[P0 P1 P2 P3 ...]
[Q0 Q1 Q2 Q3 ...]
[T0 T1 T2 T3 ...]
[I0 I1 I2 I3 ...]
[M0 M1 M2 M3 ...]

#![allow(unused)]
fn main() {
struct OrderColumns {
    prices: Vec<u64>,
    quantities: Vec<u64>,
    timestamps: Vec<u64>,
    ids: Vec<u64>,
    metadata_0: Vec<u64>,
    metadata_1: Vec<u64>,
    metadata_2: Vec<u64>,
}

impl OrderColumns {
    fn len(&self) -> usize {
        self.prices.len()
    }

    fn invariant_holds(&self) -> bool {
        let len = self.len();
        self.quantities.len() == len
            && self.timestamps.len() == len
            && self.ids.len() == len
            && self.metadata_0.len() == len
            && self.metadata_1.len() == len
            && self.metadata_2.len() == len
    }
}
}

A price scan now transfers dense prices without order IDs or metadata. Separate homogeneous arrays can also give a compiler straightforward vector inputs.

The representation introduces a central invariant:

prices.len == quantities.len == timestamps.len == ids.len
           == metadata_0.len == metadata_1.len == metadata_2.len

Insertion, removal, permutation, error handling, and recovery must preserve row identity across every column. Hiding the columns behind an API is part of making the representation correct.

3. Hot/cold splitting is often the practical middle

Many systems are neither purely record-oriented nor purely analytical. A hybrid keeps critical fields compact and resolves cold information only when needed:

hot orders:  [P Q T I] [P Q T I] [P Q T I] ...
cold table:  [metadata] [metadata] [metadata] ...

The lab’s hot record is 32 bytes, so two fit in a 64-byte line. The matching-path scan uses three quarters of the hot bytes it fetches while avoiding metadata.

The costs are another lookup and an identity/lifetime relationship between the two regions. Stable handles or dense indices can connect them; ordinary borrowed references cannot outlive a relocation of either backing collection.

4. Alignment and padding are different ideas

Alignment restricts the addresses at which a value may begin. Padding is unused space inserted between fields or at the end of a value so alignment and stride constraints are satisfied.

Consider a stable C-compatible layout:

#![allow(unused)]
fn main() {
#[repr(C)]
struct Message {
    kind: u8,
    sequence: u64,
    side: u8,
}
}

The u64 normally requires stronger alignment than u8, so padding can appear before sequence and after side. Reordering fields may reduce size, but it can also change ABI and wire compatibility.

Explicit cache-line alignment is a much stronger choice:

#![allow(unused)]
fn main() {
#[repr(C, align(64))]
struct AlignedCounter {
    value: std::sync::atomic::AtomicU64,
}
}

The alignment can isolate independently written counters, but it also expands their stride and working set. Alignment is not free speed; it trades density for placement guarantees.

In C++, the corresponding tools include alignas, sizeof, and alignof. Always inspect the compiled target rather than inferring byte offsets from how the declaration looks.

5. Field order changes holes and line crossings

For a representation with a specified field order, placing strongly aligned fields first can reduce internal holes:

less compact:  u8 | padding | u64 | u8 | tail padding
more compact:  u64 | u8 | u8 | tail padding

Minimum total size is not always the objective. You might deliberately:

• Keep fields read together on the same line.
• Separate fields written by different threads.
• Align the beginning of a batch for vector loads.
• Pad a ring entry to a fixed protocol or device descriptor size.
• Move rarely inspected diagnostic state out of the hot record.

The best field order follows access and ownership, not aesthetic sorting.

6. Cache-line boundaries are shared-resource boundaries

Two objects can be logically independent while occupying one physical line. If different cores repeatedly write them, coherence operates on the entire line. That is false sharing: no source-level variable is shared, but the cache line is.

Padding can separate writers, yet padding every object may make reads worse by reducing density. The later Coherence and False Sharing chapter will model ownership transfer between cores.

7. Layout and vectorization

SIMD instructions apply one operation to several lanes. Dense homogeneous values are convenient inputs:

prices: [100, 101, 102, 103, 104, 105, 106, 107]

Interleaved AoS fields may need shuffles or gathers before the arithmetic. Modern processors support increasingly capable gather operations, but “vectorizable” does not automatically mean “faster”: setup, masks, tails, code size, and memory traffic still matter.

Inspect optimized output and measure the representative batch. The SIMD chapter develops this separately.

8. Mutation can reverse the apparent winner

A scan benchmark can make SoA look universally superior while ignoring updates:

• Inserting one logical row modifies every column.
• Removing by swap changes row identity unless indices are repaired.
• Stable external handles need an indirection or generation scheme.
• Exception or allocation failure can leave partially updated columns in C++ if the operation is not transactional.
• Concurrent readers need a publication rule covering every related column.

AoS often makes row-level mutation simpler. Hot/cold splitting can keep the hot index stable while cold data follows a separate lifecycle. Representation must be evaluated over its complete workload, not one attractive scan.

9. In-memory layout is not a wire or storage format

Rust’s default representation does not promise stable field order for foreign interfaces or persistence. #[repr(C)] supplies C-compatible layout rules, but padding still exists and endianness is not solved. C++ object layout likewise does not turn an arbitrary object into a portable packet.

Do not serialize structs by dumping their memory unless the format explicitly defines every byte and the implementation safely enforces that contract. Network messages and durable data require explicit field widths, byte order, versioning, and validation.

10. How to choose with evidence

Benchmark at least the following dimensions:

1. The real ratio of narrow scans, matching-path reads, full reads, and mutations.
2. Working sets below and above expected cache capacities.
3. Cold-start and steady-state behavior.
4. Useful bytes versus transferred bytes.
5. Scalar and vectorized implementations.
6. Allocation and compaction costs.
7. Single-threaded access and realistic cross-core ownership.
8. Tail latency under the target load, not only maximum scan throughput.

Use compiler layout reports, size_of/align_of, optimized assembly, and hardware counters to test the model. Do not infer a processor’s cache traffic solely from the source type.

11. What you should internalize

1. Logical records do not dictate one physical layout.
2. AoS keeps records together; SoA keeps fields together.
3. Hot/cold splitting is a useful third design, not a compromise to ignore.
4. Alignment restricts placement; padding consumes bytes to satisfy placement or stride decisions.
5. Smaller types do not guarantee a smaller struct when holes dominate.
6. Field-only scans can waste most bytes in an AoS line.
7. SoA introduces cross-column identity and mutation invariants.
8. Cache lines define coherence traffic as well as transfer size.
9. In-memory, wire, and persistent layouts are separate contracts.
10. The winning layout is the one that serves the complete measured workload.

Retrieval drill

Using the lab’s eight-record model:

1. Why does a price-only SoA scan need one line?
2. Why can 64-byte AoS alignment reduce price-scan utilization to 12.5%?
3. Which bytes move during the matching workload under the hot/cold layout?
4. What invariant must a SoA removal preserve?
5. When could adding padding lower cross-core latency while raising scan latency?

Sources

• Rust Reference: type layout
• Denis Bakhvalov et al., Performance Analysis and Tuning on Modern CPUs
• Intel 64 and IA-32 Architectures Optimization Reference Manual

The examples establish reasoning tools, not a universal ABI or cache geometry. Confirm sizes, offsets, alignments, generated code, and counters for the exact compiler and processor used in an experiment.

Branch Prediction — When Control Flow Becomes Data-Dependent

A pipelined CPU encounters a conditional branch before it necessarily knows which path the program will take. It predicts the outcome so useful work can continue; a wrong prediction discards speculative work and redirects execution.

The simulator uses one two-bit saturating counter. States zero and one predict not taken; states two and three predict taken. Each observed outcome moves the counter one step toward that outcome. Real processors use multiple predictors, branch and path histories, target prediction, and other mechanisms. The small model teaches adaptation and hysteresis without pretending to reproduce a particular CPU.

When branch behavior matters

Branch behavior becomes relevant when:

• A small loop executes the same conditional millions of times.
• Outcomes depend on irregular input data.
• Profiling attributes meaningful stalls or branch misses to the loop.
• Validation, parsing, filtering, or dispatch dominates the critical path.
• A latency-sensitive operation has little independent work to hide recovery.

Do not eliminate every if. Predictable branches can be inexpensive, and a branchless replacement can perform more instructions, more loads, or more work on both paths. Begin with clear control flow and optimize measured hotspots.

1. Why prediction exists

Modern high-performance cores overlap and reorder work from multiple instructions. A conditional branch creates two possible future instruction streams:

condition
   ├─ true path
   └─ false path

Waiting for every condition to resolve before fetching later instructions would leave execution resources idle. The processor predicts a path and works ahead. When correct, much of that work remains useful. When wrong, younger speculative work is abandoned and the correct path must be supplied.

The recovery cost is not one universal number. It depends on the processor, the surrounding dependency chain, available parallel work, and how early the condition becomes known.

2. A two-bit predictor

One bit would reverse its prediction after a single unusual outcome. A two-bit counter adds hysteresis:

0  strongly not taken
1  weakly not taken
2  weakly taken
3  strongly taken

For a taken outcome:

state = min(3, state + 1)

For a not-taken outcome:

state = max(0, state - 1)

A predictor in a strong state needs two consecutive contrary outcomes before its predicted direction changes. That resists occasional noise while still adapting when behavior changes.

3. Patterns are easier or harder to predict

Grouped outcomes

N N N N N N T T T T T T

The predictor stabilizes, misses near the transition, then stabilizes again.

Mostly one direction

T T T N T T T T N T T T

Occasional exceptions may cause isolated misses without changing the long-term prediction.

Alternating outcomes

T N T N T N T N T N T N

The simple counter has too little history to recognize alternation. More sophisticated predictors can learn patterns that this model cannot.

The durable lesson is not that one data ordering is always fastest. It is that the sequence of outcomes—not merely the number of branches—affects prediction.

4. Ordinary code produces data-dependent branches

Consider a threshold count:

fn count_at_or_above(values: &[u32], threshold: u32) -> usize {
    let mut count = 0;

    for &value in values {
        if value >= threshold {
            count += 1;
        }
    }

    count
}

fn main() {
    let grouped = [1, 2, 3, 4, 90, 91, 92, 93];
    let mixed = [1, 90, 2, 91, 3, 92, 4, 93];

    assert_eq!(count_at_or_above(&grouped, 50), 4);
    assert_eq!(count_at_or_above(&mixed, 50), 4);
}

Both inputs perform the same comparisons and have the same big-O complexity. Their branch outcome sequences differ. Whether that produces a material timing difference depends on the compiled instructions and target processor.

Compilers can sometimes convert simple conditions into conditional moves, masks, or vector operations. Source-level if does not prove that the final machine code contains a hard-to-predict branch.

5. Branchless is a tradeoff, not a goal

A programmer might express the count as arithmetic on a boolean:

fn count_at_or_above(values: &[u32], threshold: u32) -> usize {
    values
        .iter()
        .map(|&value| usize::from(value >= threshold))
        .sum()
}

fn main() {
    assert_eq!(count_at_or_above(&[1, 90, 2, 91], 50), 2);
}

This source shape may encourage a non-branching implementation, but the compiler and target architecture decide the emitted instructions. Even truly branchless code is not automatically faster:

• It may execute work that a correct branch would skip.
• It can lengthen a dependency chain.
• It may need extra masks, moves, or loads.
• Computing both paths can be unsafe when one path must not access invalid data.
• Predictable control flow may already perform well.

Treat branchless transformation as a hypothesis to compile, inspect, and measure—not as a stylistic improvement.

6. Changing data order has a cost

Grouping similar outcomes can improve predictability, but rearranging input may require sorting, buffering, or extra latency. It may also violate semantic order or make another stage’s locality worse.

Batching is valuable when the system naturally permits it. For example, a pipeline may classify a batch once and then process homogeneous groups. A single-record latency path may not have that freedom.

Optimization must include the cost and correctness constraints of producing the new order, not only the speed of the final loop.

7. Measuring branch effects

Useful evidence can include:

• Optimized machine code for the hot loop.
• Hardware performance counters for retired branches and branch misses.
• A benchmark using representative outcome distributions.
• End-to-end latency distributions, not only loop throughput.
• Tests across the actual deployment CPUs and compiler configuration.

Avoid benchmarks whose inputs are constant enough for the compiler to remove the work or whose tiny data set accidentally measures one predictor warm-up instead of steady behavior.

8. What you should internalize

1. Prediction lets a pipelined core continue before a branch resolves.
2. A wrong prediction discards speculative work and redirects execution.
3. Outcome sequences influence predictability.
4. A two-bit counter demonstrates adaptation and hysteresis, not a modern CPU’s complete predictor.
5. Source-level branches may compile into other forms.
6. Branchless code can do more work and is not universally faster.
7. Optimize only after inspecting and measuring the actual hot path.

Exercise

Start the two-bit predictor in state one and trace the outcomes T, T, N, T, N, N, N. Record the prediction, correctness, and next state for each outcome. Then design a different seven-outcome sequence that causes more mispredictions without changing the number of taken outcomes.

Virtual Memory — Pages, Page Tables, and the TLB

A program uses virtual addresses. Before the CPU can access memory, each virtual address must be translated into a physical location. Page tables define the mapping; the translation lookaside buffer caches recently used translations.

The simulator uses five virtual pages, conceptual 4 KiB pages, a three-entry fully associative TLB with least-recently-used replacement, and a one-level page table. Every page is already resident in memory. Real systems use architecture- specific page sizes, multi-level tables, multiple TLBs, set associativity, and more complex replacement behavior.

When virtual-memory behavior matters

Translation becomes relevant when:

• A hot loop touches a large number of pages.
• Access jumps unpredictably across a large working set.
• Tail latency is sensitive to first-touch page faults.
• Threads migrate between cores and lose core-local translation state.
• Huge pages, memory locking, or NUMA placement are being considered.
• Profiling reports translation misses, page walks, or page faults.

Do not tune page behavior from folklore. Page size, TLB structure, operating- system policy, and available counters vary by platform. Measure the deployed hardware and workload.

1. Virtual addresses separate programs from physical placement

Each process operates in a virtual address space. The same virtual address in two processes can refer to different physical memory. The operating system and hardware use page tables to establish mappings and permissions.

Virtual memory enables:

• Isolation between processes.
• Per-page read, write, and execute permissions.
• Sparse address spaces.
• Shared mappings when explicitly configured.
• Moving or replacing physical storage without changing every program pointer.

The abstraction is powerful, but every memory access still needs a translation.

2. Split an address into page number and offset

For a power-of-two page size, a virtual address divides into:

virtual address = virtual page number | offset within page

With a conceptual 4 KiB page:

virtual_page = address / 4096
offset       = address % 4096

The page table maps the virtual page number to a physical frame number. The offset does not change:

VPN 2 + offset 192
    ↓ page-table mapping
frame 7 + offset 192

Translation changes which page-sized frame is used, not the position within that frame.

3. Page tables are too expensive to consult naively

Page tables live in memory and are commonly hierarchical. Walking them can require several dependent memory references before the original load or store can be completed.

If every ordinary access performed a full page-table walk, translation would dominate execution. Hardware therefore caches translations in the translation lookaside buffer, or TLB.

Conceptually:

virtual page ──TLB hit──────────────▶ physical frame
             └─TLB miss─▶ page table ─▶ physical frame + cache translation

A TLB hit avoids the walk. A TLB miss does not mean that the requested data is absent from physical memory.

4. A TLB miss is not a page fault

These events answer different questions:

A page can be fully resident and still miss in the TLB. The page-table walk finds a valid mapping, fills the TLB, and retries or completes the access.

A page fault transfers control to the operating system. Some faults establish a mapping for an already available physical page; others may require allocating, zeroing, copying, or obtaining data from storage. Their cost and behavior differ dramatically.

5. Translation has a working set

The TLB can cover only a finite number of pages at once. A loop whose active pages fit can warm its translations and reuse them. A loop cycling through more pages than the relevant TLB can hold may repeatedly replace entries.

The amount of virtual memory covered by a TLB is often called its reach:

TLB reach ≈ number of usable entries × page size

This is a conceptual estimate. Multiple page sizes, associativity, conflicts, and separate instruction/data structures complicate actual coverage.

6. Data layout affects translation too

Cache locality asks whether useful bytes share cache lines. Translation locality asks whether useful addresses share pages whose mappings remain cached.

A contiguous batch can provide both:

• Neighboring values reuse cache lines.
• Many accesses reuse one page translation.
• Sequential page crossings can be predictable.

A large pointer-linked structure can scatter nodes across many pages. That may increase cache misses and translation misses together. Allocation policy and data layout therefore influence more than one level of the machine.

7. First touch and prefaulting

Reserving virtual address space does not necessarily mean every page already has private physical storage behind it. The first access can trigger mapping, allocation, or zeroing work depending on the operating system and allocation.

A latency-sensitive service may deliberately initialize and touch its working memory before entering the critical path. That moves predictable setup work out of later requests. It does not guarantee that pages can never fault again, and the exact behavior remains platform-specific.

This function touches one byte per caller-supplied page interval:

fn touch_each_page(bytes: &mut [u8], page_size: usize) {
    assert!(page_size > 0);
    for index in (0..bytes.len()).step_by(page_size) {
        bytes[index] = bytes[index].wrapping_add(1);
    }
}

fn main() {
    let mut storage = vec![0_u8; 16 * 1024];
    touch_each_page(&mut storage, 4096);
    assert_eq!(storage[0], 1);
    assert_eq!(storage[4096], 1);
    assert_eq!(storage[8192], 1);
    assert_eq!(storage[12288], 1);
}

The page size is an input because production code should obtain platform facts deliberately rather than assume the book’s conceptual size.

8. Huge pages trade granularity for reach

Larger pages let one TLB entry cover more memory. They can reduce translation pressure for large, stable working sets. They also increase allocation granularity and can complicate availability, fragmentation, startup, deployment, and memory waste.

Huge pages are not a universal low-latency switch. They are an operational and measurement decision with platform-specific configuration and failure modes.

9. Memory locking and CPU pinning solve different problems

Memory locking aims to keep selected mappings resident according to operating- system policy. CPU affinity constrains where a thread may run. Neither action automatically provides the other:

• Pinning a thread does not ensure all of its pages are resident.
• Locking memory does not keep a thread on one core.
• Both can still leave cache, TLB, NUMA, interrupt, and scheduling effects.

Later chapters treat memory locking, NUMA placement, scheduling, and CPU isolation as separate mechanisms that must be designed together.

10. What you should internalize

1. Programs issue virtual addresses; hardware translates them to physical locations.
2. The page offset remains unchanged during translation.
3. Page tables define mappings and permissions.
4. The TLB caches page translations.
5. A TLB miss can cause a page-table walk without causing a page fault.
6. Translation has a finite working set just as data caches do.
7. Contiguous layouts can improve cache-line and page-translation locality.
8. First touch, huge pages, locking, and affinity are distinct mechanisms.
9. Platform measurements must guide low-level memory policy.

Exercise

Using a three-entry fully associative TLB initially empty, trace the virtual-page sequence 0, 1, 2, 0, 3, 0, 1, 2. Apply least-recently-used replacement and record every hit, walk, and eviction. Then repeat with four entries and explain which behavior changes and which does not.

Allocation — General Heaps, Pools, and Predictable Reuse

Status Draft outlineSection The Machine

Dynamic allocation finds storage for values whose size or lifetime is decided at runtime. The allocator’s policy affects bookkeeping, reuse, fragmentation, locality, synchronization, and the possibility of slow paths.

This chapter will compare three deliberately different lifetime models rather than treating “allocation” as one operation.

Planned interactive model

The simulator will offer the same sequence of requests to three allocators:

general allocator    variable-size blocks; allocate and free individually
fixed-size pool      equal-size slots; reuse through a free list
bump arena           advance one pointer; release the region as a unit

Planned controls:

• Choose general allocator, object pool, or bump arena.
• Allocate small, medium, or large objects.
• Free an individual object when the model permits it.
• Reset the entire region.
• Run identical scripted workloads across all three models.

The visual state should expose:

• Occupied and free regions.
• Reused slots.
• Internal and external fragmentation.
• Bookkeeping operations.
• Capacity exhaustion.
• Individual cleanup versus bulk cleanup.

The simulator will be a conceptual model, not a claim about a particular Rust global allocator or operating-system implementation.

Questions the chapter should answer

• What does Box, Vec, or String actually request from an allocator?
• Why can allocation latency vary?
• When does freeing memory make it reusable without returning it to the OS?
• How do size classes and free lists reduce search cost?
• What is the difference between internal and external fragmentation?
• Why can pools improve predictability and locality?
• Why is a bump arena cheap, and what lifetime restriction buys that speed?
• When can thread-local allocation avoid shared contention?
• Which costs come from the allocator, virtual memory, first touch, or object initialization?
• When is preallocation simpler than replacing the allocator?

Proposed structure

1. “Heap” has two meanings

Separate the process’s dynamic-allocation region from the BinaryHeap data structure. They share a historical word, not an implementation.

2. The allocation request

Introduce size, alignment, lifetime, initialization, and ownership as distinct concerns. Show that reserving bytes and constructing a Rust value are related but different operations.

3. General-purpose allocators

Explain variable-size requests, size classes, metadata, free lists, splitting, coalescing, and why an implementation balances average throughput, memory use, and concurrency rather than guaranteeing one fixed latency.

4. Fixed-size object pools

Model a collection of equal-size slots and a free list. Connect the design to orders, messages, descriptors, tasks, and other bounded object populations.

Discuss exhaustion policy explicitly:

reject | fall back | block | grow | shed work

5. Bump arenas

Allocate by advancing an offset. Explain why individual removal is normally absent and why resetting or dropping the whole arena is cheap.

Connect the model to parsing, request-scoped scratch space, compilation phases, and batch processing.

6. Fragmentation

Distinguish:

• Internal fragmentation: unused bytes inside an allocated block or size class.
• External fragmentation: free space exists but is divided into unsuitable regions.

Also separate virtual address-space fragmentation from committed physical memory and allocator-visible blocks.

7. Locality and first touch

Tie allocation back to cache lines, pages, TLB entries, and NUMA placement. Objects allocated near one another are not automatically used near one another; lifetime grouping and access grouping may disagree.

8. Concurrency and allocator state

Describe shared locks, atomic metadata, per-thread caches, remote frees, and the tradeoff between reducing contention and retaining more memory in local caches.

9. Rust ownership and destruction

Cover:

• Allocation versus initialization.
• Moving an owning handle versus moving the allocation.
• Drop order and bulk destruction.
• Pools that return handles instead of long-lived references.
• Why unsafe custom allocators require stronger invariants than a container.

10. Preallocation before specialization

Show the ordinary tools to try first:

• Vec::with_capacity
• Reusing buffers with clear
• Keeping scratch storage across iterations
• Bounded queues
• Slabs and generational arenas

The central rule should be:

Remove allocation from a measured critical path by controlling capacity and lifetime before reaching for a custom allocator.

11. Measurement plan

The finished chapter should distinguish:

• Warm allocator throughput.
• Cold page and first-touch behavior.
• Single-threaded versus contended allocation.
• Typical latency versus tail latency.
• Allocation cost versus initialization and destruction.
• Memory retained, committed, and actively used.

Candidate Rust examples

• Reuse a Vec buffer without discarding its capacity.
• Implement a small fixed-capacity pool with a free list.
• Implement a safe bump arena for byte slices with one bulk reset point.
• Compare handle-based removal with borrowed references.
• Make exhaustion an explicit Result rather than an accidental allocation.

Planned exercise

Given a pipeline that holds at most 8,192 fixed-size messages, design a pool and its exhaustion policy. State which operations must be constant-time, which thread owns allocation and reclamation, how stale handles are prevented, and what happens when the producer outruns the consumer.

Open decisions

• Whether to introduce allocator APIs or remain at the container/pool level.
• Whether the main pool example should be single-threaded or SPSC-owned.
• Whether fragmentation deserves its own animation.
• Whether NUMA-aware allocation belongs here or in the later NUMA chapter.
• Which measurement tools belong here versus the performance-engineering section.

SIMD and Vectorization

Status Draft outlineSection The Machine

Single-instruction, multiple-data execution applies one operation across several lanes, provided data layout and control flow expose enough independent work.

Planned model

Compare scalar and lane-based processing. Animate loads, masks, horizontal reductions, tail handling, and the effect of aligned contiguous data.

Questions

• Which loops can the compiler auto-vectorize?
• How do branches become masks?
• When do gathering, shuffling, and horizontal reduction erase the gain?

Exercise

Reshape a scalar filter-and-sum loop so its data dependencies and remainder handling are explicit.

NUMA and Memory Placement

Status Draft outlineSection The Machine

In a NUMA system, memory latency depends on which CPU accesses which physical pages. CPU placement and memory placement therefore form one decision.

Planned model

Place threads and pages on two sockets, then animate local and remote accesses, interconnect traffic, first-touch placement, and migration.

Questions

• Who determines a page’s initial NUMA node?
• When does replication beat shared remote access?
• How can a thread be pinned correctly while its data remains remote?

Exercise

Partition a read-mostly table and mutable worker state across two sockets and explain every cross-node access that remains.

Hardware Clocks and Timestamp Counters

Status Draft outlineSection The Machine

Measuring short intervals requires knowing what a clock counts, whether cores agree, how reads are ordered, and how ticks become time.

Planned model

Compare a timestamp counter, monotonic OS clock, and wall clock while injecting frequency conversion, read overhead, migration, drift, and clock adjustment.

Questions

• What distinguishes monotonic time from civil time?
• When must instruction execution be ordered around a timestamp read?
• How should clock overhead and resolution be measured?

Exercise

Design a microbenchmark timer that reports its own read overhead and rejects samples affected by migration or preemption.

Operating Systems and Execution

Status Draft

This part follows work across privilege boundaries, scheduler queues, page faults, timers, files, interrupts, and wait strategies.

The objective is to understand what the operating system can do between the start and end timestamps of an otherwise tiny operation.

Processes, Threads, and System Calls

Status Draft outlineSection Operating Systems and Execution

Processes isolate resources; threads share an address space; system calls cross into the kernel to request privileged work.

Planned model

Trace one operation through user code, a syscall boundary, kernel work, blocking, wake-up, and return. Show which state belongs to the process, thread, and kernel.

Questions

• What is shared by threads and what remains per-thread?
• Which ordinary-looking operations can enter the kernel or block?
• What must be saved during an execution-context switch?

Exercise

Trace the complete state and privilege transitions for reading from a socket whose receive queue is initially empty.

Scheduling, Preemption, and Jitter

Status Draft outlineSection Operating Systems and Execution

The scheduler multiplexes runnable work onto CPUs. Preemption makes progress fairer, but adds delay that application code does not directly control.

Planned model

Run tasks under round-robin, priority, and isolated-core scenarios. Display run queues, time slices, migrations, wake-ups, and the latency distribution of one critical task.

Questions

• What makes a runnable thread wait?
• How do priority and affinity change latency without eliminating interrupts?
• Why does low average utilization not guarantee immediate scheduling?

Exercise

Explain a one-millisecond outlier in a ten-microsecond operation using a scheduling timeline and the evidence needed to confirm it.

CPU Affinity, Pinning, and Isolation

Status Draft outlineSection Operating Systems and Execution

Affinity constrains where a thread may execute. Isolation coordinates the scheduler, interrupts, background work, and memory placement around a latency-sensitive CPU.

Planned model

Move workers, interrupts, and kernel tasks across a topology map. Show migrations, cache warming, sibling contention, and NUMA locality.

Questions

• What is gained and lost by pinning a thread?
• Why can simultaneous-multithreading siblings interfere?
• Which work still reaches an allegedly isolated CPU?

Exercise

Assign receive, strategy, logging, and housekeeping threads to a two-socket machine and state the assumptions behind the layout.

Page Faults, Memory Locking, and Huge Pages

Status Draft outlineSection Operating Systems and Execution

An address can be valid without its page being immediately usable. Fault handling, page population, locking, and page size change latency and translation cost.

Planned model

Touch pages in an allocated region and distinguish minor faults, major faults, zero-fill, copy-on-write, locked memory, and huge-page translation coverage.

Questions

• Why does reserving memory not guarantee that every page is resident?
• What does prefaulting accomplish?
• Which tradeoffs accompany huge pages and memory locking?

Exercise

Prepare a fixed working set before a critical loop and describe what residual page-related delays can still occur.

Signals, Timers, and Clock Sources

Status Draft outlineSection Operating Systems and Execution

Signals and timers inject asynchronous events into otherwise sequential execution. Clock choice determines whether elapsed-time and deadline calculations remain meaningful.

Planned model

Schedule timers against monotonic and realtime clocks while introducing signal delivery delay, coalescing, interruption, drift, and wall-clock adjustment.

Questions

• Which work is safe inside a signal handler?
• How do timer resolution and delivery latency differ?
• Why should deadlines normally use monotonic time?

Exercise

Design a periodic task that handles overruns without silently drifting later on every cycle.

Files, Memory Mapping, and Asynchronous I/O

Status Draft outlineSection Operating Systems and Execution

Buffered reads, memory mappings, and asynchronous requests expose different interfaces to the same storage and page-cache machinery.

Planned model

Trace data from a file through page cache, copying, faults, queued requests, completion, dirty pages, and writeback.

Questions

• When does mmap avoid copying, and when does it merely defer work to faults?
• What does asynchronous I/O make asynchronous?
• Which durability guarantees require explicit synchronization?

Exercise

Choose an I/O design for replaying a large append-only log while bounding stalls and memory use.

Interrupts, Polling, and Busy Waiting

Status Draft outlineSection Operating Systems and Execution

Interrupts save CPU time while idle; polling spends CPU time to detect work with less wake-up machinery. Hybrid designs occupy the space between them.

Planned model

Deliver events under interrupt, periodic polling, busy waiting, and adaptive spinning. Plot CPU consumption beside typical and tail response time.

Questions

• At what event rate does polling become attractive?
• How do interrupt moderation and batching interact?
• When should a spin loop yield or sleep?

Exercise

Choose a wait strategy for a bursty queue and justify the transition points between spinning, yielding, and blocking.

Concurrency

Status Draft

This part begins with ownership and invariants, then introduces locks, atomics, coherence, bounded communication, lock-free rings, contention, reclamation, and execution models.

Correctness comes first. Predictability and throughput follow from measuring the coordination the correct design requires.

Threads, Ownership Transfer, and Shared State

Status Draft outlineSection Concurrency

Concurrency begins with deciding who owns each piece of state and how ownership or observations move between execution contexts.

Planned model

Pass messages and shared objects among threads while displaying ownership, aliases, synchronization edges, and illegal races.

Questions

• Can state be partitioned instead of shared?
• What does a successful handoff guarantee about prior writes?
• Which Rust traits prevent unsafe cross-thread movement or access?

Exercise

Assign ownership for every buffer and mutable field in a three-stage pipeline, including shutdown and error paths.

Mutexes, Reader-Writer Locks, and Condition Variables

Status Draft outlineSection Concurrency

Locks protect invariants, not merely variables. Their behavior depends on contention, critical-section length, wake-up policy, and the code executed while held.

Planned model

Schedule readers and writers around mutexes, reader-writer locks, and condition variables. Show queues, ownership, spurious wake-ups, convoying, and wait time.

Questions

• What exact invariant does the lock protect?
• When can a reader-writer lock perform worse than a mutex?
• Why must a condition predicate be checked in a loop?

Exercise

Design a bounded blocking queue and specify the predicates, lock boundaries, and notifications for every state transition.

Atomics and Memory Ordering

Status Draft outlineSection Concurrency

Atomicity prevents torn operations; memory ordering constrains what other reads and writes may appear before or after them.

Planned model

Execute litmus tests under relaxed, acquire-release, and sequentially consistent ordering. Display per-thread operations, allowed observations, and synchronization edges.

Questions

• What correctness property requires an atomic operation?
• Which write publishes the data and which read consumes it?
• Why is “the CPU reordered it” an incomplete explanation?

Exercise

Prove the ordering of a one-time publication pattern and identify the weakest defensible ordering for each atomic access.

Cache Coherence and False Sharing

Status Draft outlineSection Concurrency

Coherence keeps cached copies of a memory location consistent. Because ownership moves at cache-line granularity, independent variables can still interfere.

Planned model

Place counters on cache lines and alternate writes from several cores. Animate line ownership, invalidations, read sharing, and padding.

Questions

• Why can per-thread counters contend without a lock?
• When does padding help, and what memory cost does it impose?
• How does read-mostly sharing differ from write sharing?

Exercise

Diagnose a scaling collapse in a sharded counter and redesign its layout without changing its logical ownership.

Bounded Queues and Backpressure

Status Draft outlineSection Concurrency

A bounded queue makes overload visible. Its capacity and full-queue policy determine memory use, delay, loss, and how pressure propagates upstream.

Planned model

Vary producer and consumer rates while plotting occupancy, queueing delay, dropped work, blocked producers, and batch size.

Questions

• Does a full queue block, reject, overwrite, or shed lower-value work?
• How does capacity affect burst tolerance and worst-case residence time?
• Where should backpressure terminate?

Exercise

Choose a capacity and overload policy for a pipeline with a stated burst size and latency budget.

Lock-Free SPSC Ring Buffers

Status Draft outlineSection Concurrency

A single-producer/single-consumer ring exploits exclusive ownership of the write and read positions. Lock-free does not mean synchronization-free.

Planned model

Animate producer and consumer cursors, wraparound, full and empty states, data publication, cache-line placement, and acquire-release edges.

Questions

• Which cursor may each thread modify?
• How is a written slot published before it is observed?
• How are full and empty distinguished safely?

Exercise

State the invariants and memory orderings for a fixed-capacity SPSC queue before implementing any unsafe storage.

LMAX Disruptor — A Sequence-Gated Event Pipeline

A preallocated ring stores events; monotonically increasing sequences coordinate producers, consumers, dependencies, and backpressure.

Section ConcurrencyModel Multicast pipelineGoal Separate storage from coordination

Use the controls to publish events and advance the three consumers. The journal and replication stages may run in parallel. The engine may process sequence n only after both upstream stages have processed n. When the engine falls a full ring behind, the producer must stop rather than overwrite live data.

That yields the central model:

preallocated slots + monotonic sequences + dependency barriers + gating
    = a bounded, multicast event pipeline

The Disruptor is not merely a fast circular queue. Its important contribution is the separation of event storage, sequence allocation, publication, consumer progress, dependency graphs, and waiting policy.

Why ordinary queue language is misleading

In a work queue, one item is normally removed by one worker. In a typical Disruptor graph, every independent consumer sees every published event:

producer
   ├── journal ──┐
   └── replicate ├── engine
                 ┘

The journal and replication handlers both observe sequence 42. The engine’s barrier waits until both have reached at least 42, then the engine observes the same ring slot. Nothing is copied into three ordinary queues.

The dependency graph can express parallel stages, pipelines, and joins. It does not automatically mean that several consumers divide the work between them.

The ring stores reusable event objects

The ring has a fixed capacity, normally a power of two. Slots are allocated in advance and reused:

physical_index = sequence & (capacity - 1)

Sequence numbers keep increasing across wraparound. Physical slot 2 might hold sequence 2, later sequence 10, and later sequence 18 in an eight-slot ring. The sequence identifies the logical event; the masked index identifies reusable storage.

Preallocation can reduce allocation and garbage-collection pressure, but reuse creates a strict rule:

A producer must never wrap onto a slot that any gating consumer can still read.

That rule is the source of bounded backpressure.

Claim, write, then publish

A producer conceptually performs three distinct actions:

sequence = claim_next()
write event into ring[sequence & mask]
publish(sequence)

Publication is the handoff. Consumers must not observe a claimed slot before its event is completely initialized. The actual Java implementation uses carefully designed sequence operations and memory-ordering guarantees; a translation to C++ or Rust must recreate the happens-before relationship rather than copy surface syntax.

The visualization combines claim, write, and publish into one button so that the storage and gating rules remain visible. A multi-producer sequencer has additional work: producers may claim different sequences concurrently, so publication must not expose an unpublished hole as available data.

Consumers own progress sequences

Each event processor owns a sequence recording the highest contiguous event it has completed:

published = 12
journal   = 12
replicate = 10
engine    = 10

The journal can continue to 12, but the engine’s dependency barrier exposes only:

available_to_engine = min(journal, replicate) = 10

The engine cannot process 11 until replication reaches it. This is coordination through progress counters rather than moving event ownership between linked queue nodes.

Gating prevents destructive wraparound

For a ring of capacity C, a producer considering sequence S computes:

wrap_point = S - C

If the wrap point is greater than the minimum gating sequence, publishing S would overwrite a slot still needed downstream. The producer must wait, reject, or apply a surrounding overload policy.

In the chapter’s graph, the engine is the final consumer and therefore gates reuse. The journal and replication stages constrain the engine; the engine in turn constrains the producer.

This makes the system bounded, but it does not decide what the application should do when full. A real system must choose deliberately among backpressure, bounded waiting, shedding, disconnecting, or failure.

Sequence barriers encode dependencies

A consumer asks a sequence barrier whether its next sequence is available. The barrier considers both the producer cursor and any upstream consumer sequences.

Conceptually:

next = my_sequence + 1
available = min(published_cursor, dependencies...)

if next <= available:
    process a contiguous batch
else:
    apply the configured wait strategy

The official API separates the Sequencer, Sequence, SequenceBarrier, event processor, handler, and wait strategy. That separation is the architecture, not incidental library vocabulary.

Batching emerges naturally

If a consumer wakes for sequence 40 and discovers that sequences through 57 are available, it can process the entire contiguous range:

for sequence in 40..=57 {
    handle(ring[sequence & mask]);
}
consumer_sequence = 57;

This amortizes barrier checks and can improve instruction and data locality. Batching also changes latency behavior: throughput may improve while an individual event waits behind earlier work. Report both throughput and a latency distribution.

Wait strategies exchange CPU for wake-up behavior

Waiting is policy, not an intrinsic ring-buffer operation:

Busy spinning is not free speed. On an oversubscribed host it can steal execution time from the producer or the consumer it is waiting for. CPU affinity, sibling hyperthreads, NUMA placement, power management, and deployment isolation become part of the design.

Cache lines still matter

The coordination variables are written frequently by different threads. If two independent sequences occupy one cache line, otherwise unrelated writers can bounce that line between cores. The Disruptor’s Sequence includes measures to avoid false sharing.

Padding is not a magic annotation. Verify object layout, alignment, and generated code for the actual runtime. Also remember that event fields written by different parallel handlers can false-share even when their sequence counters do not.

Single producer and multiple producers are different algorithms

A single producer owns sequence allocation and can advance it without contending with another publisher. A multi-producer sequencer must coordinate claims and track which claimed sequences have actually been published.

Choose the single-producer mode when the architecture guarantees it. Do not select multi-producer mode “for flexibility” without measuring the coordination it adds. Likewise, do not serialize several natural producers merely to satisfy a benchmark. The topology should follow the real ownership model.

What the Disruptor does not solve

It does not provide:

• Unbounded buffering.
• Durability merely because a journal consumer exists.
• Network transport.
• Automatic load shedding or overload policy.
• General work stealing.
• A portable promise of a particular nanosecond latency.
• Freedom from memory-ordering and lifecycle proofs.
• Faster behavior for every workload than every ordinary bounded queue.

It is most compelling when a bounded stream is multicast through stable stages, events can be preallocated, dependency order is explicit, and cores may be dedicated. An ordinary channel or bounded queue is often better when traffic is light, blocking is desirable, consumer topology is simple, or operational simplicity matters more than removing coordination overhead.

Relationship to the LMAX architecture

LMAX used Disruptors around a single-threaded business-logic processor. The single writer made domain-state transitions deterministic; surrounding stages handled activities such as input, journaling, replication, and output concurrently.

These are related ideas, but not identical:

• Disruptor: a library and pattern for sequence-coordinated event pipelines.
• Single-writer state machine: an ownership architecture for mutable domain state.
• Event sourcing: reconstructing state from an authoritative event history.

A system can use any one without adopting all three.

What to measure

Compare the Disruptor design with the simplest correct bounded queue for the actual workload. Record:

• Single-event latency and full distributions under sustained load.
• Throughput at the reported tail-latency target.
• Batch sizes and burst behavior.
• Time spent waiting because the ring is full.
• CPU utilization per core, not only process-wide utilization.
• Context switches, migrations, cache misses, and coherence traffic.
• Effects of core placement and simultaneous multithreading.
• Recovery behavior after a consumer stalls or fails.

A benchmark that keeps consumers perfectly balanced does not test the gating rule that protects the system under stress.

What you should internalize

1. The ring owns reusable storage; sequences coordinate access to it.
2. Logical sequences increase monotonically even though physical slots wrap.
3. A producer must write before publishing.
4. Consumers track independent progress and usually see every event.
5. Barriers express pipeline dependencies and joins.
6. The slowest required downstream sequence ultimately gates slot reuse.
7. Gating creates bounded backpressure instead of permitting overwrite.
8. Batching, wait policy, core placement, and cache lines affect observed latency.
9. Single- and multi-producer sequencing require different coordination.
10. The Disruptor is useful only when its topology matches the workload.

Retrieval drill

For capacity 8, suppose the producer has published through sequence 14, the journal is at 14, replication is at 12, and the engine is at 12:

1. What sequence does the engine want next, and is it available yet?
2. Which physical slot contains sequence 14?
3. Can the producer safely publish sequence 21? What about 22?
4. Which sequence must move before the producer can reuse the blocked slot?
5. Would adding another busy-spinning consumer necessarily reduce latency?

Sources

• Official LMAX Disruptor user guide
• LMAX Disruptor technical paper
• Official source repository
• Martin Fowler, The LMAX Architecture

The named classes and current library behavior are Java-specific. The sequence, publication, dependency, gating, and measurement models apply more broadly, but a C++ or Rust implementation needs its own memory-model and lifetime argument.

Multi-Producer Algorithms and Contention

Status Draft outlineSection Concurrency

Adding producers changes ownership from exclusive cursor updates to coordinated claims, retries, and possible contention hotspots.

Planned model

Let producers claim shared slots with a lock, fetch-add, or compare-exchange loop. Display failed retries, fairness, cache-line traffic, and consumer progress.

Questions

• Where is the serialization point?
• Can work be sharded before coordinating globally?
• What progress guarantee does the algorithm actually provide?

Exercise

Compare one MPSC queue with per-producer SPSC queues and define workloads that favor each design.

RCU, Epochs, and Memory Reclamation

Status Draft outlineSection Concurrency

Removing an object from a shared structure does not prove that no reader can still reach it. Reclamation determines when its storage may be reused.

Planned model

Track readers, retired nodes, epochs, grace periods, and reclamation. Contrast reference counting, hazard pointers, epochs, and read-copy-update.

Questions

• What event proves that every old reader has finished?
• How can a stalled participant delay reclamation?
• Which problem is the ABA pattern exposing?

Exercise

Specify a safe lifecycle for removing and eventually freeing a node that lock-free readers may already hold.

Async Runtimes Versus Dedicated Threads

Status Draft outlineSection Concurrency

Async tasks multiplex waiting operations over executor threads; dedicated threads give execution contexts stronger placement and blocking assumptions.

Planned model

Run the same I/O-heavy and CPU-heavy workloads through an async executor and dedicated workers. Show task queues, wake-ups, blocking, migration, and latency.

Questions

• Is the work mostly waiting or computing?
• What happens when an async task blocks its executor thread?
• Which design gives the required affinity and scheduling control?

Exercise

Partition a system between async coordination and dedicated critical-path threads, explaining every boundary.

Networking and I/O

Status Draft

This part traces bytes from the wire to application state through protocols, NIC queues, socket buffers, interrupts, polling, copies, shared rings, and bypass paths.

Every chapter identifies who owns each buffer and where queues, copies, batching, wake-ups, and loss enter the path.

Ethernet, IP, UDP, TCP, and Multicast

Status Draft outlineSection Networking and I/O

Each network layer adds addressing, framing, delivery semantics, and failure modes. Applications must know which guarantees exist and which they must supply.

Planned model

Encapsulate an application message through Ethernet, IP, and transport headers, then inject loss, reordering, duplication, fragmentation, and retransmission.

Questions

• Which layer detects corruption, loss, or ordering problems?
• When is UDP or multicast preferable to a reliable byte stream?
• Why can TCP preserve bytes while obscuring message boundaries?

Exercise

Specify the framing and recovery responsibilities of an application protocol over both TCP and UDP.

Socket Buffers, Batching, and Packet Timestamps

Status Draft outlineSection Networking and I/O

Socket queues absorb bursts and decouple producers from consumers, but every queued packet acquires residence time and can eventually be dropped.

Planned model

Move packets through NIC and socket queues while adjusting buffer sizes, application batch size, and timestamp location. Plot drops, syscalls, and latency.

Questions

• Which queue does a socket-buffer setting actually change?
• When does batching improve throughput but harm first-packet latency?
• What event does each software or hardware timestamp represent?

Exercise

Select buffer and batch policies for a bursty receiver with a strict stale-data deadline.

NIC Queues, RSS, and Flow Steering

Status Draft outlineSection Networking and I/O

Modern NICs expose multiple queues so packet processing can be distributed, but queue, interrupt, CPU, and application ownership must align.

Planned model

Hash flows into receive queues and steer queues to CPUs. Display reordering risks, hot flows, interrupt affinity, cache locality, and NUMA placement.

Questions

• Which packet fields feed the receive-side scaling hash?
• How can one heavy flow dominate a queue?
• Where should queue memory and its consumer thread reside?

Exercise

Map eight receive queues to a two-socket CPU topology and explain how application flow ownership follows the mapping.

Interrupt Moderation and Busy Polling

Status Draft outlineSection Networking and I/O

NIC interrupt moderation waits for more packets before notifying the CPU. Busy polling looks for them proactively. Both trade CPU consumption for batching and response time.

Planned model

Deliver adjustable packet bursts under immediate interrupts, coalescing, adaptive moderation, and busy polling. Plot notification count and latency distribution.

Questions

• What does a coalescing timer delay?
• How does packet rate change the best policy?
• Which CPU performs the poll and what else can run there?

Exercise

Choose an interrupt and polling policy for quiet periods punctuated by high-value bursts.

Zero-Copy Techniques

Status Draft outlineSection Networking and I/O

“Zero copy” names several techniques that eliminate particular copies, not a universal guarantee that bytes never move or incur ownership costs.

Planned model

Trace buffers through ordinary reads, scatter-gather I/O, memory mapping, page remapping, and registered buffers. Count copies, mappings, pins, and lifetime constraints.

Questions

• Which specific source-to-destination copy is removed?
• What setup, pinning, alignment, or lifetime cost replaces it?
• When is copying a small message faster and simpler?

Exercise

Audit a claimed zero-copy path and enumerate every point at which payload bytes or metadata still move.

io_uring and AF_XDP

Status Draft outlineSection Networking and I/O

These are different mechanisms. io_uring is an asynchronous kernel I/O interface; it does not generally bypass the kernel. AF_XDP exposes a fast packet path through XDP and shared rings while retaining kernel participation. DPDK’s poll-mode drivers are the book’s primary example of userspace NIC access that bypasses the ordinary kernel network stack.

Planned model

Compare conventional sockets, io_uring, AF_XDP, and DPDK. Show submissions, completions, copies, wake-ups, ownership, setup cost, and which kernel work remains in each path.

Questions

• Which kernel work remains in each path?
• Who owns a registered buffer at every instant?
• When does operational complexity outweigh saved overhead?

Exercise

Draw the lifecycle of one receive buffer from NIC arrival through application processing and safe reuse.

DPDK-Style Poll-Mode Processing

Status Draft outlineSection Networking and I/O

Poll-mode networking dedicates CPU capacity to repeatedly draining NIC queues, usually with preallocated packet buffers and batched processing.

Planned model

Animate receive descriptors, packet-buffer pools, bursts, worker ownership, transmission, and reclamation. Expose empty polls and queue backlogs.

Questions

• Why are huge pages and pinned cores commonly involved?
• How are packet buffers recycled without allocation?
• How should work be divided without reintroducing shared contention?

Exercise

Design a two-stage poll-mode pipeline and account for queue ownership, buffer ownership, and overload behavior.

Protocol Parsing and Sequence Recovery

Status Draft outlineSection Networking and I/O

A fast parser is useless if it silently accepts corrupt frames or advances application state across missing sequence numbers.

Planned model

Deliver fragmented, duplicated, reordered, missing, and malformed messages. Track framing state, expected sequence, gap detection, buffering, recovery, and resumption.

Questions

• Which validation occurs before any state mutation?
• How are duplicates and gaps distinguished?
• When should live processing pause, buffer, or continue provisionally?

Exercise

Specify a feed-state machine from startup through synchronization, normal processing, gap recovery, and unrecoverable failure.

Performance Engineering

Status Draft

This part makes performance claims measurable. It covers throughput, latency distributions, honest histograms, benchmark design, profiling, critical paths, replay, and overload.

The standard is evidence that survives warm-up effects, queueing, tail events, and experimental bias.

Throughput Versus Latency

Status Draft outlineSection Performance Engineering

Throughput counts completed work per unit time; latency measures how long individual work waits and executes. Optimizing one can damage the other.

Planned model

Adjust arrival rate, service rate, batching, and parallelism. Plot throughput, utilization, queue depth, and latency together.

Questions

• When does a system saturate?
• Why does queueing delay rise sharply near capacity?
• Which latency is measured: service time, queue time, or end-to-end time?

Exercise

Explain why doubling batch size can increase throughput while violating the latency objective.

Latency Distributions and Tail Behavior

Status Draft outlineSection Performance Engineering

A mean compresses a distribution into one number and can hide the rare delays that define user-visible or deadline-sensitive behavior.

Planned model

Generate mixtures of fast and slow paths. Compare mean, median, percentiles, maximum, histogram, and survival curve as rare events change.

Questions

• What population and time interval does a percentile summarize?
• How many samples support a claimed high percentile?
• How do correlated pauses affect end-to-end tail latency?

Exercise

Interpret two systems with equal means but different p99 and p99.99 behavior, then choose one for a stated deadline.

Histograms and Coordinated Omission

Status Draft outlineSection Performance Engineering

Histograms approximate distributions through buckets. A load generator that waits for a delayed response before scheduling more work can omit the delay’s consequences.

Planned model

Compare closed-loop and open-loop load generation through an injected stall. Display intended arrivals, actual requests, omitted samples, and resulting histograms.

Questions

• What precision and range do histogram buckets provide?
• Why does a closed loop under-sample periods of poor service?
• What correction is possible, and what assumptions does it make?

Exercise

Design a latency test whose request schedule remains independent of the system’s response latency.

Warm-Up, Cache State, and Benchmark Design

Status Draft outlineSection Performance Engineering

A benchmark measures an experimental setup, not an abstract function. Warm-up, input shape, compiler behavior, cache state, and noise determine what the result means.

Planned model

Run the same operation with cold and warm code, cache, allocator, and pages. Show setup cost, steady state, optimization artifacts, and sample variance.

Questions

• Is the target workload cold, warm, or a known mixture?
• Has the compiler removed or transformed the measured work?
• Which environmental variables must be recorded or controlled?

Exercise

Write a benchmark protocol for one container operation that distinguishes typical cost from resize and cold-page slow paths.

Profiling CPU, Allocation, Locks, and I/O

Status Draft outlineSection Performance Engineering

Different profilers answer different questions. CPU samples, allocation events, lock waits, scheduler traces, and I/O traces cannot be collapsed into one universal profile.

Planned model

Inject known CPU, allocation, contention, and I/O delays into a pipeline, then reveal what sampling, tracing, and instrumentation observe or miss.

Questions

• Is time spent running, runnable, sleeping, or waiting on a resource?
• What bias and overhead does the collection method introduce?
• Can symbols and timestamps be trusted?

Exercise

Choose evidence needed to distinguish a hot loop, lock convoy, page fault, and scheduler delay that produce the same wall-clock symptom.

Jitter Budgets and Critical Paths

Status Draft outlineSection Performance Engineering

A latency budget assigns time to the dependent stages on a critical path and reserves room for variation, queueing, and failure handling.

Planned model

Compose stage distributions into an end-to-end timeline. Add queueing, parallel branches, pauses, and correlated slow paths while tracking budget violations.

Questions

• Which stages are sequential and which overlap?
• Where does waiting enter the critical path?
• Why do individual p99 values not simply add into an end-to-end p99?

Exercise

Allocate a deadline across receive, parse, decide, validate, encode, and send stages, including explicit jitter reserve.

Load Generation, Replay, and Deterministic Tests

Status Draft outlineSection Performance Engineering

Useful load reproduces arrival timing, data shape, dependencies, and bursts without letting the system under test secretly pace its generator.

Planned model

Replay one trace in wall-clock, accelerated, closed-loop, and deterministic-step modes. Show scheduling error, backlog, nondeterminism, and state divergence.

Questions

• Which properties of production traffic must the generator preserve?
• How are randomness and time controlled for repeatability?
• Can replay overload be distinguished from generator overload?

Exercise

Design a deterministic replay format containing enough information to reproduce both inputs and relevant timing decisions.

Capacity, Overload, and Graceful Degradation

Status Draft outlineSection Performance Engineering

When arrivals exceed sustainable service, work must queue, be delayed, be rejected, or displace other work. Unbounded buffering only postpones the decision.

Planned model

Drive a pipeline beyond capacity under blocking, dropping, prioritization, admission control, and load-shedding policies. Plot recovery after the burst ends.

Questions

• What is the true bottleneck and sustainable rate?
• Which work may be discarded safely?
• Can the system recover promptly, or does stale backlog prolong failure?

Exercise

Define overload behavior for every bounded resource in a pipeline and prove that memory use remains bounded.

High-Performance C++

Status Draft

This applied track connects modern C++ to the machine and performance models in the rest of the book. It is not a tour of language syntax. It concentrates on the choices that change correctness, layout, allocation, generated code, contention, and latency.

Rust and C++ will share experiment specifications rather than matching line for line. The useful question is not which language wins in the abstract, but which costs each implementation creates under a stated compiler, machine, and load.

The track covers object lifetime, layout and invalidation, allocation strategies, templates and code size, the C++ memory model, sanitizers, compiler inspection, and reproducible benchmarking.

Cost Model and Object Lifetime

Status Draft outlineSection High-Performance C++

C++ performance starts with knowing when an object is constructed, moved, copied, destroyed, or never materialized at all. RAII gives lifetime a local shape, but hidden temporaries and ownership mistakes can still dominate a hot path.

Planned model

Trace one value through construction, return-value optimization, move, container growth, and destruction. Inspect counters and generated code instead of guessing from source syntax.

Questions

• Which operations are guaranteed, permitted to disappear, or implementation-dependent?
• When is a move still expensive?
• How do lifetime and ownership choices affect tail latency and failure safety?

Exercise

Instrument a small message type, then explain every construction and destruction observed when it enters and leaves a growing container.

Layout, Containers, and Invalidation

Status Draft outlineSection High-Performance C++

Container choice determines locality, indirection, iterator stability, growth, and the validity of stored pointers and references.

Planned model

Compare contiguous, node-based, flat, and segmented containers under traversal, insertion, erasure, and growth. Animate which handles become invalid.

Questions

• What does the standard guarantee about layout and invalidation?
• When is stable identity worth pointer chasing?
• Which benchmark inputs expose capacity growth and cold-cache behavior?

Exercise

Choose representations for an order table, a FIFO price level, and a read-mostly lookup table. State the invalidation and locality contract for each.

Allocation, pmr, and Pools

Status Draft outlineSection High-Performance C++

Allocation policy affects throughput, fragmentation, locality, determinism, and which thread pays for reclamation. std::pmr separates many containers from the resource that supplies their storage.

Planned model

Run the same workload with the default allocator, a monotonic resource, a pool, and a fixed arena. Show allocation count, reuse, peak memory, and reset cost.

Questions

• Does the workload need individual frees or phase-based reset?
• Who owns the resource, and can any object outlive it?
• Does a pool improve the measured tail or merely move work elsewhere?

Exercise

Design allocation lifetimes for decoded packets that are discarded after one processing batch.

Templates, Inlining, and Code Size

Status Draft outlineSection High-Performance C++

Templates can remove abstraction overhead and enable specialization, but more instantiations and aggressive inlining can increase compile time, binary size, and instruction-cache pressure.

Planned model

Compare virtual dispatch, function objects, templates, and explicit branches. Inspect the optimized assembly and measure both steady-state work and code size.

Questions

• Did the abstraction disappear in the generated code?
• Did specialization duplicate a hot path or create instruction-cache pressure?
• Is link-time optimization changing the conclusion?

Exercise

Implement one packet handler with runtime and compile-time dispatch, then make a claim supported by assembly and benchmark evidence.

C++ Atomics and Memory Ordering

Status Draft outlineSection High-Performance C++

An atomic operation prevents a data race only for the object and ordering it actually governs. Correct lock-free code requires an explicit happens-before argument and a safe lifetime strategy.

Planned model

Build a single-producer/single-consumer ring from ordinary storage and atomic indices. Animate publication, observation, acquire/release edges, wraparound, and cache-line ownership.

Questions

• What invariant assigns each slot to exactly one owner?
• Which write publishes the payload, and which read observes it?
• What changes when weak ordering, false sharing, or object reclamation enters?

Exercise

Write the happens-before proof for one enqueue and dequeue before writing any implementation code.

Toolchains, Sanitizers, and Benchmarking

Status Draft outlineSection High-Performance C++

Debug, sanitized, profiled, and optimized binaries answer different questions. A believable performance result records the compiler, flags, linked libraries, hardware, operating-system state, workload, and sampling method.

Planned model

Follow one program through warnings, AddressSanitizer, UndefinedBehaviorSanitizer, ThreadSanitizer, optimized assembly inspection, counters, and a benchmark harness.

Questions

• Which correctness checks are incompatible with a production-speed measurement?
• Has the optimizer removed the work or moved it outside the timed region?
• Can another person reproduce the result from the recorded environment?

Exercise

Create a benchmark report template that distinguishes correctness evidence, profiling evidence, and final optimized measurements.

Storage and Database Internals

Status Draft

Storage engines provide durable examples of the same locality, batching, indexing, contention, and recovery tradeoffs found in other high-performance systems.

This part moves from pages and logs through caching, transactions, columnar execution, time-series storage, and query plans.

Pages, B-Trees, LSM Trees, and WALs

Status Draft outlineSection Storage and Database Internals

Storage engines organize durable state around page-sized I/O, ordered indexes, append-friendly structures, and logs that make recovery possible.

Planned model

Apply inserts and reads to a B-tree and an LSM-style design. Animate page splits, memtables, flushes, compaction, WAL records, and write amplification.

Questions

• Which writes must become durable before acknowledgement?
• Why do B-trees and LSM trees favor different workloads?
• Where do read, write, and space amplification arise?

Exercise

Choose a storage layout for an append-heavy workload with recent-key reads and state the compaction and recovery costs.

Buffer Pools and Caching

Status Draft outlineSection Storage and Database Internals

A buffer pool keeps selected storage pages in memory, tracks dirty state and pins, and decides which page to evict when capacity is exhausted.

Planned model

Replay page references through LRU, CLOCK, and scan-resistant policies. Show hits, misses, pinned pages, dirty writeback, and eviction stalls.

Questions

• Why can a sequential scan evict a valuable working set?
• What prevents a pinned page from being reclaimed?
• How does the database cache interact with the OS page cache?

Exercise

Choose an eviction and writeback policy for mixed point-lookups and large analytical scans.

Transactions, Isolation, and Recovery

Status Draft outlineSection Storage and Database Internals

Transactions define which intermediate states may be observed and how committed state survives failure. Isolation and durability require distinct mechanisms.

Planned model

Interleave reads and writes under locking and multiversion concurrency control. Inject crashes around log, data-page, commit, and checkpoint events.

Questions

• Which anomalies does each isolation level permit?
• What ordering between WAL and data pages enables recovery?
• How are abandoned versions or locks cleaned up?

Exercise

Construct one write-skew history and show which isolation rule prevents it.

Columnar Layouts and Vectorized Execution

Status Draft outlineSection Storage and Database Internals

Columnar storage places values of the same field together, enabling projection, compression, SIMD-friendly scans, and late materialization.

Planned model

Execute the same filter and aggregate over row and column layouts. Count bytes loaded, cache lines, decoded values, branches, and vector lanes.

Questions

• Which workload needs whole records and which needs a few columns?
• How do nulls and variable-length values alter the layout?
• When does compression improve speed by reducing memory traffic?

Exercise

Design a column representation for timestamp, symbol, price, quantity, and optional venue fields.

Time-Series Storage and Append-Only Logs

Status Draft outlineSection Storage and Database Internals

Time-ordered data favors append, segmentation, compression, retention, and sequential replay, but corrections and out-of-order events complicate the model.

Planned model

Append events into segments, build sparse indexes, rotate files, compress blocks, apply retention, and introduce late or corrected records.

Questions

• Which ordering key defines the log?
• How are segment boundaries and indexes selected?
• Are corrections rewritten, overlaid, or represented as later events?

Exercise

Specify an append-only event format that supports crash recovery, replay, retention, and schema evolution.

Index Design and Query Execution

Status Draft outlineSection Storage and Database Internals

An index is a maintained physical shortcut for selected access patterns. Every shortcut consumes memory and adds work to writes.

Planned model

Run filters and joins through scans, ordered indexes, hash indexes, and composite indexes. Display candidate rows, random reads, selectivity, and maintenance cost.

Questions

• Which key order supports a query prefix?
• When is a scan cheaper than following an index?
• How do statistics errors lead to a poor execution plan?

Exercise

Choose the smallest index set for a concrete query workload and enumerate the write amplification it creates.

Market and Trading Systems

Status Draft

This part applies the earlier foundations to sequenced market data, order state, matching, risk, positions, simulation, synchronized clocks, and failure recovery.

Finance arrives here as a demanding systems application, not as a collection of unexplained low-latency tricks.

Market Data Feeds and Gap Recovery

Status Draft outlineSection Market and Trading Systems

Market-data consumers transform sequenced messages into local state while detecting loss, duplication, stale snapshots, and recovery boundaries.

Planned model

Deliver snapshots and incrementals with duplicates, gaps, reordering, and channel failover. Show expected sequence, buffered messages, recovery, and book validity.

Questions

• When is locally reconstructed state trustworthy?
• How do snapshot and incremental sequence domains join?
• What processing may continue while a gap is repaired?

Exercise

Specify a deterministic state machine for startup, normal flow, gap detection, recovery, and reset.

Limit Order Books and Price-Time Priority

Status Draft outlineSection Market and Trading Systems

A limit order book groups resting interest by price and orders each price level according to venue rules such as price-time priority.

Planned model

Apply add, cancel, replace, and execute events. Animate best bid and offer, per-price FIFO queues, crossed books, and stale-handle rejection.

Questions

• Which operations need lookup by order ID, price, or queue position?
• How are partial executions represented?
• What invariants detect a corrupt reconstruction?

Exercise

Choose data structures for a bounded price domain and for a sparse price domain, explaining cancellation cost in each.

Matching Engines and Deterministic Replay

Status Draft outlineSection Market and Trading Systems

A matching engine applies a totally ordered command stream to a deterministic state machine and emits executions, acknowledgements, and market-data effects.

Planned model

Sequence commands through validation and matching while exposing price-time queues, emitted events, snapshots, replay, and failover divergence.

Questions

• What establishes one authoritative command order?
• Which inputs besides commands can break determinism?
• How are output and durable state coordinated?

Exercise

Define the minimum replay log needed to rebuild identical book state and outputs after a crash.

Order Gateways and State Machines

Status Draft outlineSection Market and Trading Systems

An order gateway reconciles local intent with asynchronous acknowledgements, rejects, fills, cancels, disconnects, and session recovery.

Planned model

Drive an order through pending, live, partially filled, cancel-pending, terminal, and uncertain states while messages arrive late or duplicate.

Questions

• Which transitions are legal from every state?
• How are client and venue identifiers correlated?
• What does the system know after a disconnect before reconciliation?

Exercise

Construct an order-state machine that treats duplicates idempotently and never resurrects a terminal order.

Pre-Trade Risk Checks and Kill Switches

Status Draft outlineSection Market and Trading Systems

Pre-trade risk constrains orders using current positions, outstanding exposure, limits, prices, and operational state before an order leaves the system.

Planned model

Evaluate orders against quantity, notional, position, price-band, rate, and session limits. Show reservation, concurrent updates, rejection, release, and kill-switch action.

Questions

• Which exposure must be reserved before acknowledgement?
• How do fills, rejects, and cancels release or convert reservations?
• Which failure defaults to reject rather than proceed?

Exercise

Define atomic state transitions for two concurrent orders competing for the last available risk capacity.

Position, P&L, and Exposure Tracking

Status Draft outlineSection Market and Trading Systems

Positions and profit-and-loss are derived state whose meaning depends on event ordering, price source, accounting convention, currency, and correction handling.

Planned model

Apply fills, fees, cancels, busts, and price updates while displaying position, average cost, realized P&L, unrealized P&L, and gross exposure.

Questions

• Which events are authoritative and idempotent?
• How are corrections represented without silently rewriting history?
• Which price and FX rate mark each exposure?

Exercise

Specify an event-sourced position ledger that can be replayed and reconciled against an external statement.

Simulation, Backtesting, and Look-Ahead Bias

Status Draft outlineSection Market and Trading Systems

A backtest is credible only when every decision uses information available at that simulated instant and when fills model the constraints of the historical market.

Planned model

Replay event time, receive time, decision time, and order arrival time. Toggle latency, queue position, spread, fees, missing data, and accidental future access.

Questions

• What information was observable at each decision timestamp?
• How are fills, partial fills, and market impact approximated?
• Which parameter choices were selected using the evaluation period?

Exercise

Audit a strategy loop for look-ahead, survivorship, fill, and timestamp biases, then design a train-validation-test protocol.

Clock Synchronization and Latency Attribution

Status Draft outlineSection Market and Trading Systems

Latency attribution across hosts requires clocks with known offset, drift, precision, and timestamp location. A precise timestamp can still be inaccurate.

Planned model

Send events across clocks with drift and offset, then apply software, hardware, NTP-style, and PTP-style synchronization. Show attribution error at each stage.

Questions

• Where in the packet path was a timestamp taken?
• How is clock error bounded rather than merely estimated once?
• Which intervals can be measured safely on one clock?

Exercise

Create an error budget for one-way latency measured across two hosts and identify what independent evidence validates it.

Failure Recovery and Operational Controls

Status Draft outlineSection Market and Trading Systems

Recovery is a state-reconciliation problem: after a partial failure, the system must determine what happened externally before safely resuming action.

Planned model

Inject process crashes, dropped acknowledgements, stale replicas, network partitions, and operator actions. Track durable intent, external state, uncertainty, and recovery decisions.

Questions

• Which actions are idempotent and which may duplicate exposure?
• What state survives each failure boundary?
• When must automation stop and require explicit reconciliation?

Exercise

Write a recovery runbook for a gateway crash with live orders and an incomplete local acknowledgement log.