teemperor created this revision.
teemperor added a reviewer: labath.
Herald added subscribers: lldb-commits, JDevlieghere, arphaman.
Herald added a project: LLDB.
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 binary search to find what ranges we actually have to check and skip over
all the other ranges.
Repository:
rLLDB LLDB
https://reviews.llvm.org/D67123
Files:
lldb/include/lldb/Utility/RangeMap.h
Index: lldb/include/lldb/Utility/RangeMap.h
===================================================================
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -712,6 +712,10 @@
return lhs.GetRangeBase() < rhs.GetRangeBase();
}
+ static bool BaseLessEqual(const Entry &lhs, const Entry &rhs) {
+ return lhs.GetRangeBase() <= rhs.GetRangeBase();
+ }
+
uint32_t FindEntryIndexThatContains(B addr) const {
const Entry *entry = FindEntryThatContains(addr);
if (entry)
@@ -724,12 +728,18 @@
#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);
- }
+ if (m_entries.empty())
+ return indexes.size();
+
+ // Find the first range which base address is higher than the address
+ // we are looking for. This address can't contain the address we are
+ // looking for. All addresses after also can't contain our address as
+ // we sorted our ranges by base address.
+ auto end = std::lower_bound(m_entries.begin(), m_entries.end(),
+ Entry(addr, 1), BaseLessEqual);
+ for (auto I = m_entries.begin(); I != end; ++I) {
+ if (I->Contains(addr))
+ indexes.push_back(I->data);
}
return indexes.size();
}
Index: lldb/include/lldb/Utility/RangeMap.h
===================================================================
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -712,6 +712,10 @@
return lhs.GetRangeBase() < rhs.GetRangeBase();
}
+ static bool BaseLessEqual(const Entry &lhs, const Entry &rhs) {
+ return lhs.GetRangeBase() <= rhs.GetRangeBase();
+ }
+
uint32_t FindEntryIndexThatContains(B addr) const {
const Entry *entry = FindEntryThatContains(addr);
if (entry)
@@ -724,12 +728,18 @@
#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);
- }
+ if (m_entries.empty())
+ return indexes.size();
+
+ // Find the first range which base address is higher than the address
+ // we are looking for. This address can't contain the address we are
+ // looking for. All addresses after also can't contain our address as
+ // we sorted our ranges by base address.
+ auto end = std::lower_bound(m_entries.begin(), m_entries.end(),
+ Entry(addr, 1), BaseLessEqual);
+ for (auto I = m_entries.begin(); I != end; ++I) {
+ if (I->Contains(addr))
+ indexes.push_back(I->data);
}
return indexes.size();
}
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
