BFS benchmark results
Under construction
This page is under construction ~
Out of all 4 versions, V3 was the fastest version at all four graph sizes in this run. On the largest graph, it took 69.71 ms, compared with 287.47 ms sequentially: a 4.12× speedup.
Timings
All values are median milliseconds over five measured runs after warm-up. For each parallel version, I selected the worker count with the lowest median.
Numbers in brackets are worker counts. Sequential BFS uses one thread.
| Vertices | Undirected edges | Sequential | V1: Mutex | V2: Atomic | V3: Persistent | V4: Parallel assembly |
|---|---|---|---|---|---|---|
| 200,000 | 800,000 | 17.02 | 51.96 (1) | 17.11 (4) | 12.30 (8) | 14.23 (4) |
| 500,000 | 2,000,000 | 72.15 | 196.17 (1) | 36.10 (8) | 25.92 (10) | 28.80 (8) |
| 1,000,000 | 4,000,000 | 178.31 | 477.30 (1) | 65.92 (14) | 47.63 (16) | 53.71 (14) |
| 1,500,000 | 6,000,000 | 287.47 | 764.75 (1) | 90.06 (14) | 69.71 (14) | 73.64 (14) |
Speedup is the sequential median divided by the parallel median. The worker counts above are the best among those tested, not a general recommendation for every graph.
Speedup
Compared with sequential BFS on the same graph. Brackets show the selected worker count; values below 1.00× mean slower than sequential.
| Vertices | Undirected edges | V1: Mutex | V2: Atomic | V3: Persistent | V4: Parallel assembly |
|---|---|---|---|---|---|
| 200,000 | 800,000 | 0.33× (1) | 0.99× (4) | 1.38× (8) | 1.20× (4) |
| 500,000 | 2,000,000 | 0.37× (1) | 2.00× (8) | 2.78× (10) | 2.51× (8) |
| 1,000,000 | 4,000,000 | 0.37× (1) | 2.71× (14) | 3.74× (16) | 3.32× (14) |
| 1,500,000 | 6,000,000 | 0.38× (1) | 3.19× (14) | 4.12× (14) | 3.90× (14) |
Observations
v1 did not scall well (as expected)
Its best result used only one worker at every size, and was still slower than sequential BFS. Every discovery check passes through the same shared mutex, which is obviously a huge bottle neck.
This was expected as the main purpose of V1 was transition to parallel implementation and introducing worker splitting.
V2 improved the timing significantly.
Replacing the mutex with atomic discovery reached 3.19× speedup on the largest graph. At 200,000 vertices, it was roughly equal to sequential BFS.
V3 improved on V2 at every size
It reuses workers and private output buffers. It also adds a visited check before compare-and-swap and changes the initialization stores, so the difference does not isolate thread reuse alone.
V4 was slower than V3 at every size
On the largest graph, both selected 14 workers, but V4 took 73.64 ms versus 69.71 ms, about 6% longer. I was surprised by these results, and have yet to investigate which component was responsible for the additional costs.
V3's speedup increased from 1.38× on the smallest graph to 4.12× on the largest. Larger inputs can spread fixed parallel overhead over more work and change cache behaviour.
Test conditions
- Release build on my laptop: 8 physical cores, 16 logical processors.
- One generated graph per size: an undirected binary-tree backbone plus random extra edges, using seed 67. Each undirected edge is stored in both directions.
- Tested worker counts: 1, 2, 3, 4, 6, 8, 10, 12, 14, 16. Every implementation uses the same graph at each size.
- Timings cover the complete BFS call, including initialization, thread setup and output construction. Graph generation, CSR construction and correctness checks are outside the timer.
- Every traversal is compared with sequential distances. Implementations run in a fixed order.
These results cover one graph family, one seed and one machine. Different graph structures or hardware may change the ranking and worker count. I currently use V3 as the preferred parallel BFS implementation.