You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
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 😄 ).
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: