refactor(tvix/eval): persistent, memory-sharing OrdMap for NixAttrs r/5541

This uses the `im::OrdMap` for `NixAttrs` to enable sharing of memory
between different iterations of a map.

This slightly speeds up eval, but not significantly. Future work might
include benchmarking whether using a `HashMap` and only ordering in
cases where order is actually required would help.

This switches to a fork of `im` that fixes some bugs with its OrdMap
implementation.

Change-Id: I2f6a5ff471b6d508c1e8a98b13f889f49c0d9537
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7676
Reviewed-by: sterni <sternenseemann@systemli.org>
Tested-by: BuildkiteCI

10 files changed, 144 insertions, 172 deletions

diff --git a/corp/tvixbolt/Cargo.lock b/corp/tvixbolt/Cargo.lock
index 41bd8a315f..8225e059fa 100644
--- a/corp/tvixbolt/Cargo.lock
+++ b/corp/tvixbolt/Cargo.lock
@@ -36,12 +36,9 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
 
 [[package]]
 name = "bitmaps"
-version = "2.1.0"
+version = "3.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "031043d04099746d8db04daf1fa424b2bc8bd69d92b25962dcde24da39ab64a2"
-dependencies = [
- "typenum",
-]
+checksum = "703642b98a00b3b90513279a8ede3fcfa479c126c5fb46e78f3051522f021403"
 
 [[package]]
 name = "boolinator"
@@ -283,20 +280,28 @@ dependencies = [
 ]
 
 [[package]]
-name = "im"
-version = "15.1.0"
+name = "imbl"
+version = "2.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d0acd33ff0285af998aaf9b57342af478078f53492322fafc47450e09397e0e9"
+checksum = "c2806b69cd9f4664844027b64465eacb444c67c1db9c778e341adff0c25cdb0d"
 dependencies = [
  "bitmaps",
+ "imbl-sized-chunks",
  "rand_core",
  "rand_xoshiro",
- "sized-chunks",
- "typenum",
  "version_check",
 ]
 
 [[package]]
+name = "imbl-sized-chunks"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6957ea0b2541c5ca561d3ef4538044af79f8a05a1eb3a3b148936aaceaa1076"
+dependencies = [
+ "bitmaps",
+]
+
+[[package]]
 name = "indexmap"
 version = "1.9.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -571,16 +576,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "sized-chunks"
-version = "0.6.5"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "16d69225bde7a69b235da73377861095455d298f2b970996eec25ddbb42b3d1e"
-dependencies = [
- "bitmaps",
- "typenum",
-]
-
-[[package]]
 name = "slab"
 version = "0.4.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -660,7 +655,7 @@ dependencies = [
  "codemap",
  "codemap-diagnostic",
  "dirs",
- "im",
+ "imbl",
  "path-clean",
  "regex",
  "rnix",
@@ -697,12 +692,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "typenum"
-version = "1.16.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "497961ef93d974e23eb6f433eb5fe1b7930b659f06d12dec6fc44a8f554c0bba"
-
-[[package]]
 name = "unicode-ident"
 version = "1.0.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/tvix/Cargo.lock b/tvix/Cargo.lock
index a3b91e534f..f2c0e391ca 100644
--- a/tvix/Cargo.lock
+++ b/tvix/Cargo.lock
@@ -185,12 +185,9 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
 
 [[package]]
 name = "bitmaps"
-version = "2.1.0"
+version = "3.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "031043d04099746d8db04daf1fa424b2bc8bd69d92b25962dcde24da39ab64a2"
-dependencies = [
- "typenum",
-]
+checksum = "703642b98a00b3b90513279a8ede3fcfa479c126c5fb46e78f3051522f021403"
 
 [[package]]
 name = "blake3"
@@ -829,20 +826,28 @@ dependencies = [
 ]
 
 [[package]]
-name = "im"
-version = "15.1.0"
+name = "imbl"
+version = "2.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d0acd33ff0285af998aaf9b57342af478078f53492322fafc47450e09397e0e9"
+checksum = "c2806b69cd9f4664844027b64465eacb444c67c1db9c778e341adff0c25cdb0d"
 dependencies = [
  "bitmaps",
+ "imbl-sized-chunks",
  "rand_core 0.6.4",
  "rand_xoshiro",
- "sized-chunks",
- "typenum",
  "version_check",
 ]
 
 [[package]]
