Use PointerSet<const Target> for TargetSet
Provide a faster and smaller implementation for TargetSet
based on the PointerSet<> template. Measurements shows that
this speeds up Fuchsia 'gn gen' time by about 600ms, and
reduces RAM usage by 150 MiB.
BEFORE gn-main
Done. Made 173214 targets from 5389 files in 15658ms
Done. Made 173214 targets from 5389 files in 15721ms
Done. Made 173214 targets from 5389 files in 15869ms
Done. Made 173214 targets from 5389 files in 15954ms
Done. Made 173214 targets from 5389 files in 16235ms *
Done. Made 173214 targets from 5389 files in 16362ms
Done. Made 173214 targets from 5389 files in 16565ms
Done. Made 173214 targets from 5389 files in 16677ms
Done. Made 173214 targets from 5389 files in 17781ms
3402636
3403836 *
3415256
AFTER gn-target-set
Done. Made 173214 targets from 5389 files in 15042ms
Done. Made 173214 targets from 5389 files in 15143ms
Done. Made 173214 targets from 5389 files in 15436ms
Done. Made 173214 targets from 5389 files in 15642ms
Done. Made 173214 targets from 5389 files in 15649ms *
Done. Made 173214 targets from 5389 files in 15754ms
Done. Made 173214 targets from 5389 files in 15790ms
Done. Made 173214 targets from 5389 files in 16151ms
Done. Made 173214 targets from 5389 files in 16760ms
3252084
3255684 *
3264448
Change-Id: I51d6178cbaf91211355460cf587b78ccb149eb63
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/12583
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 69fbe7d..fd93879 100644
--- a/src/gn/analyzer.cc
+++ b/src/gn/analyzer.cc
@@ -55,10 +55,7 @@
}
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;
+ return l.intersection_with(r);
}
std::vector<std::string> GetStringVector(const base::DictionaryValue& dict,
@@ -402,8 +399,7 @@
void Analyzer::FilterTarget(const Target* target,
TargetSet* seen,
TargetSet* filtered) const {
- if (seen->find(target) == seen->end()) {
- seen->insert(target);
+ if (seen->add(target)) {
if (target->output_type() != Target::GROUP) {
filtered->insert(target);
} else {
diff --git a/src/gn/command_path.cc b/src/gn/command_path.cc
index b9ed780..4ee1345 100644
--- a/src/gn/command_path.cc
+++ b/src/gn/command_path.cc
@@ -220,9 +220,7 @@
// If we've already checked this one, stop. This should be after the above
// check for a known-good check, because known-good ones will always have
// been previously visited.
- if (visited.find(current_target) == visited.end())
- visited.insert(current_target);
- else
+ if (!visited.add(current_target))
continue;
// Add public deps for this target to the queue.
diff --git a/src/gn/command_refs.cc b/src/gn/command_refs.cc
index 7fcdb26..9c83877 100644
--- a/src/gn/command_refs.cc
+++ b/src/gn/command_refs.cc
@@ -65,10 +65,7 @@
bool print_children = true;
if (seen_targets) {
- if (seen_targets->find(target) == seen_targets->end()) {
- // New target, mark it visited.
- seen_targets->insert(target);
- } else {
+ if (!seen_targets->add(target)) {
// Already seen.
print_children = false;
// Only print "..." if something is actually elided, which means that
@@ -112,9 +109,8 @@
void RecursiveCollectRefs(const DepMap& dep_map,
const Target* target,
TargetSet* results) {
- if (results->find(target) != results->end())
+ if (!results->add(target))
return; // Already found this target.
- results->insert(target);
RecursiveCollectChildRefs(dep_map, target, results);
}
diff --git a/src/gn/compile_commands_writer.cc b/src/gn/compile_commands_writer.cc
index 1aa2d1a..16f2a1a 100644
--- a/src/gn/compile_commands_writer.cc
+++ b/src/gn/compile_commands_writer.cc
@@ -349,7 +349,7 @@
// Preserve the original ordering of all_targets
// to allow easier debugging and testing.
for (auto& target : all_targets) {
- if (visited.count(target)) {
+ if (visited.contains(target)) {
preserved_targets.push_back(target);
}
}
@@ -358,8 +358,7 @@
void CompileCommandsWriter::VisitDeps(const Target* target,
TargetSet* visited) {
- if (!visited->count(target)) {
- visited->insert(target);
+ if (visited->add(target)) {
for (const auto& pair : target->GetDeps(Target::DEPS_ALL)) {
VisitDeps(pair.ptr, visited);
}
diff --git a/src/gn/desc_builder.cc b/src/gn/desc_builder.cc
index 957fde0..3b6ab23 100644
--- a/src/gn/desc_builder.cc
+++ b/src/gn/desc_builder.cc
@@ -100,9 +100,8 @@
void RecursiveCollectChildDeps(const Target* target, TargetSet* result);
void RecursiveCollectDeps(const Target* target, TargetSet* result) {
- if (result->find(target) != result->end())
+ if (!result->add(target))
return; // Already did this target.
- result->insert(target);
RecursiveCollectChildDeps(target, result);
}
@@ -660,10 +659,7 @@
bool print_children = true;
if (seen_targets) {
- if (seen_targets->find(cur_dep) == seen_targets->end()) {
- // New target, mark it visited.
- seen_targets->insert(cur_dep);
- } else {
+ if (!seen_targets->add(cur_dep)) {
// Already seen.
print_children = false;
// Only print "..." if something is actually elided, which means that
diff --git a/src/gn/json_project_writer.cc b/src/gn/json_project_writer.cc
index f5f7f5a..a54e254 100644
--- a/src/gn/json_project_writer.cc
+++ b/src/gn/json_project_writer.cc
@@ -45,8 +45,7 @@
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);
+ if (deps->add(pair.ptr)) {
AddTargetDependencies(pair.ptr, deps);
}
}
diff --git a/src/gn/metadata_walk.cc b/src/gn/metadata_walk.cc
index bb2675e..331deeb 100644
--- a/src/gn/metadata_walk.cc
+++ b/src/gn/metadata_walk.cc
@@ -13,12 +13,11 @@
Err* err) {
std::vector<Value> result;
for (const auto* target : targets_to_walk) {
- auto pair = targets_walked->insert(target);
- if (pair.second) {
+ if (targets_walked->add(target)) {
if (!target->GetMetadata(keys_to_extract, keys_to_walk, rebase_dir, false,
&result, targets_walked, err))
return std::vector<Value>();
}
}
return result;
-}
\ No newline at end of file
+}
diff --git a/src/gn/ninja_target_writer.cc b/src/gn/ninja_target_writer.cc
index 9ddebd9..efcf991 100644
--- a/src/gn/ninja_target_writer.cc
+++ b/src/gn/ninja_target_writer.cc
@@ -245,7 +245,7 @@
// Additional hard dependencies passed in. These are usually empty or small,
// and we don't want to duplicate the explicit hard deps of the target.
for (const Target* target : additional_hard_deps) {
- if (!hard_deps.count(target))
+ if (!hard_deps.contains(target))
input_deps_targets.push_back(target);
}
diff --git a/src/gn/qt_creator_writer.cc b/src/gn/qt_creator_writer.cc
index 983bccb..94fed8f 100644
--- a/src/gn/qt_creator_writer.cc
+++ b/src/gn/qt_creator_writer.cc
@@ -75,9 +75,8 @@
void QtCreatorWriter::CollectDeps(const Target* target) {
for (const auto& dep : target->GetDeps(Target::DEPS_ALL)) {
const Target* dep_target = dep.ptr;
- if (targets_.count(dep_target))
+ if (!targets_.add(dep_target))
continue;
- targets_.insert(dep_target);
CollectDeps(dep_target);
}
}
@@ -86,7 +85,8 @@
auto all_targets = builder_.GetAllResolvedTargets();
if (root_target_name_.empty()) {
- targets_ = TargetSet(all_targets.begin(), all_targets.end());
+ targets_.clear();
+ targets_.insert(all_targets.begin(), all_targets.end());
return true;
}
diff --git a/src/gn/target.cc b/src/gn/target.cc
index b9e58f3..1dcd88d 100644
--- a/src/gn/target.cc
+++ b/src/gn/target.cc
@@ -74,9 +74,8 @@
bool consider_object_files,
bool check_data_deps,
TargetSet* seen_targets) {
- if (seen_targets->find(target) != seen_targets->end())
+ if (!seen_targets->add(target))
return false; // Already checked this one and it's not found.
- seen_targets->insert(target);
// Assume that we have relatively few generated inputs so brute-force
// searching here is OK. If this becomes a bottleneck, consider storing
@@ -161,9 +160,8 @@
const LabelPattern** failure_pattern) {
static const char kIndentPath[] = " ";
- if (visited->find(target) != visited->end())
+ if (!visited->add(target))
return true; // Already checked this target.
- visited->insert(target);
if (check_this) {
// Check this target against the given list of patterns.
@@ -1248,8 +1246,7 @@
if (next.string_value().empty()) {
for (const auto& dep : all_deps) {
// If we haven't walked this dep yet, go down into it.
- auto pair = targets_walked->insert(dep.ptr);
- if (pair.second) {
+ if (targets_walked->add(dep.ptr)) {
if (!dep.ptr->GetMetadata(keys_to_extract, keys_to_walk, rebase_dir,
false, result, targets_walked, err))
return false;
@@ -1277,8 +1274,7 @@
// Match against the label with the toolchain.
if (dep.label.GetUserVisibleName(true) == canonicalize_next_label) {
// If we haven't walked this dep yet, go down into it.
- auto pair = targets_walked->insert(dep.ptr);
- if (pair.second) {
+ if (targets_walked->add(dep.ptr)) {
if (!dep.ptr->GetMetadata(keys_to_extract, keys_to_walk, rebase_dir,
false, result, targets_walked, err))
return false;
diff --git a/src/gn/target.h b/src/gn/target.h
index f870548..590d78e 100644
--- a/src/gn/target.h
+++ b/src/gn/target.h
@@ -21,6 +21,7 @@
#include "gn/lib_file.h"
#include "gn/metadata.h"
#include "gn/output_file.h"
+#include "gn/pointer_set.h"
#include "gn/rust_values.h"
#include "gn/source_file.h"
#include "gn/swift_values.h"
@@ -32,7 +33,7 @@
class Target;
class Toolchain;
-using TargetSet = std::set<const Target*>;
+using TargetSet = PointerSet<const Target>;
class Target : public Item {
public:
diff --git a/src/gn/xcode_writer.cc b/src/gn/xcode_writer.cc
index a71206c..5e57ec9 100644
--- a/src/gn/xcode_writer.cc
+++ b/src/gn/xcode_writer.cc
@@ -906,9 +906,7 @@
if (pair.ptr->output_type() != Target::EXECUTABLE)
continue;
- auto iter = targets.find(pair.ptr);
- if (iter != targets.end())
- targets.erase(iter);
+ targets.erase(pair.ptr);
}
}
