labath added a comment. In D74759#1880559 <https://reviews.llvm.org/D74759#1880559>, @jarin wrote:
> 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). 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. 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
