[Lldb-commits] [PATCH] D67123: [lldb] Use binary search in RangeDataVector:FindEntryIndexesThatContain

[Pavel Labath via Phabricator via lldb-commits]

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::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
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D67123: [lldb] Use binary search in RangeDataVector:FindEntryIndexesThatContain

[Adrian McCarthy via Phabricator via lldb-commits]

amccarth added a comment.

This feels very familiar.  I think I've reviewed a similar change back when we 
first implemented minidumps.




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) {

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::max()));
```



Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D67123/new/

https://reviews.llvm.org/D67123



___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D67123: [lldb] Use binary search in RangeDataVector:FindEntryIndexesThatContain

[Raphael Isemann via Phabricator via lldb-commits]

teemperor added a comment.

See the br-by-regex flamegraph: F9913466: br-by-regex.svg 



Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D67123/new/

https://reviews.llvm.org/D67123



___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D67123: [lldb] Use binary search in RangeDataVector:FindEntryIndexesThatContain

[Raphael Isemann via Phabricator via lldb-commits]

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 , const Entry ) {
+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  : 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 , const Entry ) {
+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  : 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