cache-route-data-accesses-for-any-start-end-index-pair - Branch - PyVRP/PyVRP

PyVRP

Blog Docs

Lazily cache route segment access

#680Closed

Comparing

cache-route-data-accesses-for-any-start-end-index-pair

(

2bad86f

) with

main

(

049800a

)

-44%

Improvements: 7

Regressions: 30

Untouched: 5

New: 0

Dropped: 0

Ignored: 0

Benchmarks

Failed

test_all_operators[mdvrp]Regression

benchmarks/search/test_LocalSearch.py::test_all_operators[mdvrp]

-40%

194.2 ms

325.3 ms

test_all_operators[vrpb]Regression

benchmarks/search/test_LocalSearch.py::test_all_operators[vrpb]

-43%

21.4 ms

37.6 ms

test_all_operators[vrptw]Regression

benchmarks/search/test_LocalSearch.py::test_all_operators[vrptw]

-44%

20.3 ms

36.3 ms

test_each_node_operator[mdvrp-Exchange10]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange10]

-42%

48.9 ms

85 ms

test_each_node_operator[mdvrp-Exchange11]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange11]

-36%

56.2 ms

87.9 ms

test_each_node_operator[mdvrp-Exchange20]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange20]

-32%

58 ms

85.4 ms

test_each_node_operator[mdvrp-Exchange21]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange21]

-34%

88.2 ms

132.9 ms

test_each_node_operator[mdvrp-Exchange22]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange22]

-26%

46.4 ms

62.3 ms

test_each_node_operator[mdvrp-Exchange30]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange30]

-29%

46.1 ms

64.7 ms

test_each_node_operator[mdvrp-Exchange31]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange31]

-29%

69.1 ms

97.9 ms

test_each_node_operator[mdvrp-Exchange32]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange32]

-24%

75.1 ms

99 ms

test_each_node_operator[mdvrp-Exchange33]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-Exchange33]

-21%

37.4 ms

47.6 ms

test_each_node_operator[mdvrp-SwapTails]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[mdvrp-SwapTails]

-12%

87.1 ms

99.4 ms

test_each_node_operator[vrpb-Exchange10]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange10]

-43%

7.7 ms

13.4 ms

test_each_node_operator[vrpb-Exchange11]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange11]

-15%

1.3 ms

1.5 ms

test_each_node_operator[vrpb-SwapTails]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-SwapTails]

-33%

4.9 ms

7.4 ms

test_each_node_operator[vrptw-Exchange10]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange10]

-44%

7.4 ms

13.3 ms

test_each_node_operator[vrptw-Exchange11]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange11]

-36%

4.5 ms

7 ms

test_each_node_operator[vrptw-Exchange20]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange20]

-43%

6.1 ms

10.6 ms

test_each_node_operator[vrptw-Exchange21]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange21]

-37%

6.1 ms

9.8 ms

test_each_node_operator[vrptw-Exchange22]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange22]

-30%

3 ms

4.3 ms

test_each_node_operator[vrptw-Exchange30]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange30]

-40%

5.9 ms

9.9 ms

test_each_node_operator[vrptw-Exchange31]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange31]

-33%

4 ms

6 ms

test_each_node_operator[vrptw-Exchange32]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange32]

-31%

3.9 ms

5.7 ms

test_each_node_operator[vrptw-Exchange33]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-Exchange33]

-24%

3.1 ms

4.1 ms

test_each_node_operator[vrptw-SwapTails]Regression

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrptw-SwapTails]

-32%

6.5 ms

9.6 ms

test_each_route_operator[mdvrp-SwapRoutes]Regression

benchmarks/search/test_LocalSearch.py::test_each_route_operator[mdvrp-SwapRoutes]

-16%

684.6 µs

811.8 µs

test_each_route_operator[mdvrp-SwapStar]Regression

benchmarks/search/test_LocalSearch.py::test_each_route_operator[mdvrp-SwapStar]

-34%

31.7 ms

47.7 ms

test_each_route_operator[vrpb-SwapStar]Regression

benchmarks/search/test_LocalSearch.py::test_each_route_operator[vrpb-SwapStar]

-16%

2.7 ms

3.2 ms

test_each_route_operator[vrptw-SwapStar]Regression

benchmarks/search/test_LocalSearch.py::test_each_route_operator[vrptw-SwapStar]

-26%

3.1 ms

4.3 ms

Improved

test_each_node_operator[vrpb-Exchange33]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange33]

+14%

873.6 µs

764.7 µs

test_each_node_operator[vrpb-Exchange32]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange32]

+14%

873.4 µs

765.8 µs

test_each_node_operator[vrpb-Exchange31]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange31]

+14%

873.4 µs

766.5 µs

test_each_node_operator[vrpb-Exchange30]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange30]

+14%

869.6 µs

765.8 µs

test_each_node_operator[vrpb-Exchange21]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange21]

+13%

873 µs

771.2 µs

test_each_node_operator[vrpb-Exchange20]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange20]

+13%

868.9 µs

771 µs

test_each_node_operator[vrpb-Exchange22]

benchmarks/search/test_LocalSearch.py::test_each_node_operator[vrpb-Exchange22]

+13%

867.8 µs

770.5 µs

Passed

test_each_route_operator[vrpb-SwapRoutes]

benchmarks/search/test_LocalSearch.py::test_each_route_operator[vrpb-SwapRoutes]

+9%

1.3 ms

1.2 ms

test_solve[vrpb]

benchmarks/test_solve.py::test_solve[vrpb]

+2%

16 ms

15.6 ms

test_each_route_operator[vrptw-SwapRoutes]

benchmarks/search/test_LocalSearch.py::test_each_route_operator[vrptw-SwapRoutes]

+2%

311.8 µs

306.2 µs

test_solve[mdvrp]

benchmarks/test_solve.py::test_solve[mdvrp]

62.4 ms

test_solve[vrptw]

benchmarks/test_solve.py::test_solve[vrptw]

10 ms

Commits

Click on a commit to change the comparison range

Base

main

049800a

-45%

Remove other segments

cf3fcfc

24 days ago

by N-Wouda

-49%

Remove all caching

1a58ea8

24 days ago

by N-Wouda

Merge branch 'main' into cache-route-data-accesses-for-any-start-end-index-pair

decafdb

24 days ago

by N-Wouda

+10%

Simplify

d04c5cf

23 days ago

by N-Wouda

Fix redeclaration of default argument

1efa9d9

23 days ago

by N-Wouda

Maybe fix clang issue?

7304ab3

23 days ago

by N-Wouda

Fingers crossed

fa183ed

23 days ago

by N-Wouda

+40%

Implement basic cache system

341b628

23 days ago

by N-Wouda

Solve a bit longer in the benchmarks

d710383

23 days ago

by N-Wouda

Rewrite to make Route::update branchless

98b2d26

23 days ago

by N-Wouda

Default constructor for concat schemes

55a4b05

23 days ago

by N-Wouda

Revert change

2bad86f

23 days ago

by N-Wouda

Home Terms Privacy Docs