search

valhalla / valhalla

Open Source Routing Engine for OpenStreetMap
https://valhalla.github.io/valhalla/
Other
4.43k stars 674 forks source link

optimize retrieving complex turn restrictions #4647

Open nilsnolde opened 5 months ago

nilsnolde commented 5 months ago

I just found a serious bug in our TomTom converter (for Valhalla at least) where we turned every simple turn restriction into a complex one accidentally, which was around 10 Mio in Europe. It seems that's responsible for a serious performance issue with our data in Valhalla (which I have yet to confirm).

Anyways, I looked a bit into it. On the OSM planet we're currently having around 600k complex turn restrictions across all levels & directions. Currently we're cycling through a tile's complex TRs for every edge in the tight expansion loop which is marked as having one, which seems a bit wasteful. I wonder if we can't do the same as when we're retrieving access restrictions: sort the data and do a binary search. The planet has around 1 Mio access restrictions (we don't log them out, but I counted the most tagged ones roughly). So they're both in the same ballpark and I'd think that in urban areas they're similarly abundant. I didn't really look in detail into how complex TRs are created today, but I'd imagine we could sort the forward & reverse ones fairly easily and binary search is quickly implemented.

Anyone sees any red flags @kevinkreiser @gknisely @dnesbitt61 ? It's not the biggest improvement possibly, but I think it could help in heavy tiles like NYC/Paris or so.

nilsnolde commented 5 months ago

Although that'd be a problem for new tiles/old code situation.. binary search wouldn't work if the complex TRs aren't already sorted for to/from graphids in their fwd/rev direction. At least a quick grep on sort in restrictionbuilder.cc doesn't show anything.. you know by heart by any chance @gknisely ? Seems you co-authored that code (though 3 years ago :smile: ).

nilsnolde commented 5 months ago

doesn't seem they're sorted today. @kevinkreiser suggested we can still add sorting today by writing a bit to the tile header indicating whether it's sorted or not and then optionally turn on binary search when retrieving complex restrictions.

with 300k complex restrictions this might make a difference, assuming they're mostly present in urban environments (as opposed to access restrictions of which there are ~ 1 Mio). I'd try this first for some urban queries before raising a PR.