Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Check cost computing overhead #490

Closed
jcoupey opened this issue Apr 20, 2021 · 2 comments · Fixed by #491
Closed

Check cost computing overhead #490

jcoupey opened this issue Apr 20, 2021 · 2 comments · Fixed by #491
Labels
compilation enhancement internals

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Apr 20, 2021

The ability to use multiple profiles introduced in #450 changed the way we now access cost values. Instead of a single matrix lookup previously, we now have a ponderation with a vehicle-dependent speed factor happening in Vehicle::Cost:

vroom/src/structures/vroom/vehicle.h

Lines 67 to 71 in 1e32124

Cost cost(Index i, Index j) const {
return static_cast<Cost>(
cost_wrapper.durations_factor *
static_cast<double>((*(cost_wrapper.durations_matrix))[i][j]));
}

This is a price we have to pay for the sake of a much bigger flexibility in cost evaluation. The downside is that this also means a computing time increase for single-profile instances even with unused vehicle speed_factor (see #450 (comment)).

I've tried to make this as efficient as possible, in particular by providing the Vehicle::Cost implementation in header file to allow the compiler to perform some optimizations in other units. I wonder if there is more to it and if we could improve the structures or the layout to further reduce the increase. I guess this would call for some profiling to get a clearer view of what are the most expensive bits here.
@krypt-n
Copy link
Contributor

krypt-n commented Apr 21, 2021

I had a couple of ideas on how to compensate for the 17% slowdown. I think the preliminary benchmark results are promising:

Current master:

,Gaps,Computing times
Min,-14.89,176
First decile,-4.56,367
Lower quartile,-0.0,455
Median,2.03,650
Upper quartile,6.67,1591
Ninth decile,8.88,1961
Max,11.53,2381

My changes:

Min,-14.89,153
First decile,-4.56,322
Lower quartile,-0.0,404
Median,2.03,562
Upper quartile,6.67,1470
Ninth decile,8.88,1727
Max,11.53,2046

I'll open a PR later to discuss the changes after I cleaned them up a little.

@jcoupey
Copy link
Collaborator Author

jcoupey commented Apr 21, 2021

@krypt-n looking forward to seeing the kind of changes you tried! I'll wait for your PR before releasing v1.10.0, we might as well take the time to include the changes.

@krypt-n krypt-n mentioned this issue Apr 21, 2021
Merged
2 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compilation enhancement internals
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Optimize cost_wrapper krypt-n/vroom
2 participants
@krypt-n @jcoupey