[clangd] BackgroundIndex rebuilds symbol index periodically.

[ioeric]

Summary

Currently, background index rebuilds symbol index on every indexed file,
which can be inefficient. This patch makes it only rebuild symbol index periodically.
As the rebuild no longer happens too often, we could also build more efficient
dex index.

[kadircet]

clangd/index/Background.cpp

464

why not simply check if BuildIndexPeriodMs has passed and issue rebuild here? That way we won't spawn an additional thread, and get rid of the CV

[dblaikie]

(from the peanut gallery): Usually what I'd expect here is "reindexing will occur X milliseconds after a write, covering anything written up until that point" - so it doesn't reindex unnecessarily if the files are unmodified/sitting idle, and it doesn't thrash reindexing for multiple changes in rapid succession (such as hitting the "save all" button in some text editor - or having made a few other quick changes one after another maybe), but still provides reasonable up-to-date data for the user.

(but I don't know anything about clangd & maybe what I'm saying makes no sense/isn't relevant)

[ioeric]

In D55770#1333271, @dblaikie wrote:

(from the peanut gallery): Usually what I'd expect here is "reindexing will occur X milliseconds after a write, covering anything written up until that point" - so it doesn't reindex unnecessarily if the files are unmodified/sitting idle, and it doesn't thrash reindexing for multiple changes in rapid succession (such as hitting the "save all" button in some text editor - or having made a few other quick changes one after another maybe), but still provides reasonable up-to-date data for the user.

(but I don't know anything about clangd & maybe what I'm saying makes no sense/isn't relevant)

Thanks for the input David.

The term indexing in clangd is getting bit overloaded :( There are two kinds of "indexing " happening in the background index: 1) parse and collect symbols from the TU and 2) build a symbol index (e.g. for fast fuzzy search. this is the real index!) for the symbols. (1) happens in a manner similar to what you described (e.g. we don't reindex files with the same hash). This patch addresses (2). As there can be multiple threads collecting symbols concurrently, it's not ideal to rebuild the symbol index (data structure) for each index action; thus, we are making the index rebuild only run periodically.

Happen to chat more and provide more details if you are interested.

clangd/index/Background.cpp

464

As chatted offline, the main problem is that the last index action might trigger an index update if it finishes shortly after an index rebuild; there is not trivial way for a index worker to figure out that it's the last run. Also the testing seems to be harder with this approach.

[kadircet]

clangd/index/Background.h

112

We already have a mutex and cv, maybe get rid of this one signal the CV whenever we have an update and sleep for buildindexperiodms before issuing the re-build?

[ioeric]

clangd/index/Background.h

112

IndexCV serves two purposes: 1) get notified when ShouldStop is set and 2) timeout after BuildIndexPeriodMs. We wouldn't want to sleep here because it can take too long to shutdown clangd if BuildIndexPeriodMs is big.

[kadircet]

clangd/index/Background.cpp

352

Is double checking really necessary? I suppose it is for the case that we miss the notification, if that's the case maybe put a comment?

clangd/index/Background.h

112

by sleep I still meant IndexCV.wait_for

[kadircet]

clangd/index/Background.h

112

well actually I believe we should use wait_until rathert than wait_for, since we don't wanna stop waiting if we weren't stopped.

[kadircet]

LGTM, thanks!

clangd/index/Background.h

112

As discussed offline, even with wait_until we still need the boolean flag to check if anything was updated.

[ioeric]

• Add comment about double-check of ShouldStop.

clangd/ClangdServer.h

struct Options {
     /// opened files and uses the index to augment code completion results.
     bool BuildDynamicSymbolIndex = false;
     /// Use a heavier and faster in-memory index implementation.
     /// FIXME: we should make this true if it isn't too slow to build!.
     bool HeavyweightDynamicSymbolIndex = false;
     /// If true, ClangdServer automatically indexes files in the current project
     /// on background threads. The index is stored in the project root.
     bool BackgroundIndex = false;
+    /// If set to non-zero, the background index rebuilds the symbol index
+    /// periodically every BuildIndexPeriodMs milliseconds; otherwise, the
+    /// symbol index will be updated for each indexed file.
+    size_t BackgroundIndexRebuildPeriodMs = 0;
 
