labath added a comment.
I remember seeing this inefficiency when looking at this class some time ago,
but it was not clear to me what should be done about that. This is still an
improvement, as it will reduce the time by 50% on average, but it is still
going to be O(n). If this is really a performance bottleneck, then we will need
to come up with some better data structure for storing this, or put some
restrictions on the kind of entries that we can have in the map...
================
Comment at: lldb/include/lldb/Utility/RangeMap.h:739
+ auto end = std::lower_bound(m_entries.begin(), m_entries.end(),
+ Entry(addr, 1), BaseLessEqual);
+ for (auto I = m_entries.begin(); I != end; ++I) {
----------------
amccarth wrote:
> You're trying to find an upper bound, so `std::upper_bound` seems more
> natural than `std::lower_bound`. Understanding how `std::lower_bound` works
> with a comparator that implements `<=` requires some mental gymnastics. With
> `std::upper_bound`, you'd just need `<` that compares only the base addresses.
>
> You could even avoid the custom comparison function by using the maximum
> value for the size:
>
> ```
> auto end = std::upper_bound(m_entries.begin(), m_entries.end(),
> Entry(addr,
> std::numeric_limits<Entry::SizeType>::max()));
> ```
>
Actually, If I understand this correctly, there is no need for either lower or
upper bound here. Since you're going to be iterating through the list anyway.
It should be sufficient to add a early exit from the loop once you encounter an
element whose base address is >= the address you search for.
Repository:
rLLDB LLDB
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D67123/new/
https://reviews.llvm.org/D67123
_______________________________________________
lldb-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
