Deterministic pre-processing for reproducible routes/alternatives

[freenerd]

In http://www.openstreetmap.org/user/naoliv/diary/35981#comment32323 @flohoff notes that osrm-backend does not return deterministic results. We've run into this at #1560 #1701 as well.

Ideally several runs of osrm-extract/osrm-prepare on the same OSM dataset should reproducibly return the same results. This is especially important for the QA work @flohoff already did and @naoliv picked up as well.

How could we make this deterministic?

/cc @TheMarex @daniel-j-h @danpat @emiltin

[daniel-j-h]

Hmm what comes to mind is 1/ set thread count to one and 2/ do stable sorting.

I think there are already some options sprinkled around for 1/, at least I have seen a few places where the thread count is calculated based on hardware concurrency and a user value. For 2/ using std::stable_sort instead of std::sort should do the trick.

I think the bigger question is: how to give users a switch to toggle between those two modes, that is how to pass down the flag to all subcomponents in a simple and clean way.

I think we also have to look at what options the dependencies offer in this regard (esp. stxxl, osmium).

[flohoff]

I have multiple issues with this:

• From what i understood the root cause is randomization in node order causing routes to alternate between same travel time alternates.
• The "same distance route" are not same distance but same travel time. This is caused by some rounding errors on travel times. I have tried moving nodes 20-50m away from alternating routes with no success. I guess 20-50m dont cause the rounding to return a different result.
• Even WHEN there is the rare case that there are same distance routes travel time wise i expect all of them beeing returned in the request. This is not the case. Its purely random which of the routes you get in return which i have shown in my initial bug report.

So IMHO its not one but multiple errors which show up.

[daniel-j-h]

For the record, I just talked to @joto re. determinism in libosmium: and although parsing is done in parallel, the handler invocations are getting serialized. That is, at least libosmium's concurrency is safe.

[danpat]

Related: #2617