significantly improve execution time and cpu use of "sample" for large trajectories

[jbeck28]

I noticed for trajectories which contain ~25k waypoints that CPU usage would grow continuously over the course of the trajectory's execution. I narrowed this down to "sample" always starting from the beginning of the trajectory. This small change fixed the issue.

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 32.48%. Comparing base (0d3fc52) to head (d4cc1b4). Report is 81 commits behind head on master.

:exclamation: Current head d4cc1b4 differs from pull request most recent head 664252c. Consider uploading reports for the commit 664252c to get more accurate results

Additional details and impacted files

@@             Coverage Diff             @@
##           master     #474       +/-   ##
===========================================
- Coverage   44.88%   32.48%   -12.41%     
===========================================
  Files          40        7       -33     
  Lines        3636      665     -2971     
  Branches     1716      357     -1359     
===========================================
- Hits         1632      216     -1416     
+ Misses        832      157      -675     
+ Partials     1172      292      -880     

Flag	Coverage Δ
unittests	32.48% <ø> (-12.41%)	:arrow_down:

Flags with carried forward coverage won't be shown. Click here to find out more.

Files	Coverage Δ
...troller/include/diff_drive_controller/odometry.hpp	20.00% <ø> (ø)

... and 39 files with indirect coverage changes

[bmagyar]

Indeed @destogl , this should be also tested not only for speed but some simple unit test setup ensuring that the scenarios we call sample() in are not broken.

[jbeck28]

I'd be happy to try my hand writing tests to verify performance, as well as verifying existing tests work - however there is a looming deadline at work on December 15th so I likely won't get around to it until after that date.

Thanks for both of your time, Josh

[mergify[bot]]

This pull request is in conflict. Could you fix it @jbeck28?

[jbeck28]

Hello,

Sorry for letting this rot for a year... also for my confusion. I don't believe that this PR should change the signature for the sample method. The only way I could see the behavior of "sample" changing would be if one were to call sample at time "t", and then subsequently called "sample" at time T < t.

It looks like the existing unit tests passed, however. Some guidance on what folks would like changed or improved would be much appreciated.

Thanks, Josh

[jodle001]

We need to think this better through and think about other possible optimizations.

Can I ask what you think might be wrong with this change? From my experience with this, if you have very large trajectories, this is much faster because otherwise the sample method always starts back at zero.

We would like to use binaries, but this one small change stops us from being able to do so.

[christophfroehlich]

It seems that something happened with the latest merge, have you worked on humble but merged now the master branch? The diff view shows >200 changed files. I suggest cherry-picking your relevant commits onto a new branch from master, and force push on your jbeck28:humble branch to keep the discussion from above in this PR. (Or you make a new one, and link this PR in the description).

[bmagyar]

Personally I'd be happy to merge this as long as we have tests that specifically address this functionality. I don't think we should do any stress-testing on the CI as it wasn't meant for that but an inherited class from Trajectory could be unit-tested with inspectability of the internal index, etc to make sure we cover the extreme cases and not segfault on something silly.

[bmagyar]

@jodle001 @jbeck28 the remaining ask is very simple: Unit tests that specifically verify the extra bit of functionality you added.

Unit tests not only ensure your code keeps working in the long run but also serves as proof of intent on what function you imagined that piece of code to fulfil. What should you test for? You probably know better than me but here's a wild guess:

• check that the internally stored index gets updated (correctly) on subsequent calls to sample()
• ensure that normal operation resets the index
• verify that the output trajectory somehow reflects where the index is set ( std::distance on iterators?)

But again, you probably know better since it's your changes ;)

You can't reliably measure performance with time or other benchmarking tools on the CI so let's forget a

[mergify[bot]]

This pull request is in conflict. Could you fix it @jbeck28?

[jbeck28]

Hi Bence, thanks for the clarification. I understand the value of unit testing but lack much experience in creating them, so my apologies if this comes across as argumentative (or stupid). I think the confusion I'm having here is that this change doesn't add functionality. The only salient change this makes is reducing the time required to execute "sample" with large trajectories - and like you pointed out that's not entirely possible to test quantitatively.

The latest commit I made "implemented" a test which was supposed to verify the index increments properly, but after pushing the commit I realized this is exactly the test cases already implemented starting here. I guess I feel like if the previous tests for trajectory are still passing, then this doesn't break any existing functionality.

That said, the one thing this does change is it demands that consecutive calls to "sample" must be done at monotonically increasing times. I don't think that it should ever happen where the nth call to sample is at time t and the n+1'th call is at time T < t.

I'll be very curious to hear your thoughts on this, and I can easily write a test to demonstrate the situation I've described if needed.

Thanks, Josh