     /// If set, use this index to augment code completion results.
     SymbolIndex *StaticIndex = nullptr;
 
     /// Clangd's workspace root. Relevant for "workspace" operations not bound
     /// to a particular file.
     /// FIXME: If not set, should use the current working directory.
     llvm::Optional<std::string> WorkspaceRoot;

clangd/ClangdServer.cpp

if (this->Index != nullptr) {
       this->Index = Idx;
     }
   };
   if (Opts.StaticIndex)
     AddIndex(Opts.StaticIndex);
   if (Opts.BackgroundIndex) {
     BackgroundIdx = llvm::make_unique<BackgroundIndex>(
         Context::current().clone(), ResourceDir, FSProvider, CDB,
-        BackgroundIndexStorage::createDiskBackedStorageFactory());
+        BackgroundIndexStorage::createDiskBackedStorageFactory(),
+        Opts.BackgroundIndexRebuildPeriodMs);
     AddIndex(BackgroundIdx.get());
   }
   if (DynamicIdx)
     AddIndex(DynamicIdx.get());
 }
 
 void ClangdServer::addDocument(PathRef File, StringRef Contents,
                                WantDiagnostics WantDiags) {

clangd/index/Background.h

 #include "Threading.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/Serialization.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/Threading.h"
+#include <atomic>
 #include <condition_variable>
 #include <deque>
+#include <mutex>
 #include <string>
 #include <thread>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 // Handles storage and retrieval of index shards. Both store and load

 };
 
 // Builds an in-memory index by by running the static indexer action over
 // all commands in a compilation database. Indexing happens in the background.
 // FIXME: it should also persist its state on disk for fast start.
 // FIXME: it should watch for changes to files on disk.
 class BackgroundIndex : public SwapIndex {
 public:
+  /// If BuildIndexPeriodMs is greater than 0, the symbol index will only be
+  /// rebuilt periodically (one per \p BuildIndexPeriodMs); otherwise, index is
+  /// rebuilt for each indexed file.
   // FIXME: resource-dir injection should be hoisted somewhere common.
   BackgroundIndex(Context BackgroundContext, llvm::StringRef ResourceDir,
                   const FileSystemProvider &,
                   const GlobalCompilationDatabase &CDB,
                   BackgroundIndexStorage::Factory IndexStorageFactory,
+                  size_t BuildIndexPeriodMs = 0,
                   size_t ThreadPoolSize = llvm::hardware_concurrency());
   ~BackgroundIndex(); // Blocks while the current task finishes.
 
   // Enqueue translation units for indexing.
   // The indexing happens in a background thread, so the symbols will be
   // available sometime later.
   void enqueue(const std::vector<std::string> &ChangedFiles);
   void enqueue(const std::string &File);
private:
   std::string ResourceDir;
   const FileSystemProvider &FSProvider;
   const GlobalCompilationDatabase &CDB;
   Context BackgroundContext;
 
   // index state
   llvm::Error index(tooling::CompileCommand,
                     BackgroundIndexStorage *IndexStorage);
+  void buildIndex(); // Rebuild index periodically every BuildIndexPeriodMs.
+  const size_t BuildIndexPeriodMs;
+  std::atomic<bool> SymbolsUpdatedSinceLastIndex;
+  std::mutex IndexMu;
+  std::condition_variable IndexCV;
 
   FileSymbols IndexedSymbols;
   llvm::StringMap<FileDigest> IndexedFileDigests; // Key is absolute file path.
   std::mutex DigestsMu;
 
   BackgroundIndexStorage::Factory IndexStorageFactory;
 
   // queue management

clangd/index/Background.cpp

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/SHA1.h"
 
+#include <chrono>
 #include <memory>
 #include <numeric>
 #include <queue>
 #include <random>
 #include <string>
+#include <thread>
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 namespace {
 // Resolves URI to file paths with cache.
 class URIToFileCache {
 public:
createFileFilter(const llvm::StringMap<FileDigest> &FileDigests,
   };
 }
 
 } // namespace
 
 BackgroundIndex::BackgroundIndex(
     Context BackgroundContext, StringRef ResourceDir,
     const FileSystemProvider &FSProvider, const GlobalCompilationDatabase &CDB,
-    BackgroundIndexStorage::Factory IndexStorageFactory, size_t ThreadPoolSize)
+    BackgroundIndexStorage::Factory IndexStorageFactory,
+    size_t BuildIndexPeriodMs, size_t ThreadPoolSize)
     : SwapIndex(make_unique<MemIndex>()), ResourceDir(ResourceDir),
       FSProvider(FSProvider), CDB(CDB),
       BackgroundContext(std::move(BackgroundContext)),
