[clangd] ignore parallelism level for quick tasks

[qchateau]

Summary

This allows quick tasks without dependencies that
need to run fast to run ASAP. This is mostly useful
for code formatting.

---

This fixes something that's been annoying me:

• Open your IDE workspace and its 20 open files
• Clangd spends 5 minutes parsing it all
• In the meantime you start to work
• Save a file, trigger format-on-save, which hangs because clangd is busy
• You're stuck waiting until clangd is done parsing your files before the formatting and save takes place

[sammccall]

Save a file, trigger format-on-save, which hangs because clangd is busy

OK, that's really terrible :-( In some way this is LSP's fault, the whole design is around async unreliable language servers, and then they put in a couple of features that really have to be sync.
But those features solve real problems...
We're really lucky here that formatting doesn't need an AST or preamble, there's no real fundamental reason for that.

I was pretty skeptical of the implementation at first, but working through the alternatives brought me around.

---

(Rest is my notes, feel free to ignore)

1. The technique in the patch: separate pool for cheap tasks with short deadlines. This gets slow if the tasks don't turn out to be cheap.
2. Or we could take them off the semaphore altogether. This spawns lots of threads if the tasks don't turn out to be cheap.
3. Another option is to lean on the fact that the task in question here isn't terribly important - we'd rather give up than queue. We could do this by using try_lock instead of lock on the semaphore. This degrades functionality if we get overlapping requests.
4. We could record priorities and run the highest-priority task next.

4 is a non-starter without pre-emption: we have to wait for a task to finish, and probably all running tasks are slow.

3 trades away reliability for latency guarantees. I don't like it because it may do so even below the threshold where latency matters.

We could combine 1+3: a separate fast-tasks semaphore, but try_lock. This will still format under load, but will refuse to ever form a queue.
I guess the most relevant scenario is some large save-all operation. Still, we don't have any evidence this is going to be slow enough that we should choose to be unreliable.

1 vs 2 is partly a question of how you want to fail. Queueing seems just as good as leaking threads to me.
But it also determines whether we get any parallelism in a large-save-all scenario. It seems a little silly not to, to me - so maybe we should increase the semaphore size.

clang-tools-extra/clangd/TUScheduler.cpp

1251

1 means if we get *any* concurrent requests they'll execute serially instead of in parallel.

I get the desire to limit this, and the idea that the tasks should be fast, but this seems like it'll be the bottleneck if the user hits "save all" after a rename hits 20 files in their editor.

We might as well set it to 4 or AsyncThreadsCount or something?

1328

nit: i'd slightly prefer runQuick, as it groups alphabetically with the other methods.

And that way "quick" is jammed ambiguously between the "run" and the "action", and applies to both :-)

[qchateau]

• [clangd] fix nits

[qchateau]

I applied your suggestion as I agree with both. I chose to use Opts.AsyncThreadsCount instead of a hard-coded constant. This way the "formatting speed" will grow as the user allow more parallelism, which IMO makes sense.

I agree the implementation had drawbacks but this is the ever-ending problem of non-preemptable tasks. You can land this if this looks good to you.

Commit email: [e-mail]

clang-tools-extra/clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===-------------------------------------------------------------------===//
 
if (!Style)
       return CB(Style.takeError());
 
     std::vector<TextEdit> Result;
     for (const tooling::Replacement &R :
          formatIncremental(Code, CursorPos, TriggerText, *Style))
       Result.push_back(replacementToEdit(Code, R));
     return CB(Result);
   };
