-
Notifications
You must be signed in to change notification settings - Fork 658
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
optimize retrieving complex turn restrictions #4647
Comments
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 |
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. |
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.
The text was updated successfully, but these errors were encountered: