refactor(3p/nix/libexpr): Use range insertion to merge nix::Bindings r/1320

Instead of manually iterating over the two bindings to be combined,
this adds a new static method on the Bindings class which merges two
attribute sets by calling the range insertion operator over them.

In some anecdotal tests, this can lead to a ~10% speed bump -
depending on the specific operation.

Change-Id: I5dea03b0589a83a789d3a8a0fc81d0d9e6598371
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1216
Tested-by: BuildkiteCI
Reviewed-by: glittershark <grfn@gws.fyi>

3 files changed, 25 insertions, 18 deletions

diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index d44df990ad1e..f1f40454c3f8 100644
--- a/third_party/nix/src/libexpr/attr-set.cc
+++ b/third_party/nix/src/libexpr/attr-set.cc
@@ -33,7 +33,7 @@ void Bindings::push_back(const Attr& attr) {
   }
 }
 
-size_t Bindings::size() { return attributes_.size(); }
+size_t Bindings::size() const { return attributes_.size(); }
 
 bool Bindings::empty() { return attributes_.empty(); }
 
@@ -56,13 +56,6 @@ Bindings::iterator Bindings::begin() { return attributes_.begin(); }
 
 Bindings::iterator Bindings::end() { return attributes_.end(); }
 
-void Bindings::merge(const Bindings& other) {
-  assert(this != &ZERO_BINDINGS);
-  for (auto& [key, value] : other.attributes_) {
-    this->attributes_.insert_or_assign(key, value);
-  }
-}
-
 Bindings* Bindings::NewGC(size_t capacity) {
   if (capacity == 0) {
     return &ZERO_BINDINGS;
@@ -71,6 +64,21 @@ Bindings* Bindings::NewGC(size_t capacity) {
   return new (GC) Bindings;
 }
 
+Bindings* Bindings::Merge(const Bindings& lhs, const Bindings& rhs) {
+  auto bindings = NewGC(lhs.size() + rhs.size());
+
+  // Values are merged by inserting the entire iterator range of both
+  // input sets. The right-hand set (the values of which take
+  // precedence) is inserted *first* because the range insertion
+  // method does not override values.
+  bindings->attributes_.insert(rhs.attributes_.cbegin(),
+                               rhs.attributes_.cend());
+  bindings->attributes_.insert(lhs.attributes_.cbegin(),
+                               lhs.attributes_.cend());
+
+  return bindings;
+}
+
 void EvalState::mkAttrs(Value& v, size_t capacity) {
   clearValue(v);
   v.type = tAttrs;
diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh
index f0b1448ba2f2..683b3e4bd75b 100644
--- a/third_party/nix/src/libexpr/attr-set.hh
+++ b/third_party/nix/src/libexpr/attr-set.hh
@@ -36,8 +36,12 @@ class Bindings {
   // collector.
   static Bindings* NewGC(size_t capacity = 0);
 
+  // Create a new attribute set by merging two others. This is used to
+  // implement the `//` operator in Nix.
+  static Bindings* Merge(const Bindings& lhs, const Bindings& rhs);
+
   // Return the number of contained elements.
-  size_t size();
+  size_t size() const;
 
   // Is this attribute set empty?
   bool empty();
@@ -48,13 +52,9 @@ class Bindings {
   // Look up a specific element of the attribute set.
   iterator find(const Symbol& name);
 
-  // TODO
   iterator begin();
   iterator end();
 
-  // Merge values from other into this attribute set.
-  void merge(const Bindings& other);
-
   // TODO: can callers just iterate?
   [[deprecated]] std::vector<const Attr*> lexicographicOrder();
 
diff --git a/third_party/nix/src/libexpr/eval.cc b/third_party/nix/src/libexpr/eval.cc
index a834e097a5cf..2b825bfd2788 100644
--- a/third_party/nix/src/libexpr/eval.cc
+++ b/third_party/nix/src/libexpr/eval.cc
@@ -19,6 +19,7 @@
 
 #include "libexpr/eval-inline.hh"
 #include "libexpr/function-trace.hh"
+#include "libexpr/value.hh"
 #include "libstore/derivations.hh"
 #include "libstore/download.hh"
 #include "libstore/globals.hh"
@@ -1240,11 +1241,9 @@ void ExprOpUpdate::eval(EvalState& state, Env& env, Value& dest) {
 
   state.nrOpUpdates++;
 
-  state.mkAttrs(dest, v1.attrs->size() + v2.attrs->size());
-
-  // Merge the sets, preferring values from the second set.
-  dest.attrs->merge(*v1.attrs);
-  dest.attrs->merge(*v2.attrs);
+  clearValue(dest);
+  dest.type = tAttrs;
+  dest.attrs = Bindings::Merge(*v1.attrs, *v2.attrs);
 }
 
 void ExprOpConcatLists::eval(EvalState& state, Env& env, Value& v) {