Bug in ResolverCache

[YuriiNskyi]

I was trying to understand, why cache for resolved points absolutely doesn't work, so has debugged library to check it's internal behavior.
Here's an Add method from ResolverCache:

public void Add(IProfileInstance[] profileInstances, float latitude, float longitude, Func<RoutingEdge, bool> isBetter, float maxSearchDistance,
	ResolveSettings settings, Result<RouterPoint> routerPointResult)
{
	var key = new Key(profileInstances, isBetter, maxSearchDistance, settings);

	if (!_data.TryGetValue(key, out var lruCache))
	{
		_data.TryAdd(key, new LRUCache<Coordinate, Result<RouterPoint>>(_size));
		_data.TryGetValue(key, out lruCache);
		if (lruCache == null)
		{ // can this happen, it shouldn't, how does concurrent dictionary work exactly?
			return;
		}
	}

	var location = new Coordinate(latitude, longitude);
	if (lruCache.TryGet(location, out var cachedResult))
	{ // already in cache.
		return;
	}

	//_added++;
	//Console.WriteLine($"Added: {_added}");
	
	lruCache.Add(location, cachedResult); // The bug is here, cachedResult is null at first and subsequent cases, so cache doesn't work either

	// lruCache.Add(location, routerPointResult) // Here's a correct version, I suppose
}

I think it's clear from comments what's the problem, and how to fix it.

I'm not sure how to properly create PR to fix that, so it's better to create issue first.

[juliusfriedman]

This seems to be done intentionally null represents already resolved maybe?

[YuriiNskyi]

@juliusfriedman at first time, when we are adding result to lruCache, it is null. Then, we always have null returned as cached result, and never refresh it, due to always successful if statement here: if (lruCache.TryGet(location, out var cachedResult)). null is not representing that this is already resolve, it is intentionally written to cache. Always written to cache.

I can't really imagine why would somebody want to do that intentionally.

[juliusfriedman]

Perhaps there are other bugs when this is fixed though and thats why it is the way it is?

I have to admit I don't see any different behavior with this enabled or disabled, performance might be a little better but it doesn't seem by much honestly.

Hence why I asked the question.

It would very well be a typo.

[YuriiNskyi]

@juliusfriedman I can describe why it's crucial for me.

The problem was on production environment, with high-load. Resolving points took about five times slower than calculation distance between them. After some search, ResolverCache was found. Unfortunately enabling it was totally useless, and, in fact, harmful, performance was even downgraded!

That's why I took some time to explore how Itinero, and this cache especially, works. After fixing this mistake, it works like a charm, resolving same points take 0.5ms from cache. It is obviously much better than 40ms when resolving them every time from scratch.

This might be a typo, might not, but, it affects entire aspect of resolving points as fast as possible.

[juliusfriedman]

@juliusfriedman I can describe why it's crucial for me.

The problem was on production environment, with high-load. Resolving points took about five times slower than calculation distance between them. After some search, ResolverCache was found. Unfortunately enabling it was totally useless, and, in fact, harmful, performance was even downgraded!

That's why I took some time to explore how Itinero, and this cache especially, works. After fixing this mistake, it works like a charm, resolving same points take 0.5ms from cache. It is obviously much better than 40ms when resolving them every time from scratch.

This might be a typo, might not, but, it affects entire aspect of resolving points as fast as possible.

I use contracted an contracted and non databases and have not had 30 second routing time ever... I know I have a routing situation which went from West Cost US -> Across the US -> To UK -> India and the router was able to route this very easily in almost less than 30 seconds....

eh, Milliseconds you say ( I read correctly now, it's still by virtue of the same fact how you use your Router I believe, see below)

Additionally, this only really helps if you re-use the same point more than one in a short period of time correct?

If I goto the cache it's very well possible the item can be removed already OR in the process of being removed.

I am not saying it's a bad change at all I am just saying I did not require it and with it enabled I sometimes have lower performance (maybe only due to my scenario).

E.g. run the Itinero unit tests with this enabled and simply take note of the time differences

[YuriiNskyi]

@juliusfriedman I really can't understand what's the problem 😄

If you don't need that ResolverCache - leave it null, as it is by default.
If you need it - use it, create new instance and set size.

And in last sentence it is where the problem occurs. I need it, but can't use it, due to that bug.

Additionally, this only really helps if you re-use the same point more than one in a short period of time correct?

You are totally right, and that's just my case.

[knormand]

Hi. Apologies for the misplaced post. I am looking for information how to best make use of the isBetter functional parameter in Router.TryResolve(). I have searched the web and can't find anything. Also sent a query via Itinero contact form, but not yet received a response. Can anyone direct me to a resource or contact that I can get some info? Thanks!