Optimize cost_wrapper #491
Conversation
This saves one level of indirection
|
But it seems like I need to find a way to make these benchmarks produce more reliable numbers |
|
Thanks a lot for this input. I quite like the Keeping the cost scaling part in the integer world is definitely something I should have done in the first place! Restricting the duration factor to two digits after the decimal point is definitely not a problem. This does not exactly apply to the |
There was a problem hiding this comment.
Looking good with the single comment and docs update.
Regarding changelog, I don't think this should generate an entry as it's a change on a change, not wrt the previous release. But it would be useful to add #490 along with #394 in the first "Support for heterogeneous vehicle routing profiles" entry.
|
On the topic of getting reliable numbers on benchmarks, the variation in computing times is probably more noticeable with small instances (homberger_200 vs homberger_1000). Maybe a good approach would be to sum computing times across a given number of runs on each instance, but that's another topic altogether. For now we're interested in overall trends and I guess they'll be consistent across benchmark classes. |
|
I just merged this PR both to |
|
Running on the usual CVRP and VRPTW benchmarks across various exploration level shows a consistent improvement. The average computing time increase between So the changes introduced here more than halved the impact on computing times for single-profile instances. |
Issue
Closes #490
Tasks
CHANGELOG.md(remove if irrelevant)Description
hommberger_200 VRPTW benchmark master at 1e32124
The first commit 3a0e9d9 turns
Matrixfrom a vector of vectors into a flat vector. This removes a layer of indirection and could perhaps improve memory locality.The second commit 3a0e9d9 just moves some code around and should not have an impact.
The third commit 9cba73e removes another layer of indirection by allowing
cost_wrapperto directly access the matrix array.My next idea was to get rid of the cast to double by turning the cost factor into a whole number. My first attempt was 510557e .
However, it turned out that 128 as a factor did not lead to correct reported costs on the HVRP instances (the cost factors can not be exactly represented as multiples of 1/128). That's why I changed the factor to 100 and fixed an additional rounding problem in eb253e2 and 6b3e488 . Leading to these final results:
Note that these computing times tend to fluctuate quite a bit on my machine, but I think the general trend towards lower computing times is visible here.
The last change effectively restricts the duration factor to two digits after the decimal point. That should probably be documented somewhere if this PR is merged.