Skip to content

Commit

Permalink
[lldb] Early exit in RangeDataVector:FindEntryIndexesThatContain
Browse files Browse the repository at this point in the history
Summary:
We currently spend a lot of time in this function (around 27% of the br-by-regex benchmark in lldb-bench)
by just iterating over all the ranges. We already sorted these ranges by their base address, we we can actually
just stop checking ranges as soon as we find one that has a higher base address.

Reviewers: labath

Reviewed By: labath

Subscribers: amccarth, arphaman, JDevlieghere, lldb-commits

Tags: #lldb

Differential Revision: https://reviews.llvm.org/D67123

llvm-svn: 370879
  • Loading branch information
Teemperor committed Sep 4, 2019
1 parent 75d7344 commit e36fd9e
Showing 1 changed file with 8 additions and 6 deletions.
14 changes: 8 additions & 6 deletions lldb/include/lldb/Utility/RangeMap.h
Original file line number Diff line number Diff line change
@@ -724,12 +724,14 @@ class RangeDataVector {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif

if (!m_entries.empty()) {
for (const auto &entry : m_entries) {
if (entry.Contains(addr))
indexes.push_back(entry.data);
}
// Search the entries until the first entry that has a larger base address
// than `addr`. As m_entries is sorted by their base address, all following
// entries can't contain `addr` as their base address is already larger.
for (const auto &entry : m_entries) {
if (entry.Contains(addr))
indexes.push_back(entry.data);
else if (entry.GetRangeBase() > addr)
break;
}
return indexes.size();
}

0 comments on commit e36fd9e

Please sign in to comment.