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

[kbobyrev]

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.

[ilya-biryukov]

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]

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]

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

[ilya-biryukov]

Great improvement for such a simple change!

[kbobyrev]

Move assertion back to ctors.

clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp

 /// OrIterator iterates through all items which can be pointed to by at least
 /// one child. To preserve the sorted order, this iterator always advances the
 /// child with smallest Child->peek() value. OrIterator becomes exhausted as
 /// soon as all of its children are exhausted.
 class OrIterator : public Iterator {
 public:
   explicit OrIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
       : Children(std::move(AllChildren)) {
-    assert(Children.size() > 0 && "OR iterator must have at least one child.");
+    assert(!Children.empty() && "OR iterator should have at least one child.");
   }
 
   /// Returns true if all children are exhausted.
   bool reachedEnd() const override {
     return std::all_of(begin(Children), end(Children),
                        [](const std::unique_ptr<Iterator> &Child) {
                          return Child->reachedEnd();
                        });

 }
 
 std::unique_ptr<Iterator> create(PostingListRef Documents) {
   return llvm::make_unique<DocumentIterator>(Documents);
 }
 
 std::unique_ptr<Iterator>
 createAnd(std::vector<std::unique_ptr<Iterator>> Children) {
-  return llvm::make_unique<AndIterator>(move(Children));
+  // If there is exactly one child, pull it one level up: AND(Child) -> Child.
+  return Children.size() == 1 ? std::move(Children.front())
+                              : llvm::make_unique<AndIterator>(move(Children));
 }
 
 std::unique_ptr<Iterator>
 createOr(std::vector<std::unique_ptr<Iterator>> Children) {
-  return llvm::make_unique<OrIterator>(move(Children));
+  // If there is exactly one child, pull it one level up: OR(Child) -> Child.
+  return Children.size() == 1 ? std::move(Children.front())
+                              : llvm::make_unique<OrIterator>(move(Children));
 }
 
 std::unique_ptr<Iterator> createTrue(DocID Size) {
   return llvm::make_unique<TrueIterator>(Size);
 }
 
 std::unique_ptr<Iterator> createBoost(std::unique_ptr<Iterator> Child,
                                       float Factor) {