+      BuildIndexPeriodMs(BuildIndexPeriodMs),
+      SymbolsUpdatedSinceLastIndex(false),
       IndexStorageFactory(std::move(IndexStorageFactory)),
       CommandsChanged(
           CDB.watch([&](const std::vector<std::string> &ChangedFiles) {
             enqueue(ChangedFiles);
           })) {
   assert(ThreadPoolSize > 0 && "Thread pool size can't be zero.");
   assert(this->IndexStorageFactory && "Storage factory can not be null!");
   while (ThreadPoolSize--)
     ThreadPool.emplace_back([this] { run(); });
+  if (BuildIndexPeriodMs > 0) {
+    log("BackgroundIndex: build symbol index periodically every {0} ms.",
+        BuildIndexPeriodMs);
+    ThreadPool.emplace_back([this] { buildIndex(); });
+  }
 }
 
 BackgroundIndex::~BackgroundIndex() {
   stop();
   for (auto &Thread : ThreadPool)
     Thread.join();
 }
 
 void BackgroundIndex::stop() {
   {
-    std::lock_guard<std::mutex> Lock(QueueMu);
+    std::lock_guard<std::mutex> QueueLock(QueueMu);
+    std::lock_guard<std::mutex> IndexLock(IndexMu);
     ShouldStop = true;
   }
   QueueCV.notify_all();
+  IndexCV.notify_all();
 }
 
 void BackgroundIndex::run() {
   WithContext Background(BackgroundContext.clone());
   while (true) {
     Optional<Task> Task;
     ThreadPriority Priority;
     {
for (const auto &F : Files) {
     // This can override a newer version that is added in another thread,
     // if this thread sees the older version but finishes later. This should be
     // rare in practice.
     IndexedFileDigests[Path] = Hash;
     IndexedSymbols.update(Path, std::move(SS), std::move(RS));
   }
 }
 
+void BackgroundIndex::buildIndex() {
+  assert(BuildIndexPeriodMs > 0);
+  while (true) {
+    {
+      std::unique_lock<std::mutex> Lock(IndexMu);
+      if (ShouldStop)
+        break;
+      // Wait until this is notified to stop or `BuildIndexPeriodMs` has past.
+      IndexCV.wait_for(Lock, std::chrono::milliseconds(BuildIndexPeriodMs));
+      if (ShouldStop)
+        break;
+    }
+    if (!SymbolsUpdatedSinceLastIndex.exchange(false))
+      continue;
+    // There can be symbol update right after the flag is reset above and before
+    // index is rebuilt below. The new index would contain the updated symbols
+    // but the flag would still be true. This is fine as we would simply run an
+    // extra index build.
+    reset(
+        IndexedSymbols.buildIndex(IndexType::Heavy, DuplicateHandling::Merge));
+    log("BackgroundIndex: rebuilt symbol index.");
+  }
+}
+
 Error BackgroundIndex::index(tooling::CompileCommand Cmd,
                              BackgroundIndexStorage *IndexStorage) {
   trace::Span Tracer("BackgroundIndex");
   SPAN_ATTACH(Tracer, "file", Cmd.Filename);
   SmallString<128> AbsolutePath;
   if (sys::path::is_absolute(Cmd.Filename)) {
     AbsolutePath = Cmd.Filename;
   } else {
llvm::StringMap<FileDigest> DigestsSnapshot;
     if (IndexedFileDigests.lookup(AbsolutePath) == Hash) {
       vlog("No need to index {0}, already up to date", AbsolutePath);
       return Error::success();
     }
 
     DigestsSnapshot = IndexedFileDigests;
   }
 
-  log("Indexing {0}", Cmd.Filename, toHex(Hash));
+  log("Indexing {0} (digest:={1})", Cmd.Filename, toHex(Hash));
   ParseInputs Inputs;
   Inputs.FS = std::move(FS);
   Inputs.FS->setCurrentWorkingDirectory(Cmd.Directory);
   Inputs.CompileCommand = std::move(Cmd);
   auto CI = buildCompilerInvocation(Inputs);
   if (!CI)
     return createStringError(inconvertibleErrorCode(),
                              "Couldn't build compiler invocation");
Error BackgroundIndex::index(tooling::CompileCommand Cmd,
   update(AbsolutePath, std::move(Index), FilesToUpdate, IndexStorage);
   {
     // Make sure hash for the main file is always updated even if there is no
     // index data in it.
     std::lock_guard<std::mutex> Lock(DigestsMu);
     IndexedFileDigests[AbsolutePath] = Hash;
   }
 
-  // FIXME: this should rebuild once-in-a-while, not after every file.
-  //       At that point we should use Dex, too.
-  vlog("Rebuilding automatic index");
-  reset(IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
+  if (BuildIndexPeriodMs > 0)
+    SymbolsUpdatedSinceLastIndex = true;
+  else
+    reset(
+        IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
 
   return Error::success();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/tool/ClangdMain.cpp

static cl::opt<Path> IndexFile(
     cl::init(""), cl::Hidden);
 
 static cl::opt<bool> EnableBackgroundIndex(
     "background-index",
     cl::desc("Index project code in the background and persist index on disk. "
              "Experimental"),
     cl::init(false), cl::Hidden);
 
+static cl::opt<int> BackgroundIndexRebuildPeriod(
+    "background-index-rebuild-period",
+    cl::desc(
+        "If set to non-zero, the background index rebuilds the symbol index "
+        "periodically every X milliseconds; otherwise, the "
+        "symbol index will be updated for each indexed file."),
+    cl::init(5000), cl::Hidden);
+
 enum CompileArgsFrom { LSPCompileArgs, FilesystemCompileArgs };
 static cl::opt<CompileArgsFrom> CompileArgsFrom(
     "compile_args_from", cl::desc("The source of compile commands"),
     cl::values(clEnumValN(LSPCompileArgs, "lsp",
                           "All compile commands come from LSP and "
                           "'compile_commands.json' files are ignored"),
                clEnumValN(FilesystemCompileArgs, "filesystem",
                           "All compile commands come from the "
case PCHStorageFlag::Disk:
     Opts.StorePreamblesInMemory = false;
     break;
   }
   if (!ResourceDir.empty())
     Opts.ResourceDir = ResourceDir;
   Opts.BuildDynamicSymbolIndex = EnableIndex;
   Opts.HeavyweightDynamicSymbolIndex = UseDex;
   Opts.BackgroundIndex = EnableBackgroundIndex;
+  Opts.BackgroundIndexRebuildPeriodMs = BackgroundIndexRebuildPeriod;
   std::unique_ptr<SymbolIndex> StaticIdx;
   std::future<void> AsyncIndexLoad; // Block exit while loading the index.
   if (EnableIndex && !IndexFile.empty()) {
     // Load the index asynchronously. Meanwhile SwapIndex returns no results.
     SwapIndex *Placeholder;
     StaticIdx.reset(Placeholder = new SwapIndex(llvm::make_unique<MemIndex>()));
     AsyncIndexLoad = runAsync<void>([Placeholder] {
       if (auto Idx = loadIndex(IndexFile, /*UseDex=*/true))

test/clangd/background-index.test

 # We need to splice paths into file:// URIs for this test.
 # UNSUPPORTED: win32
 
 # Use a copy of inputs, as we'll mutate it (as will the background index).
 # RUN: rm -rf %t
 # RUN: cp -r %S/Inputs/background-index %t
 # Need to embed the correct temp path in the actual JSON-RPC requests.
 # RUN: sed -i -e "s|DIRECTORY|%t|" %t/*
 
 # We're editing bar.cpp, which includes foo.h.
 # foo() is declared in foo.h and defined in foo.cpp.
 # The background index should allow us to go-to-definition on foo().
-# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc
+# RUN: clangd -background-index -background-index-rebuild-period=0 -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc
 
 # Test that the index is writing files in the expected location.
 # RUN: ls %t/.clangd-index/foo.cpp.*.idx
 
 # Test the index is read from disk: delete code and restart clangd.
 # FIXME: This test currently fails as we don't read the index yet.
 # RUN: rm %t/foo.cpp
 # RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | not FileCheck %t/definition.jsonrpc

unittests/clangd/BackgroundIndexTests.cpp

 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "index/Background.h"
 #include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/Threading.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <thread>
 
 using testing::_;
 using testing::AllOf;
+using testing::ElementsAre;
 using testing::Not;
 using testing::UnorderedElementsAre;
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
EXPECT_THAT(
       ShardHeader->Sources->lookup("unittest:///root/A.h").DirectIncludes,
       UnorderedElementsAre("unittest:///root/B.h"));
   EXPECT_NE(ShardHeader->Sources->lookup("unittest:///root/A.h").Digest,
             FileDigest{{0}});
   EXPECT_THAT(ShardHeader->Sources->lookup("unittest:///root/B.h"),
               EmptyIncludeNode());
 }
 
+TEST_F(BackgroundIndexTest, PeriodicalIndex) {
+  MockFSProvider FS;
+  llvm::StringMap<std::string> Storage;
+  size_t CacheHits = 0;
+  MemoryShardStorage MSS(Storage, CacheHits);
+  OverlayCDB CDB(/*Base=*/nullptr);
+  BackgroundIndex Idx(
+      Context::empty(), "", FS, CDB, [&](llvm::StringRef) { return &MSS; },
+      /*BuildIndexPeriodMs=*/10);
+
+  FS.Files[testPath("root/A.cc")] = "#include \"A.h\"";
+
+  tooling::CompileCommand Cmd;
+  FS.Files[testPath("root/A.h")] = "class X {};";
+  Cmd.Filename = testPath("root/A.cc");
+  Cmd.CommandLine = {"clang++", Cmd.Filename};
+  CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
+
+  ASSERT_TRUE(Idx.blockUntilIdleForTest());
+  EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre());
+  std::this_thread::sleep_for(std::chrono::milliseconds(15));
+  EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("X")));
+
+  FS.Files[testPath("root/A.h")] = "class Y {};";
+  FS.Files[testPath("root/A.cc")] += " "; // Force reindex the file.
+  Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")};
+  CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
+
+  ASSERT_TRUE(Idx.blockUntilIdleForTest());
+  EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("X")));
+  std::this_thread::sleep_for(std::chrono::milliseconds(15));
+  EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("Y")));
+}
+
 } // namespace clangd
 } // namespace clang