jarin added a comment. In D74759#1880499 <https://reviews.llvm.org/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. Repository: rLLDB LLDB CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
