An introduction to algorithm analysis with a practical focus on how CPUs execute code and fetch data. Topics include growth rates, locality, and why memory layout matters

An introduction to data structures and algorithms from a practical, hardware-first perspective. Learn how the physical layout of your data in memory impacts performance.

Data Structures & Algorithms

Understand how our code interacts with physical hardware. Learn about virtual memory, the stack vs. heap, cache lines, and prefetching.

CPUs, Memory, and Locality

Learn how input size affects execution speed and the most common class of algorithms.

Polynomial Algorithms

Working with massive datasets using divide and conquer strategies, and the the required trade-offs.

Logarithmic and Linearithmic Algorithms

Learn why some problems are impossible to solve exactly and how we can use approximations like Monte Carlo simulations to cheat.

NP-Hard and Approximations

Practical Algorithm Analysis

Setting up a lightweight framework for measuring performance. Create benchmarks that produce reliable, meaningful results

Separate our core logic into libraries, configure CMake for multiple targets, and apply hardware-aware optimizations.

Configuring a CMake Project

Integrate the industry-standard Google Benchmark library into a CMake project to capture nanosecond-precision timings.

Integrating Google Benchmark

Fight the compiler's aggressive optimizations to ensure benchmarks measure reality.

Writing Effective Benchmarks

Learn to interpret CPU time, variance, and the trade-offs between insertion speed and read speed.

Analyzing Benchmark Data

Using Google Benchmark's Range and Complexity features to visualize Big O growth and identify the moment our data falls off the CPU cache cliff.

Mapping Complexity and Hardware Cliffs

Using benchmarks to calculate the 'break-even point' where investing in data preparation pays off.

Amortized Costs and Crossover Points

Google Benchmark for C++

Understand how C++20 ranges reshape the standard library. Learn to combine algorithms and views for clean, efficient code

The bridge between data layout and algorithms. Learn how iterators abstract memory traversal and the hierarchy of capabilities.

The Iterator Pattern

An introduction to the C++ Standard Library's algorithms, lambda expressions, and handling memory safely with insertion iterators.

Standard Library Algorithms

Learn how C++20 Ranges and Views allow us to compose safe, lazy-evaluated data pipelines without sacrificing performance.

C++20 Ranges

Learn how to build readable, lazy-evaluated data pipelines that execute in a single pass, and chain C++20 views together using the pipe operator `|`

View Composition and Pipes

Bridge the gap between iterators and views using `std::ranges::subrange` to turn any pair of iterators into a composable, safe C++20 View.

Subranges and Range Interoperability

Iterators, Ranges, and Views

Implement modern C++23 data processing with views and algorithms. Reduce boilerplate while improving correctness and performance

The Producer-Consumer model of C++20 Ranges and the hardware implications of eager vs lazy evaluation.

The Four Algorithm Families

Integrate sorting into C++20 pipelines, the difference between stable and unstable sorts, and how to use partial sorting.

Sorting and Materialization

Learn how C++20 Projections allow us to separate sorting logic from data layout, the mechanics of `std::invoke` and the hardware reality of sorting large objects.

Comparators and Projections

Learn why sorting large objects is slow, and how to optimize it using Proxy Sorting and Data-Oriented Design (SoA).

Proxy Sort and Structure of Arrays

Iterate multiple containers simultaneously with `zip`, handle indices with `enumerate`, and skip elements with `drop` and `stride`.

Composition, Zipping, and Indicies

Using Algorithms and Views

Modern processors are built for parallel execution, not sequential code. Learn how to use multithreading and vectorization in C++ to match that reality

Offload heavy work to other CPU cores. Learn how `std::async` and `std::future` enable concurrent execution.

Asynchronous Tasks with `std::async`

Combine the elegance of C++20 Ranges with the power of parallel execution policies.

Parallel Algorithms and Execution Policies

Learn how mutexes and atomics prevent race conditions, and why hardware contention can make multithreaded code slower than single-threaded code.

Locks and Atomics

Explore the performance cost of synchronization, how to mitigate it, and how to avoid it entirely with better algorithm design.

Cache Coherency and False Sharing

Learn how SIMD registers allow you to process multiple data points in a single instruction, unlocking the full power of each CPU core.

SIMD and Automatic Vectorization

