This repository was archived by the owner on May 31, 2025. It is now read-only.
Performance improvement for lower/upper bound#1223
Merged
dirk-thomas merged 2 commits intoros:lunar-develfrom Dec 19, 2017
Merged
Performance improvement for lower/upper bound#1223dirk-thomas merged 2 commits intoros:lunar-develfrom
dirk-thomas merged 2 commits intoros:lunar-develfrom
Conversation
Changed updateQueries() to use member functions of `multiset` instead of `std::lower_bound` and `std::upper_bound`
Contributor
|
Huh ... multiset::lower_bound does a tree search, which is "obviously efficient", while doing a (generic) binary search on the iterators of a tree structure is a bad idea: Even computing the mid of the range requires you to iterate over all elements to count them, which makes this operation linear instead of logarithmic :) |
Changed the calls to lower/upper bounds so they dont use the "new" C++11 extended initializer lists.
Contributor
|
This code looks OK to me, and seems to be an obvious performance improvement. @mikepurvis any thoughts? |
Member
|
Thank you for the patch. |
dirk-thomas
pushed a commit
that referenced
this pull request
Feb 9, 2018
* Performance improvement for lower/upper bound Changed updateQueries() to use member functions of `multiset` instead of `std::lower_bound` and `std::upper_bound` * Fixed warnings for C++98 Changed the calls to lower/upper bounds so they dont use the "new" C++11 extended initializer lists.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Changed updateQueries() to use member functions of
multisetinstead ofstd::lower_boundandstd::upper_boundWithout this change, playing a bag file containing over 200K messages (under a single topic) yields in a major performance hit.
Running performance diagnostic shows that most of the time is spent in
std::advanceandstd::distancewhich are used insidestd::lower_boundandstd::upper_bound.From cppreference - lower_bound:
Changing to
std::multiset<IndexEntry>::lower_boundresults in a major performance improvement.I have not measure the improvement, but I have a bag file containing a video of a stopwatch. In my code, for each
sensor_msgs::ImageI try to find a matching (single) message.Just by looking at the playback, I can see that the FPS is now fast enough to show a real second, whereas without this change, 1 second in the video (time it took for the stop watch to advanced by 1 second) took about 17 seconds in the real world!