[clangd] Use thread pool for background indexing.

[ilya-biryukov]

It's fine to spend one thread spinning on background tasks, but if we're going to do a threadpool, we should be more careful to not hurt the performance of foreground tasks. To do that, we should at least:

• share the semaphore for the number of actively running tasks between TUScheduler and BackgroundIndex.
• prioritize foreground tasks over background tasks.

Ideally, probably outside the scope of this change, we should make the background tasks cancellable (or find another way to keep them from interfering with the foreground tasks) in addition to that and make sure the scheduling is aware of distinction between foreground and background tasks. (@sammcall suggested simply using thread priorities for that).
Another high-level comment is that we should probably use llvm::ThreadPool here, this would have give code reuse and would make BackgroundIndex more focused on the actual indexing part.

clangd/index/Background.h

80

Why not std::vector? Memory allocs won't ever be a bottleneck here.

[sammccall]

In D53651#1275517, @ilya-biryukov wrote:

It's fine to spend one thread spinning on background tasks, but if we're going to do a threadpool, we should be more careful to not hurt the performance of foreground tasks. To do that, we should at least:

• share the semaphore for the number of actively running tasks between TUScheduler and BackgroundIndex.
• prioritize foreground tasks over background tasks.

I don't think I agree with this, at least not without evidence. Can we try thread priorities first?

clangd/index/Background.cpp

96

I always forget the details of how these work :-\
Is it possible for the "one" notification to be consumed by a waiter on blockUntilIdleForTest?

In general I'm not sure whether the notify_one optimization is worth the correctness risk as the code evolves.

clangd/index/Background.h

80

ilya was saying nice things about llvm::ThreadPool recently - worth a look?

[kadircet]

Moving forward with priorities then.

clangd/index/Background.cpp

96

Ah, you are right, a thread waiting for done might catch that one as well, but I think it only applies to that one. Is there a possibility of blockUntilIdleForTest and enqueue being called from different threads?

There is still the argument of code evolution, but I don't think we should ever end up in a state in which an enqueue and a wait that will not consume that enqueue should occur concurrently.

clangd/index/Background.h

80

going for llvm::ThreadPool

[ilya-biryukov]

Update from the offline meeting: decided to start with llvm::ThreadPool for background tasks and lower thread priorities for background tasks.

clangd/index/Background.cpp

96

but I don't think we should ever end up in a state in which an enqueue and a wait that will not consume that enqueue should occur concurrently.

We definitely will, +1 to Sam's comment, please call notify_all here. It's too easy to deadlock with notify_one.
E.g. just from the top of my mind, we can easily start adding tasks from a different thread if we start watching for changes (to compile commands, to header dependencies, etc.)

[kadircet]

• Use notify_all.
• Use priorities.

[sammccall]

clangd/Threading.cpp

105

don't you also need to actually include it?

clangd/Threading.h

120

nit: enum class since this is at clangd scope

121

nit: llvm tends to spell enum values like Low, Normal

124

This deserves a comment - in particular that it may be a no-op.

clangd/index/Background.cpp

35

nit: clang-format

37

we discussed having different priority tasks, which would require priorities to be set up differently (to avoid workers never waking up to consume high priority tasks).

OK to leave this for now, but deserves a comment.

clangd/index/Background.h

19

depending on TUScheduler doesn't make sense here. Move the function to Threading.h instead?

80

Any problems with llvm::ThreadPool?

[ilya-biryukov]

clangd/Threading.cpp

104

Maybe put this helper into llvm/Support/Threading.h?

clangd/Threading.h

120

Maybe use enum class?

clangd/index/Background.h

19

Maybe move the getDefaultAsyncThreadsCount into Threading.h?
Having a dependency on TUScheduler in Background indexing is a bit misleading, since we're not actually sharing any threading infrastructure there.

[kadircet]

• Address comments && Use ThreadPool

[kadircet]

clangd/Threading.cpp

105

Turns out it was included transitively.

clangd/index/Background.h

