AddContraction Stalls

[jonwagner]

I'm trying to process the following PBF:

http://download.geofabrik.de/north-america/us/pennsylvania-latest.osm.pbf

            using (var stream = File.OpenRead(filename))
                routerDb.LoadOsmData(stream, Vehicle.Car);

            var profile = Vehicle.Car.Fastest();
            routerDb.AddContracted(profile);

AddContracted stalls and takes forever (I didn't actually wait for forever, but a really long time).

I downloaded the master branch and from the logs it shows that FastHierarchyBuilder is calling CalculateQueue very frequently.

I noticed that CalculateQueue is called when the number of cache misses is higher than private int _k = 20; // The amount of queue 'misses' before recalculation of queue.

Changing _k to 200 allowed me to process the file successfully.

I don't know if this is caused by having a large file, or if there's something wrong with the file, or if you should increase the cache miss threshold.

Please let me know if there is anything else you need to reproduce the issue.

[jonwagner]

Interesting...I ran the same file through IDP 2.13.1 and it processes successfully and contraction is significantly faster.

IDP seems to use the following code:

var profileInstance = routerDb.GetSupportedProfile(profile);
routerDb.AddContracted(profileInstance);

Would that make a difference?

[xivk]

Thanks for your feedback.

I think the reason for this is that by default when Itinero 1.4 detects a turn restriction it will turn to another flavor of contraction by building a edge-based contracted graph, more than doubling the vertex/edges counts. This enables Itinero to gracefully handle turn restrictions and, in the future, is prepared for turning costs (turning left is cheaper than turning right for example, depending on the country). We did put in a lot of work to make this scale properly but we're not quite there yet, so any feedback that may help is very valuable thanks!

It's interesting to see that for your case increasing k to 200 improves things. I'll keep this issue open and do some more testing with other areas/countries.

If I'm right IDP 2.13.1 uses Itinero 1.3 and that doesn't use the edge-based contraction thus making it faster but less feature complete (some restrictions won't be handled properly). The resulting routerdb should still be compatible and load in 1.4.

[jonwagner]

To be clear, the serialization was being performed with namespace Itinero.Algorithms.Contracted.Dual

[jonwagner]

Here are some of the processing warnings, in case they are helpful for debugging:

Lots of these:

[RouterDbStreamTarget] warning - No before vertex found for from way for restriction relation -1!

A few of these:

[RouterDbStreamTarget] warning - No after vertex found for to way for restriction relation 5972447!
[RouterDbStreamTarget] warning - No after vertex found for to way for restriction relation 5972448!

and a few more warnings:

[RouterDbStreamTarget] warning - No link could be found between from and via node for restriction relation 3619752!
[RouterDbStreamTarget] warning - From way not found for restriction relation 5537689!
[RouterDbStreamTarget] warning - To way not found for restriction relation 5537690!

[jonwagner]

Itinero 1.3.2 from nuget does successfully load, contract, save and reload this file. (~30 minutes processing time).