Simplify InheritedLibraries
This CL simplifies the implementation of InheritedLibraries
to use a UniqueVector<const Target*> as well as a parallel
vector of booleans (for the public flags). This doesn't
change the semantics of this type.
Combined with the previous CL, measurements show that this
saves about 10% of 'gn gen' time, and 8% of peak RAM usage
for both Fuchsia and Chromium.
Bug: None
--------------------------------------------------------
For Fuchsia
gn-main
Done. Made 184670 targets from 5446 files in 12960ms
Done. Made 184670 targets from 5446 files in 13277ms
Done. Made 184670 targets from 5446 files in 13713ms *
Done. Made 184670 targets from 5446 files in 13882ms
Done. Made 184670 targets from 5446 files in 14259ms
3271324
3275512
3280504 *
3282032
3293832
gn-inherited-libraries
Done. Made 184670 targets from 5446 files in 12248ms
Done. Made 184670 targets from 5446 files in 12267ms
Done. Made 184670 targets from 5446 files in 12326ms *
Done. Made 184670 targets from 5446 files in 12697ms
Done. Made 184670 targets from 5446 files in 12770ms
DIFF = 13713 - 12326 = 1387ms (-10%)
3026696
3027940
3032296 *
3035976
3037732
DIFF = 3280504 - 3032296 = 248208 = 242 MiB (-7.5%)
For Chromium
gn-main
Done. Made 17155 targets from 3025 files in 3289ms
Done. Made 17155 targets from 3025 files in 3314ms
Done. Made 17155 targets from 3025 files in 3328ms *
Done. Made 17155 targets from 3025 files in 3362ms
Done. Made 17155 targets from 3025 files in 3488ms
666764
670480
674792 *
676516
692592
gn-inherited-libraries
Done. Made 17155 targets from 3025 files in 2987ms
Done. Made 17155 targets from 3025 files in 3008ms
Done. Made 17155 targets from 3025 files in 3001ms *
Done. Made 17155 targets from 3025 files in 3021ms
Done. Made 17155 targets from 3025 files in 3106ms
DIFF = 3328 - 3001 = 327ms (-9.8%)
613600
616748
618460 *
621900
626768
DIFF = 674792 - 618460 = 56332 = 55 MiB (-8.3%)
Change-Id: I245367f121cb2b2d542db171146b494209793028
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/12700
Reviewed-by: Brett Wilson <brettw@chromium.org>
Commit-Queue: David Turner <digit@google.com>
diff --git a/src/gn/inherited_libraries.cc b/src/gn/inherited_libraries.cc
index 37e0b97..977e97d 100644
--- a/src/gn/inherited_libraries.cc
+++ b/src/gn/inherited_libraries.cc
@@ -10,49 +10,23 @@
InheritedLibraries::~InheritedLibraries() = default;
-std::vector<const Target*> InheritedLibraries::GetOrdered() const {
- std::vector<const Target*> result;
- result.resize(map_.size());
-
- // The indices in the map should be from 0 to the number of items in the
- // map, so insert directly into the result (with some sanity checks).
- for (const auto& pair : map_) {
- size_t index = pair.second.index;
- DCHECK(index < result.size());
- DCHECK(!result[index]);
- result[index] = pair.first;
- }
-
- return result;
-}
-
std::vector<std::pair<const Target*, bool>>
InheritedLibraries::GetOrderedAndPublicFlag() const {
std::vector<std::pair<const Target*, bool>> result;
- result.resize(map_.size());
-
- for (const auto& pair : map_) {
- size_t index = pair.second.index;
- DCHECK(index < result.size());
- DCHECK(!result[index].first);
- result[index] = std::make_pair(pair.first, pair.second.is_public);
- }
-
+ result.reserve(targets_.size());
+ for (size_t i = 0; i < targets_.size(); ++i)
+ result.emplace_back(targets_[i], public_flags_[i]);
return result;
}
void InheritedLibraries::Append(const Target* target, bool is_public) {
// Try to insert a new node.
- auto insert_result =
- map_.insert(std::make_pair(target, Node(map_.size(), is_public)));
-
- if (!insert_result.second) {
- // Element already present, insert failed and insert_result indicates the
- // old one. The old one may need to have its public flag updated.
- if (is_public) {
- Node& existing_node = insert_result.first->second;
- existing_node.is_public = true;
- }
+ auto ret = targets_.PushBackWithIndex(target);
+ if (ret.first) {
+ public_flags_.push_back(is_public);
+ } else if (is_public) {
+ // Target already present, if |is_public|, set its flag.
+ public_flags_[ret.second] = true;
}
}
@@ -60,15 +34,19 @@
bool is_public) {
// Append all items in order, mark them public only if the're already public
// and we're adding them publicly.
- for (const auto& cur : other.GetOrderedAndPublicFlag())
- Append(cur.first, is_public && cur.second);
+ for (size_t i = 0; i < other.targets_.size(); ++i) {
+ Append(other.targets_[i], is_public && other.public_flags_[i]);
+ }
}
void InheritedLibraries::AppendPublicSharedLibraries(
const InheritedLibraries& other,
bool is_public) {
- for (const auto& cur : other.GetOrderedAndPublicFlag()) {
- if (cur.first->output_type() == Target::SHARED_LIBRARY && cur.second)
- Append(cur.first, is_public);
+ for (size_t i = 0; i < other.targets_.size(); ++i) {
+ const Target* target = other.targets_[i];
+ if (target->output_type() == Target::SHARED_LIBRARY &&
+ other.public_flags_[i]) {
+ Append(target, is_public);
+ }
}
}
diff --git a/src/gn/inherited_libraries.h b/src/gn/inherited_libraries.h
index 758e3c9..7a3fc25 100644
--- a/src/gn/inherited_libraries.h
+++ b/src/gn/inherited_libraries.h
@@ -7,10 +7,11 @@
#include <stddef.h>
-#include <map>
#include <utility>
#include <vector>
+#include "gn/unique_vector.h"
+
class Target;
// Represents an ordered uniquified set of all shared/static libraries for
@@ -30,7 +31,7 @@
// Returns the list of dependencies in order, optionally with the flag
// indicating whether the dependency is public.
- std::vector<const Target*> GetOrdered() const;
+ std::vector<const Target*> GetOrdered() const { return targets_.vector(); }
std::vector<std::pair<const Target*, bool>> GetOrderedAndPublicFlag() const;
// Adds a single dependency to the end of the list. See note on adding above.
@@ -52,16 +53,8 @@
bool is_public);
private:
- struct Node {
- Node() : index(static_cast<size_t>(-1)), is_public(false) {}
- Node(size_t i, bool p) : index(i), is_public(p) {}
-
- size_t index;
- bool is_public;
- };
-
- using LibraryMap = std::map<const Target*, Node>;
- LibraryMap map_;
+ UniqueVector<const Target*> targets_;
+ std::vector<bool> public_flags_;
InheritedLibraries(const InheritedLibraries&) = delete;
InheritedLibraries& operator=(const InheritedLibraries&) = delete;
