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 first half of this course, we stripped away the abstractions of object-oriented programming and flattened everything into contiguous memory.  By packing data into dense `std::vector` arrays, we spoon-fed the CPU's hardware prefetcher, virtually eliminating cache misses and maximizing throughput.


But contiguous arrays are not the answer to every engineering problem.  We will now start to look at problems that are best solved with non-contiguous data layouts, such as lists, trees, and graphs.  Conceptually, these data structures are collections of nodes - chunks of memory that we link together using pointers:


<Interactive id="dsa-list-tree-graph">


An interactive showing a list, a tree, and a graph


</Interactive>


These designs immediately make our memory layout more complex.  With data stored in a contiguous structure like a `std::vector`, we are managing a large, single block of contiguous memory.  However, with a linked structure, there are typically many smaller blocks of memory that we need to allocate and keep track of.  In the simplest implementation of a linked list, for example, every single element in the collection gets its own dedicated chunk of memory.


So, before we can design high-performance linked data structures, we'll spend the first two lessons understanding the main problems of allocating and working with lots of discrete blocks of memory:

- Each dynamic allocation of memory has a significant performance cost.
- Each block of memory we allocate requires additional bookkeeping, which increases memory demands.
- Allocating and deallocating memory causes memory fragmentation, which degrades the performance of our program over time.

## Stack and Heap Allocation


Memory allocated for our local variables is typically placed on the **stack**. The stack is a continuous block of memory managed automatically by the compiler. When a function is called, the stack pointer is simply moved to make room for its variables. When the function finishes, the pointer moves back, instantly freeing that memory:


```c++
void FastFunction() {
  // Memory is automatically reserved on the stack
  int x{42};

  // Do work...

  // Memory is automatically reclaimed when the function returns
}
```


Stack allocation is incredibly fast because it only requires basic pointer arithmetic. However, stack space is limited, and the memory only lives for the duration of the function call. If we need memory that persists beyond the function's scope, or if we need a large amount of memory, we must allocate it on the **heap**.


We use the `new` keyword to dynamically request memory from the heap, and `delete` to free it:


```c++
void SlowFunction() {
  // Ask the global allocator for memory on the heap
  int* x = new int{42}; //<w>

  // Do work...

  // We must explicitly free the memory when we are done
  delete x;
}
```


This simple `new` keyword invokes a highly complex function call to a general-purpose memory allocator.


The operating system manages the physical RAM in your machine. However, the operating system does not care about our 4-byte integer. The OS manages memory in large, fixed-size chunks called **pages** - typically 4KB (4096 bytes).


If we ask the OS for memory, it will hand us an entire 4KB page. It is then up to our program to divide that page into usable pieces.  This subdivision is the job of the C++ runtime allocator.


When we call `new`, the allocator must look at its current pool of pages and run an algorithm to find a gap of unused memory that is perfectly sized to fit our request. It has to scan internal data structures, check availability, carve out the requested bytes, and update its records.


If it can't find a suitable location, it must pause our application, perform an expensive system call to ask the OS for another 4KB page, and then resume.  This is a heavy, expensive process.


## Benchmarking the Heap


Let's quantify the cost using Google Benchmark.


We will write tests where we allocate 1,000 integers in different ways.  The first test allocates them on the stack, the second allocates them contiguously on the heap using `std::vector`, and the third allocates them as individual chunks of memory using 1,000 `new` calls:


```c++
#include <benchmark/benchmark.h>
#include <vector>

static void BM_StackAllocation(benchmark::State& state) {
  for (auto _ : state) {
    int data[1000];
    benchmark::DoNotOptimize(data);
  }
}
BENCHMARK(BM_StackAllocation);

static void BM_HeapAllocation(benchmark::State& state) {
  for (auto _ : state) {
    std::vector<int> data(1000);
    benchmark::DoNotOptimize(data);
  }
}
BENCHMARK(BM_HeapAllocation);

static void BM_MultipleHeapAllocation(benchmark::State& state) {
  for (auto _ : state) {
    for (int i = 0; i < 1000; ++i) {
      int* p = new int;
      benchmark::DoNotOptimize(p);
      delete p;
    }
  }
}
BENCHMARK(BM_MultipleHeapAllocation);
```


