[clangd] Improve clangd-indexer performance

[ArcsinX]

Summary

This is a try to improve clangd-indexer tool performance:

• avoid processing already processed files.
• use different mutexes for different entities (e.g. do not block insertion of references while symbols are inserted)

Results for LLVM project indexing:

• before: ~30 minutes
• after: ~10 minutes

[kadircet]

clang-tools-extra/clangd/indexer/IndexerMain.cpp

46

this changes the behavior of clangd-indexer slightly. it feels like an okay-ish trade-off considering the 3x speed up, but might have dire consequences.

Without this change, clangd-indexer can index headers in multiple configurations, e.g. if you have src1.cc that includes a.h with a -DFOO and src2.cc that includes a.h with -DBAR, a.h might end up producing different symbols. All of them are being indexed at the moment. After this change, the first one to index will win.

This is also what we do with background-index but we have different requirements for this behavior, as we store only a single shard per source file, even if we indexed sources in different configurations only one of them would prevail (unless we postpone shard writing to end of indexing and accumulate results in memory).

Also we are planning to make use of this binary in a server-like setup, and use the produced index to serve multiple clients. In some situations keeping symbols from multiple configurations might be really useful, but I am not so sure about it as they'll still be collapsed if USR generation produces same IDs for those symbols (and I think it will). So I am leaning towards making this change, but I would like to hear what others think too.

[hokein]

clang-tools-extra/clangd/indexer/IndexerMain.cpp

46

+1, this looks like a good trade-off to me.

[sammccall]

This seems like an accuracy/latency tradeoff in an environment where... it's not clear why we care about latency very much. Do we?

OTOH, how useful is it to have a static index that's more accurate if it's going to be shadowed by a dynamic index for the files you care most about.

[ArcsinX]

Thank you all for your comments.

I will try to describe my thoughts:

• the more data SymbolCollector will collect, the greater the difference (N will increase in this patch improves performance in N times). E.g. collection call/contain relations will affect clangd-indexer performance significantly while clangd background indexer will not have such huge affection.
• performance improvement will help to update the index file more often (for remote server scenario). I mean an index file will be up to date every K commits instead of every 3 x K commits (assume constant time difference between commits)
• the behavior with this patch is basically the same as clangd background indexer behavior.

If this patch could not be approved as is, then maybe we could add command line option to switch old/new behavior. What do you think? (Сan't think of a suitable name for this option =))

[kadircet]

Looks like everyone thinks that this sounds reasonable. So LGTM. Thanks for the patch!

[ArcsinX]

Don't check that AbsPath is not in Files twice.

clang-tools-extra/clangd/indexer/IndexerMain.cpp

 
 class IndexActionFactory : public tooling::FrontendActionFactory {
 public:
   IndexActionFactory(IndexFileIn &Result) : Result(Result) {}
 
   std::unique_ptr<FrontendAction> create() override {
     SymbolCollector::Options Opts;
     Opts.CountReferences = true;
+    Opts.FileFilter = [&](const SourceManager &SM, FileID FID) {
+      const auto *F = SM.getFileEntryForID(FID);
+      if (!F)
+        return false; // Skip invalid files.
+      auto AbsPath = getCanonicalPath(F, SM);
+      if (!AbsPath)
+        return false; // Skip files without absolute path.
+      std::lock_guard<std::mutex> Lock(FilesMu);
+      return Files.insert(*AbsPath).second; // Skip already processed files.
+    };
     return createStaticIndexingAction(
         Opts,
         [&](SymbolSlab S) {
           // Merge as we go.
           std::lock_guard<std::mutex> Lock(SymbolsMu);
           for (const auto &Sym : S) {
             if (const auto *Existing = Symbols.find(Sym.ID))
               Symbols.insert(mergeSymbol(*Existing, Sym));
             else
               Symbols.insert(Sym);
           }
         },
         [&](RefSlab S) {
-          std::lock_guard<std::mutex> Lock(SymbolsMu);
+          std::lock_guard<std::mutex> Lock(RefsMu);
           for (const auto &Sym : S) {
             // Deduplication happens during insertion.
             for (const auto &Ref : Sym.second)
               Refs.insert(Sym.first, Ref);
           }
         },
         [&](RelationSlab S) {
-          std::lock_guard<std::mutex> Lock(SymbolsMu);
+          std::lock_guard<std::mutex> Lock(RelsMu);
           for (const auto &R : S) {
             Relations.insert(R);
           }
         },
         /*IncludeGraphCallback=*/nullptr);
   }
 
   // Awkward: we write the result in the destructor, because the executor
   // takes ownership so it's the easiest way to get our data back out.
   ~IndexActionFactory() {
     Result.Symbols = std::move(Symbols).build();
     Result.Refs = std::move(Refs).build();
     Result.Relations = std::move(Relations).build();
   }
 
 private:
   IndexFileIn &Result;
+  std::mutex FilesMu;
+  llvm::StringSet<> Files;
   std::mutex SymbolsMu;
   SymbolSlab::Builder Symbols;
+  std::mutex RefsMu;
   RefSlab::Builder Refs;
+  std::mutex RelsMu;
   RelationSlab::Builder Relations;
 };
 
 } // namespace
 } // namespace clangd
 } // namespace clang
 
 int main(int argc, const char **argv) {