osrm-backend icon indicating copy to clipboard operation
osrm-backend copied to clipboard

Implement path unpacking cache

Open TheMarex opened this issue 7 years ago • 0 comments

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:

  1. What do we store in the cache: Just EdgeIDs that we need to turn into PathData again to full lists of PathData
  2. What is a good cache size and how do we determine it
  3. 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.
  4. 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

TheMarex avatar Mar 17 '17 22:03 TheMarex