[lldb] Early exit in RangeDataVector:FindEntryIndexesThatContain

[teemperor]

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.

[teemperor]

See the br-by-regex flamegraph:

br-by-regex.svg677 KBDownload

[amccarth]

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

lldb/include/lldb/Utility/RangeMap.h

739 ↗

(On Diff #218509)

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()));

[labath]

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...

lldb/include/lldb/Utility/RangeMap.h

739 ↗

(On Diff #218509)

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.

[teemperor]

• Refactor to just stop the search when we find a higher base address.

[teemperor]

lldb/include/lldb/Utility/RangeMap.h

739 ↗

(On Diff #218509)

Oh true, I got confused by all the other lower_bounding we do in the surrounding functions :)

[labath]

lgtm

lldb/include/lldb/Utility/RangeMap.h

728–729 ↗

(On Diff #218602)

This pattern seems to be common in lldb, but I really don't understand the reason behind it -- it just checks the condition that would be checked by the for loop anyway. I've personally just started removing checks like these whenever I touch some code which uses them...

[teemperor]

• remove empty check

[amccarth]

lldb/include/lldb/Utility/RangeMap.h

739 ↗

(On Diff #218509)

I still don't see the early exit from the loop. Have you uploaded the latest diff to Phabricator?

(Thanks Pavel for pointing out the obvious that teemperor and I both missed.)

[amccarth]

Disregard my last comment. Phabricator wasn't showing me that latest, nor that the patch had already been submitted, which seems to be happening with increasing frequency.

lldb/trunk/include/lldb/Utility/RangeMap.h

uint32_t FindEntryIndexThatContains(B addr) const {
     return UINT32_MAX;
   }
 
   uint32_t FindEntryIndexesThatContain(B addr,
                                        std::vector<uint32_t> &indexes) const {
 #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.
+      else if (entry.GetRangeBase() > addr)
+        break;
     }
     return indexes.size();
   }
 
   Entry *FindEntryThatContains(B addr) {
     return const_cast<Entry *>(
         static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
             addr));