[clangd][NFC] Cache ClangTidy check globs to speed up createChecks

[njames93]

Summary

Build a fast factory for creating clang-tidy check lists based off a glob string.

Compile Globs into a BitVector representation that can be used to build a vector of checks without having to consult the glob string. Cache these representations as most invocations will be using the same glob string.

[njames93]

Pre-allocate both vectors

[carlosgalvezp]

Haven't looked much in detail so apologies if my comment is stupid - can't CachedGlobList be used for this purpose? Should be a one-liner change I think.

[njames93]

In D117529#3251949, @carlosgalvezp wrote:

Haven't looked much in detail so apologies if my comment is stupid - can't CachedGlobList be used for this purpose? Should be a one-liner change I think.

Not a stupid question, but CachedGlobList is doing something very different. That's just caching the result of strings when they are passed to a glob to simplify re-evaluation of the same string.
However this implementation is about avoiding the need to check any check-names when building the list of checks. It's also thread safe unlike CachedGlobList.

[sammccall]

Happy to take a look at this, but is there a particular motive for optimizing this?
Looking at some profiles this appears to be something like 0.1-0.5ms in fairly complex configurations.

clang-tools-extra/clangd/ParsedAST.cpp

288

if it's possible, it seems like this class really wants to be a function

292

I wonder if a global map is overkill (and the locking maybe undesirable).

In practice, this is being called in a loop on a single thread (the AST worker thread), with no other calls on that thread.
The idea with caching is that the checks globs are usually the same, that is especially true for parses of the main file.

So maybe we could just use a single-entry thread_local cache, with no map and no locking?

295

why cache a bitmap instead of the vector<factory> directly?

448–449

we need to be more careful with static state than this. This adds global destructors and we need to suppress them. (e.g. by using new without delete)

[njames93]

Address comments

[njames93]

Remove now unnecessary changes in ClangTidyModule.
Fix Cache miss reporting

clang-tools-extra/clangd/ParsedAST.cpp

 //===--- ParsedAST.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
 //
 //===----------------------------------------------------------------------===//
 
 #include "ParsedAST.h"
 #include "../clang-tidy/ClangTidyCheck.h"
 #include "../clang-tidy/ClangTidyDiagnosticConsumer.h"
 #include "../clang-tidy/ClangTidyModuleRegistry.h"
+#include "../clang-tidy/GlobList.h"
 #include "AST.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "Diagnostics.h"
 #include "Feature.h"
 #include "FeatureModule.h"
 #include "Headers.h"
 #include "HeuristicResolver.h"
if (NeedsWerrorExclusion) {
       // FIXME: there's no API to suppress -Werror for single diagnostics.
       // In some cases with sub-groups, we may end up erroneously
       // downgrading diagnostics that were -Werror in the compile command.
       Diags.setDiagnosticGroupWarningAsError(Group, false);
     }
   }
 }
 
+std::vector<std::unique_ptr<tidy::ClangTidyCheck>>
+buildChecks(tidy::ClangTidyContext *Context) {
+  using FactoryFunc = std::function<std::unique_ptr<tidy::ClangTidyCheck>(
+      llvm::StringRef, tidy::ClangTidyContext *)>;
+  const llvm::Optional<std::string> &CheckGlob = Context->getOptions().Checks;
+  if (!CheckGlob || CheckGlob->empty())
+    return {};
+  thread_local std::pair<std::string,
+                         std::vector<std::pair<std::string, FactoryFunc>>>
+      Cached;
+  static std::atomic<size_t> CacheMiss, CacheAccess;
+  ++CacheAccess;
+  if (*CheckGlob != Cached.first) {
+    ++CacheMiss;
+    vlog("ClangTidyCheck factory cache miss '{0:P2}%'\n"
+         "Rebuilding ClangTidyChecks factory with new glob '{1}'",
+         static_cast<double>(CacheMiss) / CacheAccess, *CheckGlob);
+    Cached.first.assign(CheckGlob->data(), CheckGlob->size());
+    Cached.second.clear();
+    tidy::ClangTidyCheckFactories CTFactories;
+    for (const auto &E : tidy::ClangTidyModuleRegistry::entries())
+      E.instantiate()->addCheckFactories(CTFactories);
+    tidy::GlobList Glob(*CheckGlob);
+    for (const auto &Check : CTFactories) {
+      if (Glob.contains(Check.getKey()))
+        Cached.second.emplace_back(Check.getKey(), Check.getValue());
+    }
+  }
+  std::vector<std::unique_ptr<tidy::ClangTidyCheck>> Result;
+  Result.reserve(Cached.second.size());
+  for (auto &Factory : Cached.second) {
+    Result.push_back(Factory.second(Factory.first, Context));
+  }
+  return Result;
+}
 } // namespace
 
 llvm::Optional<ParsedAST>
 ParsedAST::build(llvm::StringRef Filename, const ParseInputs &Inputs,
                  std::unique_ptr<clang::CompilerInvocation> CI,
                  llvm::ArrayRef<Diag> CompilerInvocationDiags,
                  std::shared_ptr<const PreambleData> Preamble) {
   trace::Span Tracer("BuildAST");
ParsedAST::build(llvm::StringRef Filename, const ParseInputs &Inputs,
   std::vector<std::unique_ptr<tidy::ClangTidyCheck>> CTChecks;
   ast_matchers::MatchFinder CTFinder;
   llvm::Optional<tidy::ClangTidyContext> CTContext;
   llvm::Optional<IncludeFixer> FixIncludes;
   llvm::DenseMap<diag::kind, DiagnosticsEngine::Level> OverriddenSeverity;
   // No need to run clang-tidy or IncludeFixerif we are not going to surface
   // diagnostics.
   if (PreserveDiags) {
     trace::Span Tracer("ClangTidyInit");
-    tidy::ClangTidyCheckFactories CTFactories;
-    for (const auto &E : tidy::ClangTidyModuleRegistry::entries())
-      E.instantiate()->addCheckFactories(CTFactories);
     CTContext.emplace(std::make_unique<tidy::DefaultOptionsProvider>(
         tidy::ClangTidyGlobalOptions(), ClangTidyOpts));
     CTContext->setDiagnosticsEngine(&Clang->getDiagnostics());
     CTContext->setASTContext(&Clang->getASTContext());
     CTContext->setCurrentFile(Filename);
-    CTChecks = CTFactories.createChecks(CTContext.getPointer());
+    CTChecks = buildChecks(CTContext.getPointer());
     llvm::erase_if(CTChecks, [&](const auto &Check) {
       return !Check->isLanguageVersionSupported(CTContext->getLangOpts());
     });
     Preprocessor *PP = &Clang->getPreprocessor();
     for (const auto &Check : CTChecks) {
       Check->registerPPCallbacks(Clang->getSourceManager(), PP, PP);
       Check->registerMatchers(&CTFinder);
     }