osrm-backend
osrm-backend copied to clipboard
Project-OSRM
Table request time complexity
Hi folks, was curious about knowing that given S sources and D destinations, what is the time complexity for the table retrieval request? Is it S * D?
In our use-case, we would like to understand how to tackle our ever increasing request runtime based on the increasing source/destination points. So if, for e.g., a 5000*5000 request takes around 5 seconds, would we receive some speed-up by splitting them into 5 1000*5000 requests across multiple instances? Thanks.
The original implementation is based on this paper: http://algo2.iti.kit.edu/schultes/hwy/distTable.pdf
|S|·Dijkstra(F +|G′K |)+|T |·Dijkstra(F )+O(|S|·|T |·f ). If both sets S and T are large, the dominating term is |S| · |T | · f
As you can see, there are a lot of pieces in the complexity puzzle. Your best bet is to try. One observation to make though - you will pay the coordinate snapping price multiple times if you make multiple requests.
To address that, @oxidase made a PR a few years ago that made the manyToMany plugin capable of doing the routing part multi-threaded: https://github.com/Project-OSRM/osrm-backend/pull/4454 - but it was removed at some point, I think when we added support for both CH and MLD algorithms. It might be worth attempting to restore if you really want to squeeze the lowest latency out of a single request.
it was removed at some point, I think when we added support for both CH and MLD
Interesting. Does it mean that the parallelization approach used back then was only viable for CH and would not have been usable with MLD?
@jcoupey I honestly don't remember, but I'm sure we can dig up the commits where it happened and see if the commit messages give more context.
It's a bit of a tradeoff - if you're only handling your own requests, then it makes sense to split a single request across many processors to make it fast.
If you're handling public traffic (like we do at Mapbox), then it can make sense to limit a request to a single CPU, despite the slower response time. If there are enough other concurrent requests occurring that you can utilize all your compute, it is arguably better to provide consistent latency based on request shape, rather than variable performance depending on load (which is what would happen if large requests were allowed to use other CPU cores and fight with other concurrent smaller requests).
it was removed at some point, I think when we added support for both CH and MLD
Interesting. Does it mean that the parallelization approach used back then was only viable for CH and would not have been usable with MLD?
That's a fair assessment.
For practical purposes the CH based many-to-many implementation is in O(S*T).
It's a bit of a tradeoff
Sure, totally get that eating up all cores is not always desired. But this means it would probably be possible to pass the number of cores allowed as a runtime option, a bit like what osrm-extract does. Then users would be able to make their own tradeoff. Then the single-threaded scenario would just be a particular case. Or am I missing something here and this would imply some overhead for the current default?
Thank you for the clarifications
This might be a silly question but assuming we are pre-processing our map data using osrm-extract followed by osrm-contract and instead of the in-built server access the map data using FFI (OSRM object) which is initiatized with a .osrm file, would it be fair to assume we end up using the CH algorithm internally as opposed to MLD?
Yes - the access method (osrm-routed or FFI) has nothing to do with the algorithms used and the structure of the data. If you're using osrm-contract and not osrm-customize, then you have CH data.