Introduction to Parallelism

Learn how to design and implement a domain-specific container from scratch. The chapter focuses on cache efficiency, data-oriented design, and real-world performance trade-offs

Build a custom container that combines the performance of data-oriented design with the ergonomics of object-oriented programming.

Domain-Specific Containers

Implement proxy sorting, physical memory permutations, and multi-threaded reordering.

Sorting and Permuting Containers

Comparing the performance cost of deletion techniques, and implementing the Swap-and-Pop approach in a Structure of Arrays container.

The Swap-and-Pop Idiom

Solving the index invalidation problem and the trade-offs between memory density and reference stability.

Stable Addressing and Tombstones

Upgrade simple indices into Generational Handles, creating safe, persistent references that detect stale access.

Generational Indices

The hidden cost of `std::vector` growth, why it is dangerous for real-time systems, and how to mitigate it.

The Reallocation Spike

Implementing a Structure of Arrays

Learn advanced bit-centric techniques including fast filtering, bit packing, and compression to maximize efficiency

Learn to use bitwise operators to pack multiple states into a single byte, reducing memory bandwidth use.

Working with Bits

Replace slow logical operators with fast bitwise arithmetic. Learn how to filter data without branching, avoiding pipeline flushes and speeding up queries.

Fast Filtering and Branchless Logic

Trade CPU cycles for memory bandwidth by compressing data using bit packing, quantization, and delta encoding.

Quantization and Delta Encoding

Use bloom filters for fast rejection, hierarchical bitmasks for spatial skipping, and hardware intrinsics using C++20's `<bit>` library.

Advanced Bitwise Techniques

Implement the high-performance Entity-Component-System (ECS) design pattern, alongside an API that makes the architecture easy to use

Transitioning from monolithic data structures to the ECS architecture, splitting our data into dedicated component pools.

Entity-Component-System (ECS)

Connecting components to their entities using the sparse set pattern, achieving fast lookups while maintaining cache-friendly contiguous data.

Relational Data and Sparse Sets

Efficiently pulling data from multiple component pools simultaneously using the smallest set driver pattern, and optimizing it using bitmasks to minimize cache misses.

The Join Algorithm

Improving our API using templates and a centralized registry using `std::tuple`.

Templatizing Components

Updating our ECS to support composable, range-based views that handle the smallest-set algorithm automatically using C++20 ranges.

Creating Views

Entity-Component-System

Learn the physical reality and problems of allocating memory on the heap, and how to bypass these issues using custom allocators

Understanding the mechanisms of memory allocation, and the severe hardware cost of working with the heap.

The Physical Reality of `new` and `delete`

Why do long-running programs inevitably degrade and crash? Discover the hardware reality of memory fragmentation and TLB thrashing.

Memory Fragmentation

Bypass the OS and the global allocator. Build a custom linear arena allocator to implement fast memory allocation with zero fragmentation.

Linear and Arena Allocators

Solve the problem of dynamic entity lifespans. Build a zero-allocation object pool using an implicit free list hidden inside dead memory.

Object Pools and Free Lists

Memory Management and Custom Allocators

An introduction to the mechanics of linked lists, their strengths and weaknesses, and how those weaknesses can be mitigated in high-performance systems

An introduction to node-based data structures. The physical reality of `std::list`, pointer swapping, fast insertions, and why pointer chasing destroys performance.

The Mechanics of Linked Lists

Replace 64-bit pointers with lightweight indices and back our linked list with a contiguous memory pool to maximize performance.

Index-Based and Pool-Allocated Lists

Balance the flexibility of linked lists with cache-line sympathy of arrays. Learn how to group data into contiguous chunks to drastically reduce pointer chasing.

Unrolled Linked Lists

Eliminate node wrappers and heap allocations entirely. Learn how the Linux kernel uses intrusive structures to weave physical memory into multiple logical lists simultaneously.

Intrusive Linked Lists

Trade memory capacity for faster search speeds. Learn how probabilistic express lanes create highly concurrent, self-balancing data structures.

Skip Lists and Probabilistic Linking

Linked Lists

Build high-performance, lock-free algorithms using native hardware instructions. Master optimistic concurrency, tame out-of-order execution with memory fences, and navigate the ABA pointer problem.

Review concurrency and learn how to directly manage OS threads using `std::thread` and `std::jthread`.

Execution Contexts and `std::thread`

Understand the physical reality of moving data between RAM and registers. Learn why explicit loads and stores are required to prevent data tearing in complex structs.

Data Tearing and `std::atomic`

Learn how to perform complex lock-free atomic updates using `compare_exchange_weak()` and the hardware limitations.

Compare-And-Swap (CAS)

Learn how CPU out-of-order execution breaks lock-free code, and how to use `seq_cst`, `acquire`, `release`, `acq_rel`, and `relaxed` to fix it.

Instruction Reordering

Discover why using CAS on pointers is a hardware minefield, exposing the physical realities of memory allocators and the infamous ABA problem.

Lock-Free Pointers

Lock-Free Mechanics

Transition from static data storage to data flow. Implement decoupled architectures and stream data across CPU cores using lock-free concurrency

Learn how to decouple producers and consumers using FIFO and LIFO buffering structures.

Queues and Stacks

Learn how to bend a contiguous array into an infinite circle to build fast FIFO data pipelines.

Ring Buffers

Build a Single-Producer Single-Consumer lock-free queue using atomics, memory barriers, and cache-line alignment.

SPSC Ring Buffers

Build a Multi-Producer Multi-Consumer lock-free queue using CAS loops, Sequence Tickets, and memory ordering.

MPMC Ring Buffers

Build a highly concurrent, lock-free object pool and defeat the ABA problem using generation tags.

Lock-Free Object Pools

Build a highly concurrent Treiber stack using atomic Compare-And-Swap (CAS) instructions.

Lock-Free Stacks

Stacks and Queues

Building optimized containers that use open addressing, Robin Hood heuristics, cuckoo hashing, and consistent hashing techniques

Explore hashing, bitwise masking, and why the standard library's implementations hurt CPU cache performance.

Hash-Based Containers

Learn how to build a contiguous, cache-friendly hash set using open addressing and linear probing.

Flat Sets and Linear Probing

Fix the worst-case scenarios of linear probing by implementing Robin Hood Hashing to minimize variance and keep CPU cache lines packed.

Robin Hood Hashing

Learn why string keys destroy cache locality, and how to fix it using Hash Caching and Heterogeneous Lookups.

Hash Caching and Heterogeneous Lookups

Learn how to globally deduplicate string data and transform complex data into fast integer handles.

String Interning

When our work outgrows a single machine's capability, learn how to partition it across a cluster using Consistent Hashing.

Hash Rings and Consistent Hashing

Implement strict guarantees by bounding a lookup to exactly two memory locations, and build a fast rejection path for massive databases.

Cuckoo Hashing and Filters

High-Speed Hashing

Additional lessons and chapters covering vectorization and trees are coming soon

Coming Soon

This course is intended for those who already have a basic familiarity with C++

Learn data structures and algorithms by building real systems, measuring performance, and understanding how your code interacts with the physical hardware.

A hands-on course where you'll implement, benchmark, and optimize code, turning abstract concepts into practical skills you can immediately apply.

Implement real systems like ECS and custom containers from scratch, reinforcing concepts through hands-on work and gaining confidence by building complete, working solutions.

Learn by Building

Turn abstract concepts into efficient implementations, learning how theoretical ideas translate into real-world code you can understand, modify, and confidently apply.

From Theory to Code

Identify performance bottlenecks, measure improvements correctly, and apply practical optimization techniques without guesswork or misleading assumptions about what actually matters.

Debug and Optimize

Use C++20 and C++23 features to write cleaner, more expressive code while reducing boilerplate and improving both safety and performance in everyday development.

Modern C++ Techniques

Build a toolkit of reusable patterns and approaches that transfer across projects, helping you solve new problems faster without relying on memorized solutions.

Reusable Patterns

Learn how to balance performance, readability, and maintainability, making better engineering decisions based on real constraints rather than idealized or purely theoretical scenarios.

Real-World Tradeoffs

What You'll Learn

Become a software engineer with C++.  Starting from the basics, we guide you step by step along the way

Intro to C++ Programming

If you're completely new to programming, we recommend starting with our introductory course:

New to Programming?

Practical DSA

