copilot/suggest-performance-improvements - Branch - evenfurther/pathfinding

perf: reduce allocations in pathfinding hot paths

#720

Comparing

copilot/suggest-performance-improvements

(

6aafd93

) with

main

(

f1d662c

)

-23%

Improvements: 2

Regressions: 1

Untouched: 35

Benchmarks

Failed

fill-corner_to_corner_astar

benches/algos-fill.rs::benches::corner_to_corner_astar

Regression

-23%

98.1 µs127.6 µs

Improved

separate_components

benches/algos.rs::benches::bench_separate_components

×2

2.2 ms1.1 ms

separate_components

benches/separate_components.rs::benches::bench_separate_components

+16%

7.4 ms6.4 ms

Passed

no_path_dfs

benches/algos.rs::benches::no_path_dfs

+5%

1.3 ms1.2 ms

no_path_bfs

benches/algos.rs::benches::no_path_bfs

+5%

1.3 ms1.2 ms

corner_to_corner_astar

benches/algos.rs::benches::corner_to_corner_astar

+3%

76.8 µs74.6 µs

corner_to_corner_dijkstra

benches/algos.rs::benches::corner_to_corner_dijkstra

+2%

1.4 ms1.4 ms

fill-corner_to_corner_fringe

benches/algos-fill.rs::benches::corner_to_corner_fringe

+2%

108.7 µs106.8 µs

fill-corner_to_corner_dijkstra

benches/algos-fill.rs::benches::corner_to_corner_dijkstra

+1%

1.2 ms1.2 ms

no_path_fringe

benches/algos.rs::benches::no_path_fringe

+1%

1.9 ms1.9 ms

arena

benches/movingai.rs::benches::arena

43.9 ms43.7 ms

no_path_bfs_bidirectional

benches/algos.rs::benches::no_path_bfs_bidirectional

1.5 ms1.5 ms

fill-corner_to_corner_idastar

benches/algos-fill.rs::benches::corner_to_corner_idastar

228.6 µs228 µs

no_path_astar

benches/algos.rs::benches::no_path_astar

1.4 ms1.4 ms

fill-corner_to_corner_dfs

benches/algos-fill.rs::benches::corner_to_corner_dfs

3.5 ms3.5 ms

fill-no_path_dijkstra

benches/algos-fill.rs::benches::no_path_dijkstra

1.3 ms1.3 ms

fill-no_path_bfs

benches/algos-fill.rs::benches::no_path_bfs

1.2 ms1.2 ms

fill-corner_to_corner_bfs

benches/algos-fill.rs::benches::corner_to_corner_bfs

1.1 ms1.1 ms

Compare kuhn_munkres with different input sizes[512]

benches/kuhn_munkres.rs::benches::compare_size

455 ms455 ms

Compare kuhn_munkres with different input sizes[256]

benches/kuhn_munkres.rs::benches::compare_size

19.4 ms19.4 ms

transpose

benches/matrices.rs::benches::transpose_benchmark

40.9 µs40.9 µs

Compare kuhn_munkres with different input sizes[128]

benches/kuhn_munkres.rs::benches::compare_size

1.8 ms1.8 ms

wikipedia_example_sparse

benches/edmondskarp.rs::benches::wikipedia_example_sparse

45.5 µs45.5 µs

fill-no_path_dfs

benches/algos-fill.rs::benches::no_path_dfs

3.2 ms3.2 ms

Compare kuhn_munkres with different input sizes[64]

benches/kuhn_munkres.rs::benches::compare_size

507 µs507 µs

wikipedia_example_dense

benches/edmondskarp.rs::benches::wikipedia_example_dense

30.4 µs30.4 µs

corner_to_corner_bfs_bidirectional

benches/algos.rs::benches::corner_to_corner_bfs_bidirectional

1.7 ms1.7 ms

corner_to_corner_bfs

benches/algos.rs::benches::corner_to_corner_bfs

1.3 ms1.3 ms

transpose_non_square

benches/matrices.rs::benches::transpose_non_square_benchmark

159.8 µs159.9 µs

no_path_dijkstra

benches/algos.rs::benches::no_path_dijkstra

1.3 ms1.3 ms

Compare kuhn_munkres with different input sizes[32]

benches/kuhn_munkres.rs::benches::compare_size

112.4 µs112.5 µs

fill-corner_to_corner_iddfs

benches/algos-fill.rs::benches::corner_to_corner_iddfs

4.1 ms4.1 ms

corner_to_corner_iddfs

benches/algos.rs::benches::corner_to_corner_iddfs

1.4 ms1.4 ms

corner_to_corner_dfs

benches/algos.rs::benches::corner_to_corner_dfs

1.5 ms1.5 ms

fill-no_path_fringe

benches/algos-fill.rs::benches::no_path_fringe

1.4 ms1.4 ms

corner_to_corner_idastar

benches/algos.rs::benches::corner_to_corner_idastar

-1%

118.6 µs119.3 µs

corner_to_corner_fringe

benches/algos.rs::benches::corner_to_corner_fringe

-2%

97 µs98.8 µs

fill-no_path_astar

benches/algos-fill.rs::benches::no_path_astar

-3%

1.2 ms1.2 ms

Commits

Click on a commit to change the comparison range

Base

main

f1d662c

-23.17%

perf: pre-allocate BinaryHeap in astar_bag Add capacity hint to reduce reallocations in astar_bag BinaryHeap, similar to the optimization already done for regular astar function. Co-authored-by: samueltardieu <44656+samueltardieu@users.noreply.github.com>

6aafd93

2 days ago

by Copilot

Home Terms Privacy Docs