diff --git a/clang-tools-extra/clangd/ClangdServer.h b/clang-tools-extra/clangd/ClangdServer.h --- a/clang-tools-extra/clangd/ClangdServer.h +++ b/clang-tools-extra/clangd/ClangdServer.h @@ -130,8 +130,8 @@ llvm::Optional 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; diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp --- a/clang-tools-extra/clangd/ClangdServer.cpp +++ b/clang-tools-extra/clangd/ClangdServer.cpp @@ -106,7 +106,7 @@ 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; diff --git a/clang-tools-extra/clangd/TUScheduler.h b/clang-tools-extra/clangd/TUScheduler.h --- a/clang-tools-extra/clangd/TUScheduler.h +++ b/clang-tools-extra/clangd/TUScheduler.h @@ -61,6 +61,28 @@ 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. +/// The debounce time should be 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. + /// (Debounce may still be disabled/interrupted if we must build this version) + 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 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. @@ -158,7 +180,7 @@ /// 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; @@ -273,7 +295,7 @@ // asynchronously. llvm::Optional PreambleTasks; llvm::Optional WorkerThreads; - std::chrono::steady_clock::duration UpdateDebounce; + DebouncePolicy UpdateDebounce; }; } // namespace clangd diff --git a/clang-tools-extra/clangd/TUScheduler.cpp b/clang-tools-extra/clangd/TUScheduler.cpp --- a/clang-tools-extra/clangd/TUScheduler.cpp +++ b/clang-tools-extra/clangd/TUScheduler.cpp @@ -61,6 +61,7 @@ #include "llvm/Support/Threading.h" #include #include +#include #include #include @@ -164,7 +165,7 @@ 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: @@ -176,7 +177,7 @@ 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(); @@ -242,7 +243,10 @@ 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; + /// Times of recent AST rebuilds, used for UpdateDebounce computation. + llvm::SmallVector + RebuildTimes; /* GUARDED_BY(Mutex) */ /// File that ASTWorker is responsible for. const Path FileName; const GlobalCompilationDatabase &CDB; @@ -326,7 +330,7 @@ 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 Worker( new ASTWorker(FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks, @@ -340,7 +344,7 @@ 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), @@ -488,6 +492,7 @@ // Get the AST for diagnostics. llvm::Optional> AST = IdleASTs.take(this); + auto RebuildStartTime = DebouncePolicy::clock::now(); if (!AST) { llvm::Optional NewAST = buildAST(FileName, std::move(Invocation), CompilerInvocationDiags, @@ -510,6 +515,19 @@ // 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 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); @@ -756,7 +774,7 @@ 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; } @@ -1036,5 +1054,33 @@ return Result; } +DebouncePolicy::clock::duration +DebouncePolicy::compute(llvm::ArrayRef 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 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(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 diff --git a/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp b/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp --- a/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp +++ b/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp @@ -23,6 +23,7 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" #include +#include #include namespace clang { @@ -208,7 +209,7 @@ std::atomic 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"); @@ -361,7 +362,7 @@ // 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 Files; @@ -754,6 +755,32 @@ EXPECT_THAT(Diagnostics, IsEmpty()); } +TEST(DebouncePolicy, Compute) { + namespace c = std::chrono; + std::vector 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 History) { + using FloatingSeconds = c::duration; + return static_cast(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