```c++
//<o>
------------------------------------
Benchmark                        CPU
------------------------------------
BM_StackAllocation           1.28 ns
BM_HeapAllocation            5441 ns
BM_MultipleHeapAllocation   33551 ns
```


Our `BM_StackAllocation` benchmark requests space for 1,000 integers on the stack, and is effectively instantaneous.


The `BM_HeapAllocation` benchmark uses a `std::vector`, which dynamically allocates space for 1,000 integers on the heap. This triggers the heavy search algorithm we described above.


The `BM_MultipleHeapAllocation` benchmark uses `new` to individually allocate 1,000 integers. Even though it allocates the exact same number of useful bytes as the `std::vector`, it takes significantly longer.  Whilst some optimizations are possible in simple cases like this, as a general rule, the performance cost of heap allocation is paid **per allocation**, not per byte.


## Hidden Metadata and Chunk Headers


Let's cover this internal bookkeeping some more by considering the mechanics of `delete`.  When we ask the allocator to free our memory, we pass it a pointer. Notice that we do **not** tell it how many bytes to free:


```c++
Player* p = new Player();
// ...
delete p; //<h>
```


How does the allocator know if `p` points to a 16-byte object or a 1024-byte object?


It knows because it secretly recorded that information when it created the object. The global allocator doesn't just give you the memory you asked for; it allocates extra memory to store its own bookkeeping data.  This is called the **chunk header**, containing the size of the allocation, flags indicating if the block is free or in use, and sometimes padding to ensure CPU alignment rules are met.


<Interactive id="dsa-chunk-header">


A memory layout showing a physical heap block. A label points to the pointer returned to the user. Directly before that address in memory, colored in red, is a "Chunk Header" containing an integer size and metadata flags.


</Interactive>


If we are allocating a large 10-megabyte array of objects, a 16-byte hidden header is a meaningless rounding error.  But in the context of a linked data structure where each of our objects might be a discrete node, there are many more chunks of memory involved, and therefore many more chunk headers.


If each node is 16 bytes, and the allocator attaches a 16-byte header to each of them, we have instantly doubled our memory footprint.


<Aside>


### The `sizeof` Operator


It is worth noting that the `sizeof` operator will never reveal this hidden metadata.  If we call `sizeof(Node)`, the compiler evaluates this at compile-time based purely on your class or struct definition. The chunk header is a runtime construct added dynamically by the allocator.


The only way to see this physical memory waste is by profiling the application's total memory consumption at the OS level.


</Aside>


## The Global Allocator and Thread Contention


The complex search algorithm and administrative overhead of `new` is bad, but in the modern era of multi-core CPUs, there is another problem.


In our previous lessons on parallelism, we learned about the dangers of data races. If two threads attempt to modify the same data at the same time, the program will crash or be corrupted.  


The heap is a globally shared resource, so the dangers of concurrency apply with memory allocation, too.  The allocator manages a complex web of internal "free lists" to keep track of which memory blocks are available. If multiple threads search the free list and claim the same block of memory, the system is doomed.


To prevent this, general-purpose allocators are forced to use locks - usually a Mutex (Mutual Exclusion) lock around the allocation logic.  When a thread calls `new`, it acquires the lock, runs the search algorithm, claims the memory, updates the bookkeeping, and then releases the lock.


If another thread tries to allocate memory during that process, the OS is forced to put it to sleep while it waits in line for the allocator.


In the following benchmark, we update our dynamic allocation of 1,000 integers to be a multithreaded algorithm using `std::async`. We split the work across four separate threads, hoping to speed it up:


