osrm-extract drops node-based edges when run multi-threaded
osrm-extract produces a different node-based graph on every run when it is given more than one thread, and the graph gets smaller as the thread count goes up. Single-threaded extraction is reproducible.
Measured on master e9436d329, europe/france/ile-de-france-latest.osm.pbf from Geofabrik, profiles/foot.lua, macOS, one binary, varying only -t:
| threads | node-based edges | difference from one thread |
|---|---|---|
| 1 | 3 214 880 | |
| 2 | 3 208 849 | -6 031 (0.19%) |
| 4 | 3 184 946 | -29 934 (0.93%) |
| 8 | 3 167 815 | -47 065 (1.46%) |
Two runs at -t 1 gave the same edge count and the same .osrm.geometry md5. Every threaded run differed from every other threaded run.
A sort cannot explain this. The count itself changes, so edges are being lost rather than reordered, and the loss grows with the number of threads.
What it affects
.osrm.nbg_nodes, .osrm.names and .osrm.restrictions come out identical between runs. .osrm.geometry, .osrm.edges, .osrm.ebg_nodes, .osrm.ebg and .osrm.turn_weight_penalties all differ, so everything from geometry compression onwards inherits it.
It is visible in routing. Serving two extractions of the same file side by side and asking each the same questions:
- 400 ordinary street routes: 4 differed, none by more than 1%
- 300 routes with both ends inside Place de la Republique: 67 differed, 20 of them by more than 1%, the worst being 37.5 m against 59.5 m for the same request
The area scenarios are flaky for what looks like the same reason. Five consecutive runs of features/foot/area*.feature on a clean tree gave two passes, two failures at the same scenario, and one hang.
Where it looks like it is
The parse pipeline in Extractor::ParseOSMData is location_cache_filter (serial_in_order), process_elements_filter (parallel), extractor_callbacks_filter (serial_in_order). The appends into all_edges_list happen in the serial filter, so the loss is upstream of that, in the parallel stage that runs the profile.
Worth noting separately: CmpEdgeByOSMStartID and CmpEdgeByOSMTargetID in extraction_containers.cpp each compare a single id, so neither is a total order, and tbb::parallel_sort is not stable. That is a real reproducibility problem on its own, but giving them secondary keys does not change any of the numbers above.
Reproducing
osrm-extract -t 1 -p profiles/foot.lua ile-de-france.osm.pbf # note the edge count
osrm-extract -t 8 -p profiles/foot.lua ile-de-france.osm.pbf # smaller, and different each timeThe "Node-based graph contains N edges" line is enough to see it. Comparing the md5 of .osrm.geometry between two runs shows it as well.
Source: Project-OSRM/osrm-backend