sammccall created this revision.
Herald added subscribers: usaxena95, arphaman.
sammccall requested review of this revision.
Herald added subscribers: cfe-commits, MaskRay, ilya-biryukov.
Herald added a project: clang.
...updated and in practice it's often a net negative)
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D94503
Files:
clang-tools-extra/clangd/index/Background.cpp
clang-tools-extra/clangd/index/Background.h
clang-tools-extra/clangd/index/BackgroundQueue.cpp
clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp
Index: clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp
+++ clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp
@@ -9,6 +9,7 @@
#include "index/BackgroundRebuild.h"
#include "clang/Tooling/ArgumentsAdjusters.h"
#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/ScopedPrinter.h"
#include "llvm/Support/Threading.h"
#include "gmock/gmock.h"
@@ -829,6 +830,30 @@
}
}
+TEST(BackgroundQueueTest, Duplicates) {
+ std::string Sequence;
+ BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
+ A.QueuePri = 100;
+ A.Key = 1;
+ BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
+ // B has no key, and is not subject to duplicate detection.
+ B.QueuePri = 50;
+
+ BackgroundQueue Q;
+ Q.append({A, B, A, B}); // One A is dropped, the other is high priority.
+ Q.work(/*OnIdle=*/[&] {
+ // The first time we go idle, we enqueue the same task again.
+ if (!llvm::is_contained(Sequence, ' ')) {
+ Sequence.push_back(' ');
+ Q.append({A, B, A, B}); // One A is dropped, the other is zero priority.
+ } else {
+ Q.stop();
+ }
+ });
+
+ EXPECT_EQ("ABB BBA", Sequence);
+}
+
TEST(BackgroundQueueTest, Progress) {
using testing::AnyOf;
BackgroundQueue::Stats S;
Index: clang-tools-extra/clangd/index/BackgroundQueue.cpp
===================================================================
--- clang-tools-extra/clangd/index/BackgroundQueue.cpp
+++ clang-tools-extra/clangd/index/BackgroundQueue.cpp
@@ -33,6 +33,8 @@
std::pop_heap(Queue.begin(), Queue.end());
Task = std::move(Queue.back());
Queue.pop_back();
+ if (Task->Key)
+ ActiveKeys.erase(Task->Key);
notifyProgress();
}
@@ -72,10 +74,23 @@
CV.notify_all();
}
+// Tweaks the priority of a newly-enqueued task, or returns false to cancel it.
+bool BackgroundQueue::adjust(Task &T) {
+ if (T.Key) {
+ if (!ActiveKeys.insert(T.Key).second)
+ return false;
+ if (!SeenKeys.insert(T.Key).second)
+ T.QueuePri = 0;
+ }
+ T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
+ return true;
+}
+
void BackgroundQueue::push(Task T) {
{
std::lock_guard<std::mutex> Lock(Mu);
- T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
+ if (!adjust(T))
+ return;
Queue.push_back(std::move(T));
std::push_heap(Queue.begin(), Queue.end());
++Stat.Enqueued;
@@ -87,11 +102,13 @@
void BackgroundQueue::append(std::vector<Task> Tasks) {
{
std::lock_guard<std::mutex> Lock(Mu);
- for (Task &T : Tasks)
- T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
- std::move(Tasks.begin(), Tasks.end(), std::back_inserter(Queue));
+ for (Task &T : Tasks) {
+ if (!adjust(T))
+ continue;
+ Queue.push_back(std::move(T));
+ ++Stat.Enqueued;
+ }
std::make_heap(Queue.begin(), Queue.end());
- Stat.Enqueued += Tasks.size();
notifyProgress();
}
CV.notify_all();
Index: clang-tools-extra/clangd/index/Background.h
===================================================================
--- clang-tools-extra/clangd/index/Background.h
+++ clang-tools-extra/clangd/index/Background.h
@@ -76,6 +76,9 @@
llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Background;
unsigned QueuePri = 0; // Higher-priority tasks will run first.
std::string Tag; // Allows priority to be boosted later.
+ uint64_t Key = 0; // If the key matches a previous task:
+ // - in the queue ==> new task is dropped
+ // - completed ==> new task gets priority 0
bool operator<(const Task &O) const { return QueuePri < O.QueuePri; }
};
@@ -114,6 +117,7 @@
private:
void notifyProgress() const; // Requires lock Mu
+ bool adjust(Task &T);
std::mutex Mu;
Stats Stat;
@@ -122,6 +126,8 @@
std::vector<Task> Queue; // max-heap
llvm::StringMap<unsigned> Boosts;
std::function<void(Stats)> OnProgress;
+ llvm::DenseSet<uint64_t> ActiveKeys;
+ llvm::DenseSet<uint64_t> SeenKeys;
};
// Builds an in-memory index by by running the static indexer action over
@@ -213,6 +219,7 @@
// from lowest to highest priority
enum QueuePriority {
+ ReindexFile = 0, // Implicitly applied by BackgroundQueue
IndexFile,
IndexBoostedFile,
LoadShards,
Index: clang-tools-extra/clangd/index/Background.cpp
===================================================================
--- clang-tools-extra/clangd/index/Background.cpp
+++ clang-tools-extra/clangd/index/Background.cpp
@@ -43,6 +43,7 @@
#include "llvm/Support/Error.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/Threading.h"
+#include "llvm/Support/xxhash.h"
#include <algorithm>
#include <atomic>
@@ -139,8 +140,8 @@
std::mt19937(std::random_device{}()));
std::vector<BackgroundQueue::Task> Tasks;
Tasks.reserve(NeedsReIndexing.size());
- for (auto &Cmd : NeedsReIndexing)
- Tasks.push_back(indexFileTask(std::move(Cmd)));
+ for (const auto &Cmd : NeedsReIndexing)
+ Tasks.push_back(indexFileTask(Cmd));
Queue.append(std::move(Tasks));
});
@@ -156,6 +157,7 @@
BackgroundQueue::Task BackgroundIndex::indexFileTask(std::string Path) {
std::string Tag = filenameWithoutExtension(Path).str();
+ uint64_t Key = llvm::xxHash64(Path);
BackgroundQueue::Task T([this, Path(std::move(Path))] {
llvm::Optional<WithContext> WithProvidedContext;
if (ContextProvider)
@@ -168,6 +170,7 @@
});
T.QueuePri = IndexFile;
T.Tag = std::move(Tag);
+ T.Key = Key;
return T;
}
@@ -353,13 +356,15 @@
std::vector<std::string>
BackgroundIndex::loadProject(std::vector<std::string> MainFiles) {
// Drop files where background indexing is disabled in config.
- if (ContextProvider)
+ if (ContextProvider) {
+ trace::Span Tracer("BackgroundPolicy");
llvm::erase_if(MainFiles, [&](const std::string &TU) {
// Load the config for each TU, as indexing may be selectively enabled.
WithContext WithProvidedContext(ContextProvider(TU));
return Config::current().Index.Background ==
Config::BackgroundPolicy::Skip;
});
+ }
Rebuilder.startLoading();
// Load shards for all of the mainfiles.
const std::vector<LoadedShard> Result =
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
