Treat RangeDataVector as an augmented BST

[unnar]

Summary

Since RangeDataVector is assumed to always be sorted we can treat it as an flattened BST and augment it with additional information about the ranges belonging to each "subtree". By storing the maximum endpoint in every subtree we can query for intervals in O(log n) time.

Note: this is not a complete patch, I just wanted to put it out there and see how you feel about this. Also what kind of testing could and should be done for this.

[jarin]

Thanks for putting this together, some comments below. Let us see what Pavel thinks.

lldb/include/lldb/Utility/RangeMap.h

437

BST -> binary search tree

445

Here, B() should be the min value of type B, no? Perhaps this should be std::numeric_limits<B>::min() instead of B()?

527

Hmm, weird, I am surprised this is not std::vector<T> &indexes (I realize this was in the code before).

608

I am guessing this should have the m_ prefix?

[labath]

I like this idea a lot, in principle. It is much simpler than a full blown interval tree, and it should give us similar performance characteristics.

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

The implementation itself needs some work though. My incomplete list of comments is:

• replace int with size_t and closed intervals with half-open ones
• let's move the computation of the upper bound into the "Sort" function. sorting is O(n log(n)), this is O(n) -- we can just hide it there.
• make private functions private
• we should avoid the business of figuring out what is the suitable "minimum" value of B by ensuring we call the recursive function on non-empty intervals
• clang-format the patch

For testing you should add some c++ unit tests for the relevant interfaces.

[jarin]

In D74759#1880499, @labath wrote:

I like this idea a lot, in principle. It is much simpler than a full blown interval tree, and it should give us similar performance characteristics.

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

Thanks for the feedback! We were aiming for something simple and efficient enough. Our preliminary results show that the lookup pretty much disappears even from the profiles it was dominating before.

The implementation is pretty much taken from the "Augmented tree" section of https://en.wikipedia.org/wiki/Interval_tree where we just use the tree induced by the pivots of the binary search as the binary search tree that we augment. I believe the complexity is O(m log n), even though the wikipedia article makes a O(m + log n) claim. This should be still much better than the current O(n) and the memory cost seems to be quite palatable (extra word per symbol).

The implementation itself needs some work though. My incomplete list of comments is:

• replace int with size_t and closed intervals with half-open ones
• let's move the computation of the upper bound into the "Sort" function. sorting is O(n log(n)), this is O(n) -- we can just hide it there.
• make private functions private
• we should avoid the business of figuring out what is the suitable "minimum" value of B by ensuring we call the recursive function on non-empty intervals
• clang-format the patch

For testing you should add some c++ unit tests for the relevant interfaces.

[teemperor]

If we get away with this approach them I'm completely fine with it. But I would feel better if we first have some more unit tests for RangeDataVector first.

[labath]

In D74759#1880559, @jarin wrote:

In D74759#1880499, @labath wrote:

I like this idea a lot, in principle. It is much simpler than a full blown interval tree, and it should give us similar performance characteristics.

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

Thanks for the feedback! We were aiming for something simple and efficient enough. Our preliminary results show that the lookup pretty much disappears even from the profiles it was dominating before.

The implementation is pretty much taken from the "Augmented tree" section of https://en.wikipedia.org/wiki/Interval_tree where we just use the tree induced by the pivots of the binary search as the binary search tree that we augment. I believe the complexity is O(m log n), even though the wikipedia article makes a O(m + log n) claim. This should be still much better than the current O(n) and the memory cost seems to be quite palatable (extra word per symbol).

Ok, I see. Thanks for that reference. The wikipedia description is somewhat short, but I am beginning to understand how this could work. Maybe you could include a pointer to the wikipedia page and/or the book it references next to the algorithm.

[unnar]

In D74759#1880499, @labath wrote:

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

I should have been more specific, searching for any interval that contains a point can be done in O(log n) but in our case where we are searching for all intervals that contain the point and as Jarin said we believe it takes O(m log n) (I admit I have not done a thorough analysis of the time complexity myself). The theoretical best you can do is indeed O(m + log n).

The implementation itself needs some work though. My incomplete list of comments is:

