feat(3p/nix): Statically pass bindings capacity where possible r/1285

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 <git@lukegb.com>
Paired-With: Vincent Ambo <mail@tazj.in>
Paired-With: Perry Lorier <isomer@tvl.fyi>
Change-Id: I1858c161301a1cd0e83aeeb9a58839378869e71d
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1124
Tested-by: BuildkiteCI
Reviewed-by: lukegb <lukegb@tvl.fyi>
Reviewed-by: isomer <isomer@tvl.fyi>

1 files changed, 34 insertions, 22 deletions

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