sammccall created this revision.
sammccall added a reviewer: hokein.
Herald added subscribers: cfe-commits, usaxena95, kadircet, arphaman, jkorous,
MaskRay, javed.absar, ilya-biryukov.
Herald added a project: clang.
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
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D73873
Files:
clang-tools-extra/clangd/ClangdServer.cpp
clang-tools-extra/clangd/ClangdServer.h
clang-tools-extra/clangd/TUScheduler.cpp
clang-tools-extra/clangd/TUScheduler.h
clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp
Index: clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp
+++ clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp
@@ -23,6 +23,7 @@
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include <algorithm>
+#include <chrono>
#include <utility>
namespace clang {
@@ -208,7 +209,7 @@
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");
@@ -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<std::string> Files;
@@ -754,6 +755,32 @@
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
Index: clang-tools-extra/clangd/TUScheduler.h
===================================================================
--- clang-tools-extra/clangd/TUScheduler.h
+++ 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<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.
@@ -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<AsyncTaskRunner> PreambleTasks;
llvm::Optional<AsyncTaskRunner> WorkerThreads;
- std::chrono::steady_clock::duration UpdateDebounce;
+ DebouncePolicy UpdateDebounce;
};
} // namespace clangd
Index: clang-tools-extra/clangd/TUScheduler.cpp
===================================================================
--- clang-tools-extra/clangd/TUScheduler.cpp
+++ clang-tools-extra/clangd/TUScheduler.cpp
@@ -61,6 +61,7 @@
#include "llvm/Support/Threading.h"
#include <algorithm>
#include <memory>
+#include <mutex>
#include <queue>
#include <thread>
@@ -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<DebouncePolicy::clock::duration, 8>
+ 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<ASTWorker> 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<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,
@@ -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<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);
@@ -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<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
Index: clang-tools-extra/clangd/ClangdServer.h
===================================================================
--- clang-tools-extra/clangd/ClangdServer.h
+++ clang-tools-extra/clangd/ClangdServer.h
@@ -130,8 +130,8 @@
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;
Index: clang-tools-extra/clangd/ClangdServer.cpp
===================================================================
--- clang-tools-extra/clangd/ClangdServer.cpp
+++ 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;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
