[clangd] Load YAML static index asynchronously.

[ioeric]

Summary

Loading static index can be slow (>10s for LLVM index). This allows
the clangd server to be initialized before index is loaded.

[ioeric]

• revert unintended change

[ilya-biryukov]

clangd/tool/ClangdMain.cpp

103

I believe is a data race (multiple threads may run this line concurrently).
You would want some synchronization around this, std::shared_future could be a good fit

[ilya-biryukov]

Any reason to not just wait for the index to load? Is this a UX concern or a problem when experimenting?

[ioeric]

• Fix data race.

[ioeric]

In D51475#1219133, @ilya-biryukov wrote:

Any reason to not just wait for the index to load? Is this a UX concern or a problem when experimenting?

The index loading can be slow. When using LLVM YAML index, I need to wait for >10s before clangd starts giving me anything useful. We could potentially speed up loading (e.g. replacing yaml), but the index can be arbitrary large. I think it's an improvement in general to be able to get clangd running before index is loaded.

clangd/tool/ClangdMain.cpp

103

Nice catch.

I am a bit hesitated about using shared_future though. It could potentially get rid of the mutex but would require much more careful use. For example, Index can be set to the same value repeatedly, which makes me a bit nervous.

[ilya-biryukov]

In D51475#1219184, @ioeric wrote:

The index loading can be slow. When using LLVM YAML index, I need to wait for >10s before clangd starts giving me anything useful. We could potentially speed up loading (e.g. replacing yaml), but the index can be arbitrary large. I think it's an improvement in general to be able to get clangd running before index is loaded.

I would trade-off those 10 seconds for giving consistent experience (i.e. avoiding confusing the users with different modes of completion (with and without index, etc.)).
But not terribly opposed to that.

clangd/tool/ClangdMain.cpp

103

The following pattern should give proper results:

class AsyncIndex : public Index {
public:
  AsyncIndex(std::shared_future<Index> IndexFut);
  //....
private;
  const SymbolIndex *index() const {
     if (IndexFut.wait(0) != ready)
       return nullptr;
     return &IndexFut.get();
  }

  std::shared_future<Index>IndexFut;
};