• replace int with size_t and closed intervals with half-open ones

Done.

• let's move the computation of the upper bound into the "Sort" function. sorting is O(n log(n)), this is O(n) -- we can just hide it there.

That was my first thought but I decided to have it generated lazily instead, I will move it back to the sort.

• make private functions private

Done.

• we should avoid the business of figuring out what is the suitable "minimum" value of B by ensuring we call the recursive function on non-empty intervals

Done.

• clang-format the patch

Done.

For testing you should add some c++ unit tests for the relevant interfaces.

Done. Do you think we should also unit test ComputeUpperBounds or just the interface?

lldb/include/lldb/Utility/RangeMap.h

445

Removed and made sure not to recursively call in degenerate cases.

527

I suspect this function used to have a different implementation where it would return the indexes of the entries rather than the data itself similar to FindEntryIndexThatContains and it was not properly changed when it was updated.

608

Removed as it is no longer needed.

[unnar]

Added reference to Wikipedia article.

[labath]

Thanks for adding the tests. They look good. Could you split them off into a separate patch? I believe @teemperor wanted (and I do agree it's a good idea) to check them in first in order to demonstrate that this patch does not change the behavior (or to make it what exactly changes).

lldb/unittests/Utility/RangeMapTest.cpp

22 ↗

(On Diff #246681)

returning a const value from a function is fairly useless. All it does is make the caller jump through some hoops if he really wants to modify it.

[labath]

In D74759#1893186, @unnar wrote:

In D74759#1880499, @labath wrote:

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

I should have been more specific, searching for any interval that contains a point can be done in O(log n) but in our case where we are searching for all intervals that contain the point and as Jarin said we believe it takes O(m log n) (I admit I have not done a thorough analysis of the time complexity myself). The theoretical best you can do is indeed O(m + log n).

Yep, I can easily convince myself is m*log(n). I can believe it can be O(m+log(n)) too, but proving that would require some pretty careful accounting. In either case, I am sure this is better than what we have now.

For testing you should add some c++ unit tests for the relevant interfaces.

Done. Do you think we should also unit test ComputeUpperBounds or just the interface?

Testing the interface should be enough. In fact, the main thing that is bothering me about this patch at this stage is that the new "upper_bound" member is public and accessible to the user. I haven't decided yet what to do about it. Have you looked at what it would take to make that private somehow? Maybe by storing std::pair<Entry, bound> in the private vector, and only handing out pointers to the Entry component ?

[unnar]

Sure, removed tests from this patch. They are now at D75180

lldb/unittests/Utility/RangeMapTest.cpp

22 ↗

(On Diff #246681)

Noted.

[unnar]

In D74759#1893450, @labath wrote:

In D74759#1893186, @unnar wrote:

In D74759#1880499, @labath wrote:

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

I should have been more specific, searching for any interval that contains a point can be done in O(log n) but in our case where we are searching for all intervals that contain the point and as Jarin said we believe it takes O(m log n) (I admit I have not done a thorough analysis of the time complexity myself). The theoretical best you can do is indeed O(m + log n).

Yep, I can easily convince myself is m*log(n). I can believe it can be O(m+log(n)) too, but proving that would require some pretty careful accounting. In either case, I am sure this is better than what we have now.

For testing you should add some c++ unit tests for the relevant interfaces.

Done. Do you think we should also unit test ComputeUpperBounds or just the interface?

Testing the interface should be enough. In fact, the main thing that is bothering me about this patch at this stage is that the new "upper_bound" member is public and accessible to the user. I haven't decided yet what to do about it. Have you looked at what it would take to make that private somehow? Maybe by storing std::pair<Entry, bound> in the private vector, and only handing out pointers to the Entry component ?

That should work...although I'm not sure how that is any different to the range or data being public. If a user modifies anything then it has essentially invalidated the whole structure anyway.

[labath]

In D74759#1893485, @unnar wrote:

That should work...although I'm not sure how that is any different to the range or data being public. If a user modifies anything then it has essentially invalidated the whole structure anyway.

That is a fair point. I suppose the reason why I see this as different is because this field is an implementation detail of the RangeDataVector class, and so the user should not even see it -- whereas the user has a legitimate reason to at least access the other fields (and most of the methods only provide read-only access to these fields).

I'm sorry, I haven't gotten around to looking at this patch today, but I thought I'd at least say that...

[unnar]

In D74759#1895748, @labath wrote:

In D74759#1893485, @unnar wrote:

That should work...although I'm not sure how that is any different to the range or data being public. If a user modifies anything then it has essentially invalidated the whole structure anyway.

That is a fair point. I suppose the reason why I see this as different is because this field is an implementation detail of the RangeDataVector class, and so the user should not even see it -- whereas the user has a legitimate reason to at least access the other fields (and most of the methods only provide read-only access to these fields).

I'm sorry, I haven't gotten around to looking at this patch today, but I thought I'd at least say that...

That is true. I am fine with changing it if that's the only thing that you see as blocking this change from passing.

[labath]

In D74759#1896100, @unnar wrote:

In D74759#1895748, @labath wrote:

That is a fair point. I suppose the reason why I see this as different is because this field is an implementation detail of the RangeDataVector class, and so the user should not even see it -- whereas the user has a legitimate reason to at least access the other fields (and most of the methods only provide read-only access to these fields).

I'm sorry, I haven't gotten around to looking at this patch today, but I thought I'd at least say that...

That is true. I am fine with changing it if that's the only thing that you see as blocking this change from passing.

I finally took a good look at the patch, and I think that is the only remaining question on my mind. Could you try implementing that to see how it looks like?

@teemperor, do you have any more thoughts on this?

lldb/include/lldb/Utility/RangeMap.h

615

Llvm style guide does not recommend using auto in this situation. Entry &entry is one character longer, but it makes it clear what is going on.

635

const Entry & -- http://llvm.org/docs/CodingStandards.html#beware-unnecessary-copies-with-auto

[unnar]

As discussed with @labath I made a separate struct called AugmentedEntry that is used internally but we only ever expose the Entry part to the user.

[labath]

I think this is looking very good now. Just a few polishing comments.

lldb/include/lldb/Utility/RangeMap.h

397

Add a short comment about the purpose of this class. Maybe you could just move the comment from the function ComputeUpperBounds to here?

401–402

looking at the usage, it would be simpler if this constructor just took a const RangeData<B, S, T>& argument, and then initialized the base class using its copy constructor.

422–423

and then here you'd do m_entries.emplace_back(entry)

[unnar]

Thanks for the feedback! I addressed all of your comments in the latest patch.

[labath]

Awesome. Thanks for the patch. Do you need me to commit this for you?

[unnar]

Yes please. :)

lldb/include/lldb/Utility/RangeMap.h

struct RangeData : public Range<B, S> {
 
   RangeData() : Range<B, S>(), data() {}
 
   RangeData(B base, S size) : Range<B, S>(base, size), data() {}
 
   RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
 };
 
+// We can treat the vector as a flattened Binary Search Tree, augmenting it
+// with upper bounds (max of range endpoints) for every index allows us to
+// query for range containment quicker.
+template <typename B, typename S, typename T>
+struct AugmentedRangeData : public RangeData<B, S, T> {
+  B upper_bound;
+
+  AugmentedRangeData(const RangeData<B, S, T> &rd)
+      : RangeData<B, S, T>(rd), upper_bound() {}
+};
+
 template <typename B, typename S, typename T, unsigned N = 0,
           class Compare = std::less<T>>
 class RangeDataVector {
 public:
   typedef lldb_private::Range<B, S> Range;
   typedef RangeData<B, S, T> Entry;
-  typedef llvm::SmallVector<Entry, N> Collection;
+  typedef AugmentedRangeData<B, S, T> AugmentedEntry;
+  typedef llvm::SmallVector<AugmentedEntry, N> Collection;
 
   RangeDataVector(Compare compare = Compare()) : m_compare(compare) {}
 
   ~RangeDataVector() = default;
 
-  void Append(const Entry &entry) { m_entries.push_back(entry); }
+  void Append(const Entry &entry) { m_entries.emplace_back(entry); }
 
   void Sort() {
     if (m_entries.size() > 1)
       std::stable_sort(m_entries.begin(), m_entries.end(),
                        [&compare = m_compare](const Entry &a, const Entry &b) {
                          if (a.base != b.base)
                            return a.base < b.base;
                          if (a.size != b.size)
                            return a.size < b.size;
                          return compare(a.data, b.data);
                        });
+    if (!m_entries.empty())
+      ComputeUpperBounds(0, m_entries.size());
   }
 
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
   bool IsSorted() const {
     typename Collection::const_iterator pos, end, prev;
-    // First we determine if we can combine any of the Entry objects so we
-    // don't end up allocating and making a new collection for no reason
     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
          prev = pos++) {
       if (prev != end && *pos < *prev)
         return false;
     }
     return true;
   }
 #endif
 
   void CombineConsecutiveEntriesWithEqualData() {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
     typename Collection::iterator pos;
#endif
   Entry &GetEntryRef(size_t i) { return m_entries[i]; }
   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 
   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
     return lhs.GetRangeBase() < rhs.GetRangeBase();
   }
 
   uint32_t FindEntryIndexThatContains(B addr) const {
-    const Entry *entry = FindEntryThatContains(addr);
+    const AugmentedEntry *entry =
+        static_cast<const AugmentedEntry *>(FindEntryThatContains(addr));
     if (entry)
       return std::distance(m_entries.begin(), entry);
     return UINT32_MAX;
   }
 
-  uint32_t FindEntryIndexesThatContain(B addr,
-                                       std::vector<uint32_t> &indexes) const {
+  uint32_t FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
-    // 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;
-    }
+    if (!m_entries.empty())
+      FindEntryIndexesThatContain(addr, 0, m_entries.size(), indexes);
+
     return indexes.size();
   }
 
   Entry *FindEntryThatContains(B addr) {
     return const_cast<Entry *>(
         static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
             addr));
   }
 
   const Entry *FindEntryThatContains(B addr) const {
     return FindEntryThatContains(Entry(addr, 1));
   }
 
