refactor(tvix): Use absl::btree_map for DerivationOutputs r/1610

This container implementation is much faster than std::map. We have
stuck to an ordered container because it's unclear whether the
accesses of this field (of which there are *many*) are actually
ordering dependent.

Also includes an Arbitrary implementation for absl::btree_map (for any
K, V that are also Arbitrary).

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

4 files changed, 22 insertions, 7 deletions

diff --git a/third_party/nix/src/libstore/derivations.cc b/third_party/nix/src/libstore/derivations.cc
index 007c268bab..adfc6fc05f 100644
--- a/third_party/nix/src/libstore/derivations.cc
+++ b/third_party/nix/src/libstore/derivations.cc
@@ -40,8 +40,9 @@ BasicDerivation BasicDerivation::from_proto(
   result.builder = proto_derivation->builder().path();
   store.assertStorePath(result.builder);
 
-  result.outputs.insert(proto_derivation->outputs().begin(),
-                        proto_derivation->outputs().end());
+  for (auto [k, v] : proto_derivation->outputs()) {
+    result.outputs.emplace(k, v);
+  }
 
   result.inputSrcs.insert(proto_derivation->input_sources().paths().begin(),
                           proto_derivation->input_sources().paths().end());
diff --git a/third_party/nix/src/libstore/derivations.hh b/third_party/nix/src/libstore/derivations.hh
index 38877780e0..63527149d8 100644
--- a/third_party/nix/src/libstore/derivations.hh
+++ b/third_party/nix/src/libstore/derivations.hh
@@ -2,6 +2,8 @@
 
 #include <map>
 
+#include <absl/container/btree_map.h>
+
 #include "libproto/worker.pb.h"
 #include "libstore/store-api.hh"
 #include "libutil/hash.hh"
@@ -35,16 +37,16 @@ struct DerivationOutput {
   void parseHashInfo(bool& recursive, Hash& hash) const;
 };
 
-// TODO(grfn): change to absl::flat_hash_map
-typedef std::map<std::string, DerivationOutput> DerivationOutputs;
+// TODO(tazjin): Determine whether this actually needs to be ordered.
+using DerivationOutputs = absl::btree_map<std::string, DerivationOutput>;
 
 /* For inputs that are sub-derivations, we specify exactly which
    output IDs we are interested in. */
 // TODO(grfn): change to absl::flat_hash_map
-typedef std::map<Path, StringSet> DerivationInputs;
+using DerivationInputs = std::map<Path, StringSet>;
 
 // TODO(grfn): change to absl::flat_hash_map
-typedef std::map<std::string, std::string> StringPairs;
+using StringPairs = std::map<std::string, std::string>;
 
 struct BasicDerivation {
   DerivationOutputs outputs; /* keyed on symbolic IDs */
@@ -54,7 +56,7 @@ struct BasicDerivation {
   Strings args;
   StringPairs env;
 
-  BasicDerivation(){};
+  BasicDerivation() = default;
 
   // Convert the given proto derivation to a BasicDerivation in the given
   // nix::Store.
diff --git a/third_party/nix/src/tests/attr-set.cc b/third_party/nix/src/tests/attr-set.cc
index ae323e6bd3..17234f6b31 100644
--- a/third_party/nix/src/tests/attr-set.cc
+++ b/third_party/nix/src/tests/attr-set.cc
@@ -5,6 +5,7 @@
 #include <string>
 #include <vector>
 
+#include <absl/container/btree_map.h>
 #include <bits/stdint-intn.h>
 #include <gc/gc_cpp.h>
 #include <gtest/gtest.h>
diff --git a/third_party/nix/src/tests/derivations_test.cc b/third_party/nix/src/tests/derivations_test.cc
index 1e2719adda..63e2c3070e 100644
--- a/third_party/nix/src/tests/derivations_test.cc
+++ b/third_party/nix/src/tests/derivations_test.cc
@@ -22,6 +22,17 @@ namespace rc {
 using nix::Derivation;
 using nix::DerivationOutput;
 
+template <class K, class V>
+struct Arbitrary<absl::btree_map<K, V>> {
+  static Gen<absl::btree_map<K, V>> arbitrary() {
+    return gen::map(gen::arbitrary<std::map<K, V>>(), [](std::map<K, V> map) {
+      absl::btree_map<K, V> out_map;
+      out_map.insert(map.begin(), map.end());
+      return out_map;
+    });
+  }
+};
+
 template <>
 struct Arbitrary<nix::Base> {
   static Gen<nix::Base> arbitrary() {