Adds first sketch for a Dijkstra API, see #44 #48
Conversation
|
Ideally to bring this into the library we would find a way to unify the ergonomics for all searchers, be it bfd/dfs or dijkstra like here. |
7d159b1 to
3b168b0
Compare
e7709b6 to
b63600b
Compare
|
Here's a flamegraph for the current dijkstra implementation with a random graph and random (s,t) queries
What we can see here is that it really comes down to the heap pop and push operations, and what we don't see here is memory latency from traversing the graph of 10M nodes. |
2ba033c to
5635136
Compare
4a25b95 to
47944c5
Compare
| } | ||
|
|
||
|
|
||
| static inline uint32_t tinygraph_saturated_add_u32(uint32_t a, uint32_t b) { |
There was a problem hiding this comment.
I'm curious if this will be optimized to __builtin_uadd_overflow. 🤔 Did you check that by any chance?
There was a problem hiding this comment.
It compiles to an addition and a conditional move based on the carry flag from the addition
https://godbolt.org/z/3crhPsxo8
Did a quick perf run (check the makefile) and most time spent is in the binary heap, all the computation here is pretty much for free while we're chasing through memory.
| uint32_t* parent; | ||
| tinygraph_array_s path; | ||
|
|
||
| const uint16_t* weight; |
There was a problem hiding this comment.
One interesting optimization the size realm to look into is the following: weight is a bad way to store costs on a graph.
It is fast to have it simply as a number and that is why most people do this, but it is really wasteful if you want multiple metrics. Usually distance + speed is a better storage format. It has an additional advantage: In practical terms you can make distance an uint16 (e.g. ~65km max which is fine if you don't have CH-style shortcuts) and speed an uint8 (255 km/h). Every new metric will only need a different speed array.
Also speeds tend to be somewhat the same, in the same vicinity so that would make it even more compressible.
I'm wondering if there is a nice abstraction for this using some of the other primitives here.
There was a problem hiding this comment.
Good point! I started with a generic uint16_t weight to get something out and because so far we're not committed to the road network graph yet. The only road network related function in our API is the optional reorder function to re-order graph nodes based on a space-filling curve of their location.
At some point I believe we need to commit to one direction and stop keeping it as a generic graph library. At that point these optimizations will come into play.
| tinygraph_bitset_set_at(ctx->seen, u); | ||
| } | ||
|
|
||
| // The following is a bit different to the classical Dijkstra |
There was a problem hiding this comment.
Well, to be pedantic: This because you mark a node as settled (or here seen) before you have finished processing it. The easier logic change is to move the tinygraph_bitset_set_at(ctx->seen, u); to the end of the function and terminate here if u == t.
There was a problem hiding this comment.
Yes and I believe it requires a bit more care when restarting: If we terminate early here we pop'ed u from the heap. Now if the user runs a subsequent query with the same s but a different t we didn't settle u and we'd have to restart accordingly pushing it into the heap etc.
Maybe it's a better trade-off, tho, to have potential subsequent queries with the same s pay the penalty of taking care of restarting. Not sure if it's worth now changing, happy to accept a pull request if you want to switch this over.
Playground for what will become an API for
See the open questions in the ticket and in the code, we need to iterate here before we bring it into the main line interface.