#endif
 
   const Entry *Back() const {
     return (m_entries.empty() ? nullptr : &m_entries.back());
   }
 
 protected:
   Collection m_entries;
   Compare m_compare;
+
+private:
+  // Compute extra information needed for search
+  B ComputeUpperBounds(size_t lo, size_t hi) {
+    size_t mid = (lo + hi) / 2;
+    AugmentedEntry &entry = m_entries[mid];
+
+    entry.upper_bound = entry.base + entry.size;
+
+    if (lo < mid)
+      entry.upper_bound =
+          std::max(entry.upper_bound, ComputeUpperBounds(lo, mid));
+
+    if (mid + 1 < hi)
+      entry.upper_bound =
+          std::max(entry.upper_bound, ComputeUpperBounds(mid + 1, hi));
+
+    return entry.upper_bound;
+  }
+
+  // This is based on the augmented tree implementation found at
+  // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
+  void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi,
+                                   std::vector<uint32_t> &indexes) {
+    size_t mid = (lo + hi) / 2;
+    const AugmentedEntry &entry = m_entries[mid];
+
+    // addr is greater than the rightmost point of any interval below mid
+    // so there are cannot be any matches.
+    if (addr > entry.upper_bound)
+      return;
+
+    // Recursively search left subtree
+    if (lo < mid)
+      FindEntryIndexesThatContain(addr, lo, mid, indexes);
+
+    // If addr is smaller than the start of the current interval it
+    // cannot contain it nor can any of its right subtree.
+    if (addr < entry.base)
+      return;
+
+    if (entry.Contains(addr))
+      indexes.push_back(entry.data);
+
+    // Recursively search right subtree
+    if (mid + 1 < hi)
+      FindEntryIndexesThatContain(addr, mid + 1, hi, indexes);
+  }
 };
 
 // A simple range  with data class where you get to define the type of
 // the range base "B", the type used for the range byte size "S", and the type
 // for the associated data "T".
 template <typename B, typename T> struct AddressData {
   typedef B BaseType;
   typedef T DataType;