[clangd] Only reduce priority of a thread for indexing.

[kadircet]

Summary

We'll soon have tasks pending for reading shards from disk, we want
them to have normal priority. Because:

• They are not CPU intensive, mostly IO bound.
• Give a good coverage for the project at startup, therefore it is worth spending some cycles.
• We have only one task per whole CDB rather than one task per file.

[ilya-biryukov]

clangd/Threading.h

125

Maybe change the name to setCurrentThreadPrority?
The change itself LG, there does not seem to be a way to get the native handle from std::this_thread...

clangd/index/Background.cpp

200

Maybe make this a parameter of enqueueTask, probably with ThreadPriority::Low being the default?
Seems to be an appropriate place, enqueueTask is a starting point for scheduling and task priority is inherently a property that the scheduler cares about.

[kadircet]

• Move priority change logic into enqueueTask

[ilya-biryukov]

clangd/Threading.h

124

The comment looks redundant now. Maybe remove it?

clangd/index/Background.cpp

207–218

Since we might be interested in scheduling higher-priority tasks first anyway (not in this patch, but still), maybe store a pair of (Task, Priority) in the queue and call setCurrentThreadPriority when actually running the task?

[kadircet]

• Delete redundant comment

[kadircet]

clangd/index/Background.cpp

207–218

I believe we can introduce that later on whenever we have more than 2 priorities, currently we push to front for important tasks and back for the low priority ones. Do you think it is not enough?

[ilya-biryukov]

clangd/index/Background.cpp

207–218

Sorry, I somehow missed that push_front and push_back are used in different cases, I've only noticed the callback wrapping.
I feel storing priorities in the queue produces a more straightforward code as priority is an important scheduling signal, so it fits in nicely there. Using a wrapped callback, OTOH, is a bit hard to read. But that might be a personal preference, up to you.

See the other comment about ordering of the tasks with normal priorities, it looks more important

217

It's a bit surprising that we put the new task in front of the other tasks with a normal priority.
Do we anticipate a large number of normal priority tasks? I believe our current expectation is that we'll have a single normal task per open compilation database, right? In that case the number of pending normal tasks should be a single-digit number in practice. Therefore, maybe add the new task after all the normal tasks at the start of the queue?

[kadircet]

• Move priority change logic to runner
• Change storage for tasks from deque to list, since we only pop from front but we might end up adding into middle.

clangd/index/Background.cpp

207–218

The wrapped callback was rather for getting rid of unnecessary system calls, but since normal tasks come up rarely to queue it doesn't feel like an important thing. Changing it to store the priority in the queue.

[ilya-biryukov]

clangd/index/Background.cpp

107–108

NIT: remove braces around a single statement

141

NIT: maybe add newlines around the three lines (setCurrentThreadPriority and Task execution). These are pretty important.

141

Maybe only lower the priority iff it's != Normal. Would avoid system calls in most cases (I believe you mentioned it in the other comment before too)

209

A short comment about the structure of the queue would be in order, i.e. mention that we first store all "normal" tasks, followed by "low" tasks. And that we don't expect the number of "normal" tasks to grow beyond single-digit numbers, so it's ok to do linear search here and insert in that position

211

Maybe change to llvm::find_if(Tasks, [](Task &T) { return T.second == ThreadPriority::Low); } ?
More concise and avoids explicit loop.

[kadircet]

• Address comments

[ilya-biryukov]

clangd/index/Background.h

121

Why not std::deque?

[kadircet]

clangd/index/Background.h

121

because we can insert in the middle of the queue now, when we skip existing high priority tasks.

[ilya-biryukov]

clangd/index/Background.h

121

deque::insert is O(smaller of the distances to either begin or end) and we spend the same time on the linear search anyway.
I believe we can keep it, even though I'm not strictly sure which is more efficient (we certainly don't care)

[kadircet]

• Use std::deque instead of std::list

clangd/index/Background.h

121

Cool, didn't know that. If that's the case we definitely don't care.

[ilya-biryukov]

LGTM

clangd/index/Background.h

121

This rename makes the diff look a bit more complicated than it actually is. I personally like the new name better, but the old name also seemed ok.
Maybe considering keeping the old name to make the diff simpler?

Up to you, though, this does not seem terribly important.

[kadircet]

• Revert name from Tasks to Queue

clangd/Threading.h

private:
   mutable std::condition_variable TasksReachedZero;
   std::size_t InFlightTasks = 0;
 };
 
 enum class ThreadPriority {
   Low = 0,
   Normal = 1,
 };
