search

LdDl / ch

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

Redudant pointers #40

Closed LdDl closed 1 year ago

LdDl commented 1 year ago

Similar to https://github.com/project-echo/lddi-contraction-hierarchies/pull/5

Considering commits: https://github.com/project-echo/lddi-contraction-hierarchies/pull/5/commits/8f0d4b8e10d5477ece4b060a55eb26d10ac5c977 https://github.com/project-echo/lddi-contraction-hierarchies/pull/5/commits/0fc4fa5eba64fa3b3b332a5a76a4908dca883129 https://github.com/project-echo/lddi-contraction-hierarchies/pull/5/commits/f00820abfa0c6c327aa831ef592842d413a1c4d4

Mine benchmarks also (via both benchcmp and benchstat):

M-N search

git checkout redudant_pointers && \
go test -benchmem -run=^$ -bench ^BenchmarkShortestPathManyToMany$ github.com/LdDl/ch -v -count=1 > benchmarks/new_mn_ptr.txt && \
git checkout dcb59c8c6cbac82090b9fcab8ec256d678765a74 && \
go test -benchmem -run=^$ -bench ^BenchmarkShortestPathManyToMany$ github.com/LdDl/ch -v -count=1 > benchmarks/old_mn_ptr.txt && \
benchcmp benchmarks/old_mn_ptr.txt benchmarks/new_mn_ptr.txt && \
git checkout redudant_pointers

New:

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              424795          3677 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             300748          4192 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         307405          4684 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       219908          5668 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       159038          8034 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                80230         12535 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                53956         22585 ns/op        3114 B/op         62 allocs/op
PASS
ok      github.com/LdDl/ch  49.792s

Old:

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              407336          3508 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             337154          3532 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         260437          4250 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       179054          5598 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       132986          9080 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                65853         19216 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                37705         30074 ns/op        3113 B/op         62 allocs/op
PASS
ok      github.com/LdDl/ch  69.954s

Compare (via benchcmp):

benchmark                                                                                           old ns/op     new ns/op     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                3508          3677          +4.82%
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               3532          4192          +18.69%
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           4250          4684          +10.21%
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         5598          5668          +1.25%
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         9080          8034          -11.52%
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     19216         12535         -34.77%
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     30074         22585         -24.90%

benchmark                                                                                           old allocs     new allocs     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                65             65             +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               63             63             +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           62             62             +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         62             62             +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         62             62             +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     62             62             +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     62             62             +0.00%

benchmark                                                                                           old bytes     new bytes     delta
BenchmarkShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                3242          3242          +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               3177          3177          +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           3144          3144          +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         3128          3128          +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         3120          3120          +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     3116          3116          +0.00%
BenchmarkShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     3113          3114          +0.03%

Compare (via benchstat):

name                                                                                    old time/op    new time/op    delta
ShortestPathManyToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               3.41µs ± 0%    3.40µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              3.58µs ± 0%    3.94µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          4.37µs ± 0%    4.64µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        5.95µs ± 0%    6.29µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12        9.35µs ± 0%    8.31µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12    21.5µs ± 0%    14.1µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12    28.9µs ± 0%    24.3µs ± 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.24kB ± 0%    3.24kB ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              3.18kB ± 0%    3.18kB ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          3.14kB ± 0%    3.14kB ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        3.13kB ± 0%    3.13kB ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12        3.12kB ± 0%    3.12kB ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12    3.12kB ± 0%    3.12kB ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12    3.11kB ± 0%    3.11kB ± 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                 65.0 ± 0%      65.0 ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12                63.0 ± 0%      63.0 ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12            62.0 ± 0%      62.0 ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12          62.0 ± 0%      62.0 ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12          62.0 ± 0%      62.0 ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12      62.0 ± 0%      62.0 ± 0%   ~     (all equal)
ShortestPathManyToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12      62.0 ± 0%      62.0 ± 0%   ~     (all equal)

1-N search

git checkout redudant_pointers && \
go test -benchmem -run=^$ -bench ^BenchmarkShortestPathOneToMany$ github.com/LdDl/ch -v -count=1 > benchmarks/new_1n_ptr.txt && \
git checkout dcb59c8c6cbac82090b9fcab8ec256d678765a74 && \
go test -benchmem -run=^$ -bench ^BenchmarkShortestPathOneToMany$ github.com/LdDl/ch -v -count=1 > benchmarks/old_1n_ptr.txt && \
benchcmp benchmarks/old_1n_ptr.txt benchmarks/new_1n_ptr.txt && \
git checkout redudant_pointers

New:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkShortestPathOneToMany
    bidirectional_ch_one_to_n_test.go:41: BenchmarkShortestPathOneToMany is starting...
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               394723          3985 ns/op        1906 B/op         68 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              151969          9006 ns/op        3266 B/op        117 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           41511         24286 ns/op        7726 B/op        232 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         20596         55631 ns/op       15887 B/op        407 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12          9830        151577 ns/op       33845 B/op        792 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12              3393        420642 ns/op       74234 B/op       1644 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12              1311       1107600 ns/op      159050 B/op       3470 allocs/op
PASS
ok      github.com/LdDl/ch  49.188s

Old:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkShortestPathOneToMany
    bidirectional_ch_one_to_n_test.go:41: BenchmarkShortestPathOneToMany is starting...
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               392167          3718 ns/op        1906 B/op         68 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              145198          8132 ns/op        3266 B/op        117 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           41467         27486 ns/op        7724 B/op        232 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         19702         63562 ns/op       15883 B/op        407 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12          7298        173430 ns/op       33882 B/op        792 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12              2191        561684 ns/op       74015 B/op       1638 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12               802       1321246 ns/op      160426 B/op       3498 allocs/op
PASS
ok      github.com/LdDl/ch  68.951s

Compare (via benchcmp):

benchmark                                                                                          old ns/op     new ns/op     delta
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                3718          3985          +7.18%
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               8132          9006          +10.75%
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           27486         24286         -11.64%
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         63562         55631         -12.48%
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         173430        151577        -12.60%
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     561684        420642        -25.11%
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     1321246       1107600       -16.17%

benchmark                                                                                          old allocs     new allocs     delta
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                68             68             +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               117            117            +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           232            232            +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         407            407            +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         792            792            +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     1638           1644           +0.37%
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     3498           3470           -0.80%

benchmark                                                                                          old bytes     new bytes     delta
BenchmarkShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                1906          1906          +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               3266          3266          +0.00%
BenchmarkShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           7724          7726          +0.03%
BenchmarkShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         15883         15887         +0.03%
BenchmarkShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         33882         33845         -0.11%
BenchmarkShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     74015         74234         +0.30%
BenchmarkShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     160426        159050        -0.86%

Compare (via benchstat):

name                                                                                   old time/op    new time/op    delta
ShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               3.72µs ± 0%    3.98µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              8.13µs ± 0%    9.01µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          27.5µs ± 0%    24.3µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        63.6µs ± 0%    55.6µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         173µs ± 0%     152µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     562µs ± 0%     421µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12    1.32ms ± 0%    1.11ms ± 0%   ~     (p=1.000 n=1+1)

name                                                                                   old alloc/op   new alloc/op   delta
ShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12               1.91kB ± 0%    1.91kB ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              3.27kB ± 0%    3.27kB ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          7.72kB ± 0%    7.73kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        15.9kB ± 0%    15.9kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12        33.9kB ± 0%    33.8kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12    74.0kB ± 0%    74.2kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     160kB ± 0%     159kB ± 0%   ~     (p=1.000 n=1+1)

name                                                                                   old allocs/op  new allocs/op  delta
ShortestPathOneToMany/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                 68.0 ± 0%      68.0 ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12                 117 ± 0%       117 ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12             232 ± 0%       232 ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12           407 ± 0%       407 ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12           792 ± 0%       792 ± 0%   ~     (all equal)
ShortestPathOneToMany/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     1.64k ± 0%     1.64k ± 0%   ~     (p=1.000 n=1+1)
ShortestPathOneToMany/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     3.50k ± 0%     3.47k ± 0%   ~     (p=1.000 n=1+1)

1-1 search

git checkout redudant_pointers && \
go test -benchmem -run=^$ -bench ^BenchmarkShortestPath$ github.com/LdDl/ch -v -count=1 > benchmarks/new_11_ptr.txt && \
git checkout dcb59c8c6cbac82090b9fcab8ec256d678765a74 && \
go test -benchmem -run=^$ -bench ^BenchmarkShortestPath$ github.com/LdDl/ch -v -count=1 > benchmarks/old_11_ptr.txt && \
benchcmp benchmarks/old_11_ptr.txt benchmarks/new_11_ptr.txt && \
git checkout redudant_pointers

New:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkShortestPath
    bidirectional_ch_test.go:71: BenchmarkShortestPath is starting...
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12           1340880           826.5 ns/op       551 B/op         17 allocs/op
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12           636510          1775 ns/op         916 B/op         27 allocs/op
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12       228662          5512 ns/op        2119 B/op         51 allocs/op
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12      95059         13150 ns/op        4757 B/op         90 allocs/op
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12      36472         36013 ns/op       10523 B/op        172 allocs/op
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12              13856         95445 ns/op       23168 B/op        351 allocs/op
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12               5296        221414 ns/op       48830 B/op        724 allocs/op
PASS
ok      github.com/LdDl/ch  49.731s

Old:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkShortestPath
    bidirectional_ch_test.go:71: BenchmarkShortestPath is starting...
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12           1347783           799.3 ns/op       551 B/op         17 allocs/op
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12           794038          1851 ns/op         917 B/op         27 allocs/op
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12       217698          5431 ns/op        2119 B/op         51 allocs/op
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12      90658         14473 ns/op        4755 B/op         90 allocs/op
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12      31382         42736 ns/op       10518 B/op        172 allocs/op
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12               8028        143732 ns/op       23057 B/op        350 allocs/op
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12               4392        278996 ns/op       48331 B/op        716 allocs/op
PASS
ok      github.com/LdDl/ch  70.387s

Compare (via benchcmp):

benchmark                                                                                 old ns/op     new ns/op     delta
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                799           826           +3.40%
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               1851          1775          -4.11%
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           5431          5512          +1.49%
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         14473         13150         -9.14%
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         42736         36013         -15.73%
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     143732        95445         -33.60%
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     278996        221414        -20.64%

benchmark                                                                                 old allocs     new allocs     delta
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                17             17             +0.00%
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               27             27             +0.00%
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           51             51             +0.00%
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         90             90             +0.00%
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         172            172            +0.00%
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     350            351            +0.29%
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     716            724            +1.12%

benchmark                                                                                 old bytes     new bytes     delta
BenchmarkShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                551           551           +0.00%
BenchmarkShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12               917           916           -0.11%
BenchmarkShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12           2119          2119          +0.00%
BenchmarkShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12         4755          4757          +0.04%
BenchmarkShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12         10518         10523         +0.05%
BenchmarkShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     23057         23168         +0.48%
BenchmarkShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     48331         48830         +1.03%

Compare (via benchstat):

name                                                                          old time/op    new time/op    delta
ShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                799ns ± 0%     826ns ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12              1.85µs ± 0%    1.77µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          5.43µs ± 0%    5.51µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        14.5µs ± 0%    13.1µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12        42.7µs ± 0%    36.0µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12     144µs ± 0%      95µs ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12     279µs ± 0%     221µs ± 0%   ~     (p=1.000 n=1+1)

name                                                                          old alloc/op   new alloc/op   delta
ShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                 551B ± 0%      551B ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12                917B ± 0%      916B ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12          2.12kB ± 0%    2.12kB ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12        4.75kB ± 0%    4.76kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12        10.5kB ± 0%    10.5kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12    23.1kB ± 0%    23.2kB ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12    48.3kB ± 0%    48.8kB ± 0%   ~     (p=1.000 n=1+1)

name                                                                          old allocs/op  new allocs/op  delta
ShortestPath/CH_shortest_path/4/vertices-4-edges-9-shortcuts-1-12                 17.0 ± 0%      17.0 ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/8/vertices-8-edges-61-shortcuts-1-12                27.0 ± 0%      27.0 ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/16/vertices-16-edges-316-shortcuts-31-12            51.0 ± 0%      51.0 ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/32/vertices-32-edges-1404-shortcuts-123-12          90.0 ± 0%      90.0 ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/64/vertices-64-edges-5894-shortcuts-322-12           172 ± 0%       172 ± 0%   ~     (all equal)
ShortestPath/CH_shortest_path/128/vertices-128-edges-23977-shortcuts-1315-12       350 ± 0%       351 ± 0%   ~     (p=1.000 n=1+1)
ShortestPath/CH_shortest_path/256/vertices-256-edges-97227-shortcuts-5276-12       716 ± 0%       724 ± 0%   ~     (p=1.000 n=1+1)

