search

LdDl / ch

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) technique for computing shortest path in graph.
Apache License 2.0
46 stars 5 forks source link

Implement ShortestPathManyToMany #30

Closed magnushiie closed 1 year ago

magnushiie commented 1 year ago

This implements many-to-many simultaneous shortest path algorithm. Note: this allocates data structures O((sources + targets)*num_vertices) so the memory usage could be significant. Experimental results show 2-3x performance improvement over iterating ShortestPathOneToMany over all sources.

This also changes unifies the forward and backwards searches to reduce code duplication, allowing the ShortestPathManyToMany implementation to be simpler.

Also, this PR is currently based on #26 (commit 9e9cd42) - I could rebase this to current state of master if #26 takes time to merge.

LdDl commented 1 year ago

We'll take a look on this soon (we can't dig into instantly sadly). But first of all we see go.mod changes which seems strange.

P.S. BTW #26 has been merged

magnushiie commented 1 year ago

Sorry about the go.mod changes, I actually meant to create a PR in our fork first, but accidentally submitted upstream. But maybe you can start evaluating, I will submit an updated patch (rebased on master and without the unnecessary changes) tomorrow or over the weekend.

magnushiie commented 1 year ago

I removed the go.mod change but for the rest, let's pause this PR for a while, I'll create separate PRs (e.g. #31, #32) for the smaller changes.

LdDl commented 1 year ago

@SimonWaldherr I'm sorry to disturb you again, but here is another merge conflict due #31 and #32

SimonWaldherr commented 1 year ago

@LdDl sorry, but I think there is a misunderstanding. do you mean maybe @magnushiie

LdDl commented 1 year ago

Oh, really. Sorry for that I'm gonna punish my github's app for that :D

@magnushiie I was meant to call you here

magnushiie commented 1 year ago

I will create one more separate PR tomorrow on top of master branch, to unify the directions logic in OneToOne, and then rebase this one on top of that (it's basically a copy of OneToOne in that state with additional arrays for sources and targets).

magnushiie commented 1 year ago

This is now rebased on top of master, it's based on the restructured OneToOne algorithm from #33. #33 is not necessary for the ManyToMany implementation, this PR can be merged independently. @LdDl if you could please review now, I'd be grateful.

LdDl commented 1 year ago

@magnushiie

Did merge. I've added a couple of benchs (for synthetic graph) - https://github.com/LdDl/ch/commit/d9cab53a8d289f47e016175467ba732e9697b9f6

go test -benchmem -run=^$ github.com/LdDl/ch -bench BenchmarkOldWayShortestPathManyToMany
go test -benchmem -run=^$ github.com/LdDl/ch -bench BenchmarkShortestPathManyToMany

benchcmp:

benchmark                                                                                           old ns/op     new ns/op     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     1268879       5410451       +326.40%

benchmark                                                                                           old allocs     new allocs     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     3633           2867           -21.08%

benchstat

name                                                                                    old time/op    new time/op    delta
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12    1.27ms ± 0%    5.41ms ± 0%   ~     (p=1.000 n=1+1)

name                                                                                    old allocs/op  new allocs/op  delta
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     3.63k ± 0%     2.87k ± 0%   ~     (p=1.000 n=1+1)

Less allocations after some threshold (vertices/edges num), but more nanoseconds per operation

magnushiie commented 1 year ago

Thank you!

The current benchmarks don't highlight the benefits of ManyToMany, as there are few sources and few targets. In our real cases (100x100 matrix) this has 2-3x improvement in latency (albeit with increased memory usage).

I added the current test only for code coverage, I will try to add a benchmark with a bigger matrix in a subsequent PR.

Also I forgot about the TODO item https://github.com/LdDl/ch/pull/30/files#diff-be0728d7a21b2446cc27d05a24101ab1250d000630961e717abd16f00002ae29R137 - fixing this could bring the performance to more on par with the other implementations with small cases, and also improve the big matrices. I will submit a PR next week.