From d5597b4784e04020b4ef4968a6887d4e22cc3edd Mon Sep 17 00:00:00 2001 From: Griffin Smith Date: Sun, 12 Jul 2020 17:29:45 -0400 Subject: feat(3p/nix): Statically pass bindings capacity where possible To aid in making the decision of where to (currently just statically) use a vector or btree as the backing implementation, add an extra constructor argument to Bindings::NewGC for a capacity, and use a (currently hardcoded at 32, for no good reason other than it felt like a reasonable number) pivot to switch between our possible backing implementations. Then, update all the call sites where it feels reasonable that we know the capacity statically to *pass* that capacity to the constructor. Paired-With: Luke Granger-Brown Paired-With: Vincent Ambo Paired-With: Perry Lorier Change-Id: I1858c161301a1cd0e83aeeb9a58839378869e71d Reviewed-on: https://cl.tvl.fyi/c/depot/+/1124 Tested-by: BuildkiteCI Reviewed-by: lukegb Reviewed-by: isomer --- third_party/nix/src/libexpr/attr-set.cc | 56 +++++++++++++++---------- third_party/nix/src/libexpr/attr-set.hh | 6 +-- third_party/nix/src/libexpr/common-eval-args.cc | 2 +- third_party/nix/src/libexpr/eval.cc | 4 +- third_party/nix/src/libexpr/get-drvs.cc | 2 +- 5 files changed, 39 insertions(+), 31 deletions(-) (limited to 'third_party') diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc index 053d7d6f6c..0c8dc0baa4 100644 --- a/third_party/nix/src/libexpr/attr-set.cc +++ b/third_party/nix/src/libexpr/attr-set.cc @@ -11,6 +11,8 @@ namespace nix { +constexpr size_t ATTRS_CAPACITY_PIVOT = 32; + BindingsIterator& BindingsIterator::operator++() { std::visit(util::overloaded{ [](AttributeMap::iterator& iter) { ++iter; }, @@ -132,27 +134,13 @@ void BTreeBindings::merge(Bindings& other) { } } -void EvalState::mkAttrs(Value& v, size_t capacity) { - clearValue(v); - v.type = tAttrs; - v.attrs = Bindings::NewGC(); - assert(v.attrs->begin() == v.attrs->begin()); - assert(v.attrs->end() == v.attrs->end()); - nrAttrsets++; - nrAttrsInAttrsets += capacity; -} - -/* Create a new attribute named 'name' on an existing attribute set stored - in 'vAttrs' and return the newly allocated Value which is associated with - this attribute. */ -Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) { - Value* v = allocValue(); - vAttrs.attrs->push_back(Attr(name, v)); - return v; -} - class VectorBindings : public Bindings { public: + VectorBindings() {}; + VectorBindings(size_t capacity) : attributes_() { + attributes_.reserve(capacity); + }; + size_t size() override; bool empty() override; void push_back(const Attr& attr) override; @@ -246,8 +234,32 @@ Bindings::iterator VectorBindings::end() { return BindingsIterator{attributes_.end()}; } -// TODO pick what to do based on size -Bindings* Bindings::NewGC() { return new (GC) BTreeBindings; } -// Bindings* Bindings::NewGC() { return new (GC) VectorBindings; } +Bindings* Bindings::NewGC(size_t capacity) { + if (capacity > ATTRS_CAPACITY_PIVOT) { + return new (GC) BTreeBindings; + } else { + return new (GC) VectorBindings(capacity); + } +} + +void EvalState::mkAttrs(Value& v, size_t capacity) { + clearValue(v); + v.type = tAttrs; + v.attrs = Bindings::NewGC(capacity); + assert(v.attrs->begin() == v.attrs->begin()); + assert(v.attrs->end() == v.attrs->end()); + nrAttrsets++; + nrAttrsInAttrsets += capacity; +} + +/* Create a new attribute named 'name' on an existing attribute set stored + in 'vAttrs' and return the newly allocated Value which is associated with + this attribute. */ +Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) { + Value* v = allocValue(); + vAttrs.attrs->push_back(Attr(name, v)); + return v; +} + } // namespace nix diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh index 3834eac419..55641a0203 100644 --- a/third_party/nix/src/libexpr/attr-set.hh +++ b/third_party/nix/src/libexpr/attr-set.hh @@ -67,13 +67,9 @@ class Bindings { public: typedef BindingsIterator iterator; - // Allocate a new attribute set that is visible to the garbage - // collector. - static Bindings* NewGC(); - // Allocate a new attribute set with a static capacity that is visible to the // garbage collector. - // static Bindings* NewGC(size_t capacity); + static Bindings* NewGC(size_t capacity = 0); // Return the number of contained elements. virtual size_t size() = 0; diff --git a/third_party/nix/src/libexpr/common-eval-args.cc b/third_party/nix/src/libexpr/common-eval-args.cc index fe8a6a02af..b3e3782732 100644 --- a/third_party/nix/src/libexpr/common-eval-args.cc +++ b/third_party/nix/src/libexpr/common-eval-args.cc @@ -33,7 +33,7 @@ MixEvalArgs::MixEvalArgs() { } Bindings* MixEvalArgs::getAutoArgs(EvalState& state) { - Bindings* res = Bindings::NewGC(); + Bindings* res = Bindings::NewGC(autoArgs.size()); for (auto& i : autoArgs) { Value* v = state.allocValue(); if (i.second[0] == 'E') { diff --git a/third_party/nix/src/libexpr/eval.cc b/third_party/nix/src/libexpr/eval.cc index f733a86a89..56e4006204 100644 --- a/third_party/nix/src/libexpr/eval.cc +++ b/third_party/nix/src/libexpr/eval.cc @@ -1240,9 +1240,9 @@ void ExprOpUpdate::eval(EvalState& state, Env& env, Value& dest) { state.nrOpUpdates++; - state.mkAttrs(dest, /* capacity = */ 0); + state.mkAttrs(dest, v1.attrs->size() + v2.attrs->size()); - /* Merge the sets, preferring values from the second set. */ + // Merge the sets, preferring values from the second set. dest.attrs->merge(*v1.attrs); dest.attrs->merge(*v2.attrs); } diff --git a/third_party/nix/src/libexpr/get-drvs.cc b/third_party/nix/src/libexpr/get-drvs.cc index 875c8ca2a0..d21e8ba896 100644 --- a/third_party/nix/src/libexpr/get-drvs.cc +++ b/third_party/nix/src/libexpr/get-drvs.cc @@ -294,7 +294,7 @@ bool DrvInfo::queryMetaBool(const std::string& name, bool def) { void DrvInfo::setMeta(const std::string& name, Value* v) { getMeta(); Bindings* old = meta; - meta = Bindings::NewGC(); + meta = Bindings::NewGC(old->size()); Symbol sym = state->symbols.Create(name); if (old != nullptr) { for (auto i : *old) { -- cgit 1.4.1