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

reduce slice usage for n-m search #39

Closed LdDl closed 1 year ago

LdDl commented 1 year ago

Since early exit from [][]bool we can use []map[k]v

Master branch:

go test -benchmem -run=^$ -bench ^BenchmarkShortestPathManyToMany$ github.com/LdDl/ch -v -count=1 > old_m_n.txt
goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkShortestPathManyToMany
    bidirectional_ch_n_to_n_test.go:51: BenchmarkShortestPathManyToMany is starting...
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12              282135          4551 ns/op        3163 B/op         87 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12             151106          8814 ns/op        4242 B/op        120 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          44286         24841 ns/op        8210 B/op        198 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        15088         77301 ns/op       17146 B/op        349 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         3474        322556 ns/op       35768 B/op        671 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12                  944       1378812 ns/op       77298 B/op       1369 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12                  208       5754389 ns/op      164928 B/op       2880 allocs/op
PASS
ok      github.com/LdDl/ch  72.384s

Current branch:

go test -benchmem -run=^$ -bench ^BenchmarkShortestPathManyToMany$ github.com/LdDl/ch -v -count=1 > new_m_n.txt
goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkShortestPathManyToMany
    bidirectional_ch_n_to_n_test.go:51: BenchmarkShortestPathManyToMany is starting...
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12              397444          2972 ns/op        3242 B/op         65 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12             394033          3008 ns/op        3177 B/op         63 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12         332316          3701 ns/op        3144 B/op         62 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12       255286          5062 ns/op        3128 B/op         62 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12       123420          8593 ns/op        3120 B/op         62 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12                76993         15810 ns/op        3116 B/op         62 allocs/op
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12                39926         28519 ns/op        3113 B/op         62 allocs/op
PASS
ok      github.com/LdDl/ch  70.541s

benchcmp (yeah, it is deprecated):

benchcmp is deprecated in favor of benchstat: https://pkg.go.dev/golang.org/x/perf/cmd/benchstat
benchmark                                                                                           old ns/op     new ns/op     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                4551          2972          -34.70%
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               8814          3008          -65.87%
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           24841         3701          -85.10%
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         77301         5062          -93.45%
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         322556        8593          -97.34%
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     1378812       15810         -98.85%
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     5754389       28519         -99.50%

benchmark                                                                                           old allocs     new allocs     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                87             65             -25.29%
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               120            63             -47.50%
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           198            62             -68.69%
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         349            62             -82.23%
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         671            62             -90.76%
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     1369           62             -95.47%
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     2880           62             -97.85%

benchmark                                                                                           old bytes     new bytes     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                3163          3242          +2.50%
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               4242          3177          -25.11%
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           8210          3144          -61.71%
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         17146         3128          -81.76%
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         35768         3120          -91.28%
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     77298         3116          -95.97%
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     164928        3113          -98.11%

benchstat:

name                                                                                    old time/op    new time/op    delta
ShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               4.55µs ± 0%    2.97µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              8.81µs ± 0%    3.01µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          24.8µs ± 0%     3.7µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        77.3µs ± 0%     5.1µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         323µs ± 0%       9µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12    1.38ms ± 0%    0.02ms ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12    5.75ms ± 0%    0.03ms ± 0%   ~     (p=1.000 n=1+1)

name                                                                                    old alloc/op   new alloc/op   delta
ShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               3.16kB ± 0%    3.24kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              4.24kB ± 0%    3.18kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          8.21kB ± 0%    3.14kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        17.1kB ± 0%     3.1kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12        35.8kB ± 0%     3.1kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12    77.3kB ± 0%     3.1kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     165kB ± 0%       3kB ± 0%   ~     (p=1.000 n=1+1)

name                                                                                    old allocs/op  new allocs/op  delta
ShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                 87.0 ± 0%      65.0 ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12                 120 ± 0%        63 ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12             198 ± 0%        62 ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12           349 ± 0%        62 ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12           671 ± 0%        62 ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     1.37k ± 0%     0.06k ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     2.88k ± 0%     0.06k ± 0%   ~     (p=1.000 n=1+1)
mertakman commented 1 year ago

https://github.com/project-echo/lddi-contraction-hierarchies/ please take look at our fork , we already made so much improvement at there including this ,

mertakman commented 1 year ago

I profiled this library under some serious request load in huge graphs , and optimized for performance , and it is running faster.

LdDl commented 1 year ago

That's awesome job!

Current PR is composition of following commits in yours fork: https://github.com/project-echo/lddi-contraction-hierarchies/commit/a9fe55f14ec03869e09723af65b60d79cc90a5b5 https://github.com/project-echo/lddi-contraction-hierarchies/commit/b15c4243758e6e0a242cf9fa818b6fd217a2fc6e https://github.com/project-echo/lddi-contraction-hierarchies/commit/1851d23abd844c789d917d2c9cd5ac1cd224ae56 https://github.com/project-echo/lddi-contraction-hierarchies/commit/3205652c27aa7d03dd125c03c0c2d26703114556 https://github.com/project-echo/lddi-contraction-hierarchies/commit/f9fd927614f9af30f695d9eb961bcf232b084c9b (last two exclude each other)

am I right?

mertakman commented 1 year ago

Also please check https://github.com/project-echo/lddi-contraction-hierarchies/pull/9/files . Reduced the response times for many to many twice . Benchmarks in repo are bit micro benchmarks , but we are trying with few hundred sources and destinations .

LdDl commented 1 year ago

I'll take a look into for sure, but in another PR/commits set. Merging this one