osrm-backend
osrm-backend copied to clipboard
Implement path unpacking cache
Path unpacking takes up a considerable amount of the query time for MLD (and CH actually). A simple technique to mitigate this is to create an unpacking cache. Generally this cache would store an EdgeID
or source, target
pair to unpacked path in a LRU manner.
There are a lot of knobs one can tune to make this perform best some of the basic considerations:
- What do we store in the cache: Just
EdgeIDs
that we need to turn intoPathData
again to full lists ofPathData
- What is a good cache size and how do we determine it
- What kind of edges should be cached: For MLD we have a lot of choices here (e.g. only store clique arcs from certain levels), for CH there is no good mechanism to decide when a shortcut should be cached and when not.
- Should we have a thread-local cache or a shared cache
This would hook into SearchEngineData
(since it needs read-write and thread-safe access) and would need to be cleared on every data update.
/cc @oxidase