In the previous lessons, we built optimistic transactions using the hardware's Compare-And-Swap (CAS) instruction. We learned how to pull a struct into our local CPU registers, perform complex math, and publish the result using `compare_exchange_weak()`.


As long as our struct fits inside a 64-bit or 128-bit native register, the CPU guarantees that our updates are absolutely atomic and lock-free.  But what happens when our data doesn't fit into a CPU register?  To build lock-free algorithms in this context, we often need aim our CAS instructions at _**pointers to data**_ rather than the data itself.


In this lesson, we will uncover why lock-free pointers are a hardware minefield. We will expose the physical realities of the global memory allocator, visualize the **use-after-free** trap, and revisit the infamous **ABA Problem**.


## The Pointer CAS Trap


In our earlier examples, we used CAS on basic integers and small state structs. When the CPU executes a CAS instruction on an integer, it compares the numerical bits. If the bits match, the mathematical state of the program has not changed, and it is completely safe to execute the swap.


But a pointer is just a 64-bit hexadecimal integer that represents a physical memory address.


When we ask the CPU to execute a CAS instruction on a `std::atomic<Node*>`, the silicon checks the 64-bit address. **It does not check the data at that address**_**.**_ The CPU has absolutely no idea if the node being pointed to has been modified, corrupted, or entirely deleted by another thread.


To see why this is so dangerous, let's look at a naive attempt to write a lock-free `Pop()` function that removes the element at the `Head` of a linked list:


```c++
#include <atomic>

struct Node {
  int Value;
  Node* Next;
};

std::atomic<Node*> Head;

int NaivePop() {
  // Take a snapshot of the top of the list
  Node* Expected = Head.load();

  do {
    if (Expected == nullptr) {
      return -1; // The list is empty
    }

    // Attempt to swing the Head pointer to the Next node.
    // If Head still equals Expected, overwrite Head with Next
  } while (!Head.compare_exchange_weak(
    Expected,
    Expected->Next //<e>
  ));

  int Result = Expected->Value;
  delete Expected; //<w>
  return Result;
}
```


At first glance, this looks identical to the optimistic CAS loops we wrote previously. We read the `Expected` state, we determine the `Desired` state (which is `Expected->Next`), and we attempt the swap.


Unfortunately, this code is a ticking time bomb.


## The Race Window and Use-After-Free


The vulnerability lies within the condition of the `while` loop, specifically when we attempt to evaluate `Expected->Next`.


```c++
do {
   // ...
} while (!Head.compare_exchange_weak(
  Expected,
  Expected->Next //<e>
));
```


Between the moment our thread loads `Expected` from memory and the moment it attempts to read the `Next` pointer inside that node, we have a **race window**.  Let's step through exactly how the OS scheduler can turn this tiny window into a crash:


<Interactive id="dsa-use-after-free-race">


An interactive step-by-step animation showing two threads interacting with a list initially structured as `Node A -> Node B -> Node C`. A single button works through the following steps:

1. Thread 1 calls `NaivePop()`. It reads `Head`, storing `Node A` in its local `Expected` pointer.
2. The OS scheduler intervenes, pausing Thread 1 and swapping it out of the CPU core.
3. Thread 2 swoops in and also calls `NaivePop()`. It reads `Expected = Node A`, evaluates `Expected->Next` as `Node B`, and successfully executes its CAS instruction. The `Head` of the list is now `Node B`.
4. Thread 2 reaches the end of the function and executes `delete Expected`. `Node A` is destroyed, and the memory allocator unmaps that RAM.
5. The OS wakes Thread 1 back up.
6. Thread 1 resumes exactly where it left off. It attempts to evaluate `Expected->Next` to feed its CAS instruction.
7. Thread 1 dereferences its `Expected` pointer. A visual explosion or error state occurs because `Node A` no longer exists in physical memory.

</Interactive>


Thread 1 blindly reaches across the memory bus to read `Expected->Next`. But `Expected` is pointing to `Node A`, which has been obliterated.


The CPU attempts to access an invalid or unmapped memory address. The hardware triggers a page fault, the operating system catches the illegal access, and our application is terminated with a **segmentation fault**.


This is the classic **use-after-free** bug. In a lock-free environment, we cannot safely dereference a pointer if there is even a fractional chance that another thread might be concurrently deleting it.


## The ABA Problem (Again)


Suppose we recognize the use-after-free trap, and we find a workaround.  We'll implement one of those workarounds in the next chapter but, for now, let's just imagine we've done that and Thread 1 can safely evaluate `Expected->Next` without any use-after-free risk.


We then immediately run into a second issue: the return of  **the ABA problem** we covered <InlineLessonPromo url="dsa/generational-indices" title="Generational Indices" description="Upgrade simple indices into Generational Handles, creating safe, persistent references that detect stale access.">earlier in the course</InlineLessonPromo> in a slightly different context.


The CAS loop ensures the `Expected->Next` pointer hasn't changed, but it doesn't check that the thing it is pointing at hasn't changed.


<Interactive id="dsa-aba-problem">


An interactive step-by-step animation showing a list initially structured as `Node A -> Node B -> Node C`.

1. Thread 1 calls `NaivePop()`. It reads `Expected = Node A`. Because we banned `delete`, it safely evaluates `Expected->Next`, recording its `Desired` state as `Node B`.
2. The OS scheduler pauses Thread 1 right before it fires its CAS instruction.
3. Thread 2 wakes up and pops `Node A`. The list is now `Node B -> Node C`.
4. Thread 2 pops `Node B`. The list is now `Node C`. Thread 2 determines `Node B` is totally unreferenced and safely calls `delete Node B`.
5. Thread 2 pushes a brand new piece of data onto the list, creating `Node D`. The list is now `Node D -> Node C`.
6. Thread 2 takes the old `Node A` it popped in step 3, changes its internal payload, and pushes it _back_ onto the list. The list is now `Node A -> Node D -> Node C`.
7. Thread 1 wakes up! It is holding `Expected = Node A` and `Desired = Node B`. It fires its CAS instruction.
8. The CPU checks `Head`. It sees `Node A`. It compares this to Thread 1's `Expected` value (`Node A`). They match!
9. The CPU executes the swap, excitedly overwriting `Head` with Thread 1's `Desired` value (`Node B`).
10. The list is now pointing to `Node B` (which is corrupted garbage memory). `Node D` and `Node C` are orphaned and permanently lost.

</Interactive>


The CAS instruction only looks at the 64-bit hexadecimal memory address. It saw the memory address for `Node A` at the `Head` of the list, and it saw the memory address for `Node A` in Thread 1's register.


The CPU concluded: _"The addresses match perfectly! Nothing has changed!"_


It executed the swap, overwriting `Head` with Thread 1's desired value: `Node B`. But `Node B` was completely destroyed.


The `Head` of our list is now pointing to corrupted, recycled garbage memory. Our data structure is shattered, but the program simply continues running with silently corrupted memory.


### Why Allocators Recycle


When learning about the ABA problem, many engineers have the same reaction: _"what are the odds of that actually happening?"_


Why would the memory allocator give `Node A` back to us so quickly? If we have gigabytes of free RAM, shouldn't the allocator give us a brand new, never-before-used memory address, reducing the risk of ABA collisions?


In reality, the hardware and the allocator are often optimizing for cache locality.  They actively conspire to recycle memory addresses as aggressively as possible, making ABA issues extremely likely if we don't actively mitigate against it.


If a thread just finished using a piece of memory a few microseconds ago, that memory is physically sitting inside the CPU core's ultra-fast L1 cache.  If we immediately asks for a `new Node()`, the absolute fastest thing the allocator can do is hand back the exact same memory address it just freed.


## Double-Width CAS


If the memory address alone isn't enough to prove the node hasn't changed, we need more information.  We can solve this manifestation of the ABA problem in a very similar way we solved it for array indices earlier in the course by creating a handle that combines the array index with a <InlineLessonPromo url="dsa/generational-indices" title="Generational Indices" description="Upgrade simple indices into Generational Handles, creating safe, persistent references that detect stale access.">version tag</InlineLessonPromo>.


Combining a pointer with a version tag looks very similar:


```c++
#include <cstdint>

// Align to 16 bytes (128 bits)
struct alignas(16) TaggedPointer {
  Node* Ptr;
  uint64_t Version;
};

std::atomic<TaggedPointer> Head;
```


Every time we update the pointer or push it to a list, we also increment the version number.


Even if the memory address is recycled to create an ABA scenario, the version number will have progressed from `1` (A) to `2` (B) to `3` (A). The combined state `A1` does not match `A3`, so the CAS instruction will correctly fail.


However, as we saw earlier, we need to be cautious about how much data we try to stuff into a `std::atomic`.  On a 64-bit operating system, a standard pointer is 64 bits. If we combine it with any other data, it no longer fits within a 64-bit register.


To update our 128-bit `TaggedPointer` safely, we need the CPU to perform a **Double-Width Compare-and-Swap (DWCAS)**.  Most modern desktop and server processors support this, but earlier processors and some modern mobile ARM chips don't.


We can check if our target architecture natively supports this using the atomic's `is_always_lock_free` flag:


```c++
static_assert(
  std::atomic<TaggedPointer>::is_always_lock_free, //<h>
  "Hardware does not natively support 128-bit CAS"
);
```


If we compile a `std::atomic` using a 128-bit type for a chip that lacks 128-bit CAS, the standard library will quietly inject a hidden `std::mutex` into our wrapper to maintain the atomic behaviour. We will lose all the performance benefits of our lock-free design, suffering from OS context switches every time we touch the pointer.


In the next chapter, we will create a lock-free linked list that combine this `TaggedPointer` technique with the <InlineLessonPromo url="dsa/index-based-pool-lists" title="Index-Based and Pool-Allocated Lists" description="Replace 64-bit pointers with lightweight indices and back our linked list with a contiguous memory pool to maximize performance.">index-based links</InlineLessonPromo> we covered previously.  This means we can reduce the size of our struct to 64 bits - 32 bits for the index, and 32 bits for the version.


## Advanced: Hazard Pointers and EBR


If 128-bit DWCAS isn't perfectly portable, what other options are there?  We need to implement an architecture that follows a golden rule: never physically `delete` memory if there is any chance another thread might be looking at it.


If memory is never freed while references exist, use-after-free is impossible. If memory is never returned to the allocator, it can never be recycled, making the ABA problem impossible.  But we can't just let our programs consume infinite RAM. We need a way to **logically** remove a node from the data structure, but **defer** its physical destruction until we can be certain that every single thread has finished looking at it.


This concept is called **safe memory reclamation (SMR)**, and it requires complex architectural patterns to manage.  Two common approaches are:

1. **Hazard Pointers:** Threads announce which specific memory addresses they are currently using by placing them in a globally visible "hazard" list. Before another thread calls `delete`, it checks the hazard list. If the address is there, the deletion is deferred.
2. **Epoch-Based Reclamation:** The application is divided into epochs.  New epochs might start on a time interval, or after every frame in a game engine, or after every batch of transactions in a data service. When a node is removed, it is tagged with the current epoch. Memory is only physically deleted when all threads announce they have safely progressed to the next epoch.

## Summary


In this lesson, we discovered why taking optimistic lock-free logic and aiming it at raw pointers is inherently dangerous.

1. **The Pointer Limit:** We learned that CAS only verifies the numerical 64-bit memory address, remaining entirely blind to the actual data contents living at that address.
2. **Use-After-Free:** We visualized the fatal race window in naive lock-free loops. Dereferencing a pointer that a suspended thread expects to be valid often results in an OS-level segmentation fault if another thread deletes it.
3. **The ABA Problem:** We explored how a CAS instruction can be tricked if a memory address is popped, deleted, and then re-allocated for a new node.
4. **Cache Warmth:** We realized that the ABA problem is not a statistical anomaly. Modern thread-local allocators aggressively recycle hot L1 cache lines, practically guaranteeing address reuse.
5. **Double-Word CAS:** We reviewed the workaround of adding a version tag to the pointer, which often requires 128-bit hardware instructions that lack universal portability.

In the next chapter, we will apply these concepts to build safe lock-free containers including **ring buffers** and **Treiber stacks**.

Compare-And-Swap and Optimistic Concurrency

The `std::atomic` API and Data Tearing

ABA problem

Herb Sutter: Lock-Free Programming (or, Juggling Razor Blades)

Explore the dangers of lock-free C++ pointer concurrency. Learn why Compare-And-Swap (CAS) triggers the ABA problem, how CPU cache warmth drives memory recycling, and historical DCAS workarounds.

Lock-Free Pointers

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

Practical DSA