Page MenuHomePhabricator

[clangd] Don't create child AND and OR iterators with one posting list
ClosedPublic

Authored by kbobyrev on Sep 13 2018, 12:48 AM.

Details

Summary

AND( AND( Child ) ... ) -> AND( Child ... )
AND( OR( Child ) ... ) -> AND( Child ... )

This simple optimization results in 5-6% performance improvement in the benchmark with 2000 serialized FuzzyFindRequests.

Diff Detail

Repository
rL LLVM

Event Timeline

kbobyrev created this revision.Sep 13 2018, 12:48 AM
kbobyrev edited the summary of this revision. (Show Details)Sep 13 2018, 12:50 AM
ilya-biryukov added inline comments.Sep 13 2018, 1:17 AM
clang-tools-extra/clangd/index/dex/Dex.cpp
148 ↗(On Diff #165212)

Maybe special-case a single-iterator case in createAnd instead? Same with createOr.
Any cons to doing so?

kbobyrev updated this revision to Diff 165229.Sep 13 2018, 2:40 AM
kbobyrev marked an inline comment as done.
kbobyrev added inline comments.
clang-tools-extra/clangd/index/dex/Dex.cpp
148 ↗(On Diff #165212)

I thought that this might result in some implicit query tree generation semantics. However, since there optimizations are likely to be added at some point, I guess we could start being implicit right now, especially given that there is no good way for the user code to inspect the query tree structure (and there's no good reason to do so, too).

ilya-biryukov accepted this revision.Sep 13 2018, 2:57 AM

LGTM with a nit.

clang-tools-extra/clangd/index/dex/Dex.cpp
148 ↗(On Diff #165212)

As long as observable behaviour does not change (and this change does not seem to change it), we should be good.
Creating optimized trees on-the-fly will make sure we always get optimal results, which is nice.

clang-tools-extra/clangd/index/dex/Iterator.cpp
93 ↗(On Diff #165229)

Maybe keep the assertion here?
It's clear that createAnd is the only place that creates this class, so we can always trace the assertion back to its root-cause. Having the assertion in ctor guards against possible modifications of the code that would add more ways to construct AndIterator

Same for the assertion in OrIterator

This revision is now accepted and ready to land.Sep 13 2018, 2:57 AM

Great improvement for such a simple change!

kbobyrev updated this revision to Diff 165236.Sep 13 2018, 3:02 AM
kbobyrev marked an inline comment as done.

Move assertion back to ctors.

This revision was automatically updated to reflect the committed changes.