-  WorkScheduler.run("FormatOnType", File, std::move(Action));
+  WorkScheduler.runQuick("FormatOnType", File, std::move(Action));
 }
 
 void ClangdServer::prepareRename(PathRef File, Position Pos,
                                  llvm::Optional<std::string> NewName,
                                  const RenameOptions &RenameOpts,
                                  Callback<RenameResult> CB) {
   auto Action = [Pos, File = File.str(), CB = std::move(CB),
                  NewName = std::move(NewName), RenameOpts,
auto Action = [File = File.str(), Code = Code.str(), Ranges = Ranges.vec(),
     if (!Changed)
       return CB(Changed.takeError());
 
     CB(IncludeReplaces.merge(format::reformat(
         Style, *Changed,
         tooling::calculateRangesAfterReplacements(IncludeReplaces, Ranges),
         File)));
   };
-  WorkScheduler.run("Format", File, std::move(Action));
+  WorkScheduler.runQuick("Format", File, std::move(Action));
 }
 
 void ClangdServer::findDocumentHighlights(
     PathRef File, Position Pos, Callback<std::vector<DocumentHighlight>> CB) {
   auto Action =
       [Pos, CB = std::move(CB)](llvm::Expected<InputsAndAST> InpAST) mutable {
         if (!InpAST)
           return CB(InpAST.takeError());

clang-tools-extra/clangd/TUScheduler.h

 //===--- TUScheduler.h -------------------------------------------*-C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
public:
   /// Returns a snapshot of all file buffer contents, per last update().
   llvm::StringMap<std::string> getAllFileContents() const;
 
   /// Schedule an async task with no dependencies.
   /// Path may be empty (it is used only to set the Context).
   void run(llvm::StringRef Name, llvm::StringRef Path,
            llvm::unique_function<void()> Action);
 
+  /// Similar to run, except the task is expected to be quick.
+  /// This function will not honor AsyncThreadsCount (except
+  /// if threading is disabled with AsyncThreadsCount=0)
+  /// It is intended to run quick tasks that need to run ASAP
+  void runQuick(llvm::StringRef Name, llvm::StringRef Path,
+                llvm::unique_function<void()> Action);
+
   /// Defines how a runWithAST action is implicitly cancelled by other actions.
   enum ASTActionInvalidation {
     /// The request will run unless explicitly cancelled.
     NoInvalidation,
     /// The request will be implicitly cancelled by a subsequent update().
     /// (Only if the request was not yet cancelled).
     /// Useful for requests that are generated by clients, without any explicit
     /// user action. These can otherwise e.g. force every version to be built.
public:
   // FIXME: remove this when there is proper index support via build system
   // integration.
   // FIXME: move to ClangdServer via createProcessingContext.
   static llvm::Optional<llvm::StringRef> getFileBeingProcessedInContext();
 
   void profile(MemoryTree &MT) const;
 
 private:
+  void runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
+                        llvm::unique_function<void()> Action, Semaphore &Sem);
+
   const GlobalCompilationDatabase &CDB;
   Options Opts;
   std::unique_ptr<ParsingCallbacks> Callbacks; // not nullptr
   Semaphore Barrier;
+  Semaphore QuickRunBarrier;
   llvm::StringMap<std::unique_ptr<FileData>> Files;
   std::unique_ptr<ASTCache> IdleASTs;
   // None when running tasks synchronously and non-None when running tasks
   // asynchronously.
   llvm::Optional<AsyncTaskRunner> PreambleTasks;
   llvm::Optional<AsyncTaskRunner> WorkerThreads;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/TUScheduler.cpp

 //===--- TUScheduler.cpp -----------------------------------------*-C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // TUScheduler manages a worker per active file. This ASTWorker processes

 };
 
 TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
                          const Options &Opts,
                          std::unique_ptr<ParsingCallbacks> Callbacks)
     : CDB(CDB), Opts(Opts),
       Callbacks(Callbacks ? move(Callbacks)
                           : std::make_unique<ParsingCallbacks>()),
-      Barrier(Opts.AsyncThreadsCount),
+      Barrier(Opts.AsyncThreadsCount), QuickRunBarrier(Opts.AsyncThreadsCount),
       IdleASTs(
           std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)) {
   // Avoid null checks everywhere.
   if (!Opts.ContextProvider) {
     this->Opts.ContextProvider = [](llvm::StringRef) {
       return Context::current().clone();
     };
   }
llvm::StringMap<std::string> TUScheduler::getAllFileContents() const {
   llvm::StringMap<std::string> Results;
   for (auto &It : Files)
     Results.try_emplace(It.getKey(), It.getValue()->Contents);
   return Results;
 }
 
 void TUScheduler::run(llvm::StringRef Name, llvm::StringRef Path,
                       llvm::unique_function<void()> Action) {
+  runWithSemaphore(Name, Path, std::move(Action), Barrier);
+}
+
+void TUScheduler::runQuick(llvm::StringRef Name, llvm::StringRef Path,
+                           llvm::unique_function<void()> Action) {
+  // Use QuickRunBarrier to serialize quick tasks: we are ignoring
+  // the parallelism level set by the user, don't abuse it
+  runWithSemaphore(Name, Path, std::move(Action), QuickRunBarrier);
+}
+
+void TUScheduler::runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
+                                   llvm::unique_function<void()> Action,
+                                   Semaphore &Sem) {
   if (!PreambleTasks) {
     WithContext WithProvidedContext(Opts.ContextProvider(Path));
     return Action();
   }
-  PreambleTasks->runAsync(Name, [this, Ctx = Context::current().clone(),
+  PreambleTasks->runAsync(Name, [this, &Sem, Ctx = Context::current().clone(),
                                  Path(Path.str()),
                                  Action = std::move(Action)]() mutable {
-    std::lock_guard<Semaphore> BarrierLock(Barrier);
+    std::lock_guard<Semaphore> BarrierLock(Sem);
     WithContext WC(std::move(Ctx));
     WithContext WithProvidedContext(Opts.ContextProvider(Path));
     Action();
   });
 }
 
 void TUScheduler::runWithAST(
     llvm::StringRef Name, PathRef File,