Optimize HeaderChecker by parallelizing ReachabilityCache pre-calculation and removing lock contention.
This change introduces a pre-calculation phase in HeaderChecker::Run
that concurrently populates the ReachabilityCache for all relevant
targets using a WorkerPool. It also eliminates lock contention during
the file-checking phase by using atomic completion flags and a lock-free
fast path in ReachabilityCache::SearchForDependencyTo.
Key optimizations:
- Concurrent BFS pre-calculation during HeaderChecker::Run.
- Reusing the WorkerPool across pre-calculation and file-checking phases.
- Lock-free dependency lookup using std::atomic<bool> completion flags
with acquire/release semantics in the common case where the cache is warm.
- Significantly reduces lock contention (shared_mutex) on macOS.
Verified with existing HeaderChecker unittests and profiling on
Chromium.
Benchmark 1: ./gn_main gen --root=/Users/tikuta/chromium/src --check
/Users/tikuta/chromium/src/out/no_clang_modules
Time (mean ± σ): 6.306 s ± 0.025 s [User: 27.219 s, System: 21.382 s]
Range (min … max): 6.283 s … 6.333 s 5 runs
Benchmark 2: ./gn_optimized gen --root=/Users/tikuta/chromium/src
--check /Users/tikuta/chromium/src/out/no_clang_modules
Time (mean ± σ): 6.083 s ± 0.024 s [User: 27.499 s, System: 26.226 s]
Range (min … max): 6.049 s … 6.112 s 5 runs
Summary
./gn_optimized gen --root=/Users/tikuta/chromium/src --check /Users/tikuta/chromium/src/out/no_clang_modules ran
1.04 ± 0.01 times faster than ./gn_main gen --root=/Users/tikuta/chromium/src --check /Users/tikuta/chromium/src/out/no_clang_modules
Bug: 484862257
Change-Id: I4c9609f0b57693a1a209f4c36b810bb1597a39a9
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/21260
Reviewed-by: David Turner <digit@google.com>
Reviewed-by: Sylvain Defresne <sdefresne@chromium.org>
Commit-Queue: Takuto Ikuta <tikuta@google.com>
diff --git a/src/gn/header_checker.cc b/src/gn/header_checker.cc
index aba451b..8044896 100644
--- a/src/gn/header_checker.cc
+++ b/src/gn/header_checker.cc
@@ -163,7 +163,46 @@
if (check->IsBinary())
AddTargetToFileMap(check, &files_to_check);
}
- RunCheckOverFiles(files_to_check, force_check);
+
+ WorkerPool pool;
+ {
+ ScopedTrace precompute_trace(TraceItem::TRACE_CHECK_HEADERS,
+ "Precompute reachability");
+ std::set<const Target*> targets_to_precompute;
+ for (const auto& file : files_to_check) {
+ for (const auto& target_info : file.second) {
+ if (target_info.target->check_includes())
+ targets_to_precompute.insert(target_info.target);
+ }
+ }
+
+ if (!targets_to_precompute.empty()) {
+ task_count_.Increment();
+ for (const auto* target : targets_to_precompute) {
+ task_count_.Increment();
+ pool.PostTask([this, target]() {
+ ReachabilityCache& cache = GetReachabilityCacheForTarget(target);
+ cache.PerformDependencyWalk(true);
+ cache.PerformDependencyWalk(false);
+ if (!task_count_.Decrement()) {
+ std::unique_lock<std::mutex> lock(task_count_lock_);
+ task_count_cv_.notify_one();
+ }
+ });
+ }
+
+ if (!task_count_.Decrement()) {
+ std::unique_lock<std::mutex> lock(task_count_lock_);
+ task_count_cv_.notify_one();
+ }
+
+ std::unique_lock<std::mutex> lock(task_count_lock_);
+ while (!task_count_.IsZero())
+ task_count_cv_.wait(lock);
+ }
+ }
+
+ RunCheckOverFiles(files_to_check, force_check, &pool);
if (errors_.empty())
return true;
@@ -171,8 +210,9 @@
return false;
}
-void HeaderChecker::RunCheckOverFiles(const FileMap& files, bool force_check) {
- WorkerPool pool;
+void HeaderChecker::RunCheckOverFiles(const FileMap& files,
+ bool force_check,
+ WorkerPool* pool) {
task_count_.Increment();
for (const auto& file : files) {
@@ -204,11 +244,14 @@
continue;
task_count_.Increment();
- pool.PostTask([this, targets = std::move(targets_to_check),
- file = file.first]() { DoWork(targets, file); });
+ pool->PostTask([this, targets = std::move(targets_to_check),
+ file = file.first]() { DoWork(targets, file); });
}
- task_count_.Decrement();
+ if (!task_count_.Decrement()) {
+ std::unique_lock<std::mutex> lock(task_count_lock_);
+ task_count_cv_.notify_one();
+ }
// Wait for all tasks posted by this method to complete.
std::unique_lock<std::mutex> auto_lock(task_count_lock_);
@@ -328,12 +371,13 @@
void HeaderChecker::ReachabilityCache::PerformDependencyWalk(bool permitted) {
// Conduct the actual BFS.
+ if (permitted ? permitted_complete_.load(std::memory_order_relaxed)
+ : any_complete_.load(std::memory_order_relaxed)) {
+ return;
+ }
+
BreadcrumbTable& breadcrumbs =
permitted ? permitted_breadcrumbs_ : any_breadcrumbs_;
- bool& complete = permitted ? permitted_complete_ : any_complete_;
-
- if (complete)
- return;
// work_queue maintains a queue of targets which need to be considered as part
// of dependency chain, in the order they were first traversed. Each time a
@@ -364,28 +408,30 @@
}
}
}
- complete = true;
+ if (permitted) {
+ permitted_complete_.store(true, std::memory_order_release);
+ } else {
+ any_complete_.store(true, std::memory_order_release);
+ }
}
bool HeaderChecker::ReachabilityCache::SearchForDependencyTo(
const Target* search_for,
bool permitted,
Chain* chain) {
- {
- std::shared_lock<std::shared_mutex> read_lock(lock_);
- if (permitted ? permitted_complete_ : any_complete_) {
- return SearchBreadcrumbs(search_for, permitted, chain);
- }
+ if (permitted ? permitted_complete_.load(std::memory_order_acquire)
+ : any_complete_.load(std::memory_order_acquire)) {
+ return SearchBreadcrumbs(search_for, permitted, chain);
}
{
std::unique_lock<std::shared_mutex> write_lock(lock_);
- if (!(permitted ? permitted_complete_ : any_complete_)) {
+ if (!(permitted ? permitted_complete_.load(std::memory_order_relaxed)
+ : any_complete_.load(std::memory_order_relaxed))) {
PerformDependencyWalk(permitted);
}
}
- std::shared_lock<std::shared_mutex> read_lock(lock_);
return SearchBreadcrumbs(search_for, permitted, chain);
}
diff --git a/src/gn/header_checker.h b/src/gn/header_checker.h
index 083272f..c3c688b 100644
--- a/src/gn/header_checker.h
+++ b/src/gn/header_checker.h
@@ -6,6 +6,7 @@
#define TOOLS_GN_HEADER_CHECKER_H_
#include <array>
+#include <atomic>
#include <condition_variable>
#include <functional>
#include <map>
@@ -28,6 +29,7 @@
class InputFile;
class SourceFile;
class Target;
+class WorkerPool;
namespace base {
class FilePath;
@@ -196,20 +198,19 @@
bool permitted,
Chain* chain);
+ // Conducts a breadth-first search through the dependency graph to find a
+ // shortest chain from source_target_.
+ void PerformDependencyWalk(bool permitted);
+
const Target* source_target() const { return source_target_; }
private:
// Reconstructs the shortest dependency chain to the given target if it was
// found during a previous walk of the given type. Returns true on success.
- // Assumes the lock is held.
bool SearchBreadcrumbs(const Target* search_for,
bool permitted,
Chain* chain) const;
- // Conducts a breadth-first search through the dependency graph to find a
- // shortest chain from source_target_. Assumes unique lock is held.
- void PerformDependencyWalk(bool permitted);
-
const Target* source_target_;
mutable std::shared_mutex lock_;
@@ -218,8 +219,8 @@
// Breadcrumbs for the shortest path of any type.
BreadcrumbTable any_breadcrumbs_;
- bool permitted_complete_ = false;
- bool any_complete_ = false;
+ std::atomic<bool> permitted_complete_ = false;
+ std::atomic<bool> any_complete_ = false;
};
struct TargetInfo {
@@ -242,7 +243,9 @@
// Backend for Run() that takes the list of files to check. The errors_ list
// will be populate on failure.
- void RunCheckOverFiles(const FileMap& flies, bool force_check);
+ void RunCheckOverFiles(const FileMap& files,
+ bool force_check,
+ WorkerPool* pool);
void DoWork(const std::vector<const Target*>& targets,
const SourceFile& file);
