Introduce TargetSet type Handling sets of target pointers is a very performance-critical operation in GN, and this is currently being done by instances of the std::set<const Target*> type, which is slow and memory hungry. This CL introduces the TargetSet type as an alias to std::set<const Target*>, and updates the source code to use it. A future CL will change the TargetSet implementation to a better one after this one. Change-Id: I6e01a14d4de2d238818c8c9dd963cda5cf9e66b8 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/12581 Commit-Queue: David Turner <digit@google.com> Reviewed-by: Brett Wilson <brettw@chromium.org>
diff --git a/src/gn/analyzer.cc b/src/gn/analyzer.cc index 7bb200c..69fbe7d 100644 --- a/src/gn/analyzer.cc +++ b/src/gn/analyzer.cc
@@ -47,16 +47,15 @@ std::set<Label> invalid_labels; }; -std::set<Label> LabelsFor(const std::set<const Target*>& targets) { +std::set<Label> LabelsFor(const TargetSet& targets) { std::set<Label> labels; for (auto* target : targets) labels.insert(target->label()); return labels; } -std::set<const Target*> Intersect(const std::set<const Target*>& l, - const std::set<const Target*>& r) { - std::set<const Target*> result; +TargetSet Intersect(const TargetSet& l, const TargetSet& r) { + TargetSet result; std::set_intersection(l.begin(), l.end(), r.begin(), r.end(), std::inserter(result, result.begin())); return result; @@ -316,7 +315,7 @@ std::set<const Item*> affected_items = GetAllAffectedItems(inputs.source_files); - std::set<const Target*> affected_targets; + TargetSet affected_targets; for (const Item* affected_item : affected_items) { if (affected_item->AsTarget()) affected_targets.insert(affected_item->AsTarget()); @@ -327,18 +326,18 @@ return OutputsToJSON(outputs, default_toolchain_, err); } - std::set<const Target*> root_targets; + TargetSet root_targets; for (const auto* item : all_items_) { if (item->AsTarget() && dep_map_.find(item) == dep_map_.end()) root_targets.insert(item->AsTarget()); } - std::set<const Target*> compile_targets = TargetsFor(inputs.compile_labels); + TargetSet compile_targets = TargetsFor(inputs.compile_labels); if (inputs.compile_included_all) { for (auto* root_target : root_targets) compile_targets.insert(root_target); } - std::set<const Target*> filtered_targets = Filter(compile_targets); + TargetSet filtered_targets = Filter(compile_targets); outputs.compile_labels = LabelsFor(Intersect(filtered_targets, affected_targets)); @@ -348,7 +347,7 @@ outputs.compile_labels.size() == filtered_targets.size()) outputs.compile_includes_all = true; - std::set<const Target*> test_targets = TargetsFor(inputs.test_labels); + TargetSet test_targets = TargetsFor(inputs.test_labels); outputs.test_labels = LabelsFor(Intersect(test_targets, affected_targets)); if (outputs.compile_labels.empty() && outputs.test_labels.empty()) @@ -380,9 +379,8 @@ return invalid_labels; } -std::set<const Target*> Analyzer::TargetsFor( - const std::set<Label>& labels) const { - std::set<const Target*> targets; +TargetSet Analyzer::TargetsFor(const std::set<Label>& labels) const { + TargetSet targets; for (const auto& label : labels) { auto it = labels_to_items_.find(label); if (it != labels_to_items_.end()) { @@ -393,18 +391,17 @@ return targets; } -std::set<const Target*> Analyzer::Filter( - const std::set<const Target*>& targets) const { - std::set<const Target*> seen; - std::set<const Target*> filtered; +TargetSet Analyzer::Filter(const TargetSet& targets) const { + TargetSet seen; + TargetSet filtered; for (const auto* target : targets) FilterTarget(target, &seen, &filtered); return filtered; } void Analyzer::FilterTarget(const Target* target, - std::set<const Target*>* seen, - std::set<const Target*>* filtered) const { + TargetSet* seen, + TargetSet* filtered) const { if (seen->find(target) == seen->end()) { seen->insert(target); if (target->output_type() != Target::GROUP) {
diff --git a/src/gn/analyzer.h b/src/gn/analyzer.h index 2ffdb52..77aed2a 100644 --- a/src/gn/analyzer.h +++ b/src/gn/analyzer.h
@@ -13,6 +13,7 @@ #include "gn/item.h" #include "gn/label.h" #include "gn/source_file.h" +#include "gn/target.h" // An Analyzer can answer questions about a build graph. It is used // to answer queries for the `refs` and `analyze` commands, where we @@ -44,7 +45,7 @@ // Returns the set of all targets that have a label in the given set. // Invalid (or missing) labels will be ignored. - std::set<const Target*> TargetsFor(const std::set<Label>& labels) const; + TargetSet TargetsFor(const std::set<Label>& labels) const; // Returns a filtered set of the given targets, meaning that for each of the // given targets, @@ -66,13 +67,11 @@ // ones). // // This filtering behavior is also known as "pruning" the list of targets. - std::set<const Target*> Filter(const std::set<const Target*>& targets) const; + TargetSet Filter(const TargetSet& targets) const; // Filter an individual target and adds the results to filtered // (see Filter(), above). - void FilterTarget(const Target*, - std::set<const Target*>* seen, - std::set<const Target*>* filtered) const; + void FilterTarget(const Target*, TargetSet* seen, TargetSet* filtered) const; bool ItemRefersToFile(const Item* item, const SourceFile* file) const;
diff --git a/src/gn/command_meta.cc b/src/gn/command_meta.cc index 6ee5fe2..27897e2 100644 --- a/src/gn/command_meta.cc +++ b/src/gn/command_meta.cc
@@ -113,7 +113,7 @@ std::vector<std::string> walk_keys = base::SplitString( walk_keys_str, ",", base::TRIM_WHITESPACE, base::SPLIT_WANT_NONEMPTY); Err err; - std::set<const Target*> targets_walked; + TargetSet targets_walked; SourceDir rebase_source_dir(rebase_dir); // When SourceDir constructor is supplied with an empty string, // a trailing slash will be added. This prevent SourceDir::is_null()
diff --git a/src/gn/command_path.cc b/src/gn/command_path.cc index a82c90d..b9ed780 100644 --- a/src/gn/command_path.cc +++ b/src/gn/command_path.cc
@@ -179,7 +179,7 @@ work_queue.push_back(initial_stack); // Track checked targets to avoid checking the same once more than once. - std::set<const Target*> visited; + TargetSet visited; while (!work_queue.empty()) { PathVector current_path = work_queue.front();
diff --git a/src/gn/command_refs.cc b/src/gn/command_refs.cc index dc27f56..7fcdb26 100644 --- a/src/gn/command_refs.cc +++ b/src/gn/command_refs.cc
@@ -26,7 +26,7 @@ namespace { -using TargetSet = std::set<const Target*>; +using TargetSet = TargetSet; using TargetVector = std::vector<const Target*>; // Maps targets to the list of targets that depend on them.
diff --git a/src/gn/commands.cc b/src/gn/commands.cc index da6514b..24a16b1 100644 --- a/src/gn/commands.cc +++ b/src/gn/commands.cc
@@ -612,14 +612,12 @@ } } -void FilterAndPrintTargetSet(bool indent, - const std::set<const Target*>& targets) { +void FilterAndPrintTargetSet(bool indent, const TargetSet& targets) { std::vector<const Target*> target_vector(targets.begin(), targets.end()); FilterAndPrintTargets(indent, &target_vector); } -void FilterAndPrintTargetSet(const std::set<const Target*>& targets, - base::ListValue* out) { +void FilterAndPrintTargetSet(const TargetSet& targets, base::ListValue* out) { std::vector<const Target*> target_vector(targets.begin(), targets.end()); FilterAndPrintTargets(&target_vector, out); }
diff --git a/src/gn/commands.h b/src/gn/commands.h index 54a1a9d..4824b79 100644 --- a/src/gn/commands.h +++ b/src/gn/commands.h
@@ -217,10 +217,8 @@ void FilterAndPrintTargets(std::vector<const Target*>* targets, base::ListValue* out); -void FilterAndPrintTargetSet(bool indent, - const std::set<const Target*>& targets); -void FilterAndPrintTargetSet(const std::set<const Target*>& targets, - base::ListValue* out); +void FilterAndPrintTargetSet(bool indent, const TargetSet& targets); +void FilterAndPrintTargetSet(const TargetSet& targets, base::ListValue* out); // Computes which targets reference the given file and also stores how the // target references the file.
diff --git a/src/gn/compile_commands_writer.cc b/src/gn/compile_commands_writer.cc index c0b94d1..1aa2d1a 100644 --- a/src/gn/compile_commands_writer.cc +++ b/src/gn/compile_commands_writer.cc
@@ -338,7 +338,7 @@ const std::set<std::string>& target_filters_set) { std::vector<const Target*> preserved_targets; - std::set<const Target*> visited; + TargetSet visited; for (auto& target : all_targets) { if (target_filters_set.count(target->label().name())) { VisitDeps(target, &visited); @@ -357,7 +357,7 @@ } void CompileCommandsWriter::VisitDeps(const Target* target, - std::set<const Target*>* visited) { + TargetSet* visited) { if (!visited->count(target)) { visited->insert(target); for (const auto& pair : target->GetDeps(Target::DEPS_ALL)) {
diff --git a/src/gn/compile_commands_writer.h b/src/gn/compile_commands_writer.h index adc2986..03006c8 100644 --- a/src/gn/compile_commands_writer.h +++ b/src/gn/compile_commands_writer.h
@@ -36,7 +36,7 @@ private: // This function visits the deps graph of a target in a DFS fashion. - static void VisitDeps(const Target* target, std::set<const Target*>* visited); + static void VisitDeps(const Target* target, TargetSet* visited); }; #endif // TOOLS_GN_COMPILE_COMMANDS_WRITER_H_
diff --git a/src/gn/desc_builder.cc b/src/gn/desc_builder.cc index bcd30f3..957fde0 100644 --- a/src/gn/desc_builder.cc +++ b/src/gn/desc_builder.cc
@@ -97,11 +97,9 @@ return dir.value(); } -void RecursiveCollectChildDeps(const Target* target, - std::set<const Target*>* result); +void RecursiveCollectChildDeps(const Target* target, TargetSet* result); -void RecursiveCollectDeps(const Target* target, - std::set<const Target*>* result) { +void RecursiveCollectDeps(const Target* target, TargetSet* result) { if (result->find(target) != result->end()) return; // Already did this target. result->insert(target); @@ -109,8 +107,7 @@ RecursiveCollectChildDeps(target, result); } -void RecursiveCollectChildDeps(const Target* target, - std::set<const Target*>* result) { +void RecursiveCollectChildDeps(const Target* target, TargetSet* result) { for (const auto& pair : target->GetDeps(Target::DEPS_ALL)) RecursiveCollectDeps(pair.ptr, result); } @@ -646,7 +643,7 @@ // set is null, all dependencies will be printed. void RecursivePrintDeps(base::ListValue* out, const Target* target, - std::set<const Target*>* seen_targets, + TargetSet* seen_targets, int indent_level) { // Combine all deps into one sorted list. std::vector<LabelTargetPair> sorted_deps; @@ -694,7 +691,7 @@ RecursivePrintDeps(res.get(), target_, nullptr, 0); } else { // Don't recurse into duplicates. - std::set<const Target*> seen_targets; + TargetSet seen_targets; RecursivePrintDeps(res.get(), target_, &seen_targets, 0); } } else { // not tree @@ -702,7 +699,7 @@ // Collect the deps to display. if (all_) { // Show all dependencies. - std::set<const Target*> all_deps; + TargetSet all_deps; RecursiveCollectChildDeps(target_, &all_deps); commands::FilterAndPrintTargetSet(all_deps, res.get()); } else {
diff --git a/src/gn/json_project_writer.cc b/src/gn/json_project_writer.cc index a8aad90..f5f7f5a 100644 --- a/src/gn/json_project_writer.cc +++ b/src/gn/json_project_writer.cc
@@ -43,8 +43,7 @@ namespace { -void AddTargetDependencies(const Target* target, - std::set<const Target*>* deps) { +void AddTargetDependencies(const Target* target, TargetSet* deps) { for (const auto& pair : target->GetDeps(Target::DEPS_LINKED)) { if (deps->find(pair.ptr) == deps->end()) { deps->insert(pair.ptr); @@ -71,7 +70,7 @@ } commands::FilterTargetsByPatterns(all_targets, filters, targets); - std::set<const Target*> target_set(targets->begin(), targets->end()); + TargetSet target_set(targets->begin(), targets->end()); for (const auto* target : *targets) AddTargetDependencies(target, &target_set);
diff --git a/src/gn/metadata_walk.cc b/src/gn/metadata_walk.cc index 19011cf..bb2675e 100644 --- a/src/gn/metadata_walk.cc +++ b/src/gn/metadata_walk.cc
@@ -9,7 +9,7 @@ const std::vector<std::string>& keys_to_extract, const std::vector<std::string>& keys_to_walk, const SourceDir& rebase_dir, - std::set<const Target*>* targets_walked, + TargetSet* targets_walked, Err* err) { std::vector<Value> result; for (const auto* target : targets_to_walk) {
diff --git a/src/gn/metadata_walk.h b/src/gn/metadata_walk.h index 011ed07..2b659d6 100644 --- a/src/gn/metadata_walk.h +++ b/src/gn/metadata_walk.h
@@ -20,7 +20,7 @@ const std::vector<std::string>& keys_to_extract, const std::vector<std::string>& keys_to_walk, const SourceDir& rebase_dir, - std::set<const Target*>* targets_walked, + TargetSet* targets_walked, Err* err); #endif // TOOLS_GN_METADATAWALK_H_
diff --git a/src/gn/metadata_walk_unittest.cc b/src/gn/metadata_walk_unittest.cc index 4fcb31d..9f83fa3 100644 --- a/src/gn/metadata_walk_unittest.cc +++ b/src/gn/metadata_walk_unittest.cc
@@ -50,7 +50,7 @@ std::vector<std::string> walk_keys; Err err; - std::set<const Target*> targets_walked; + TargetSet targets_walked; std::vector<Value> result = WalkMetadata(targets, data_keys, walk_keys, SourceDir(), &targets_walked, &err); EXPECT_FALSE(err.has_error()); @@ -62,7 +62,7 @@ expected.push_back(Value(nullptr, false)); EXPECT_EQ(result, expected); - std::set<const Target*> expected_walked_targets; + TargetSet expected_walked_targets; expected_walked_targets.insert(&one); expected_walked_targets.insert(&two); EXPECT_EQ(targets_walked, expected_walked_targets); @@ -100,7 +100,7 @@ std::vector<std::string> walk_keys; Err err; - std::set<const Target*> targets_walked; + TargetSet targets_walked; std::vector<Value> result = WalkMetadata(targets, data_keys, walk_keys, SourceDir(), &targets_walked, &err); EXPECT_FALSE(err.has_error()); @@ -111,7 +111,7 @@ expected.push_back(Value(nullptr, true)); EXPECT_EQ(result, expected); - std::set<const Target*> expected_walked_targets; + TargetSet expected_walked_targets; expected_walked_targets.insert(&one); expected_walked_targets.insert(&two); EXPECT_EQ(targets_walked, expected_walked_targets); @@ -157,7 +157,7 @@ walk_keys.push_back("walk"); Err err; - std::set<const Target*> targets_walked; + TargetSet targets_walked; std::vector<Value> result = WalkMetadata(targets, data_keys, walk_keys, SourceDir(), &targets_walked, &err); EXPECT_FALSE(err.has_error()) << err.message(); @@ -167,7 +167,7 @@ expected.push_back(Value(nullptr, "foo")); EXPECT_EQ(result, expected) << result.size(); - std::set<const Target*> expected_walked_targets; + TargetSet expected_walked_targets; expected_walked_targets.insert(&one); expected_walked_targets.insert(&two); EXPECT_EQ(targets_walked, expected_walked_targets); @@ -197,7 +197,7 @@ walk_keys.push_back("walk"); Err err; - std::set<const Target*> targets_walked; + TargetSet targets_walked; std::vector<Value> result = WalkMetadata(targets, data_keys, walk_keys, SourceDir(), &targets_walked, &err); EXPECT_TRUE(result.empty());
diff --git a/src/gn/ninja_generated_file_target_writer.cc b/src/gn/ninja_generated_file_target_writer.cc index e1ad19f..994f322 100644 --- a/src/gn/ninja_generated_file_target_writer.cc +++ b/src/gn/ninja_generated_file_target_writer.cc
@@ -58,7 +58,7 @@ CHECK(target_->action_values().outputs().list().size() == 1U); contents = Value(target_->action_values().outputs().list()[0].origin(), Value::LIST); - std::set<const Target*> targets_walked; + TargetSet targets_walked; if (!target_->GetMetadata(target_->data_keys(), target_->walk_keys(), target_->rebase(), /*deps_only = */ true, &contents.list_value(), &targets_walked, &err)) {
diff --git a/src/gn/ninja_target_writer.cc b/src/gn/ninja_target_writer.cc index e85400f..9ddebd9 100644 --- a/src/gn/ninja_target_writer.cc +++ b/src/gn/ninja_target_writer.cc
@@ -232,7 +232,7 @@ // Hard dependencies that are direct or indirect dependencies. // These are large (up to 100s), hence why we check other - const std::set<const Target*>& hard_deps(target_->recursive_hard_deps()); + const TargetSet& hard_deps(target_->recursive_hard_deps()); for (const Target* target : hard_deps) { // BUNDLE_DATA should normally be treated as a data-only dependency // (see Target::IsDataOnly()). Only the CREATE_BUNDLE target, that actually
diff --git a/src/gn/qt_creator_writer.cc b/src/gn/qt_creator_writer.cc index b0fa05c..983bccb 100644 --- a/src/gn/qt_creator_writer.cc +++ b/src/gn/qt_creator_writer.cc
@@ -86,7 +86,7 @@ auto all_targets = builder_.GetAllResolvedTargets(); if (root_target_name_.empty()) { - targets_ = std::set<const Target*>(all_targets.begin(), all_targets.end()); + targets_ = TargetSet(all_targets.begin(), all_targets.end()); return true; }
diff --git a/src/gn/qt_creator_writer.h b/src/gn/qt_creator_writer.h index 4571ec1..552e300 100644 --- a/src/gn/qt_creator_writer.h +++ b/src/gn/qt_creator_writer.h
@@ -43,7 +43,7 @@ const Builder& builder_; base::FilePath project_prefix_; std::string root_target_name_; - std::set<const Target*> targets_; + TargetSet targets_; std::set<std::string> sources_; std::set<std::string> includes_; std::set<std::string> defines_;
diff --git a/src/gn/rust_project_writer.h b/src/gn/rust_project_writer.h index 5c5d453..3fbdedb 100644 --- a/src/gn/rust_project_writer.h +++ b/src/gn/rust_project_writer.h
@@ -31,7 +31,7 @@ private: // This function visits the deps graph of a target in a DFS fashion. - static void VisitDeps(const Target* target, std::set<const Target*>* visited); + static void VisitDeps(const Target* target, TargetSet* visited); }; #endif // TOOLS_GN_RUST_PROJECT_WRITER_H_
diff --git a/src/gn/target.cc b/src/gn/target.cc index 0d225b6..b9e58f3 100644 --- a/src/gn/target.cc +++ b/src/gn/target.cc
@@ -73,7 +73,7 @@ bool check_private_deps, bool consider_object_files, bool check_data_deps, - std::set<const Target*>* seen_targets) { + TargetSet* seen_targets) { if (seen_targets->find(target) != seen_targets->end()) return false; // Already checked this one and it's not found. seen_targets->insert(target); @@ -156,7 +156,7 @@ bool RecursiveCheckAssertNoDeps(const Target* target, bool check_this, const std::vector<LabelPattern>& assert_no, - std::set<const Target*>* visited, + TargetSet* visited, std::string* failure_path_str, const LabelPattern** failure_pattern) { static const char kIndentPath[] = " "; @@ -1144,7 +1144,7 @@ if (assert_no_deps_.empty()) return true; - std::set<const Target*> visited; + TargetSet visited; std::string failure_path_str; const LabelPattern* failure_pattern = nullptr; @@ -1186,7 +1186,7 @@ // 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); - std::set<const Target*> seen_targets; + TargetSet seen_targets; bool check_data_deps = false; bool consider_object_files = false; if (!EnsureFileIsGeneratedByDependency(this, out_file, true, @@ -1212,7 +1212,7 @@ const SourceDir& rebase_dir, bool deps_only, std::vector<Value>* result, - std::set<const Target*>* targets_walked, + TargetSet* targets_walked, Err* err) const { std::vector<Value> next_walk_keys; std::vector<Value> current_result;
diff --git a/src/gn/target.h b/src/gn/target.h index ee5061b..f870548 100644 --- a/src/gn/target.h +++ b/src/gn/target.h
@@ -29,8 +29,11 @@ class DepsIteratorRange; class Settings; +class Target; class Toolchain; +using TargetSet = std::set<const Target*>; + class Target : public Item { public: enum OutputType { @@ -172,7 +175,7 @@ const SourceDir& rebase_dir, bool deps_only, std::vector<Value>* result, - std::set<const Target*>* targets_walked, + TargetSet* targets_walked, Err* err) const; // GeneratedFile-related methods. @@ -328,9 +331,7 @@ return all_weak_frameworks_; } - const std::set<const Target*>& recursive_hard_deps() const { - return recursive_hard_deps_; - } + const TargetSet& recursive_hard_deps() const { return recursive_hard_deps_; } std::vector<LabelPattern>& friends() { return friends_; } const std::vector<LabelPattern>& friends() const { return friends_; } @@ -500,7 +501,7 @@ // All hard deps from this target and all dependencies. Filled in when this // target is marked resolved. This will not include the current target. - std::set<const Target*> recursive_hard_deps_; + TargetSet recursive_hard_deps_; std::vector<LabelPattern> friends_; std::vector<LabelPattern> assert_no_deps_;
diff --git a/src/gn/target_unittest.cc b/src/gn/target_unittest.cc index 0dcff0c..f8cbcd1 100644 --- a/src/gn/target_unittest.cc +++ b/src/gn/target_unittest.cc
@@ -1403,7 +1403,7 @@ Err err; std::vector<Value> result; - std::set<const Target*> targets; + TargetSet targets; one.GetMetadata(data_keys, walk_keys, SourceDir(), false, &result, &targets, &err); EXPECT_FALSE(err.has_error()); @@ -1444,7 +1444,7 @@ Err err; std::vector<Value> result; - std::set<const Target*> targets; + TargetSet targets; one.GetMetadata(data_keys, walk_keys, SourceDir(), false, &result, &targets, &err); EXPECT_FALSE(err.has_error()); @@ -1491,7 +1491,7 @@ Err err; std::vector<Value> result; - std::set<const Target*> targets; + TargetSet targets; one.GetMetadata(data_keys, walk_keys, SourceDir(), false, &result, &targets, &err); EXPECT_FALSE(err.has_error()); @@ -1540,7 +1540,7 @@ Err err; std::vector<Value> result; - std::set<const Target*> targets; + TargetSet targets; one.GetMetadata(data_keys, walk_keys, SourceDir(), false, &result, &targets, &err); EXPECT_FALSE(err.has_error()) << err.message(); @@ -1573,7 +1573,7 @@ Err err; std::vector<Value> result; - std::set<const Target*> targets; + TargetSet targets; one.GetMetadata(data_keys, walk_keys, SourceDir(), false, &result, &targets, &err); EXPECT_TRUE(err.has_error());
diff --git a/src/gn/xcode_writer.cc b/src/gn/xcode_writer.cc index 19938cd..a71206c 100644 --- a/src/gn/xcode_writer.cc +++ b/src/gn/xcode_writer.cc
@@ -894,7 +894,7 @@ // Filter out all target of type EXECUTABLE that are direct dependency of // a BUNDLE_DATA target (under the assumption that they will be part of a // CREATE_BUNDLE target generating an application bundle). - std::set<const Target*> targets(all_targets.begin(), all_targets.end()); + TargetSet targets(all_targets.begin(), all_targets.end()); for (const Target* target : all_targets) { if (!target->settings()->is_default()) continue;