tree c069433529f1511a60c6de2b404b3fc145f850a5
parent 78a2d42bb6b2b529c89101c233e247f488cec78f
author Dan Kortschak <dan@kortschak.io> 1682334116 +0930
committer GitHub <noreply@github.com> 1682334116 +0930
gpgsig -----BEGIN PGP SIGNATURE-----
 
 wsBcBAABCAAQBQJkRmGkCRBK7hj4Ov3rIwAAaQkIAG1fLdq8MBZ8o48ZFbLg2SG/
 b7ch5tvXBCCutJXs2oK8uNDglOhT3CAejIasCMJ5TZ7wDNww7SSRxdzI5RsEWvdk
 z6Jy/LkHaIaZ6/Vb6Xk5KdiF/W3+lpo2qFo3x+JJNxNbDBJd/5A2d5All5oQspQF
 XQG/cugZ62Y9WqTdtnKQqLbJiHoIFGN4D9CkCZdHDGR2xln14asp0amyihnHZAAY
 Yl34eF8NSeaSlQn7kI++RH1SkRYQkIq4+z6hGy3B9snA26KE9MRL8wK89B5rjpRm
 m7/oIlSCddYHFhyYM4JgZ7mzsrTKR+Nsmko/25ENDiZ9KNN1eBF08rEqdW6oWwA=
 =NHfZ
 -----END PGP SIGNATURE-----
 

graph/path: reduce allocations in path reconstructions

                                              │   old.bench   │               new.bench               │
                                              │    sec/op     │    sec/op      vs base                │
ShortestAlts/AllTo_100×2|0.5(17)-8              12.380µ ±  9%   8.577µ ±   6%  -30.72% (p=0.000 n=10)
ShortestAlts/AllTo_1000×2|0.5(51)-8              74.87µ ± 17%   47.66µ ±   1%  -36.35% (p=0.000 n=10)
ShortestAlts/AllTo_100×4|0.25(53)-8              25.50µ ±  3%   15.35µ ±   3%  -39.82% (p=0.000 n=10)
ShortestAlts/AllTo_1000×4|0.25(574)-8            556.5µ ±  5%   279.2µ ±   4%  -49.83% (p=0.000 n=10)
ShortestAlts/AllTo_100×16|0.1(76)-8              35.79µ ±  9%   21.71µ ±   3%  -39.35% (p=0.000 n=10)
ShortestAlts/AllTo_1000×16|0.1(822)-8            851.8µ ±  6%   400.5µ ±   6%  -52.98% (p=0.000 n=10)
AllShortest/AllBetween_100×2|0.5(17)-8          12.482µ ±  6%   8.573µ ±   3%  -31.32% (p=0.000 n=10)
AllShortest/AllBetween_1000×2|0.5(51)-8          80.74µ ±  2%   52.90µ ±   4%  -34.48% (p=0.000 n=10)
AllShortest/AllBetween_100×4|0.25(53)-8          22.54µ ±  4%   16.17µ ±   4%  -28.26% (p=0.000 n=10)
AllShortest/AllBetween_1000×4|0.25(574)-8        543.8µ ±  3%   326.7µ ±   5%  -39.93% (p=0.000 n=10)
AllShortest/AllBetween_100×16|0.1(76)-8          31.21µ ±  1%   22.45µ ±   3%  -28.07% (p=0.000 n=10)
AllShortest/AllBetween_1000×16|0.1(822)-8        678.4µ ±  1%   402.5µ ±   3%  -40.67% (p=0.000 n=10)
ShortestAlts/AllToFunc_100×2|0.5(17)-8                          5.892µ ±   2%
ShortestAlts/AllToFunc_1000×2|0.5(51)-8                         40.81µ ±   2%
ShortestAlts/AllToFunc_100×4|0.25(53)-8                         9.178µ ±   2%
ShortestAlts/AllToFunc_1000×4|0.25(574)-8                       214.6µ ±   2%
ShortestAlts/AllToFunc_100×16|0.1(76)-8                         12.62µ ±   3%
ShortestAlts/AllToFunc_1000×16|0.1(822)-8                       310.7µ ±   3%
AllShortest/AllBetweenFunc_100×2|0.5(17)-8                      5.713µ ±   1%
AllShortest/AllBetweenFunc_1000×2|0.5(51)-8                     45.68µ ±   3%
AllShortest/AllBetweenFunc_100×4|0.25(53)-8                     9.775µ ±   1%
AllShortest/AllBetweenFunc_1000×4|0.25(574)-8                   245.2µ ±   5%
AllShortest/AllBetweenFunc_100×16|0.1(76)-8                     13.76µ ±   1%
AllShortest/AllBetweenFunc_1000×16|0.1(822)-8                   314.7µ ±   1%
geomean                                          82.87µ         43.03µ         -38.14%

                                              │   old.bench   │              new.bench               │
                                              │     B/op      │     B/op      vs base                │
