[clangd] Use TRUE iterator instead of complete posting list

[kbobyrev]

Summary

Stop using $$$ (empty) trigram and generating a posting list with all items. Since TRUE iterator is already implemented and correctly inserted when there are no real trigram posting lists, this is a valid transformation.

Benchmarks show that this simple change allows ~30% speedup on dataset of real completion queries.

Before

-------------------------------------------------------
Benchmark                Time           CPU Iterations
-------------------------------------------------------
DexAdHocQueries    5640321 ns    5640265 ns        120
DexRealQ         939835603 ns  939830296 ns          1

After

-------------------------------------------------------
Benchmark                Time           CPU Iterations
-------------------------------------------------------
DexAdHocQueries    3452014 ns    3451987 ns        203
DexRealQ         667455912 ns  667455750 ns          1

[ilya-biryukov]

LGTM

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

std::vector<Token> generateIdentifierTrigrams(llvm::StringRef Identifier) {
   }
 
   DenseSet<Token> UniqueTrigrams;
 
   auto add = [&](std::string Chars) {
     UniqueTrigrams.insert(Token(Token::Kind::Trigram, Chars));
   };
 
-  // FIXME(kbobyrev): Instead of producing empty trigram for each identifier,
-  // just use True Iterator on the query side when the query string is empty.
-  add({{END_MARKER, END_MARKER, END_MARKER}});
-
   if (TwoHeads.size() == 2)
     add({{TwoHeads.front(), TwoHeads.back(), END_MARKER}});
 
   if (!LowercaseIdentifier.empty())
     add({{LowercaseIdentifier.front(), END_MARKER, END_MARKER}});
 
   if (LowercaseIdentifier.size() >= 2)
     add({{LowercaseIdentifier[0], LowercaseIdentifier[1], END_MARKER}});