+name = "imbl-sized-chunks"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6957ea0b2541c5ca561d3ef4538044af79f8a05a1eb3a3b148936aaceaa1076"
+dependencies = [
+ "bitmaps",
+]
+
+[[package]]
 name = "indexmap"
 version = "1.9.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1636,16 +1641,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "sized-chunks"
-version = "0.6.5"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "16d69225bde7a69b235da73377861095455d298f2b970996eec25ddbb42b3d1e"
-dependencies = [
- "bitmaps",
- "typenum",
-]
-
-[[package]]
 name = "slab"
 version = "0.4.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2083,7 +2078,7 @@ dependencies = [
  "codemap-diagnostic",
  "criterion",
  "dirs",
- "im",
+ "imbl",
  "itertools",
  "path-clean",
  "pretty_assertions",
diff --git a/tvix/Cargo.nix b/tvix/Cargo.nix
index fdc93f248b..a72a8d3277 100644
--- a/tvix/Cargo.nix
+++ b/tvix/Cargo.nix
@@ -656,18 +656,12 @@ rec {
       };
       "bitmaps" = rec {
         crateName = "bitmaps";
-        version = "2.1.0";
-        edition = "2018";
-        sha256 = "18k4mcwxl96yvii5kcljkpb8pg5j4jj1zbsdn26nsx4r83846403";
+        version = "3.2.0";
+        edition = "2021";
+        sha256 = "00ql08pm4l9hizkldyy54v0pk96g7zg8x6i72c2vkcq0iawl4dkh";
         authors = [
           "Bodil Stokke <bodil@bodil.org>"
         ];
-        dependencies = [
-          {
-            name = "typenum";
-            packageId = "typenum";
-          }
-        ];
         features = {
           "default" = [ "std" ];
         };
@@ -2423,13 +2417,14 @@ rec {
         ];
 
       };
-      "im" = rec {
-        crateName = "im";
-        version = "15.1.0";
+      "imbl" = rec {
+        crateName = "imbl";
+        version = "2.0.0";
         edition = "2018";
-        sha256 = "1sg0jy9y0l3lqjpjyclj6kspi027mx177dgrmacgjni8y0zx7b6h";
+        sha256 = "03fvbk1g1pqs6j77g76vq5klqi6bx9jl9di782268ilzrmlnp062";
         authors = [
           "Bodil Stokke <bodil@bodil.org>"
+          "Joe Neeman <joeneeman@gmail.com>"
         ];
         dependencies = [
           {
@@ -2437,6 +2432,10 @@ rec {
             packageId = "bitmaps";
           }
           {
+            name = "imbl-sized-chunks";
+            packageId = "imbl-sized-chunks";
+          }
+          {
             name = "rand_core";
             packageId = "rand_core 0.6.4";
           }
@@ -2444,14 +2443,6 @@ rec {
             name = "rand_xoshiro";
             packageId = "rand_xoshiro";
           }
-          {
-            name = "sized-chunks";
-            packageId = "sized-chunks";
-          }
-          {
-            name = "typenum";
-            packageId = "typenum";
-          }
         ];
         buildDependencies = [
           {
@@ -2468,6 +2459,31 @@ rec {
           "serde" = [ "dep:serde" ];
         };
       };
+      "imbl-sized-chunks" = rec {
+        crateName = "imbl-sized-chunks";
+        version = "0.1.1";
+        edition = "2021";
+        sha256 = "0xhhmb7aldl92hxkmsx10n59zxsa0hw4bvykc6jmq72lnah7x5g6";
+        authors = [
+          "Bodil Stokke <bodil@bodil.org>"
+          "Joe Neeman <joeneeman@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "bitmaps";
+            packageId = "bitmaps";
+            usesDefaultFeatures = false;
+          }
+        ];
+        features = {
+          "arbitrary" = [ "dep:arbitrary" ];
+          "array-ops" = [ "dep:array-ops" ];
+          "default" = [ "std" ];
+          "refpool" = [ "dep:refpool" ];
+          "ringbuffer" = [ "array-ops" ];
+        };
+        resolvedDefaultFeatures = [ "default" "std" ];
+      };
       "indexmap" = rec {
         crateName = "indexmap";
         version = "1.9.2";
@@ -4712,33 +4728,6 @@ rec {
         };
         resolvedDefaultFeatures = [ "default" "std" ];
       };
-      "sized-chunks" = rec {
-        crateName = "sized-chunks";
-        version = "0.6.5";
-        edition = "2018";
-        sha256 = "07ix5fsdnpf2xsb0k5rbiwlmsicm2237fcx7blirp9p7pljr5mhn";
-        authors = [
-          "Bodil Stokke <bodil@bodil.org>"
-        ];
-        dependencies = [
-          {
-            name = "bitmaps";
-            packageId = "bitmaps";
-          }
-          {
-            name = "typenum";
-            packageId = "typenum";
-          }
-        ];
-        features = {
-          "arbitrary" = [ "dep:arbitrary" ];
-          "array-ops" = [ "dep:array-ops" ];
-          "default" = [ "std" ];
-          "refpool" = [ "dep:refpool" ];
-          "ringbuffer" = [ "array-ops" ];
-        };
-        resolvedDefaultFeatures = [ "default" "std" ];
-      };
       "slab" = rec {
         crateName = "slab";
         version = "0.4.7";
@@ -6185,8 +6174,8 @@ rec {
             packageId = "dirs";
           }
           {
-            name = "im";
-            packageId = "im";
+            name = "imbl";
+            packageId = "imbl";
           }
           {
             name = "path-clean";
diff --git a/tvix/eval/Cargo.toml b/tvix/eval/Cargo.toml
index dac605f3e1..b866ec2c71 100644
--- a/tvix/eval/Cargo.toml
+++ b/tvix/eval/Cargo.toml
@@ -14,7 +14,7 @@ builtin-macros = { path = "./builtin-macros", package = "tvix-eval-builtin-macro
 codemap = "0.1.3"
 codemap-diagnostic = "0.1.1"
 dirs = "4.0.0"
-im = "15.1"
+imbl = "2.0"
 path-clean = "0.1"
 proptest = { version = "1.0.0", default_features = false, features = ["std", "alloc", "break-dead-code", "tempfile"], optional = true }
 regex = "1.6.0"
diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 3708ed04d8..9f03cd85b8 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -187,14 +187,14 @@ mod pure_builtins {
             .collect::<Result<Vec<NixList>, ErrorKind>>()?;
 
         Ok(Value::List(NixList::from(
-            lists.into_iter().flatten().collect::<im::Vector<Value>>(),
+            lists.into_iter().flatten().collect::<imbl::Vector<Value>>(),
         )))
     }
 
     #[builtin("concatMap")]
     fn builtin_concat_map(vm: &mut VM, f: Value, list: Value) -> Result<Value, ErrorKind> {
         let list = list.to_list()?;
-        let mut res = im::Vector::new();
+        let mut res = imbl::Vector::new();
         for val in list {
             res.extend(vm.call_with(&f, [val])?.force(vm)?.to_list()?);
         }
@@ -295,7 +295,7 @@ mod pure_builtins {
 
                 result
             })
-            .collect::<Result<im::Vector<Value>, _>>()
+            .collect::<Result<imbl::Vector<Value>, _>>()
             .map(|list| Value::List(NixList::from(list)))
             .map_err(Into::into)
     }
@@ -356,7 +356,7 @@ mod pure_builtins {
 
         let operator = attrs.select_required("operator")?;
 
-        let mut res = im::Vector::new();
+        let mut res = imbl::Vector::new();
         let mut done_keys: Vec<Value> = vec![];
 
         let mut insert_key = |k: Value, vm: &mut VM| -> Result<bool, ErrorKind> {
@@ -391,7 +391,7 @@ mod pure_builtins {
         let len = length.as_int()?;
         (0..len)
             .map(|i| vm.call_with(&generator, [i.into()]))
-            .collect::<Result<im::Vector<Value>, _>>()
+            .collect::<Result<imbl::Vector<Value>, _>>()
             .map(|list| Value::List(NixList::from(list)))
             .map_err(Into::into)
     }
@@ -411,11 +411,11 @@ mod pure_builtins {
 
     #[builtin("groupBy")]
     fn builtin_group_by(vm: &mut VM, f: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut res: BTreeMap<NixString, im::Vector<Value>> = BTreeMap::new();
+        let mut res: BTreeMap<NixString, imbl::Vector<Value>> = BTreeMap::new();
         for val in list.to_list()? {
             let key = vm.call_with(&f, [val.clone()])?.force(vm)?.to_str()?;
             res.entry(key)
-                .or_insert_with(im::Vector::new)
+                .or_insert_with(imbl::Vector::new)
                 .push_back(val);
         }
         Ok(Value::attrs(NixAttrs::from_iter(
@@ -550,7 +550,7 @@ mod pure_builtins {
 
         list.into_iter()
             .map(|val| vm.call_with(&f, [val]))
-            .collect::<Result<im::Vector<Value>, _>>()
+            .collect::<Result<imbl::Vector<Value>, _>>()
             .map(|list| Value::List(NixList::from(list)))
             .map_err(Into::into)
     }
@@ -744,7 +744,7 @@ mod pure_builtins {
         let re: Regex = Regex::new(re.as_str()).unwrap();
         let mut capture_locations = re.capture_locations();
         let num_captures = capture_locations.len();
-        let mut ret = im::Vector::new();
+        let mut ret = imbl::Vector::new();
         let mut pos = 0;
 
         while let Some(thematch) = re.captures_read_at(&mut capture_locations, text, pos) {
@@ -755,7 +755,7 @@ mod pure_builtins {
             // group in the regex, containing the characters
             // matched by that capture group, or null if no match.
             // We skip capture 0; it represents the whole match.
-            let v: im::Vector<Value> = (1..num_captures)
+            let v: imbl::Vector<Value> = (1..num_captures)
                 .map(|i| capture_locations.get(i))
                 .map(|o| {
                     o.map(|(start, end)| Value::from(&text[start..end]))
@@ -775,7 +775,7 @@ mod pure_builtins {
     #[builtin("sort")]
     fn builtin_sort(vm: &mut VM, comparator: Value, list: Value) -> Result<Value, ErrorKind> {
         // TODO: the bound on the sort function in
-        // `im::Vector::sort_by` is `Fn(...)`, which means that we can
+        // `imbl::Vector::sort_by` is `Fn(...)`, which means that we can
         // not use the mutable VM inside of its closure, hence the
         // dance via `Vec`. I think this is just an unnecessarily
         // restrictive bound in `im`, not a functional requirement.
@@ -810,7 +810,7 @@ mod pure_builtins {
         });
 
         match error {
-            #[allow(deprecated)] // im::Vector usage prevented by its API
+            #[allow(deprecated)] // imbl::Vector usage prevented by its API
             None => Ok(Value::List(NixList::from_vec(list))),
             Some(e) => Err(e),
         }
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix
index 68dca62ee1..cd95b971f8 100644
--- a/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix
@@ -6,7 +6,7 @@ let
   atermFun = { stdenv, fetchurl }: { name = "aterm-${stdenv.name}"; };
   aterm2Fun = { stdenv, fetchurl }: { name = "aterm2-${stdenv.name}"; };
   nixFun = { stdenv, fetchurl, aterm }: { name = "nix-${stdenv.name}-${aterm.name}"; };
-  
+
   mplayerFun =
     { stdenv, fetchurl, enableX11 ? false, xorg ? null, enableFoo ? true, foo ? null  }:
     assert stdenv.name == "stdenv2";
@@ -18,7 +18,7 @@ let
     { override = newArgs:
         makeOverridable f (origArgs // (if builtins.isFunction newArgs then newArgs origArgs else newArgs));
     };
-    
+
   callPackage_ = pkgs: f: args:
     makeOverridable f ((builtins.intersectAttrs (builtins.functionArgs f) pkgs) // args);
 
@@ -42,7 +42,7 @@ let
   libX11Fun = { stdenv, fetchurl }: { name = "libX11"; };
   libX11_2Fun = { stdenv, fetchurl }: { name = "libX11_2"; };
   libXvFun = { stdenv, fetchurl, libX11 }: { name = "libXv"; };
-  
+
   xorgFun =
     { pkgs }:
     let callPackage = callPackage_ (pkgs // pkgs.xorg); in
@@ -56,7 +56,7 @@ in
 let
 
   pkgs = allPackages { };
-  
+
   pkgs2 = allPackages {
     overrides = pkgs: pkgsPrev: {
       stdenv = pkgs.stdenv2;
@@ -64,7 +64,7 @@ let
       xorg = pkgsPrev.xorg // { libX11 = libX11_2Fun { inherit (pkgs) stdenv fetchurl; }; };
     };
   };
-  
+
 in
 
   [ pkgs.stdenv.name
diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs
index 833cb2fd60..adf56567fb 100644
--- a/tvix/eval/src/value/attrs.rs
+++ b/tvix/eval/src/value/attrs.rs
@@ -5,10 +5,10 @@
 //!
 //! Due to this, construction and management of attribute sets has
 //! some peculiarities that are encapsulated within this module.
-use std::collections::btree_map;
-use std::collections::BTreeMap;
 use std::iter::FromIterator;
 
+use imbl::{ordmap, OrdMap};
+
 use crate::errors::ErrorKind;
 use crate::vm::VM;
 
@@ -23,7 +23,8 @@ mod tests;
 #[derive(Clone, Debug)]
 enum AttrsRep {
     Empty,
-    Map(BTreeMap<NixString, Value>),
+
+    Im(OrdMap<NixString, Value>),
 
     /// Warning: this represents a **two**-attribute attrset, with
     /// attribute names "name" and "value", like `{name="foo";
@@ -43,20 +44,21 @@ impl Default for AttrsRep {
 impl AttrsRep {
     /// Retrieve reference to a mutable map inside of an attrs,
     /// optionally changing the representation if required.
-    fn map_mut(&mut self) -> &mut BTreeMap<NixString, Value> {
+    fn map_mut(&mut self) -> &mut OrdMap<NixString, Value> {
         match self {
-            AttrsRep::Map(m) => m,
+            AttrsRep::Im(m) => m,
 
             AttrsRep::Empty => {
-                *self = AttrsRep::Map(BTreeMap::new());
+                *self = AttrsRep::Im(OrdMap::new());
                 self.map_mut()
             }
 
             AttrsRep::KV { name, value } => {
-                *self = AttrsRep::Map(BTreeMap::from([
-                    (NixString::NAME, name.clone()),
-                    (NixString::VALUE, value.clone()),
-                ]));
+                *self = AttrsRep::Im(ordmap! {
+                    NixString::NAME => name.clone(),
+                    NixString::VALUE => value.clone()
+                });
+
                 self.map_mut()
             }
         }
@@ -72,7 +74,7 @@ impl AttrsRep {
                 _ => None,
             },
 
-            AttrsRep::Map(map) => map.get(&key.into()),
+            AttrsRep::Im(map) => map.get(&key.into()),
         }
     }
 
@@ -80,7 +82,7 @@ impl AttrsRep {
         match self {
             AttrsRep::Empty => false,
             AttrsRep::KV { .. } => key == "name" || key == "value",
-            AttrsRep::Map(map) => map.contains_key(&key.into()),
+            AttrsRep::Im(map) => map.contains_key(&key.into()),
         }
     }
 }
@@ -98,7 +100,7 @@ where
     where
         T: IntoIterator<Item = (K, V)>,
     {
-        NixAttrs(AttrsRep::Map(
+        NixAttrs(AttrsRep::Im(
             iter.into_iter()
                 .map(|(k, v)| (k.into(), v.into()))
                 .collect(),
@@ -121,7 +123,7 @@ impl TotalDisplay for NixAttrs {
                 f.write_str("; ")?;
             }
 
-            AttrsRep::Map(map) => {
+            AttrsRep::Im(map) => {
                 for (name, value) in map {
                     write!(f, "{} = ", name.ident_str())?;
                     value.total_fmt(f, set)?;
@@ -139,6 +141,7 @@ impl TotalDisplay for NixAttrs {
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
     use super::*;
+    use std::collections::BTreeMap;
 
     use proptest::prelude::*;
     use proptest::prop_oneof;
@@ -158,7 +161,7 @@ mod arbitrary {
                 )
                     .prop_map(|(name, value)| Self(AttrsRep::KV { name, value })),
                 any_with::<BTreeMap<NixString, Value>>(args)
-                    .prop_map(|map| Self(AttrsRep::Map(map)))
+                    .prop_map(|map| Self::from_iter(map.into_iter()))
             ]
             .boxed()
         }
@@ -183,44 +186,41 @@ impl NixAttrs {
             // Explicitly handle all branches instead of falling
             // through, to ensure that we get at least some compiler
             // errors if variants are modified.
-            (AttrsRep::Map(_), AttrsRep::Map(_))
-            | (AttrsRep::Map(_), AttrsRep::KV { .. })
-            | (AttrsRep::KV { .. }, AttrsRep::Map(_)) => {}
+            (AttrsRep::Im(_), AttrsRep::Im(_))
+            | (AttrsRep::Im(_), AttrsRep::KV { .. })
+            | (AttrsRep::KV { .. }, AttrsRep::Im(_)) => {}
         };
 
         // Slightly more advanced, but still optimised updates
         match (self.0, other.0) {
-            (AttrsRep::Map(mut m), AttrsRep::KV { name, value }) => {
+            (AttrsRep::Im(mut m), AttrsRep::KV { name, value }) => {
                 m.insert(NixString::NAME, name);
                 m.insert(NixString::VALUE, value);
-                NixAttrs(AttrsRep::Map(m))
+                NixAttrs(AttrsRep::Im(m))
             }
 
-            (AttrsRep::KV { name, value }, AttrsRep::Map(mut m)) => {
+            (AttrsRep::KV { name, value }, AttrsRep::Im(mut m)) => {
                 match m.entry(NixString::NAME) {
-                    btree_map::Entry::Vacant(e) => {
+                    imbl::ordmap::Entry::Vacant(e) => {
                         e.insert(name);
                     }
 
-                    btree_map::Entry::Occupied(_) => { /* name from `m` has precedence */ }
+                    imbl::ordmap::Entry::Occupied(_) => { /* name from `m` has precedence */ }
                 };
 
                 match m.entry(NixString::VALUE) {
-                    btree_map::Entry::Vacant(e) => {
+                    imbl::ordmap::Entry::Vacant(e) => {
                         e.insert(value);
                     }
 
-                    btree_map::Entry::Occupied(_) => { /* value from `m` has precedence */ }
+                    imbl::ordmap::Entry::Occupied(_) => { /* value from `m` has precedence */ }
                 };
 
-                NixAttrs(AttrsRep::Map(m))
+                NixAttrs(AttrsRep::Im(m))
             }
 
             // Plain merge of maps.
-            (AttrsRep::Map(mut m1), AttrsRep::Map(mut m2)) => {
-                m1.append(&mut m2);
-                NixAttrs(AttrsRep::Map(m1))
-            }
+            (AttrsRep::Im(m1), AttrsRep::Im(m2)) => NixAttrs(AttrsRep::Im(m2.union(m1))),
 
             // Cases handled above by the borrowing match:
             _ => unreachable!(),
@@ -230,7 +230,7 @@ impl NixAttrs {
     /// Return the number of key-value entries in an attrset.
     pub fn len(&self) -> usize {
         match &self.0 {
-            AttrsRep::Map(map) => map.len(),
+            AttrsRep::Im(map) => map.len(),
             AttrsRep::Empty => 0,
             AttrsRep::KV { .. } => 2,
         }
@@ -256,7 +256,7 @@ impl NixAttrs {
     #[allow(clippy::needless_lifetimes)]
     pub fn iter<'a>(&'a self) -> Iter<KeyValue<'a>> {
         Iter(match &self.0 {
-            AttrsRep::Map(map) => KeyValue::Map(map.iter()),
+            AttrsRep::Im(map) => KeyValue::Im(map.iter()),
             AttrsRep::Empty => KeyValue::Empty,
 
             AttrsRep::KV {
@@ -280,7 +280,7 @@ impl NixAttrs {
                 ]
                 .into_iter(),
             )),
-            AttrsRep::Map(map) => IntoIter(IntoIterRepr::Map(map.into_iter())),
+            AttrsRep::Im(map) => IntoIter(IntoIterRepr::Im(map.into_iter())),
         }
     }
 
@@ -294,7 +294,7 @@ impl NixAttrs {
     pub fn keys(&self) -> Keys {
         Keys(match &self.0 {
             AttrsRep::Empty => KeysInner::Empty,
-            AttrsRep::Map(m) => KeysInner::Map(m.keys()),
+            AttrsRep::Im(m) => KeysInner::Im(m.keys()),
             AttrsRep::KV { .. } => KeysInner::KV(IterKV::default()),
         })
     }
@@ -321,7 +321,7 @@ impl NixAttrs {
             }
         }
 
-        let mut attrs = NixAttrs(AttrsRep::Map(BTreeMap::new()));
+        let mut attrs = NixAttrs(AttrsRep::Im(OrdMap::new()));
 
         for _ in 0..count {
             let value = stack_slice.pop().unwrap();
@@ -363,7 +363,7 @@ impl NixAttrs {
             // elements after key construction). In practice this
             // probably does not happen, so it's better to just bite
             // the bullet and implement this branch.
-            (AttrsRep::Empty, AttrsRep::Map(map)) | (AttrsRep::Map(map), AttrsRep::Empty) => {
+            (AttrsRep::Empty, AttrsRep::Im(map)) | (AttrsRep::Im(map), AttrsRep::Empty) => {
                 Ok(map.is_empty())
             }
 
@@ -382,8 +382,8 @@ impl NixAttrs {
                 },
             ) => Ok(n1.nix_eq(n2, vm)? && v1.nix_eq(v2, vm)?),
 
-            (AttrsRep::Map(map), AttrsRep::KV { name, value })
-            | (AttrsRep::KV { name, value }, AttrsRep::Map(map)) => {
+            (AttrsRep::Im(map), AttrsRep::KV { name, value })
+            | (AttrsRep::KV { name, value }, AttrsRep::Im(map)) => {
                 if map.len() != 2 {
                     return Ok(false);
                 }
@@ -397,7 +397,7 @@ impl NixAttrs {
                 Ok(false)
             }
 
-            (AttrsRep::Map(m1), AttrsRep::Map(m2)) => {
+            (AttrsRep::Im(m1), AttrsRep::Im(m2)) => {
                 if m1.len() != m2.len() {
                     return Ok(false);
                 }
@@ -462,11 +462,11 @@ fn attempt_optimise_kv(slice: &mut [Value]) -> Option<NixAttrs> {
 /// checking against duplicate keys.
 fn set_attr(attrs: &mut NixAttrs, key: NixString, value: Value) -> Result<(), ErrorKind> {
     match attrs.0.map_mut().entry(key) {
-        btree_map::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey {
+        imbl::ordmap::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey {
             key: entry.key().as_str().to_string(),
         }),
 
-        btree_map::Entry::Vacant(entry) => {
+        imbl::ordmap::Entry::Vacant(entry) => {
             entry.insert(value);
             Ok(())
         }
@@ -495,7 +495,6 @@ impl IterKV {
 
 /// Iterator representation over the keys *and* values of an attribute
 /// set.
-#[derive(Debug)]
 pub enum KeyValue<'a> {
     Empty,
 
@@ -505,7 +504,7 @@ pub enum KeyValue<'a> {
         at: IterKV,
     },
 
-    Map(btree_map::Iter<'a, NixString, Value>),
+    Im(imbl::ordmap::Iter<'a, NixString, Value>),
 }
 
 /// Iterator over a Nix attribute set.
@@ -519,7 +518,7 @@ impl<'a> Iterator for Iter<KeyValue<'a>> {
 
     fn next(&mut self) -> Option<Self::Item> {
         match &mut self.0 {
-            KeyValue::Map(inner) => inner.next(),
+            KeyValue::Im(inner) => inner.next(),
             KeyValue::Empty => None,
 
             KeyValue::KV { name, value, at } => match at {
@@ -544,7 +543,7 @@ impl<'a> ExactSizeIterator for Iter<KeyValue<'a>> {
         match &self.0 {
             KeyValue::Empty => 0,
             KeyValue::KV { .. } => 2,
-            KeyValue::Map(inner) => inner.len(),
+            KeyValue::Im(inner) => inner.len(),
         }
     }
 }
@@ -552,7 +551,7 @@ impl<'a> ExactSizeIterator for Iter<KeyValue<'a>> {
 enum KeysInner<'a> {
     Empty,
     KV(IterKV),
-    Map(btree_map::Keys<'a, NixString, Value>),
+    Im(imbl::ordmap::Keys<'a, NixString, Value>),
 }
 
 pub struct Keys<'a>(KeysInner<'a>);
@@ -572,7 +571,7 @@ impl<'a> Iterator for Keys<'a> {
                 Some(NixString::VALUE_REF)
             }
             KeysInner::KV(IterKV::Done) => None,
-            KeysInner::Map(m) => m.next(),
+            KeysInner::Im(m) => m.next(),
         }
     }
 }
@@ -592,7 +591,7 @@ impl<'a> ExactSizeIterator for Keys<'a> {
         match &self.0 {
             KeysInner::Empty => 0,
             KeysInner::KV(_) => 2,
-            KeysInner::Map(m) => m.len(),
+            KeysInner::Im(m) => m.len(),
         }
     }
 }
@@ -601,7 +600,7 @@ impl<'a> ExactSizeIterator for Keys<'a> {
 pub enum IntoIterRepr {
     Empty,
     Finite(std::vec::IntoIter<(NixString, Value)>),
-    Map(std::collections::btree_map::IntoIter<NixString, Value>),
+    Im(imbl::ordmap::ConsumingIter<(NixString, Value)>),
 }
 
 #[repr(transparent)]
@@ -613,8 +612,8 @@ impl Iterator for IntoIter {
     fn next(&mut self) -> Option<Self::Item> {
         match &mut self.0 {
             IntoIterRepr::Empty => None,
-            IntoIterRepr::Map(inner) => inner.next(),
             IntoIterRepr::Finite(inner) => inner.next(),
+            IntoIterRepr::Im(inner) => inner.next(),
         }
     }
 }
@@ -623,8 +622,8 @@ impl ExactSizeIterator for IntoIter {
     fn len(&self) -> usize {
         match &self.0 {
             IntoIterRepr::Empty => 0,
-            IntoIterRepr::Map(inner) => inner.len(),
             IntoIterRepr::Finite(inner) => inner.len(),
+            IntoIterRepr::Im(inner) => inner.len(),
         }
     }
 }
diff --git a/tvix/eval/src/value/attrs/tests.rs b/tvix/eval/src/value/attrs/tests.rs
index 2e80fa6f23..2039c509fd 100644
--- a/tvix/eval/src/value/attrs/tests.rs
+++ b/tvix/eval/src/value/attrs/tests.rs
@@ -56,7 +56,7 @@ fn test_simple_attrs() {
     .expect("simple attr construction should succeed");
 
     assert!(
-        matches!(attrs, NixAttrs(AttrsRep::Map(_))),
+        matches!(attrs, NixAttrs(AttrsRep::Im(_))),
         "simple attribute set should use map representation",
     )
 }
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs
index 0ab180a341..fa1f266c87 100644
--- a/tvix/eval/src/value/list.rs
+++ b/tvix/eval/src/value/list.rs
@@ -1,7 +1,7 @@
 //! This module implements Nix lists.
 use std::ops::Index;
 
-use im::{vector, Vector};
+use imbl::{vector, Vector};
 
 use crate::errors::ErrorKind;
 use crate::vm::VM;
@@ -119,7 +119,7 @@ impl NixList {
 
 impl IntoIterator for NixList {
     type Item = Value;
-    type IntoIter = im::vector::ConsumingIter<Value>;
+    type IntoIter = imbl::vector::ConsumingIter<Value>;
 
     fn into_iter(self) -> Self::IntoIter {
         self.0.into_iter()
@@ -128,7 +128,7 @@ impl IntoIterator for NixList {
 
 impl<'a> IntoIterator for &'a NixList {
     type Item = &'a Value;
-    type IntoIter = im::vector::Iter<'a, Value>;
+    type IntoIter = imbl::vector::Iter<'a, Value>;
 
     fn into_iter(self) -> Self::IntoIter {
         self.0.iter()
diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs
index 1c6d104bd8..7791a4a8c3 100644
--- a/tvix/eval/src/value/mod.rs
+++ b/tvix/eval/src/value/mod.rs
@@ -601,7 +601,7 @@ fn type_error(expected: &'static str, actual: &Value) -> ErrorKind {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use im::vector;
+    use imbl::vector;
 
     mod nix_eq {
         use crate::observer::NoOpObserver;