A C++17 benchmarking tool that demonstrates how CPU cache behavior impacts data structure and algorithm performance. It measures traversal, search, and aggregation operations across multiple data structures and highlights the dramatic effect of memory layout on real-world execution time.
Modern CPUs rely heavily on multi-level caches (L1, L2, L3) to bridge the gap between processor speed and main memory latency. A cache miss to DRAM can cost 100+ nanoseconds — roughly 200x slower than an L1 hit. Despite this, most textbook algorithm analysis only considers time complexity (Big-O) and ignores memory access patterns entirely.
This leads to surprising real-world behavior:
- A linked list (O(n) traversal, same as array) can be 5-10x slower than an array due to pointer chasing and scattered memory allocation causing cache misses on every node access.
- A Binary Search Tree (O(log n) search) can be slower than a B-Tree (also O(log n)) because BST nodes are scattered in memory while B-Tree nodes pack multiple keys into cache-line-sized blocks.
- A naive matrix multiply and a tiled matrix multiply are both O(n^3), but tiling can deliver a 2-4x speedup by keeping working data within the L1 cache.
This project quantifies these effects by benchmarking identical operations across data structures with different memory layouts, making cache behavior visible and measurable.
| Data Structure | Memory Layout | Why It's Included |
|---|---|---|
| Array | Contiguous std::vector<int> |
Baseline — best possible spatial locality |
| Linked List (Scattered) | Individual new per node |
Worst case — nodes scattered across heap |
| Linked List (Arena) | Nodes in a contiguous std::vector |
Shows how arena allocation recovers locality |
| Binary Search Tree | Individual new per node |
Pointer-chasing tree — poor cache behavior |
| B-Tree (order 16) | Nodes sized to fit ~2 cache lines | Cache-friendly tree — keys packed in arrays |
| Hash Table | std::unordered_map |
Bucket-based — mixed locality characteristics |
- Traversal — Visit every element (measures sequential access pattern)
- Search — Find a specific key (measures random access pattern)
- Sum — Aggregate all values (measures read throughput)
- Stride Access — Array access at strides 1, 2, 4, ..., 128 (measures spatial locality degradation)
- Scattered vs Arena Linked List — Direct comparison showing how contiguous allocation speeds up pointer-based structures
- Matrix Multiply — Three algorithms compared:
- Naive — Standard ijk loop (poor cache behavior on column access of B)
- Tiled/Blocked — Block size tuned so 3 blocks fit in L1 cache (cache-aware)
- Recursive Divide-and-Conquer — Automatically adapts to cache hierarchy (cache-oblivious)
cache_bench/
├── include/ # Header files
│ ├── benchmark.h # Benchmark runner (timing, statistics)
│ ├── perf_counters.h # High-resolution timer (chrono-based)
│ ├── result_table.h # Formatted table output
│ ├── array_ds.h # Contiguous array wrapper
│ ├── linked_list.h # Linked list (scattered + arena variants)
│ ├── bst.h # Binary search tree
│ ├── btree.h # B-Tree (order 16, cache-line optimized)
│ ├── hashtable.h # Hash table (std::unordered_map wrapper)
│ └── matrix_ops.h # Matrix multiply (naive, tiled, recursive)
├── src/ # Implementations
│ ├── main.cpp # Entry point — orchestrates all benchmarks
│ ├── benchmark.cpp # Runs N iterations, computes median/mean/stddev
│ ├── perf_counters.cpp # Timer implementation
│ ├── result_table.cpp # Pretty-prints results as ASCII tables
│ ├── array_ds.cpp # Array operations (traverse, search, sum, stride)
│ ├── linked_list.cpp # Scattered (heap) and arena (contiguous) allocation
│ ├── bst.cpp # BST insert/traverse/search/sum
│ ├── btree.cpp # B-Tree with split/insert/traverse/search
│ ├── hashtable.cpp # unordered_map wrapper operations
│ └── matrix_ops.cpp # Three matrix multiply algorithms
├── scripts/
│ └── run_all.sh # Runs small, medium, and large benchmark configs
├── build/ # Compiled objects and binary (generated)
└── Makefile # Build system (clang++, C++17, -O2)
- B-Tree node sizing:
ORDER=16means up to 31 keys per node (124 bytes) + 32 child pointers, sized to fit in ~2 cache lines (128 bytes each on most architectures). This maximizes useful data per cache fetch during search. - Arena allocation: The linked list's
build_contiguous()allocates all nodes in a singlestd::vector<ListNode>, ensuring nodes are adjacent in memory even though they're connected by pointers. - Tiled matrix block size: Default
block_size=48is chosen so that 3 blocks (A, B, C sub-matrices) of48 * 48 * 8 bytes = ~55 KBfit within a typical 64 KB L1 data cache. - Statistical rigor: Each benchmark runs N iterations (default 30), reporting median, mean, and standard deviation to account for OS scheduling noise.
- C++17 compatible compiler (clang++ or g++)
- macOS or Linux
# Build
make
# Run with default settings (N=1000,10000,100000 | 30 iterations | 256x256 matrix)
make run
# Custom run
./build/cache_bench --sizes 1000,10000,100000,1000000 --iterations 50 --matrix-size 512
# Run all configurations (small, medium, large)
./scripts/run_all.sh| Flag | Default | Description |
|---|---|---|
--sizes N1,N2,... |
1000,10000,100000 |
Data structure sizes to benchmark |
--iterations N |
30 |
Number of iterations per benchmark |
--matrix-size N |
256 |
Matrix dimension for multiply test |
- Contiguous memory (arrays) yields the best cache locality — hardware prefetchers thrive on sequential access
- Pointer chasing (linked lists, BSTs) causes cache misses on every node access
- Arena allocation recovers locality for pointer-based structures without changing the data structure's API
- B-Trees outperform BSTs for the same operations due to cache-line-sized nodes that pack multiple keys
- Tiled matrix multiply exploits spatial locality by keeping working sets within L1 cache
- Stride access demonstrates spatial locality degradation — as stride increases, cache line utilization drops