[OSRM-talk] Route flapping / osrm-prepare adds randomness?

[Patrick Niklaus]

Your data is broken, this happens if you run osmium to verify the integrity:

osmium check-refs -v -r -i germany.osm.pbf

There are 217165748 nodes, 34578441 ways, and 472363 relations in this file.
Nodes     in ways      missing: 575586
Nodes     in relations missing: 9665
Ways      in relations missing: 171812
Relations in relations missing: 0


On Wed, Jul 1, 2015 at 4:09 PM, Patrick Niklaus
<patrick.niklaus at student.kit.edu> wrote:
> Checked the supposedly broken routes, indeed they all have exactly the
> same length. So yes this is down to non-deterministic node ordering
> caused by parallel sorting/parsing. We can't fix this, it is just a
> side-effect of parallel parsing done by osmium and parallel sorting.
> It might be desirable to have consistent soriting, but not at the cost
> of removing parallelization.
> So this isn't a bug after all.
>
> The "random" JSON ordering is due to using `std::unordered_map` (you
> might guess the effect of that from its name).
>
> On Wed, Jul 1, 2015 at 3:19 PM, Florian Lohoff <f at zz.de> wrote:
>> On Wed, Jul 01, 2015 at 02:37:25PM +0200, Patrick Niklaus wrote:
>>> Confirmed on current develop branch using the Isle of Man extract.
>>> Currently bisecting to find out which change caused this. It is
>>> expected that pre-processing is not 100% deterministic, since we use
>>> parallel sorting (node IDs will change), so the JSON response will
>>> always have a different checksum. However the geometry should always
>>> be the same.
>>>
>>> In theory it could happen that two paths with exactly the same travel
>>> time get chosen in different files (because of different node ids, so
>>> the edges are traversed in different order).
>>
>> Even with the same travel time it'll be very much appreciated if there
>> was a deterministic ordering (which is the route and which the
>> alternate) - In the end by highest osm node id or street name or
>> whatever.
>>
>> And it seems the order of the json result is also "random". I know
>> that its not specified what order an json dictionary/object gets
>> serialized but its interesting to see.
>>
>> BTW: I have seen this kind of route flap before 0.3.9 IMHO probably even
>> before 0.3.4 - It just got more anoying as i process a lot more routes
>> so the noise went way up.
>>
>> Flo
>> --
>> Florian Lohoff                                                 f at zz.de
>>      We need to self-defense - GnuPG/PGP enable your email today!
>>
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.10 (GNU/Linux)
>>
>> iQIVAwUBVZPo2ZDdQSDLCfIvAQpY8w//SKS6FnIKV3agk1TIYKOxMWUqSCFWBv+l
>> G8QuZSfQB4PAE4JfuV2PtIF8IOceV7MRSQKo6IoA0XOuAzew7wYAgo1vJDh2rwNQ
>> mwLmxUD2JAaYtt1ci9pqghOwym9nPHYNRNYxSJ+EHL4Ijf2TC2JtH33pHQI0nwvH
>> djppJPypJ/LxEWCs/AI8TnQ/uetZcXyCB7Y3xSj91PDGcfXkuFpnPQY1fHmBcONW
>> MiG9W15X/f4tx+E25xRkSeP8VR1Oge2FrzB9UtvtInr9K251YuCwWnEUWb+xEhpG
>> soK07xcMcXLeAB3CYLf/OxnEuQg4mz6HjV/RH1xCus48d3rJSfJ6AajhB4UPRYEB
>> 0ZpQUURJPlptX5syBhepaXNNPoRW/dH151Ro0L6lpWPtMvfp2rL6xGy3iFH/BlNC
>> rZ2oFjMmkrvtTzTtiqvh75YVPG9+XmnGIpFn8adQVcsXW0FloEj7O2lh+LK0qMl7
>> rom1/UYTBpHmuWAC/+dwJDjyiZSqWDgrO9yP6x6O1f4jTV1+1/XfeiA8Nu/9JAwX
>> Z188GY09iPMBOGKSDPHfUfrLf34YRTgyrfZaatpY9GcDeO7QFqRLtiUTzs73HpIP
>> pNKicGgWmtvzrafQX1yCW0Y66+jKoNqsL/6/KAfeUW6OIBfxwEuuf+daHw4s/cc/
>> kOvTF934pIg=
>> =wRJ5
>> -----END PGP SIGNATURE-----
>>
>> _______________________________________________
>> OSRM-talk mailing list
>> OSRM-talk at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>