AsyncIndex AI(std::async([]() { /* load the index here */ return Index; });

[ioeric]

In D51475#1219197, @ilya-biryukov wrote:

In D51475#1219184, @ioeric wrote:

The index loading can be slow. When using LLVM YAML index, I need to wait for >10s before clangd starts giving me anything useful. We could potentially speed up loading (e.g. replacing yaml), but the index can be arbitrary large. I think it's an improvement in general to be able to get clangd running before index is loaded.

I would trade-off those 10 seconds for giving consistent experience (i.e. avoiding confusing the users with different modes of completion (with and without index, etc.)).
But not terribly opposed to that.

I think the inconsistency is benign and should be worth 10 seconds (which for me personally is loong...). Besides, this is just LLVM index; the loading could be arbitrary long depending on the corpus size.

clangd/tool/ClangdMain.cpp

103

My concern with this approach is that we are still calling wait even though it's not necessary once Index has been loaded.

[ilya-biryukov]

clangd/tool/ClangdMain.cpp

103

Maybe not bother before we know it causes actual performance issues? My bet is that it would never become a bottleneck, given the amount of work we're doing in addition to every call here.

[sammccall]

I don't have a strong opinion on async vs sync - startup time is important and we shouldn't block simple AST-based functionality on the index, but this introduces some slightly confusing UX for that speed.

However I think this should be based on D51422 which extracts most of what you need out of MemIndex into the new SwapIndex.
So static index would just be initialized as an empty SwapIndex, then spawn a thread that loads the YAML and calls SwapIndex::reset.
This will get avoid adding nontrivial threading stuff to the main file.

[sammccall]

(Sorry for catching this earlier, and that the patch isn't landed yet - feel free to pick up the review, else @kbobyrev will take a first pass tomorrow I think)

[ioeric]

clangd/tool/ClangdMain.cpp

103

Sure, the performance overhead is small in both cases. But I would still try to avoid wait e.g. OS can decide to yield even if the timeout is 0.

[ioeric]

In D51475#1219291, @sammccall wrote:

I don't have a strong opinion on async vs sync - startup time is important and we shouldn't block simple AST-based functionality on the index, but this introduces some slightly confusing UX for that speed.

However I think this should be based on D51422 which extracts most of what you need out of MemIndex into the new SwapIndex.
So static index would just be initialized as an empty SwapIndex, then spawn a thread that loads the YAML and calls SwapIndex::reset.
This will get avoid adding nontrivial threading stuff to the main file.

Oops, didn't realize that. That sounds great. Thanks!

[kbobyrev]

clangd/tool/ClangdMain.cpp

48

Also, do we want only static index to be built asynchronously? Do we want it to be used only in our Clangd tool driver? Loading dynamic index might also be useful if we have this kind of behavior for the static one. I'm not completely sure about that, though.

78

Shouldn't this index()->estimateMemoryUsage() when the index is built?

102

Do we want to be more explicit about loading index asynchronously? If we're not that fact might be implicit to the user (e.g. "my Clangd is not frozen, but global completion doesn't work"), CLI flag/documentation entry might solve that issue. Introducing tons of not-so-useful flags is not optimal, though, and I'm also not sure about that.

What do you think?

[ioeric]

Dropping this in favor of D51638

clangd/tool/ClangdMain.cpp

 //===--- ClangdMain.cpp - clangd server loop ------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
 #include "JSONRPCDispatcher.h"
 #include "Path.h"
 #include "Trace.h"
 #include "index/SymbolYAML.h"
 #include "index/dex/DexIndex.h"
 #include "clang/Basic/Version.h"
+#include "clang/Basic/Version.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <iostream>
 #include <memory>
+#include <mutex>
 #include <string>
 #include <thread>
 
 using namespace clang;
 using namespace clang::clangd;
 
 // FIXME: remove this option when Dex is stable enough.
 static llvm::cl::opt<bool>
     UseDex("use-dex-index",
            llvm::cl::desc("Use experimental Dex static index."),
            llvm::cl::init(true), llvm::cl::Hidden);
 
 namespace {
 
 enum class PCHStorageFlag { Disk, Memory };
 
-// Build an in-memory static index for global symbols from a YAML-format file.
-// The size of global symbols should be relatively small, so that all symbols
-// can be managed in memory.
+// Loads the index asynchornously. This acts like an empty index before
+// finishing loading and proxies index requests to the loaded index after
+// loading.
+class AsyncLoadIndex : public SymbolIndex {
+public:
+  AsyncLoadIndex(
+      llvm::unique_function<std::unique_ptr<SymbolIndex>()> LoadIndex)
+      : AsyncLoad(runAsync(std::move(LoadIndex))) {}
+
+  bool
+  fuzzyFind(const FuzzyFindRequest &Req,
+            llvm::function_ref<void(const Symbol &)> Callback) const override {
+    if (!index())
+      return false; // More
+    return index()->fuzzyFind(Req, Callback);
+  }
+
+  void
+  lookup(const LookupRequest &Req,
+         llvm::function_ref<void(const Symbol &)> Callback) const override {
+    if (!index())
+      return;
+    return index()->lookup(Req, Callback);
+  }
+
+  void findOccurrences(const OccurrencesRequest &Req,
+                       llvm::function_ref<void(const SymbolOccurrence &)>
+                           Callback) const override {
+    if (!index())
+      return;
+    return index()->findOccurrences(Req, Callback);
+  }
+
+  size_t estimateMemoryUsage() const override { return 0; }
+
+private:
+  const SymbolIndex *index() const {
+    if (Index) // Index doesn't change once initialized, so no need for mutex.
+      return Index.get();
+
+    std::lock_guard<std::mutex> Lock(Mutex);
+    if (Index) // Make sure Index has not been set by the last mutex owner.
+      return Index.get();
+    if (AsyncLoad.wait_for(std::chrono::seconds(0)) !=
+        std::future_status::ready)
+      return nullptr;
+
+    Index = AsyncLoad.get();
+    return Index.get();
+  }
+  mutable std::unique_ptr<SymbolIndex> Index;
+  mutable std::future<std::unique_ptr<SymbolIndex>> AsyncLoad;
+  mutable std::mutex Mutex;
+};
+// Asynchronously build an in-memory static index for global symbols from a
+// YAML-format file. The size of global symbols should be relatively small, so
+// that all symbols can be managed in memory.
 std::unique_ptr<SymbolIndex> buildStaticIndex(llvm::StringRef YamlSymbolFile) {
+  return llvm::make_unique<AsyncLoadIndex>(
+      [YamlSymbolFile]() -> std::unique_ptr<SymbolIndex> {
+        trace::Span Tracer("Build static index");
+
         auto Buffer = llvm::MemoryBuffer::getFile(YamlSymbolFile);
         if (!Buffer) {
           llvm::errs() << "Can't open " << YamlSymbolFile << "\n";
           return nullptr;
         }
-  auto Slab = symbolsFromYAML(Buffer.get()->getBuffer());
+
         SymbolSlab::Builder SymsBuilder;
+        {
+          trace::Span Tracer("YAML to symbols");
+          auto Slab = symbolsFromYAML(Buffer.get()->getBuffer());
           for (auto Sym : Slab)
             SymsBuilder.insert(Sym);
+        }
 
+        trace::Span Build("Build index");
         return UseDex ? dex::DexIndex::build(std::move(SymsBuilder).build())
                       : MemIndex::build(std::move(SymsBuilder).build());
+      });
 }
 
 } // namespace
 
 static llvm::cl::opt<Path> CompileCommandsDir(
     "compile-commands-dir",
     llvm::cl::desc("Specify a path to look for compile_commands.json. If path "
                    "is invalid, clangd will look in the current directory and "