Optimize Target::EnsureFileIsGeneratedByDependency()
For targets with a large number of generated inputs, it's very common
for those generated inputs to be generated by the same target, and for
them to be listed in the same order within that target. As such, start
the search for subsequent generated sources where the previous one was
found.
In Chromium, some large target onresolve() steps were taking 500-800ms
on my machine to run this check. With this change, they now take ~1ms.
//third_party/blink/renderer/bindings/modules/v8:v8 was the slowest one.
It has a large tree of public_deps, and lot of generated source files
(~5000), and has deps with a large number of outputs (mojom).
I at first tried creating creating an unordered_set<OutputFile> for
targets with large number of outputs, but that did not noticeably
improve runtime.
Hyperfine Benchmark from Chromium:
Before:
Time (mean ± σ): 8.001 s ± 0.203 s [User: 62.682 s, System: 53.541 s]
Range (min … max): 7.773 s … 8.362 s 10 runs
After:
Time (mean ± σ): 7.349 s ± 0.251 s [User: 66.903 s, System: 50.486 s]
Range (min … max): 6.974 s … 7.655 s 10 runs
Bug: chromium:398002893
Change-Id: I4989052ecaf6e3cc4ad2acb4cb5c94e98e83c5a1
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/18960
Reviewed-by: David Turner <digit@google.com>
Commit-Queue: Andrew Grieve <agrieve@google.com>
diff --git a/src/gn/target.cc b/src/gn/target.cc
index ca08459..bc8bae1 100644
--- a/src/gn/target.cc
+++ b/src/gn/target.cc
@@ -27,6 +27,14 @@
using ConfigSet = std::set<const Config*>;
+// Used to optimize the search for a target generating a given output file.
+// Keeps track of the last target and index where the file was found, so that
+// the next search can start from there.
+struct CheckSourceGeneratedCursor {
+ const Target* target = nullptr;
+ size_t index = 0;
+};
+
// Merges the public configs from the given target to the given config list.
void MergePublicConfigsFrom(const Target* from_target,
UniqueVector<LabelConfigPair>* dest) {
@@ -64,6 +72,29 @@
"Either mark it test-only or don't do this dependency.");
}
+// Return true if |file| is a direct output of |target|. Uses |cursor| to speed
+// up consecutive calls to this function when files are checked in the same
+// order as a target's real outputs, which happens extremely often.
+bool HasDirectOutput(const Target* target,
+ const OutputFile& file,
+ CheckSourceGeneratedCursor* cursor) {
+ const auto& computed_outputs = target->computed_outputs();
+ size_t start_index = target == cursor->target ? cursor->index + 1 : 0;
+ size_t count = computed_outputs.size();
+
+ for (size_t i = 0; i < count; ++i) {
+ size_t idx = (start_index + i) % count;
+
+ const auto& cur = computed_outputs[idx];
+ if (file == cur) {
+ cursor->target = target;
+ cursor->index = idx;
+ return true;
+ }
+ }
+ return false;
+}
+
// Set check_private_deps to true for the first invocation since a target
// can see all of its dependencies. For recursive invocations this will be set
// to false to follow only public dependency paths.
@@ -80,16 +111,13 @@
bool check_private_deps,
bool consider_object_files,
bool check_data_deps,
- TargetSet* seen_targets) {
+ TargetSet* seen_targets,
+ CheckSourceGeneratedCursor* cursor) {
if (!seen_targets->add(target))
return false; // Already checked this one and it's not found.
- // Assume that we have relatively few generated inputs so brute-force
- // searching here is OK. If this becomes a bottleneck, consider storing
- // computed_outputs as a hash set.
- for (const OutputFile& cur : target->computed_outputs()) {
- if (file == cur)
- return true;
+ if (HasDirectOutput(target, file, cursor)) {
+ return true;
}
if (file == target->write_runtime_deps_output())
@@ -107,12 +135,30 @@
}
}
+ // Only check private deps if requested.
+ if (check_private_deps) {
+ for (const auto& pair : target->private_deps()) {
+ if (EnsureFileIsGeneratedByDependency(pair.ptr, file, false,
+ consider_object_files,
+ check_data_deps, seen_targets, cursor))
+ return true; // Found a path.
+ }
+ if (target->output_type() == Target::CREATE_BUNDLE) {
+ for (const auto* dep : target->bundle_data().bundle_deps()) {
+ if (EnsureFileIsGeneratedByDependency(dep, file, false,
+ consider_object_files,
+ check_data_deps, seen_targets, cursor))
+ return true; // Found a path.
+ }
+ }
+ }
+
if (check_data_deps) {
check_data_deps = false; // Consider only direct data_deps.
for (const auto& pair : target->data_deps()) {
if (EnsureFileIsGeneratedByDependency(pair.ptr, file, false,
consider_object_files,
- check_data_deps, seen_targets))
+ check_data_deps, seen_targets, cursor))
return true; // Found a path.
}
}
@@ -122,30 +168,57 @@
for (const auto& pair : target->public_deps()) {
if (EnsureFileIsGeneratedByDependency(pair.ptr, file, false,
consider_object_files,
- check_data_deps, seen_targets))
+ check_data_deps, seen_targets, cursor))
return true; // Found a path.
}
- // Only check private deps if requested.
- if (check_private_deps) {
- for (const auto& pair : target->private_deps()) {
- if (EnsureFileIsGeneratedByDependency(pair.ptr, file, false,
- consider_object_files,
- check_data_deps, seen_targets))
- return true; // Found a path.
- }
- if (target->output_type() == Target::CREATE_BUNDLE) {
- for (const auto* dep : target->bundle_data().bundle_deps()) {
- if (EnsureFileIsGeneratedByDependency(dep, file, false,
- consider_object_files,
- check_data_deps, seen_targets))
- return true; // Found a path.
- }
- }
- }
return false;
}
+void CheckSourceGenerated(const Target* source_target,
+ const SourceFile& source,
+ CheckSourceGeneratedCursor* cursor) {
+ const auto& build_settings = source_target->settings()->build_settings();
+ if (!IsStringInOutputDir(build_settings->build_dir(), source.value()))
+ return; // Not in output dir, this is OK.
+
+ // Tell the scheduler about unknown files. This will be noted for later so
+ // the list of files written by the GN build itself (often response files)
+ // can be filtered out of this list.
+ OutputFile out_file(build_settings, source);
+ TargetSet seen_targets;
+ bool check_data_deps = false;
+ bool consider_object_files = false;
+
+ // If this is not the first file, start by looking where the last one was
+ // found.
+ if (cursor->target) {
+ bool check_private_deps = cursor->target == source_target;
+ if (EnsureFileIsGeneratedByDependency(
+ cursor->target, out_file, check_private_deps, consider_object_files,
+ check_data_deps, &seen_targets, cursor))
+ return;
+ }
+
+ bool check_private_deps = true;
+ if (!EnsureFileIsGeneratedByDependency(
+ source_target, out_file, check_private_deps, consider_object_files,
+ check_data_deps, &seen_targets, cursor)) {
+ seen_targets.clear();
+ // Allow dependency to be through data_deps for files generated by gn.
+ check_data_deps =
+ g_scheduler->IsFileGeneratedByWriteRuntimeDeps(out_file) ||
+ g_scheduler->IsFileGeneratedByTarget(source);
+ // Check object files (much slower and very rare) only if the "normal"
+ // output check failed.
+ consider_object_files = !check_data_deps;
+ if (!EnsureFileIsGeneratedByDependency(
+ source_target, out_file, check_private_deps, consider_object_files,
+ check_data_deps, &seen_targets, cursor))
+ g_scheduler->AddUnknownGeneratedInput(source_target, source);
+ }
+}
+
// check_this indicates if the given target should be matched against the
// patterns. It should be set to false for the first call since assert_no_deps
// shouldn't match the target itself.
@@ -1157,46 +1230,19 @@
// to the build dir.
//
// See Scheduler::AddUnknownGeneratedInput's declaration for more.
+ CheckSourceGeneratedCursor cursor;
for (const SourceFile& file : sources_)
- CheckSourceGenerated(file);
+ CheckSourceGenerated(this, file, &cursor);
+
+ cursor.target = nullptr;
for (ConfigValuesIterator iter(this); !iter.done(); iter.Next()) {
for (const SourceFile& file : iter.cur().inputs())
- CheckSourceGenerated(file);
+ CheckSourceGenerated(this, file, &cursor);
}
// TODO(agrieve): Check all_libs_ here as well (those that are source files).
// http://crbug.com/571731
}
-void Target::CheckSourceGenerated(const SourceFile& source) const {
- if (!IsStringInOutputDir(settings()->build_settings()->build_dir(),
- source.value()))
- return; // Not in output dir, this is OK.
-
- // Tell the scheduler about unknown files. This will be noted for later so
- // the list of files written by the GN build itself (often response files)
- // can be filtered out of this list.
- OutputFile out_file(settings()->build_settings(), source);
- TargetSet seen_targets;
- bool check_data_deps = false;
- bool consider_object_files = false;
- if (!EnsureFileIsGeneratedByDependency(this, out_file, true,
- consider_object_files, check_data_deps,
- &seen_targets)) {
- seen_targets.clear();
- // Allow dependency to be through data_deps for files generated by gn.
- check_data_deps =
- g_scheduler->IsFileGeneratedByWriteRuntimeDeps(out_file) ||
- g_scheduler->IsFileGeneratedByTarget(source);
- // Check object files (much slower and very rare) only if the "normal"
- // output check failed.
- consider_object_files = !check_data_deps;
- if (!EnsureFileIsGeneratedByDependency(this, out_file, true,
- consider_object_files,
- check_data_deps, &seen_targets))
- g_scheduler->AddUnknownGeneratedInput(this, source);
- }
-}
-
bool Target::GetMetadata(const std::vector<std::string>& keys_to_extract,
const std::vector<std::string>& keys_to_walk,
const SourceDir& rebase_dir,
diff --git a/src/gn/target.h b/src/gn/target.h
index b6947f9..4b0bed9 100644
--- a/src/gn/target.h
+++ b/src/gn/target.h
@@ -488,7 +488,6 @@
bool CheckTestonly(Err* err) const;
bool CheckAssertNoDeps(Err* err) const;
void CheckSourcesGenerated() const;
- void CheckSourceGenerated(const SourceFile& source) const;
bool CheckSourceSetLanguages(Err* err) const;
OutputType output_type_ = UNKNOWN;