1-1 search (single b.Run(...))

git checkout redudant_pointers && \
go test -benchmem -run=^$ -bench ^BenchmarkStaticCaseShortestPath$ github.com/LdDl/ch -v -count=1 > benchmarks/new_11static_ptr.txt && \
git checkout dcb59c8c6cbac82090b9fcab8ec256d678765a74 && \
go test -benchmem -run=^$ -bench ^BenchmarkStaticCaseShortestPath$ github.com/LdDl/ch -v -count=1 > benchmarks/old_11static_ptr.txt && \
benchcmp benchmarks/old_11static_ptr.txt benchmarks/new_11static_ptr.txt && \
git checkout redudant_pointers

New:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkStaticCaseShortestPath
    bidirectional_ch_test.go:93: BenchmarkStaticCaseShortestPath is starting...
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12               1051       1104207 ns/op     3455553 B/op       1031 allocs/op
PASS
ok      github.com/LdDl/ch  5.649s

Old:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkStaticCaseShortestPath
    bidirectional_ch_test.go:93: BenchmarkStaticCaseShortestPath is starting...
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12                782       1366040 ns/op     3455542 B/op       1031 allocs/op
PASS
ok      github.com/LdDl/ch  7.858s

Compare (via benchcmp):

benchmark                                                                                             old ns/op     new ns/op     delta
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12     1366040       1104207       -19.17%

benchmark                                                                                             old allocs     new allocs     delta
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12     1031           1031           +0.00%

benchmark                                                                                             old bytes     new bytes     delta
BenchmarkStaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12     3455542       3455553       +0.00%

Compare (via benchstat):

name                                                                                      old time/op    new time/op    delta
StaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12    1.37ms ± 0%    1.10ms ± 0%   ~     (p=1.000 n=1+1)

name                                                                                      old alloc/op   new alloc/op   delta
StaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12    3.46MB ± 0%    3.46MB ± 0%   ~     (p=1.000 n=1+1)

name                                                                                      old allocs/op  new allocs/op  delta
StaticCaseShortestPath/CH_shortest_path/vertices-187853-edges-366113-shortcuts-394840-12     1.03k ± 0%     1.03k ± 0%   ~     (all equal)

CH Prepare

git checkout redudant_pointers && \
go test -benchmem -run=^$ -bench ^BenchmarkPrepareContracts$ github.com/LdDl/ch -v -count=1 > benchmarks/new_ch_prepare_ptr.txt && \
git checkout dcb59c8c6cbac82090b9fcab8ec256d678765a74 && \
go test -benchmem -run=^$ -bench ^BenchmarkPrepareContracts$ github.com/LdDl/ch -v -count=1 > benchmarks/old_ch_prepare_ptr.txt && \
benchcmp benchmarks/old_ch_prepare_ptr.txt benchmarks/new_ch_prepare_ptr.txt && \
git checkout redudant_pointers

New:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkPrepareContracts
BenchmarkPrepareContracts-12               1    3101841094 ns/op    281313696 B/op   2579382 allocs/op
PASS
ok      github.com/LdDl/ch  3.306s

Old:

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
cpu: Intel(R) Core(TM) i5-10600K CPU @ 4.10GHz
BenchmarkPrepareContracts
BenchmarkPrepareContracts-12               1    6267384213 ns/op    362381184 B/op   3744997 allocs/op
PASS
ok      github.com/LdDl/ch  6.504s

Compare (via benchcmp):

benchmark                        old ns/op      new ns/op      delta
BenchmarkPrepareContracts-12     6267384213     3101841094     -50.51%

benchmark                        old allocs     new allocs     delta
BenchmarkPrepareContracts-12     3744997        2579382        -31.12%

benchmark                        old bytes     new bytes     delta
BenchmarkPrepareContracts-12     362381184     281313696     -22.37%

Compare (via benchstat):

name                 old time/op    new time/op    delta
PrepareContracts-12     6.27s ± 0%     3.10s ± 0%   ~     (p=1.000 n=1+1)

name                 old alloc/op   new alloc/op   delta
PrepareContracts-12     362MB ± 0%     281MB ± 0%   ~     (p=1.000 n=1+1)

name                 old allocs/op  new allocs/op  delta
PrepareContracts-12     3.74M ± 0%     2.58M ± 0%   ~     (p=1.000 n=1+1)