19

actually there is one in llvm with the same semantics we use(never return zero) llvm::hardware_concurrency

[kadircet]

• Delete outdated comment.

[kadircet]

• Address comments.

[sammccall]

Nice! Sorry about the back and forth with threadpool...

clangd/index/Background.cpp

35

(need to clang-format again)

[kadircet]

• Add comment.

clangd/Threading.cpp

104

We talked with Sam about that one and rather decided to keep it here for a while and put into LLVM later on when we are sure about it is the right use case for everyone in LLVM with the right API.

[kadircet]

• Format the code.

[uabelho]

Hi,

I've got a post-review comment about the use of SCHED_IDLE vs the needed gcc version.

clang-tools-extra/trunk/clangd/Threading.cpp

110 ↗

(On Diff #171677)

I noticed that when I compile this with gcc 5.4.0, I get a compilation error about SCHED_IDLE not being defined.
Indeed, if I look in sched.h used with gcc 5.4.0, these are the SCHED_* definitions:

/* Scheduling algorithms.  */
#define SCHED_OTHER	0
#define SCHED_FIFO	1
#define SCHED_RR	2
#ifdef __USE_GNU
# define SCHED_BATCH	3
#endif

I suppose SCHED_IDLE was added in some later version...

On
https://llvm.org/docs/GettingStarted.html#host-c-toolchain-both-compiler-and-standard-library
it says that gcc 4.8 should work, but it doesn't now then?

[cfe-commits]

Hi,

clangd/Threading.h

 
 #include "Context.h"
 #include "Function.h"
 #include "llvm/ADT/Twine.h"
 #include <cassert>
 #include <condition_variable>
 #include <memory>
 #include <mutex>
+#include <thread>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 /// A threadsafe flag that is initially clear.
 class Notification {
 public:
public:
   // The name is used for tracing and debugging (e.g. to name a spawned thread).
   void runAsync(const llvm::Twine &Name, llvm::unique_function<void()> Action);
 
 private:
   mutable std::mutex Mutex;
   mutable std::condition_variable TasksReachedZero;
   std::size_t InFlightTasks = 0;
 };
+
+enum class ThreadPriority {
+  Low = 0,
+  Normal = 1,
+};
+void setThreadPriority(std::thread &T, ThreadPriority Priority);
+
 } // namespace clangd
 } // namespace clang
 #endif

clangd/Threading.cpp

 #include "Threading.h"
 #include "Trace.h"
 #include "llvm/ADT/ScopeExit.h"
+#include "llvm/Config/config.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Threading.h"
 #include <thread>
