A performance study of Breadth-First Search across two graph memory layouts:
- Pointer graph — linked-list adjacency lists, scattered across the heap
- CSR graph — Compressed Sparse Row, two flat contiguous arrays
The central question is: when algorithm complexity is identical, how much does memory layout change real performance? The answer, measured through wall-clock timing and Cachegrind cache simulations, is a lot.
A full analysis with graphs and data is in report.pdf.
.
├── src/
│ ├── bfs_pointer.c # BFS over pointer-based adjacency list
│ ├── bfs_csr.c # BFS over CSR graph
│ ├── graph_csr.c # Pointer → CSR conversion
│ ├── graph_loader.c # Graph file parser
│ ├── benchmark.c # Timing harness
│ └── main.c # CLI entry point
├── include/
│ └── graph.h # Shared type definitions
├── scripts/
│ └── gen_graph.py # Synthetic graph generator
├── tests/ # Correctness test cases + expected outputs
├── data/ # Sample graphs (up to 100k vertices)
├── run_tests.py # Correctness test runner
├── Makefile
└── report.pdf
Each vertex holds a linked list of Edge structs allocated individually on the heap.
vertex 0 → [Edge{dst=1}] → [Edge{dst=2}] → NULL
vertex 1 → [Edge{dst=2}] → NULL
Simple to build, but BFS requires pointer chasing: each neighbor access is a potential cache miss.
The entire graph lives in two flat integer arrays.
row_ptr: [0, 2, 3, 3]
col_idx: [1, 2, 2]
Neighbors of vertex v are col_idx[row_ptr[v] .. row_ptr[v+1]-1]. Sequential memory access; the hardware prefetcher can actually help here.
n
deg v1 v2 ... v_deg
deg v1 v2 ... v_deg
...
Each line after the first describes outgoing neighbors of a vertex. Example:
3
2 1 2
1 2
0
Vertex 0 → {1, 2}, vertex 1 → {2}, vertex 2 → {}.
makeProduces ./graph_bench. Requires GCC and a POSIX system.
make clean # remove build artifacts# Run BFS using the pointer representation
./graph_bench --impl=pointer --graph=tests/test_small.txt --source=0
# Run BFS using CSR
./graph_bench --impl=csr --graph=tests/test_small.txt --source=0
# Repeat N times for stable timing
./graph_bench --impl=csr --graph=data/er_100k.txt --source=0 --repeat=10Output:
visited=99873
time_ms=42.17
# Erdős–Rényi random graph: 10k vertices, avg degree 8
python3 scripts/gen_graph.py --kind er --n 10000 --deg 8 --seed 1 --out data/er_10k.txt
# Grid graph: 316 × 316 ≈ 100k vertices
python3 scripts/gen_graph.py --kind grid --rows 316 --cols 316 --out data/grid_100k.txt
# Star (hub-and-spoke)
python3 scripts/gen_graph.py --kind star --n 100000 --out data/star_100k.txt
# Chain (path graph)
python3 scripts/gen_graph.py --kind chain --n 100000 --out data/chain_100k.txtSupported types: er, grid, star, chain.
# Profile pointer BFS
valgrind --tool=cachegrind ./graph_bench --impl=pointer --graph=data/er_100k.txt --source=0
# Profile CSR BFS
valgrind --tool=cachegrind ./graph_bench --impl=csr --graph=data/er_100k.txt --source=0Simulate a different L1 data cache (size, associativity, line size):
valgrind --tool=cachegrind --D1=32768,8,64 ./graph_bench --impl=csr --graph=data/er_100k.txt --source=0
valgrind --tool=cachegrind --D1=32768,8,128 ./graph_bench --impl=pointer --graph=data/er_100k.txt --source=0Key metrics to compare: D1 misses and LLd misses.
python3 run_tests.py .Builds a test driver, runs both implementations against all test cases in tests/, and checks visited-count and distance arrays against a reference Python BFS.
- CSR BFS is consistently 2–5× faster than pointer BFS on large graphs.
- CSR generates an order of magnitude fewer L1 and LLC cache misses.
- The gap grows with graph size and shrinks with larger cache lines (which amortize pointer-chase misses).
- Graph topology matters: random (ER) graphs show the largest CSR advantage; chain graphs are near-equal because both layouts access memory almost sequentially.
See report.pdf for full data, plots, and analysis.
- Manya Jain
- Prabuddha Sinha