-void setThreadPriority(std::thread &T, ThreadPriority Priority);
+void setCurrentThreadPriority(ThreadPriority Priority);
 // Avoid the use of scheduler policies that may starve low-priority threads.
 // This prevents tests from timing out on loaded systems.
 // Affects subsequent setThreadPriority() calls.
 void preventThreadStarvationInTests();
 
 } // namespace clangd
 } // namespace clang
 #endif

clangd/Threading.cpp

if (D == Deadline::zero())
     return;
   if (D == Deadline::infinity())
     return CV.wait(Lock);
   CV.wait_until(Lock, D.time());
 }
 
 static std::atomic<bool> AvoidThreadStarvation = {false};
 
-void setThreadPriority(std::thread &T, ThreadPriority Priority) {
+void setCurrentThreadPriority(ThreadPriority Priority) {
   // Some *really* old glibcs are missing SCHED_IDLE.
 #if defined(__linux__) && defined(SCHED_IDLE)
   sched_param priority;
   priority.sched_priority = 0;
   pthread_setschedparam(
-      T.native_handle(),
+      pthread_self(),
       Priority == ThreadPriority::Low && !AvoidThreadStarvation ? SCHED_IDLE
                                                                 : SCHED_OTHER,
       &priority);
 #endif
 }
 
 void preventThreadStarvationInTests() { AvoidThreadStarvation = true; }
 
 } // namespace clangd
 } // namespace clang

clangd/index/Background.h

 //===--- Background.h - Build an index in a background thread ----*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
 
 #include "Context.h"
 #include "FSProvider.h"
 #include "GlobalCompilationDatabase.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 <condition_variable>
private:
   llvm::StringMap<FileDigest> IndexedFileDigests; // Key is absolute file path.
   std::mutex DigestsMu;
 
   BackgroundIndexStorage::Factory IndexStorageFactory;
 
   // queue management
   using Task = std::function<void()>;
   void run(); // Main loop executed by Thread. Runs tasks from Queue.
-  void enqueueTask(Task T);
+  void enqueueTask(Task T, ThreadPriority Prioirty);
   void enqueueLocked(tooling::CompileCommand Cmd,
                      BackgroundIndexStorage *IndexStorage);
-  std::mutex QueueMu;
+  std::mutex TasksMu;
   unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
-  std::condition_variable QueueCV;
+  std::condition_variable TasksCV;
   bool ShouldStop = false;
-  std::deque<Task> Queue;
+  std::list<std::pair<Task, ThreadPriority>> Tasks;
   std::vector<std::thread> ThreadPool; // FIXME: Abstract this away.
   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/index/Background.cpp

 #include "URI.h"
 #include "index/IndexAction.h"
 #include "index/MemIndex.h"
 #include "index/Serialization.h"
 #include "index/SymbolCollector.h"
 #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 <memory>
 #include <numeric>
 #include <queue>
 #include <random>