```c++
#include <benchmark/benchmark.h>
#include <future> //<h>

//<c title="Single Theaded Implementation (Unchanged)">
//<l>static void BM_SingleThread(benchmark::State&) {/*...*/}
static void BM_SingleThread(benchmark::State& state) {
  for (auto _ : state) {
    for (int i = 0; i < 1000; ++i) {
      int* p = new int;
      benchmark::DoNotOptimize(p);
      delete p;
    }
  }
}
BENCHMARK(BM_SingleThreaded);
//</c>

static void BM_MultiThread(benchmark::State& state) {
  for (auto _ : state) {
    auto allocate_work = []() {
      for (int i = 0; i < 250; ++i) {
        int* p = new int;
        benchmark::DoNotOptimize(p);
        delete p;
      }
    };

    // Launch 4 asynchronous tasks to share the 1,000 allocations
    auto t1 = std::async(std::launch::async, allocate_work);//<h>
    auto t2 = std::async(std::launch::async, allocate_work);//<h>
    auto t3 = std::async(std::launch::async, allocate_work);//<h>
    auto t4 = std::async(std::launch::async, allocate_work);//<h>

    t1.wait();
    t2.wait();
    t3.wait();
    t4.wait();
  }
}

// We use MeasureProcessCPUTime() to capture the total CPU effort across all threads
BENCHMARK(BM_MultiThread)->MeasureProcessCPUTime();
```


Even though we now have four cores working on the problem, the contention and synchronization overhead usually make the process take even longer than a single-threaded implementation:


```c++
//<o>
--------------------------------------------------
Benchmark                         Time         CPU
--------------------------------------------------
BM_SingleThread               36129 ns    36098 ns
BM_MultiThread/process_time   44490 ns   123460 ns
```


### Custom Allocators


Earlier, we saw how we could resolve multithread contention by having each thread work on local data owned exclusively by that thread, and then synchronize that data with other threads only when needed.  This was the pattern underlying MapReduce and similar techniques.


A similar concept can be applied to memory, too.  Modern allocators like [TCMalloc](https://github.com/google/tcmalloc) or [jemalloc](https://github.com/jemalloc/jemalloc) can mitigate contention by giving each thread its own mini-heap to work with, transferring memory ownership between threads only when synchronization is required.


However, any general-purpose allocator is inherently constrained by a need to be flexible.  It doesn't know if we're writing code to run on a supercomputer or an electric toothbrush. It has no idea what kind of data we are storing, how long it will live, or what our performance requirements are.  It needs to work reasonably well across all of these dimensions and more.


But in our projects, we don't need maximum flexibility.  We are usually allocating memory to implement a specific feature within a specific domain.  We will have a pretty good idea of the type of systems our program will run on, what our data looks like, and how it will be used.  Therefore, we can often do a better job than the general-purpose allocators.  We'll see how to create custom allocators in this chapter.


## Summary


In this lesson, we established the fundamental rules of dynamic memory that will govern the rest of this course.

1. Dynamic allocation is a heavy algorithmic search through the OS's available memory pages.
2. The global allocator inflates your memory footprint by attaching hidden metadata headers to every single allocation.
3. The heap is a global resource protected by locks. Multithreaded systems that spam `new` will stall and idle their CPU cores.

We have proven that the global allocator is slow and explained why. However, there is a secondary, much more destructive consequence of using `new` and `delete` over long periods of time. Even if we perfectly `delete` every object we create and have zero memory leaks, our program will still eventually choke and die.  In the next lesson, we will explore the silent killer of long-running applications: **memory fragmentation**.

`new` expression

Memory Management

CppCon 2015: Andrei Alexandrescu `std::allocator...`

Game Engine Architecture

The GNU Allocator

Explore the hidden performance costs of C++ dynamic memory allocation. Learn how new and delete interact with the OS, hidden metadata headers, and multithreaded lock contention.

C++ Heap Allocation: The Physical Cost of new and delete

The Global Allocator and Thread Contention

The Physical Reality of `new` and `delete`

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

Practical DSA

The Physical Reality of new and delete

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

The Physical Reality of `new` and `delete`