diff --git a/clang-tools-extra/clangd/TidyProvider.cpp b/clang-tools-extra/clangd/TidyProvider.cpp
--- a/clang-tools-extra/clangd/TidyProvider.cpp
+++ b/clang-tools-extra/clangd/TidyProvider.cpp
@@ -77,12 +77,24 @@
   }
 };
 
+llvm::SmallString<256> pathAppend(PathRef Path, llvm::StringRef Tail) {
+  llvm::SmallString<256> ConfigPath(Path);
+  llvm::sys::path::append(ConfigPath, Tail);
+  return ConfigPath;
+}
+
 // Access to combined config from .clang-tidy files governing a source file.
 // Each config file is cached and the caches are shared for affected sources.
 //
 // FIXME: largely duplicates config::Provider::fromAncestorRelativeYAMLFiles.
 // Potentially useful for compile_commands.json too. Extract?
 class DotClangTidyTree {
+  struct DirectoryNode {
+    DirectoryNode(PathRef File) : Cache(File), Parent(nullptr) {}
+    DotClangTidyCache Cache;
+    DirectoryNode *Parent;
+  };
+
   const ThreadsafeFS &FS;
   std::string RelPath;
   std::chrono::steady_clock::duration MaxStaleness;
@@ -91,45 +103,79 @@
   // Keys are the ancestor directory, not the actual config path within it.
   // We only insert into this map, so pointers to values are stable forever.
   // Mutex guards the map itself, not the values (which are threadsafe).
-  mutable llvm::StringMap<DotClangTidyCache> Cache;
-
-public:
-  DotClangTidyTree(const ThreadsafeFS &FS)
-      : FS(FS), RelPath(".clang-tidy"), MaxStaleness(std::chrono::seconds(5)) {}
+  // We store values as linked lists pointing to their parent directories nodes,
+  // this saves quering the map for each component of a path.
+  mutable llvm::StringMap<DirectoryNode> Cache;
 
-  void apply(tidy::ClangTidyOptions &Result, PathRef AbsPath) {
+  /// Ensures there is a FileCache for each .clang-tidy file in the directory
+  /// tree up to \p AbsPath and returns a linked list structure pointing to the
+  /// first item.
+  /// \pre \p AbsPath is an absolute path to a file.
+  DirectoryNode *getNode(PathRef AbsPath) {
     namespace path = llvm::sys::path;
     assert(path::is_absolute(AbsPath));
 
-    // Compute absolute paths to all ancestors (substrings of P.Path).
-    // Ensure cache entries for each ancestor exist in the map.
-    llvm::SmallVector<DotClangTidyCache *> Caches;
-    {
-      std::lock_guard<std::mutex> Lock(Mu);
-      for (auto Ancestor = absoluteParent(AbsPath); !Ancestor.empty();
-           Ancestor = absoluteParent(Ancestor)) {
-        auto It = Cache.find(Ancestor);
-        // Assemble the actual config file path only if needed.
-        if (It == Cache.end()) {
-          llvm::SmallString<256> ConfigPath = Ancestor;
-          path::append(ConfigPath, RelPath);
-          It = Cache.try_emplace(Ancestor, ConfigPath.str()).first;
-        }
-        Caches.push_back(&It->second);
+    // AbsPath should be pointing to a file, get the directory.
+    auto Ancestor = absoluteParent(AbsPath);
+    assert(!Ancestor.empty() &&
+           "There should be at least 1 path component to traverse");
+
+    std::lock_guard<std::mutex> Lock(Mu);
+
+    auto It = Cache.find(Ancestor);
+    // This is the hot path. After invoking this method on a given path once,
+    // The path will stay in the map for the life of this object, saving any
+    // further lookup.
+    if (LLVM_LIKELY(It != Cache.end()))
+      return &It->getValue();
+
+    // Build the FileCache for this item and store a pointer to its parent node,
+    // this will be filled in when we process the next component in the path.
+    DirectoryNode *Result =
+        &Cache.try_emplace(Ancestor, pathAppend(Ancestor, RelPath).str())
+             .first->getValue();
+    DirectoryNode **ParentPtr = &Result->Parent;
+
+    // Skip the first item as we have already processed it.
+    for (Ancestor = absoluteParent(Ancestor); !Ancestor.empty();
+         Ancestor = absoluteParent(Ancestor)) {
+
+      It = Cache.find(Ancestor);
+      if (It != Cache.end()) {
+        // We have found a relative parent already in the map. Update the childs
+        // parent pointer to this, then stop. This items Parent should contain
+        // the tree below it already.
+        *ParentPtr = &It->getValue();
+        break;
       }
+
+      // The item isn't in the cache, so assemble it.
+      auto *Node =
+          &Cache.try_emplace(Ancestor, pathAppend(Ancestor, RelPath).str())
+               .first->getValue();
+      *ParentPtr = Node;
+      // Keep track of this nodes parent pointer for the next iteration.
+      ParentPtr = &Node->Parent;
     }
-    // Finally query each individual file.
-    // This will take a (per-file) lock for each file that actually exists.
+    return Result;
+  }
+
+public:
+  DotClangTidyTree(const ThreadsafeFS &FS)
+      : FS(FS), RelPath(".clang-tidy"), MaxStaleness(std::chrono::seconds(5)) {}
+
+  void apply(tidy::ClangTidyOptions &Result, PathRef AbsPath) {
     std::chrono::steady_clock::time_point FreshTime =
         std::chrono::steady_clock::now() - MaxStaleness;
     llvm::SmallVector<std::shared_ptr<const tidy::ClangTidyOptions>>
         OptionStack;
-    for (const DotClangTidyCache *Cache : Caches)
-      if (auto Config = Cache->get(FS, FreshTime)) {
+    for (auto *DirNode = getNode(AbsPath); DirNode; DirNode = DirNode->Parent) {
+      if (auto Config = DirNode->Cache.get(FS, FreshTime)) {
         OptionStack.push_back(std::move(Config));
         if (!OptionStack.back()->InheritParentConfig.getValueOr(false))
           break;
       }
+    }
     unsigned Order = 1u;
     for (auto &Option : llvm::reverse(OptionStack))
       Result.mergeWith(*Option, Order++);