[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

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

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

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/clangd/index/dex/Dex.cpp

bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
   // Generate query trigrams and construct AND iterator over all query
   // trigrams.
   std::vector<std::unique_ptr<Iterator>> TrigramIterators;
   for (const auto &Trigram : TrigramTokens) {
     const auto It = InvertedIndex.find(Trigram);
     if (It != InvertedIndex.end())
       TrigramIterators.push_back(create(It->second));
   }
-  if (!TrigramIterators.empty())
+  if (TrigramIterators.size() > 1)
     TopLevelChildren.push_back(createAnd(move(TrigramIterators)));
+  else if (TrigramIterators.size() == 1)
+    TopLevelChildren.push_back(move(TrigramIterators.front()));
 
   // Generate scope tokens for search query.
   std::vector<std::unique_ptr<Iterator>> ScopeIterators;
   for (const auto &Scope : Req.Scopes) {
     const auto It = InvertedIndex.find(Token(Token::Kind::Scope, Scope));
     if (It != InvertedIndex.end())
       ScopeIterators.push_back(create(It->second));
   }
   // Add OR iterator for scopes if there are any Scope Iterators.
-  if (!ScopeIterators.empty())
+  if (ScopeIterators.size() > 1)
     TopLevelChildren.push_back(createOr(move(ScopeIterators)));
+  else if (ScopeIterators.size() == 1)
+    TopLevelChildren.push_back(move(ScopeIterators.front()));
 
   // Add proximity paths boosting.
   auto BoostingIterators = createFileProximityIterators(
       Req.ProximityPaths, URISchemes, InvertedIndex);
   // Boosting iterators do not actually filter symbols. In order to preserve
   // the validity of resulting query, TRUE iterator should be added along
   // BOOSTs.
   if (!BoostingIterators.empty()) {