ShortestAlts/AllTo_100×2|0.5(17)-8              14.148Ki ± 0%   9.727Ki ± 0%  -31.25% (p=0.000 n=10)
ShortestAlts/AllTo_1000×2|0.5(51)-8              189.8Ki ± 0%   127.5Ki ± 0%  -32.80% (p=0.000 n=10)
ShortestAlts/AllTo_100×4|0.25(53)-8              22.32Ki ± 0%   14.99Ki ± 0%  -32.83% (p=0.000 n=10)
ShortestAlts/AllTo_1000×4|0.25(574)-8           1272.9Ki ± 0%   681.9Ki ± 0%  -46.42% (p=0.000 n=10)
ShortestAlts/AllTo_100×16|0.1(76)-8              33.23Ki ± 0%   22.66Ki ± 0%  -31.79% (p=0.000 n=10)
ShortestAlts/AllTo_1000×16|0.1(822)-8           1799.9Ki ± 0%   953.2Ki ± 0%  -47.04% (p=0.000 n=10)
AllShortest/AllBetween_100×2|0.5(17)-8          13.039Ki ± 0%   8.617Ki ± 0%  -33.91% (p=0.000 n=10)
AllShortest/AllBetween_1000×2|0.5(51)-8          181.5Ki ± 0%   119.3Ki ± 0%  -34.29% (p=0.000 n=10)
AllShortest/AllBetween_100×4|0.25(53)-8          21.34Ki ± 0%   14.01Ki ± 0%  -34.35% (p=0.000 n=10)
AllShortest/AllBetween_1000×4|0.25(574)-8       1264.8Ki ± 0%   673.8Ki ± 0%  -46.72% (p=0.000 n=10)
AllShortest/AllBetween_100×16|0.1(76)-8          32.24Ki ± 0%   21.68Ki ± 0%  -32.76% (p=0.000 n=10)
AllShortest/AllBetween_1000×16|0.1(822)-8       1791.8Ki ± 0%   945.1Ki ± 0%  -47.25% (p=0.000 n=10)
ShortestAlts/AllToFunc_100×2|0.5(17)-8                          6.922Ki ± 0%
ShortestAlts/AllToFunc_1000×2|0.5(51)-8                         119.8Ki ± 0%
ShortestAlts/AllToFunc_100×4|0.25(53)-8                         9.531Ki ± 0%
ShortestAlts/AllToFunc_1000×4|0.25(574)-8                       611.1Ki ± 0%
ShortestAlts/AllToFunc_100×16|0.1(76)-8                         13.12Ki ± 0%
ShortestAlts/AllToFunc_1000×16|0.1(822)-8                       870.7Ki ± 0%
AllShortest/AllBetweenFunc_100×2|0.5(17)-8                      5.812Ki ± 0%
AllShortest/AllBetweenFunc_1000×2|0.5(51)-8                     111.5Ki ± 0%
AllShortest/AllBetweenFunc_100×4|0.25(53)-8                     8.547Ki ± 0%
AllShortest/AllBetweenFunc_1000×4|0.25(574)-8                   603.0Ki ± 0%
AllShortest/AllBetweenFunc_100×16|0.1(76)-8                     12.14Ki ± 0%
AllShortest/AllBetweenFunc_1000×16|0.1(822)-8                   862.6Ki ± 0%
geomean                                          126.5Ki        68.27Ki       -37.99%

                                              │  old.bench  │              new.bench              │
                                              │  allocs/op  │  allocs/op   vs base                │
ShortestAlts/AllTo_100×2|0.5(17)-8              141.00 ± 0%    94.00 ± 0%  -33.33% (p=0.000 n=10)
ShortestAlts/AllTo_1000×2|0.5(51)-8              420.0 ± 0%    269.0 ± 0%  -35.95% (p=0.000 n=10)
ShortestAlts/AllTo_100×4|0.25(53)-8              279.0 ± 0%    174.0 ± 0%  -37.63% (p=0.000 n=10)
ShortestAlts/AllTo_1000×4|0.25(574)-8           2.888k ± 0%   1.741k ± 0%  -39.72% (p=0.000 n=10)
ShortestAlts/AllTo_100×16|0.1(76)-8              395.0 ± 0%    244.0 ± 0%  -38.23% (p=0.000 n=10)
ShortestAlts/AllTo_1000×16|0.1(822)-8           4.128k ± 0%   2.485k ± 0%  -39.80% (p=0.000 n=10)
AllShortest/AllBetween_100×2|0.5(17)-8          136.00 ± 0%    89.00 ± 0%  -34.56% (p=0.000 n=10)
AllShortest/AllBetween_1000×2|0.5(51)-8          415.0 ± 0%    264.0 ± 0%  -36.39% (p=0.000 n=10)
AllShortest/AllBetween_100×4|0.25(53)-8          275.0 ± 0%    170.0 ± 0%  -38.18% (p=0.000 n=10)
AllShortest/AllBetween_1000×4|0.25(574)-8       2.884k ± 0%   1.737k ± 0%  -39.77% (p=0.000 n=10)
AllShortest/AllBetween_100×16|0.1(76)-8          391.0 ± 0%    240.0 ± 0%  -38.62% (p=0.000 n=10)
AllShortest/AllBetween_1000×16|0.1(822)-8       4.124k ± 0%   2.481k ± 0%  -39.84% (p=0.000 n=10)
ShortestAlts/AllToFunc_100×2|0.5(17)-8                         71.00 ± 0%
ShortestAlts/AllToFunc_1000×2|0.5(51)-8                        211.0 ± 0%
ShortestAlts/AllToFunc_100×4|0.25(53)-8                        114.0 ± 0%
ShortestAlts/AllToFunc_1000×4|0.25(574)-8                     1.156k ± 0%
ShortestAlts/AllToFunc_100×16|0.1(76)-8                        160.0 ± 0%
ShortestAlts/AllToFunc_1000×16|0.1(822)-8                     1.652k ± 0%
AllShortest/AllBetweenFunc_100×2|0.5(17)-8                     66.00 ± 0%
AllShortest/AllBetweenFunc_1000×2|0.5(51)-8                    206.0 ± 0%
AllShortest/AllBetweenFunc_100×4|0.25(53)-8                    110.0 ± 0%
AllShortest/AllBetweenFunc_1000×4|0.25(574)-8                 1.152k ± 0%
AllShortest/AllBetweenFunc_100×16|0.1(76)-8                    156.0 ± 0%
AllShortest/AllBetweenFunc_1000×16|0.1(822)-8                 1.648k ± 0%
geomean                                          649.3         336.5       -37.70%