[clangd] Mechanism to make update debounce responsive to rebuild speed.

[sammccall]

Summary

Currently we delay AST rebuilds by 500ms after each edit, to wait for
further edits. This is a win if a rebuild takes 5s, and a loss if it
takes 50ms.

This patch sets debouncepolicy = clamp(min, ratio * rebuild_time, max).
However it sets min = max = 500ms so there's no policy change or actual
customizability - will do that in a separate patch.

See https://github.com/clangd/clangd/issues/275

[merge_guards_bot]

Unit tests: pass. 62406 tests passed, 0 failed and 839 were skipped.

clang-tidy: fail. clang-tidy found 0 errors and 1 warnings. 1 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[hokein]

looks good, a few nits.

clang-tools-extra/clangd/TUScheduler.cpp

249

nit: maybe move it after the Mutex declaration.

771

nit: update the stale comment.

clang-tools-extra/clangd/TUScheduler.h

66

nit: should be sounds like this is something we haven't done yet? maybe add FIXME?

72

nit: this comment in () seems to be more related to the DebouncePolicy, maybe move it around the class.

[thakis]

This seems to break tests: http://45.33.8.238/linux/9296/step_9.txt

[sammccall]

In D73873#1856880, @thakis wrote:

This seems to break tests: http://45.33.8.238/linux/9296/step_9.txt

Thanks, I've reverted to take a look. It's weird though:

• don't see this on any lab buildbots or locally
• the lit test stack traces are all in one specific codepath (in selectiontree) that's totally unrelated
• the unit test traces aren't symbolized, but if it's the same stack then they never even use TUScheduler

So possible i'm tickling something latent.

[thakis]

I agree it's a bit strange. The linux bot didn't recover after the revert either, so something's amiss.

My Win bot has been hanging since this landed and I just CRD'd in and it's hanging in check-clangd and there are tens of ClangdTests processes hanging around and doing nothing.

On the more official win bot, instead the link of ClangdTests has been failing since this landed, which on Windows is likely caused by the processes still hanging around (http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/14120/steps/stage%201%20check/logs/stdio). This is the first bad build: http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/14113/

[sammccall]

In D73873#1857042, @thakis wrote:

I agree it's a bit strange. The linux bot didn't recover after the revert either, so something's amiss.

My Win bot has been hanging since this landed and I just CRD'd in and it's hanging in check-clangd and there are tens of ClangdTests processes hanging around and doing nothing.

On the more official win bot, instead the link of ClangdTests has been failing since this landed, which on Windows is likely caused by the processes still hanging around (http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/14120/steps/stage%201%20check/logs/stdio). This is the first bad build: http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/14113/

Windows: the stacktrace in the first bad build is almost certainly the bug above.
The processes hanging around after a crash (on the main thread) is surprising. The crash is on the main thread, though there are others. Something I should look into.

Linux: (some of) the stacktraces seem very unrelated to this code, and a revert didn't fix them, but a clean rebuild did (thanks @thakis!).

Next step: wait for the gn linux bot to be back in a good state, reland with the double-unlock fixed.

clang-tools-extra/clangd/TUScheduler.cpp

528

Here's a double-unlock (thanks @kadircet)

clang-tools-extra/clangd/ClangdServer.h

struct Options {
 
     /// The resource directory is used to find internal headers, overriding
     /// defaults and -resource-dir compiler flag).
     /// If None, ClangdServer calls CompilerInvocation::GetResourcePath() to
     /// obtain the standard resource directory.
     llvm::Optional<std::string> ResourceDir = llvm::None;
 
     /// Time to wait after a new file version before computing diagnostics.
-    std::chrono::steady_clock::duration UpdateDebounce =
-        std::chrono::milliseconds(500);
+    DebouncePolicy UpdateDebounce =
+        DebouncePolicy::fixed(std::chrono::milliseconds(500));
 
     bool SuggestMissingIncludes = false;
 
     /// Clangd will execute compiler drivers matching one of these globs to
     /// fetch system include path.
     std::vector<std::string> QueryDriverGlobs;
 
