[Exception resolving points with No- or Limited-Cache-Mode] Graph not sorted: Binary search using hilbert distance not possible

[goersen]

Setup:

1. OSM-Data of germany (http://download.geofabrik.de/europe/germany-latest.osm.pbf)
2. Create a routerdb
3. Add contracted graph for Itinero.OSM.Vehicles.Vehicle.Car.Fastest() 
4. Save and reuse that routerdb for everything
5. When loading the routerDb use a limited-cache-profile like 'RouterDbProfile.MobileHighEnd' or 'RouterDbProfile.NoCache'
6. Running in a .NET Standard Library 2.0 (i.e. compatible with normal .Net Framework)
7. Tested on the latest prerelease (31)

Data:

• Example Lat/Lng points that cannot be resolved:

  1. 52.3641, 9.6683
  2. 50.87851, 7.09868
  3. 52.55001, 13.45777
  4. 53.57401, 10.04214

• 250m radius is used for TryResolve

Error:

• About 70% of the time Graph not sorted: Binary search using hilbert distance not possible is thrown
• Sometimes (~30%) Non-negative number required. Parameter name: count is thrown instead

Additional Info:

• Trying to resolve any of the above points while using 'RouterDbProfile.NoCache' or 'RouterDbProfile.MobileHighEnd' for RouterDb-initialization throws one of the above errors.

• When initializing the RouterDb without a cache-limit everything works fine.

[goersen]

This issue can be closed. Seems to have occured due to wrong implementation.

[xivk]

Ok thanks! Any suggestion on making things clearer so this doesn't happen in the future?

[goersen]

Actually my previous comment sadly was too hasty :(. We refactored our routing structure and the exception didn't occur anymore. I figured the mess we had for initial testing & evaluation was responsible.

But then Non-negative number required. | Parameter name: count just popped up again. But at least I can pinpoint it now quite exact. This happens when:

1. Using a RouterDb with a limited-cache-profile
2. Using the same Router object for everything
3. Try to resolve points simultaneously on multiple threads
Disclaimer: The test I just ran for this tried to resolve the same points on both threads. I don't know if this is a factor in the issue.

When I wait for the first thread to be finished with resolving and moving into router.Calculate(...), before starting the second thread, both threads finish fine.

[xivk]

Ah ok, so it's possible when using the 'memory mapping' feature it's possible multithreading is an issue.

• [x] I'll see if I can confirm this and improve on this but it's only going to be synchronization internally to make sure the API is stable. Performance won't really improve because all data is read from one stream and that stream can only read one piece of data at a time.

As a solution to this you can in this case have for example one router with it's own routerdb per thread where you open them individually using a new stream. But also there it will depend on your disk/OS if that will improve things AFAIK.

[goersen]

Thanks so much @xivk !

I think for now we'll build a wrapper for resolving points which synchronizes it and can also cache the RoutePoint-objects. This'll also help a bit with performance.

This also brings me to another question I have, but I don't want to open yet another issue bothering you:

The cache/no cache options put us a little bit into a dilemma.

• Using full-cache-mode initialization of the RouterDb takes ~1.5min and ~3GB memory. Routing is pretty fast.
• Using no- or limited-cache-mode initialization of the RouterDb is pretty instantaneous and takes basically no memory. Routing is pretty slow (8 points ~30sec).

This is with OSM-data of germany and on normal windows-machines (i.e. i7 3.4GHz, 8GB memory), not mobile devices.

My questions would be: a) Is this normal or are we using something wrong? b) Is there some workaround, middleground or anything? Maybe we could expand the cache-profiles or something?

[xivk]

To load everything in memory you leave the caching profile null. That is always fastest.

If startup time is important then you could load the RouterDb using RouterDbProfile.NoCache, it's ready instantly. Routing is fastest on mobile when having a contracted graph using RouterDbProfile.NoCache, haven't tested this on a regular machine but I'm guessing this would be best there too. This way you can start serving routes immediately, and in the background you load another RouterDb in memory and replace the NoCache one once it's loaded.

If RAM is the constraint then you're kind of stuck but there is room for improvement, for example, it is doable to only load the data that is crucial for the routing algorithm only and the meta-data using memory mapping. You can do this by customizing the caching profiles but you would also need to profile your service and look at where Itinero spends the most time.

[xivk]

Closing this issue, feel free to reopen if you have further questions.