A Tale of Breadth-First Search
summary
Starts from a baseline BFS over a social graph of 65 million nodes, 1.8 billion edges using a compact adjacency list that cuts memory from 15.9GB to 7GB. Uses measurement, profiling and iterative experiments: replacing visited set with level array, sorting node slices (uint32 specialization then radix), loop unrolling, fusing checks, and chunked parallelism to avoid load imbalance and cache fights. Results end up 48s → 3.8s on a 48-core NUMA box and 2× on one core (48s→24s); many failed attempts (bloom/cuckoo, naive parallel split).
AI-written summary · about
chapters (13)
- 0:00Intro
- 2:04Basic Process
- 3:51Basic ideas for modern processors
- 6:23Breadth First Search
- 9:25Back of the envelope calculation...
- 11:52Reusing Level
- 15:21Random Access Part 2
- 18:09Cuckoo and Bloom Filter?
- 18:53Unrolling loops
- 20:22Basic ideas for modern processor parallelism
- 23:42Bottlenecks
- 26:34Multilevel bitmaps
- 27:57Single Core: 48s - 24s
