[gn] Optimize Value::LIST with Copy-On-Write using nullptr To reduce the execution time of `gn gen`, the internal holding of Value::LIST was changed from `std::vector<Value>` to `scoped_refptr<ValueList>` to enable Copy-On-Write (COW). This reduces unnecessary deep copies and allocation overhead for large lists, significantly improving performance. Performance benchmark comparing this optimization to the main branch: Benchmark 1: gn_unoptimized gen out/Default Time (mean ± σ): 2.384 s ± 0.085 s [User: 23.577 s, System: 20.115 s] Benchmark 2: gn_optimized gen out/Default Time (mean ± σ): 2.051 s ± 0.043 s [User: 21.155 s, System: 19.339 s] Summary gn_optimized ran 1.16 ± 0.05 times faster than gn_unoptimized Bug: 484863025 Change-Id: I08a3d8f5bc2dd9c794fb06a99de48ec0c36e18d8 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/21340 Commit-Queue: Takuto Ikuta <tikuta@google.com> Reviewed-by: Sylvain Defresne <sdefresne@chromium.org> Reviewed-by: David Turner <digit@google.com>
diff --git a/src/gn/value.cc b/src/gn/value.cc index c3bb9b5..43e2118 100644 --- a/src/gn/value.cc +++ b/src/gn/value.cc
@@ -11,6 +11,10 @@ #include "base/strings/string_util.h" #include "gn/scope.h" +ValueList::ValueList() = default; +ValueList::ValueList(std::vector<Value> v) : values_(std::move(v)) {} +ValueList::~ValueList() = default; + // NOTE: Cannot use = default here due to the use of a union member. Value::Value() {} @@ -28,7 +32,7 @@ new (&string_value_) std::string(); break; case LIST: - new (&list_value_) std::vector<Value>(); + new (&list_ptr_) scoped_refptr<ValueList>(); break; case SCOPE: new (&scope_value_) std::unique_ptr<Scope>(); @@ -65,7 +69,7 @@ new (&string_value_) std::string(other.string_value_); break; case LIST: - new (&list_value_) std::vector<Value>(other.list_value_); + new (&list_ptr_) scoped_refptr<ValueList>(other.list_ptr_); break; case SCOPE: new (&scope_value_) std::unique_ptr<Scope>( @@ -90,7 +94,7 @@ new (&string_value_) std::string(std::move(other.string_value_)); break; case LIST: - new (&list_value_) std::vector<Value>(std::move(other.list_value_)); + new (&list_ptr_) scoped_refptr<ValueList>(std::move(other.list_ptr_)); break; case SCOPE: new (&scope_value_) std::unique_ptr<Scope>(std::move(other.scope_value_)); @@ -121,10 +125,10 @@ string_value_.~string(); break; case LIST: - list_value_.~vector<Value>(); + list_ptr_.~scoped_refptr(); break; case SCOPE: - scope_value_.~unique_ptr<Scope>(); + scope_value_.~unique_ptr(); break; default:; } @@ -151,6 +155,30 @@ } } +std::vector<Value>& Value::list_value() { + DCHECK(type_ == LIST); + if (!list_ptr_) { + list_ptr_ = new ValueList(); + } else if (!list_ptr_->HasOneRef()) { + // Copy-On-Write (COW): If this ValueList is shared with other Value objects + // (reference count is > 1), we must not modify the shared vector directly. + // Doing so would incorrectly mutate the other Values sharing this data. + // Instead, we create a deep copy of the vector for this Value to safely + // modify. + list_ptr_ = new ValueList(list_ptr_->values_); + } + return list_ptr_->values_; +} + +const std::vector<Value>& Value::list_value() const { + DCHECK(type_ == LIST); + if (!list_ptr_) { + static const std::vector<Value>* empty_list = new std::vector<Value>(); + return *empty_list; + } + return list_ptr_->values_; +} + void Value::SetScopeValue(std::unique_ptr<Scope> scope) { DCHECK(type_ == SCOPE); scope_value_ = std::move(scope); @@ -191,10 +219,13 @@ return string_value_; case LIST: { std::string result = "["; - for (size_t i = 0; i < list_value_.size(); i++) { - if (i > 0) - result += ", "; - result += list_value_[i].ToString(true); + if (list_ptr_) { + const std::vector<Value>& list = list_value(); + for (size_t i = 0; i < list.size(); i++) { + if (i > 0) + result += ", "; + result += list[i].ToString(true); + } } result.push_back(']'); return result; @@ -240,13 +271,11 @@ case Value::STRING: return string_value() == other.string_value(); case Value::LIST: - if (list_value().size() != other.list_value().size()) + if (list_ptr_ == other.list_ptr_) + return true; + if (!list_ptr_ || !other.list_ptr_) return false; - for (size_t i = 0; i < list_value().size(); i++) { - if (list_value()[i] != other.list_value()[i]) - return false; - } - return true; + return list_value() == other.list_value(); case Value::SCOPE: return scope_value()->CheckCurrentScopeValuesEqual(other.scope_value()); case Value::NONE:
diff --git a/src/gn/value.h b/src/gn/value.h index fd16c6b..d963447 100644 --- a/src/gn/value.h +++ b/src/gn/value.h
@@ -9,12 +9,29 @@ #include <map> #include <memory> +#include <vector> #include "base/logging.h" +#include "base/memory/ref_counted.h" +#include "base/memory/scoped_refptr.h" #include "gn/err.h" class ParseNode; class Scope; +class Value; + +class ValueList : public base::RefCountedThreadSafe<ValueList> { + public: + ValueList(); + ValueList(std::vector<Value> v); + + private: + friend class base::RefCountedThreadSafe<ValueList>; + friend class Value; + ~ValueList(); + + std::vector<Value> values_; +}; // Represents a variable value in the interpreter. class Value { @@ -84,14 +101,8 @@ return string_value_; } - std::vector<Value>& list_value() { - DCHECK(type_ == LIST); - return list_value_; - } - const std::vector<Value>& list_value() const { - DCHECK(type_ == LIST); - return list_value_; - } + std::vector<Value>& list_value(); + const std::vector<Value>& list_value() const; Scope* scope_value() { DCHECK(type_ == SCOPE); @@ -128,7 +139,11 @@ bool boolean_value_; int64_t int_value_; std::string string_value_; - std::vector<Value> list_value_; + // Used to implement Copy-On-Write for lists. + // By sharing the list data via a reference-counted pointer, we avoid + // expensive deep copies of large lists when Values are passed around or + // copied, only performing a real copy when a modification is attempted. + scoped_refptr<ValueList> list_ptr_; std::unique_ptr<Scope> scope_value_; }; };