+#ifdef HAVE_PTHREAD_H
+#include <pthread.h>
+#endif
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 
 void Notification::notify() {
   {
     std::lock_guard<std::mutex> Lock(Mu);
void wait(std::unique_lock<std::mutex> &Lock, std::condition_variable &CV,
           Deadline D) {
   if (D == Deadline::zero())
     return;
   if (D == Deadline::infinity())
     return CV.wait(Lock);
   CV.wait_until(Lock, D.time());
 }
 
+void setThreadPriority(std::thread &T, ThreadPriority Priority) {
+#ifdef HAVE_PTHREAD_H
+  sched_param priority;
+  priority.sched_priority = 0;
+  pthread_setschedparam(
+      T.native_handle(),
+      Priority == ThreadPriority::Low ? SCHED_IDLE : SCHED_OTHER, &priority);
+#endif
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/Background.h

 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
 
 #include "Context.h"
 #include "FSProvider.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/Support/SHA1.h"
+#include "llvm/Support/Threading.h"
 #include <condition_variable>
 #include <deque>
 #include <string>
 #include <thread>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 // Builds an in-memory index by by running the static indexer action over
 // all commands in a compilation database. Indexing happens in the background.
 // FIXME: it should also persist its state on disk for fast start.
 // FIXME: it should watch for changes to files on disk.
 class BackgroundIndex : public SwapIndex {
 public:
   // FIXME: resource-dir injection should be hoisted somewhere common.
   BackgroundIndex(Context BackgroundContext, StringRef ResourceDir,
                   const FileSystemProvider &,
-                  ArrayRef<std::string> URISchemes = {});
+                  ArrayRef<std::string> URISchemes = {},
+                  size_t ThreadPoolSize = llvm::hardware_concurrency());
   ~BackgroundIndex(); // Blocks while the current task finishes.
 
   // Enqueue a translation unit for indexing.
   // The indexing happens in a background thread, so the symbols will be
   // available sometime later.
   void enqueue(llvm::StringRef Directory, tooling::CompileCommand);
   // Index all TUs described in the compilation database.
   void enqueueAll(llvm::StringRef Directory,
private:
 
   // index state
   llvm::Error index(tooling::CompileCommand);
   FileSymbols IndexedSymbols; // Index contents.
   using Hash = decltype(llvm::SHA1::hash({}));
   llvm::StringMap<Hash> FileHash; // Digest of indexed file.
 
   // queue management
-  using Task = std::function<void()>; // FIXME: use multiple worker threads.
+  using Task = std::function<void()>;
   void run(); // Main loop executed by Thread. Runs tasks from Queue.
   void enqueueLocked(tooling::CompileCommand Cmd);
   std::mutex QueueMu;
   unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
   std::condition_variable QueueCV;
   bool ShouldStop = false;
   std::deque<Task> Queue;
-  std::thread Thread; // Must be last, spawned thread reads instance vars.
+  std::vector<std::thread> ThreadPool; // FIXME: Abstract this away.
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/index/Background.cpp

 //===-- Background.cpp - Build an index in a background thread ------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "index/Background.h"
 #include "ClangdUnit.h"
 #include "Compiler.h"
 #include "Logger.h"
+#include "Threading.h"
 #include "Trace.h"
 #include "index/IndexAction.h"
 #include "index/MemIndex.h"
 #include "index/Serialization.h"
 #include "llvm/Support/SHA1.h"
 #include <random>
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 
 BackgroundIndex::BackgroundIndex(Context BackgroundContext,
                                  StringRef ResourceDir,
                                  const FileSystemProvider &FSProvider,
-                                 ArrayRef<std::string> URISchemes)
+                                 ArrayRef<std::string> URISchemes,
+                                 size_t ThreadPoolSize)
     : SwapIndex(make_unique<MemIndex>()), ResourceDir(ResourceDir),
       FSProvider(FSProvider), BackgroundContext(std::move(BackgroundContext)),
-      URISchemes(URISchemes), Thread([this] { run(); }) {}
+      URISchemes(URISchemes) {
+  assert(ThreadPoolSize > 0 && "Thread pool size can't be zero.");
+  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 a 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);
     ShouldStop = true;
   }
   QueueCV.notify_all();
 }
 
 void BackgroundIndex::run() {
-  WithContext Background(std::move(BackgroundContext));
+  WithContext Background(BackgroundContext.clone());
   while (true) {
     Optional<Task> Task;
     {
       std::unique_lock<std::mutex> Lock(QueueMu);
       QueueCV.wait(Lock, [&] { return ShouldStop || !Queue.empty(); });
       if (ShouldStop) {
         Queue.clear();
         QueueCV.notify_all();

 }
 
 void BackgroundIndex::enqueue(StringRef Directory,
                               tooling::CompileCommand Cmd) {
   {
     std::lock_guard<std::mutex> Lock(QueueMu);
     enqueueLocked(std::move(Cmd));
   }
   QueueCV.notify_all();
 }
 
 void BackgroundIndex::enqueueAll(StringRef Directory,
                                  const tooling::CompilationDatabase &CDB) {
   trace::Span Tracer("BackgroundIndexEnqueueCDB");
   // FIXME: this function may be slow. Perhaps enqueue a task to re-read the CDB
   // from disk and enqueue the commands asynchronously?
   auto Cmds = CDB.getAllCompileCommands();