: SwapIndex(make_unique<MemIndex>()), ResourceDir(ResourceDir),
       BackgroundContext(std::move(BackgroundContext)),
       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--) {
+  while (ThreadPoolSize--)
     ThreadPool.emplace_back([this] { run(); });
-    // Set priority to low, since background indexing is a long running task we
-    // do not want to eat up cpu when there are any other high priority threads.
-    // FIXME: In the future we might want a more general way of handling this to
-    // support tasks with various priorities.
-    setThreadPriority(ThreadPool.back(), ThreadPriority::Low);
-  }
 }
 
 BackgroundIndex::~BackgroundIndex() {
   stop();
   for (auto &Thread : ThreadPool)
     Thread.join();
 }
 
 void BackgroundIndex::stop() {
   {
-    std::lock_guard<std::mutex> Lock(QueueMu);
+    std::lock_guard<std::mutex> Lock(TasksMu);
     ShouldStop = true;
   }
-  QueueCV.notify_all();
+  TasksCV.notify_all();
 }
 
 void BackgroundIndex::run() {
   WithContext Background(BackgroundContext.clone());
   while (true) {
     Optional<Task> Task;
+    ThreadPriority Priority;
     {
-      std::unique_lock<std::mutex> Lock(QueueMu);
-      QueueCV.wait(Lock, [&] { return ShouldStop || !Queue.empty(); });
+      std::unique_lock<std::mutex> Lock(TasksMu);
+      TasksCV.wait(Lock, [&] { return ShouldStop || !Tasks.empty(); });
       if (ShouldStop) {
-        Queue.clear();
-        QueueCV.notify_all();
+        Tasks.clear();
+        TasksCV.notify_all();
         return;
       }
       ++NumActiveTasks;
-      Task = std::move(Queue.front());
-      Queue.pop_front();
+      std::tie(Task, Priority) = std::move(Tasks.front());
+      Tasks.pop_front();
     }
+
+    if (Priority != ThreadPriority::Normal)
+      setCurrentThreadPriority(Priority);
     (*Task)();
+    if (Priority != ThreadPriority::Normal)
+      setCurrentThreadPriority(ThreadPriority::Normal);
+
     {
-      std::unique_lock<std::mutex> Lock(QueueMu);
+      std::unique_lock<std::mutex> Lock(TasksMu);
       assert(NumActiveTasks > 0 && "before decrementing");
       --NumActiveTasks;
     }
-    QueueCV.notify_all();
+    TasksCV.notify_all();
   }
 }
 
 bool BackgroundIndex::blockUntilIdleForTest(
     llvm::Optional<double> TimeoutSeconds) {
-  std::unique_lock<std::mutex> Lock(QueueMu);
-  return wait(Lock, QueueCV, timeoutSeconds(TimeoutSeconds),
-              [&] { return Queue.empty() && NumActiveTasks == 0; });
+  std::unique_lock<std::mutex> Lock(TasksMu);
+  return wait(Lock, TasksCV, timeoutSeconds(TimeoutSeconds),
+              [&] { return Tasks.empty() && NumActiveTasks == 0; });
 }
 
 void BackgroundIndex::enqueue(const std::vector<std::string> &ChangedFiles) {
-  enqueueTask([this, ChangedFiles] {
+  enqueueTask(
+      [this, ChangedFiles] {
         trace::Span Tracer("BackgroundIndexEnqueue");
         // We're doing this asynchronously, because we'll read shards here too.
         // FIXME: read shards here too.
 
         log("Enqueueing {0} commands for indexing", ChangedFiles.size());
         SPAN_ATTACH(Tracer, "files", int64_t(ChangedFiles.size()));
 
         // We shuffle the files because processing them in a random order should
         // quickly give us good coverage of headers in the project.
         std::vector<unsigned> Permutation(ChangedFiles.size());
         std::iota(Permutation.begin(), Permutation.end(), 0);
         std::mt19937 Generator(std::random_device{}());
         std::shuffle(Permutation.begin(), Permutation.end(), Generator);
 
         for (const unsigned I : Permutation)
           enqueue(ChangedFiles[I]);
-  });
+      },
+      ThreadPriority::Normal);
 }
 
 void BackgroundIndex::enqueue(const std::string &File) {
   ProjectInfo Project;
   if (auto Cmd = CDB.getCompileCommand(File, &Project)) {
     auto *Storage = IndexStorageFactory(Project.SourceRoot);
+    // Set priority to low, since background indexing is a long running
+    // task we do not want to eat up cpu when there are any other high
+    // priority threads.
     enqueueTask(Bind(
                     [this, File, Storage](tooling::CompileCommand Cmd) {
                       Cmd.CommandLine.push_back("-resource-dir=" + ResourceDir);
                       if (auto Error = index(std::move(Cmd), Storage))
                         log("Indexing {0} failed: {1}", File, std::move(Error));
                     },
-        std::move(*Cmd)));
+                    std::move(*Cmd)),
+                ThreadPriority::Low);
   }
 }
 
-void BackgroundIndex::enqueueTask(Task T) {
+void BackgroundIndex::enqueueTask(Task T, ThreadPriority Priority) {
   {
-    std::lock_guard<std::mutex> Lock(QueueMu);
-    Queue.push_back(std::move(T));
+    std::lock_guard<std::mutex> Lock(TasksMu);
+    auto I = Tasks.end();
+    // We first store the tasks with Normal priority in the front of the queue.
+    // Then we store low priority tasks. Normal priority tasks are pretty rare,
+    // they should not grow beyond single-digit numbers, so it is OK to do
+    // linear search and insert after that.
+    if (Priority == ThreadPriority::Normal) {
+      I = llvm::find_if(Tasks, [](const std::pair<Task, ThreadPriority> &Elem) {
+        return Elem.second == ThreadPriority::Low;
+      });
+    }
+    Tasks.insert(I, {std::move(T), Priority});
   }
-  QueueCV.notify_all();
+  TasksCV.notify_all();
 }
 
 /// Given index results from a TU, only update files in \p FilesToUpdate.
 void BackgroundIndex::update(StringRef MainFile, IndexFileIn Index,
                              const StringMap<FileDigest> &FilesToUpdate,
                              BackgroundIndexStorage *IndexStorage) {
   // Partition symbols/references into files.
   struct File {