     /// Enable semantic highlighting features.

clang-tools-extra/clangd/ClangdServer.cpp

private:
   FileIndex *FIndex;
   ClangdServer::Callbacks *ServerCallbacks;
   bool SemanticHighlighting;
 };
 } // namespace
 
 ClangdServer::Options ClangdServer::optsForTest() {
   ClangdServer::Options Opts;
-  Opts.UpdateDebounce = std::chrono::steady_clock::duration::zero(); // Faster!
+  Opts.UpdateDebounce = DebouncePolicy::fixed(/*zero*/ {});
   Opts.StorePreamblesInMemory = true;
   Opts.AsyncThreadsCount = 4; // Consistent!
   Opts.SemanticHighlighting = true;
   return Opts;
 }
 
 ClangdServer::Options::operator TUScheduler::Options() const {
   TUScheduler::Options Opts;

clang-tools-extra/clangd/TUScheduler.h

 /// *idle* ASTs. If queue has operations requiring the AST, they might be
 /// kept in memory.
 struct ASTRetentionPolicy {
   /// Maximum number of ASTs to be retained in memory when there are no pending
   /// requests for them.
   unsigned MaxRetainedASTs = 3;
 };
 
+/// Clangd may wait after an update to see if another one comes along.
+/// This is so we rebuild once the user stops typing, not when they start.
+/// Debounce may be disabled/interrupted if we must build this version.
+/// The debounce time is responsive to user preferences and rebuild time.
+/// In the future, we could also consider different types of edits.
+struct DebouncePolicy {
+  using clock = std::chrono::steady_clock;
+
+  /// The minimum time that we always debounce for.
+  clock::duration Min = /*zero*/ {};
+  /// The maximum time we may debounce for.
+  clock::duration Max = /*zero*/ {};
+  /// Target debounce, as a fraction of file rebuild time.
+  /// e.g. RebuildRatio = 2, recent builds took 200ms => debounce for 400ms.
+  float RebuildRatio = 1;
+
+  /// Compute the time to debounce based on this policy and recent build times.
+  clock::duration compute(llvm::ArrayRef<clock::duration> History) const;
+  /// A policy that always returns the same duration, useful for tests.
+  static DebouncePolicy fixed(clock::duration);
+};
+
 struct TUAction {
   enum State {
     Queued,           // The TU is pending in the thread task queue to be built.
     RunningAction,    // Starting running actions on the TU.
     BuildingPreamble, // The preamble of the TU is being built.
     BuildingFile,     // The TU is being built. It is only emitted when building
                       // the AST for diagnostics in write action (update).
     Idle, // Indicates the worker thread is idle, and ready to run any upcoming
struct Options {
     /// If 0, executes actions synchronously on the calling thread.
     unsigned AsyncThreadsCount = getDefaultAsyncThreadsCount();
 
     /// Cache (large) preamble data in RAM rather than temporary files on disk.
     bool StorePreamblesInMemory = false;
 
     /// Time to wait after an update to see if another one comes along.
     /// This tries to ensure we rebuild once the user stops typing.
-    std::chrono::steady_clock::duration UpdateDebounce = /*zero*/ {};
+    DebouncePolicy UpdateDebounce;
 
     /// Determines when to keep idle ASTs in memory for future use.
     ASTRetentionPolicy RetentionPolicy;
   };
 
   TUScheduler(const GlobalCompilationDatabase &CDB, const Options &Opts,
               std::unique_ptr<ParsingCallbacks> ASTCallbacks = nullptr);
   ~TUScheduler();
private:
   std::unique_ptr<ParsingCallbacks> Callbacks; // not nullptr
   Semaphore Barrier;
   llvm::StringMap<std::unique_ptr<FileData>> Files;
   std::unique_ptr<ASTCache> IdleASTs;
   // None when running tasks synchronously and non-None when running tasks
   // asynchronously.
   llvm::Optional<AsyncTaskRunner> PreambleTasks;
   llvm::Optional<AsyncTaskRunner> WorkerThreads;
-  std::chrono::steady_clock::duration UpdateDebounce;
+  DebouncePolicy UpdateDebounce;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/TUScheduler.cpp

 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Threading.h"
 #include <algorithm>
 #include <memory>
+#include <mutex>
 #include <queue>
 #include <thread>
 
 namespace clang {
 namespace clangd {
 using std::chrono::steady_clock;
 
 namespace {

 /// remove() is called, but its thread may be busy and we don't want to block.
 /// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
 /// signals the worker to exit its run loop and gives up shared ownership of the
 /// worker.
 class ASTWorker {
   friend class ASTWorkerHandle;
   ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
             TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync,
-            steady_clock::duration UpdateDebounce, bool StorePreamblesInMemory,
+            DebouncePolicy UpdateDebounce, bool StorePreamblesInMemory,
             ParsingCallbacks &Callbacks);
 
 public:
   /// Create a new ASTWorker and return a handle to it.
   /// The processing thread is spawned using \p Tasks. However, when \p Tasks
   /// is null, all requests will be processed on the calling thread
   /// synchronously instead. \p Barrier is acquired when processing each
   /// request, it is used to limit the number of actively running threads.
   static ASTWorkerHandle
   create(PathRef FileName, const GlobalCompilationDatabase &CDB,
          TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks,
-         Semaphore &Barrier, steady_clock::duration UpdateDebounce,
+         Semaphore &Barrier, DebouncePolicy UpdateDebounce,
          bool StorePreamblesInMemory, ParsingCallbacks &Callbacks);
   ~ASTWorker();
 
   void update(ParseInputs Inputs, WantDiagnostics);
   void
   runWithAST(llvm::StringRef Name,
              llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action);
   bool blockUntilIdle(Deadline Timeout) const;
struct Request {
     Context Ctx;
     llvm::Optional<WantDiagnostics> UpdateType;
   };
 
   /// Handles retention of ASTs.
   TUScheduler::ASTCache &IdleASTs;
   const bool RunSync;
   /// Time to wait after an update to see whether another update obsoletes it.
-  const steady_clock::duration UpdateDebounce;
+  const DebouncePolicy UpdateDebounce;
   /// File that ASTWorker is responsible for.
   const Path FileName;
   const GlobalCompilationDatabase &CDB;
   /// Whether to keep the built preambles in memory or on disk.
   const bool StorePreambleInMemory;
   /// Callback invoked when preamble or main file AST is built.
   ParsingCallbacks &Callbacks;
   /// Only accessed by the worker thread.
   TUStatus Status;
 
   Semaphore &Barrier;
   /// Whether the 'onMainAST' callback ran for the current FileInputs.
   bool RanASTCallback = false;
   /// Guards members used by both TUScheduler and the worker thread.
   mutable std::mutex Mutex;
   /// File inputs, currently being used by the worker.
   /// Inputs are written and read by the worker thread, compile command can also
   /// be consumed by clients of ASTWorker.
   std::shared_ptr<const ParseInputs> FileInputs;         /* GUARDED_BY(Mutex) */
   std::shared_ptr<const PreambleData> LastBuiltPreamble; /* GUARDED_BY(Mutex) */
+  /// Times of recent AST rebuilds, used for UpdateDebounce computation.
+  llvm::SmallVector<DebouncePolicy::clock::duration, 8>
+      RebuildTimes; /* GUARDED_BY(Mutex) */
   /// Becomes ready when the first preamble build finishes.
   Notification PreambleWasBuilt;
   /// Set to true to signal run() to finish processing.
   bool Done;                    /* GUARDED_BY(Mutex) */
   std::deque<Request> Requests; /* GUARDED_BY(Mutex) */
   mutable std::condition_variable RequestsCV;
   /// Guards the callback that publishes results of AST-related computations
   /// (diagnostics, highlightings) and file statuses.

 
 private:
   std::shared_ptr<ASTWorker> Worker;
 };
 
 ASTWorkerHandle
 ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
                   TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks,
-                  Semaphore &Barrier, steady_clock::duration UpdateDebounce,
+                  Semaphore &Barrier, DebouncePolicy UpdateDebounce,
                   bool StorePreamblesInMemory, ParsingCallbacks &Callbacks) {
   std::shared_ptr<ASTWorker> Worker(
       new ASTWorker(FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks,
                     UpdateDebounce, StorePreamblesInMemory, Callbacks));
   if (Tasks)
     Tasks->runAsync("worker:" + llvm::sys::path::filename(FileName),
                     [Worker]() { Worker->run(); });
 
   return ASTWorkerHandle(std::move(Worker));
 }
 
 ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
                      TUScheduler::ASTCache &LRUCache, Semaphore &Barrier,
-                     bool RunSync, steady_clock::duration UpdateDebounce,
+                     bool RunSync, DebouncePolicy UpdateDebounce,
                      bool StorePreamblesInMemory, ParsingCallbacks &Callbacks)
     : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(UpdateDebounce),
       FileName(FileName), CDB(CDB),
       StorePreambleInMemory(StorePreamblesInMemory),
       Callbacks(Callbacks), Status{TUAction(TUAction::Idle, ""),
                                    TUStatus::BuildDetails()},
       Barrier(Barrier), Done(false) {
   auto Inputs = std::make_shared<ParseInputs>();
if (WantDiags == WantDiagnostics::No)
       // No need to rebuild the AST if we won't send the diagnostics. However,
       // note that we don't prevent preamble rebuilds.
       if (!CanPublishResults)
         return;
     }
 
     // Get the AST for diagnostics.
     llvm::Optional<std::unique_ptr<ParsedAST>> AST = IdleASTs.take(this);
+    auto RebuildStartTime = DebouncePolicy::clock::now();
     if (!AST) {
       llvm::Optional<ParsedAST> NewAST =
           buildAST(FileName, std::move(Invocation), CompilerInvocationDiags,
                    Inputs, NewPreamble);
       AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
       if (!(*AST)) { // buildAST fails.
         TUStatus::BuildDetails Details;
         Details.BuildFailed = true;
         emitTUStatus({TUAction::BuildingFile, TaskName}, &Details);
       }
     } else {
       // We are reusing the AST.
       TUStatus::BuildDetails Details;
       Details.ReuseAST = true;
       emitTUStatus({TUAction::BuildingFile, TaskName}, &Details);
     }
 
     // We want to report the diagnostics even if this update was cancelled.
     // It seems more useful than making the clients wait indefinitely if they
     // spam us with updates.
     // Note *AST can still be null if buildAST fails.
     if (*AST) {
+      {
+        // Try to record the AST-build time, to inform future update debouncing.
+        // This is best-effort only: if the lock is held, don't bother.
+        auto RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime;
+        std::unique_lock<std::mutex> Lock(Mutex, std::try_to_lock);
+        if (Lock.owns_lock()) {
+          // Do not let RebuildTimes grow beyond its small-size (i.e. capacity).
+          if (RebuildTimes.size() == RebuildTimes.capacity())
+            RebuildTimes.erase(RebuildTimes.begin());
+          RebuildTimes.push_back(RebuildDuration);
+          Mutex.unlock();
+        }
+      }
       trace::Span Span("Running main AST callback");
 
       Callbacks.onMainAST(FileName, **AST, RunPublish);
       RanASTCallback = true;
     } else {
       // Failed to build the AST, at least report diagnostics from the command
       // line if there were any.
       // FIXME: we might have got more errors while trying to build the AST,
if (I->UpdateType == WantDiagnostics::Yes)
       I->UpdateType = WantDiagnostics::Auto;
   }
 
   while (shouldSkipHeadLocked())
     Requests.pop_front();
   assert(!Requests.empty() && "skipped the whole queue");
   // Some updates aren't dead yet, but never end up being used.
   // e.g. the first keystroke is live until obsoleted by the second.
-  // We debounce "maybe-unused" writes, sleeping 500ms in case they become dead.
+  // We debounce "maybe-unused" writes, sleeping in case they become dead.
   // But don't delay reads (including updates where diagnostics are needed).
   for (const auto &R : Requests)
     if (R.UpdateType == None || R.UpdateType == WantDiagnostics::Yes)
       return Deadline::zero();
   // Front request needs to be debounced, so determine when we're ready.
-  Deadline D(Requests.front().AddTime + UpdateDebounce);
+  Deadline D(Requests.front().AddTime + UpdateDebounce.compute(RebuildTimes));
   return D;
 }
 
 // Returns true if Requests.front() is a dead update that can be skipped.
 bool ASTWorker::shouldSkipHeadLocked() const {
   assert(!Requests.empty());
   auto Next = Requests.begin();
   auto UpdateType = Next->UpdateType;
std::vector<Path> TUScheduler::getFilesWithCachedAST() const {
   for (auto &&PathAndFile : Files) {
     if (!PathAndFile.second->Worker->isASTCached())
       continue;
     Result.push_back(std::string(PathAndFile.first()));
   }
   return Result;
 }
 
+DebouncePolicy::clock::duration
+DebouncePolicy::compute(llvm::ArrayRef<clock::duration> History) const {
+  assert(Min <= Max && "Invalid policy");
+  if (History.empty())
+    return Max; // Arbitrary.
+
+  // Base the result on the median rebuild.
+  // nth_element needs a mutable array, take the chance to bound the data size.
+  History = History.take_back(15);
+  llvm::SmallVector<clock::duration, 15> Recent(History.begin(), History.end());
+  auto Median = Recent.begin() + Recent.size() / 2;
+  std::nth_element(Recent.begin(), Median, Recent.end());
+
+  clock::duration Target =
+      std::chrono::duration_cast<clock::duration>(RebuildRatio * *Median);
+  if (Target > Max)
+    return Max;
+  if (Target < Min)
+    return Min;
+  return Target;
+}
+
+DebouncePolicy DebouncePolicy::fixed(clock::duration T) {
+  DebouncePolicy P;
+  P.Min = P.Max = T;
+  return P;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp

 #include "Threading.h"
 #include "clang/Basic/DiagnosticDriver.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <algorithm>
+#include <chrono>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::AnyOf;
 using ::testing::Each;
TEST_F(TUSchedulerTests, WantDiagnostics) {
   }
   EXPECT_EQ(2, CallbackCount);
 }
 
 TEST_F(TUSchedulerTests, Debounce) {
   std::atomic<int> CallbackCount(0);
   {
     auto Opts = optsForTest();
-    Opts.UpdateDebounce = std::chrono::seconds(1);
+    Opts.UpdateDebounce = DebouncePolicy::fixed(std::chrono::seconds(1));
     TUScheduler S(CDB, Opts, captureDiags());
     // FIXME: we could probably use timeouts lower than 1 second here.
     auto Path = testPath("foo.cpp");
     updateWithDiags(S, Path, "auto (debounced)", WantDiagnostics::Auto,
                     [&](std::vector<Diag>) {
                       ADD_FAILURE()
                           << "auto should have been debounced and canceled";
                     });
TEST_F(TUSchedulerTests, ManyUpdates) {
   std::mutex Mut;
   int TotalASTReads = 0;
   int TotalPreambleReads = 0;
   int TotalUpdates = 0;
 
   // Run TUScheduler and collect some stats.
   {
     auto Opts = optsForTest();
-    Opts.UpdateDebounce = std::chrono::milliseconds(50);
+    Opts.UpdateDebounce = DebouncePolicy::fixed(std::chrono::milliseconds(50));
     TUScheduler S(CDB, Opts, captureDiags());
 
     std::vector<std::string> Files;
     for (int I = 0; I < FilesCount; ++I) {
       std::string Name = "foo" + std::to_string(I) + ".cpp";
       Files.push_back(testPath(Name));
       this->Files[Files.back()] = "";
     }
updateWithDiags(S, testPath("foo.cpp"), "void test() {}",
                     Diagnostics = std::move(D);
                     Ready.notify();
                   });
   Ready.wait();
 
   EXPECT_THAT(Diagnostics, IsEmpty());
 }
 
+TEST(DebouncePolicy, Compute) {
+  namespace c = std::chrono;
+  std::vector<DebouncePolicy::clock::duration> History = {
+      c::seconds(0),
+      c::seconds(5),
+      c::seconds(10),
+      c::seconds(20),
+  };
+  DebouncePolicy Policy;
+  Policy.Min = c::seconds(3);
+  Policy.Max = c::seconds(25);
+  // Call Policy.compute(History) and return seconds as a float.
+  auto Compute = [&](llvm::ArrayRef<DebouncePolicy::clock::duration> History) {
+    using FloatingSeconds = c::duration<float, c::seconds::period>;
+    return static_cast<float>(Policy.compute(History) / FloatingSeconds(1));
+  };
+  EXPECT_NEAR(10, Compute(History), 0.01) << "(upper) median = 10";
+  Policy.RebuildRatio = 1.5;
+  EXPECT_NEAR(15, Compute(History), 0.01) << "median = 10, ratio = 1.5";
+  Policy.RebuildRatio = 3;
+  EXPECT_NEAR(25, Compute(History), 0.01) << "constrained by max";
+  Policy.RebuildRatio = 0;
+  EXPECT_NEAR(3, Compute(History), 0.01) << "constrained by min";
+  EXPECT_NEAR(25, Compute({}), 0.01) << "no history -> max";
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang