refactor(tvix/eval): remove use of imbl::OrdMap r/8521

Removes imbl::OrdMap in favour of an Rc over the standard library's BTreeMap,
which allows us to drop the imbl dependency completely.

In my local tests this is actually slightly faster for `hello` and `firefox`.

Change-Id: Ic9597ead4e98bf9530f290c6a94a3c5c3efd0acc
Reviewed-on: https://cl.tvl.fyi/c/depot/+/12201
Reviewed-by: aspen <root@gws.fyi>
Tested-by: BuildkiteCI

8 files changed, 95 insertions, 451 deletions

diff --git a/tvix/Cargo.lock b/tvix/Cargo.lock
index d99936e804fc..3eddfcbe7d33 100644
--- a/tvix/Cargo.lock
+++ b/tvix/Cargo.lock
@@ -461,21 +461,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "bit-set"
-version = "0.5.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0700ddab506f33b20a03b13996eccd309a48e5ff77d0d95926aa0210fb4e95f1"
-dependencies = [
- "bit-vec",
-]
-
-[[package]]
-name = "bit-vec"
-version = "0.6.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "349f9b6a179ed607305526ca489b34ad0a41aed5f7980fa90eb03160b69598fb"
-
-[[package]]
 name = "bitflags"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -488,12 +473,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "ed570934406eb16438a4e976b1b4500774099c13b8cb96eec99f620f05090ddf"
 
 [[package]]
-name = "bitmaps"
-version = "3.2.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "703642b98a00b3b90513279a8ede3fcfa479c126c5fb46e78f3051522f021403"
-
-[[package]]
 name = "blake3"
 version = "1.5.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1848,30 +1827,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "imbl"
-version = "3.0.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bc3be8d8cd36f33a46b1849f31f837c44d9fa87223baee3b4bd96b8f11df81eb"
-dependencies = [
- "bitmaps",
- "imbl-sized-chunks",
- "proptest",
- "rand_core",
- "rand_xoshiro",
- "serde",
- "version_check",
-]
-
-[[package]]
-name = "imbl-sized-chunks"
-version = "0.1.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "144006fb58ed787dcae3f54575ff4349755b00ccc99f4b4873860b654be1ed63"
-dependencies = [
- "bitmaps",
-]
-
-[[package]]
 name = "indexmap"
 version = "1.9.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2899,8 +2854,6 @@ version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "31b476131c3c86cb68032fdc5cb6d5a1045e3e42d96b69fa599fd77701e1f5bf"
 dependencies = [
- "bit-set",
- "bit-vec",
  "bitflags 2.4.2",
  "lazy_static",
  "num-traits",
@@ -2908,7 +2861,6 @@ dependencies = [
  "rand_chacha",
  "rand_xorshift",
  "regex-syntax 0.8.2",
- "rusty-fork",
  "tempfile",
  "unarray",
 ]
@@ -3089,12 +3041,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "quick-error"
-version = "1.2.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"
-
-[[package]]
 name = "quick-xml"
 version = "0.36.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -3210,15 +3156,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "rand_xoshiro"
-version = "0.6.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "6f97cdb2a36ed4183de61b2f824cc45c9f1037f28afe0a322e9fff4c108b5aaa"
-dependencies = [
- "rand_core",
-]
-
-[[package]]
 name = "rayon"
 version = "1.8.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -3649,18 +3586,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "7ffc183a10b4478d04cbbbfc96d0873219d962dd5accaff2ffbd4ceb7df837f4"
 
 [[package]]
-name = "rusty-fork"
-version = "0.3.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "cb3dcc6e454c328bb824492db107ab7c0ae8fcffe4ad210136ef014458c1bc4f"
-dependencies = [
- "fnv",
- "quick-error",
- "tempfile",
- "wait-timeout",
-]
-
-[[package]]
 name = "rustyline"
 version = "10.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -4909,7 +4834,6 @@ dependencies = [
  "data-encoding",
  "dirs",
  "genawaiter",
- "imbl",
  "itertools 0.12.0",
  "lazy_static",
  "lexical-core",
@@ -5334,15 +5258,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "c51a178c8f3f425d86542b14f3dce9e16e86bb86328e2293745e6744ebd62e11"
 
 [[package]]
-name = "wait-timeout"
-version = "0.2.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9f200f5b12eb75f8c1ed65abd4b2db8a6e1b138a20de009dacee265a2498f3f6"
-dependencies = [
- "libc",
-]
-
-[[package]]
 name = "walkdir"
 version = "2.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/tvix/Cargo.nix b/tvix/Cargo.nix
index 002e59c0858c..54cbcf20721f 100644
--- a/tvix/Cargo.nix
+++ b/tvix/Cargo.nix
@@ -1667,45 +1667,6 @@ rec {
         ];
 
       };
-      "bit-set" = rec {
-        crateName = "bit-set";
-        version = "0.5.3";
-        edition = "2015";
-        sha256 = "1wcm9vxi00ma4rcxkl3pzzjli6ihrpn9cfdi0c5b4cvga2mxs007";
-        libName = "bit_set";
-        authors = [
-          "Alexis Beingessner <a.beingessner@gmail.com>"
-        ];
-        dependencies = [
-          {
-            name = "bit-vec";
-            packageId = "bit-vec";
-            usesDefaultFeatures = false;
-          }
-        ];
-        features = {
-          "default" = [ "std" ];
-          "std" = [ "bit-vec/std" ];
-        };
-        resolvedDefaultFeatures = [ "default" "std" ];
-      };
-      "bit-vec" = rec {
-        crateName = "bit-vec";
-        version = "0.6.3";
-        edition = "2015";
-        sha256 = "1ywqjnv60cdh1slhz67psnp422md6jdliji6alq0gmly2xm9p7rl";
-        libName = "bit_vec";
-        authors = [
-          "Alexis Beingessner <a.beingessner@gmail.com>"
-        ];
-        features = {
-          "default" = [ "std" ];
-          "serde" = [ "dep:serde" ];
-          "serde_no_std" = [ "serde/alloc" ];
-          "serde_std" = [ "std" "serde/std" ];
-        };
-        resolvedDefaultFeatures = [ "default" "std" ];
-      };
       "bitflags 1.3.2" = rec {
         crateName = "bitflags";
         version = "1.3.2";
@@ -1739,19 +1700,6 @@ rec {
         };
         resolvedDefaultFeatures = [ "std" ];
       };
-      "bitmaps" = rec {
-        crateName = "bitmaps";
-        version = "3.2.0";
-        edition = "2021";
-        sha256 = "00ql08pm4l9hizkldyy54v0pk96g7zg8x6i72c2vkcq0iawl4dkh";
-        authors = [
-          "Bodil Stokke <bodil@bodil.org>"
-        ];
-        features = {
-          "default" = [ "std" ];
-        };
-        resolvedDefaultFeatures = [ "default" "std" ];
-      };
       "blake3" = rec {
         crateName = "blake3";
         version = "1.5.0";
@@ -5886,96 +5834,6 @@ rec {
         };
         resolvedDefaultFeatures = [ "alloc" "default" "std" ];
       };
-      "imbl" = rec {
-        crateName = "imbl";
-        version = "3.0.0";
-        edition = "2018";
-        sha256 = "1sw1vw8qysyr9cxyxfi3fal9ykf46zw337w4n533mwrnrpcfhfxw";
-        authors = [
-          "Bodil Stokke <bodil@bodil.org>"
-          "Joe Neeman <joeneeman@gmail.com>"
-        ];
-        dependencies = [
-          {
-            name = "bitmaps";
-            packageId = "bitmaps";
-          }
-          {
-            name = "imbl-sized-chunks";
-            packageId = "imbl-sized-chunks";
-          }
-          {
-            name = "proptest";
-            packageId = "proptest";
-            optional = true;
-          }
-          {
-            name = "rand_core";
-            packageId = "rand_core";
-          }
-          {
-            name = "rand_xoshiro";
-            packageId = "rand_xoshiro";
-          }
-          {
-            name = "serde";
-            packageId = "serde";
-            optional = true;
-          }
-        ];
-        buildDependencies = [
-          {
-            name = "version_check";
-            packageId = "version_check";
-          }
-        ];
-        devDependencies = [
-          {
-            name = "proptest";
-            packageId = "proptest";
-          }
-          {
-            name = "serde";
-            packageId = "serde";
-          }
-        ];
-        features = {
-          "arbitrary" = [ "dep:arbitrary" ];
-          "proptest" = [ "dep:proptest" ];
-          "quickcheck" = [ "dep:quickcheck" ];
-          "rayon" = [ "dep:rayon" ];
-          "refpool" = [ "dep:refpool" ];
-          "serde" = [ "dep:serde" ];
-          "triomphe" = [ "dep:triomphe" ];
-        };
-        resolvedDefaultFeatures = [ "proptest" "serde" ];
-      };
-      "imbl-sized-chunks" = rec {
-        crateName = "imbl-sized-chunks";
-        version = "0.1.2";
-        edition = "2021";
-        sha256 = "0qzdw55na2w6fd44p7y9rh05nxa98gzpaigmwg57sy7db3xhch0l";
-        libName = "imbl_sized_chunks";
-        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 1.9.3" = rec {
         crateName = "indexmap";
         version = "1.9.3";
@@ -9198,16 +9056,6 @@ rec {
         ];
         dependencies = [
           {
-            name = "bit-set";
-            packageId = "bit-set";
-            optional = true;
-          }
-          {
-            name = "bit-vec";
-            packageId = "bit-vec";
-            optional = true;
-          }
-          {
             name = "bitflags";
             packageId = "bitflags 2.4.2";
           }
@@ -9243,12 +9091,6 @@ rec {
             optional = true;
           }
           {
-            name = "rusty-fork";
-            packageId = "rusty-fork";
-            optional = true;
-            usesDefaultFeatures = false;
-          }
-          {
             name = "tempfile";
             packageId = "tempfile";
             optional = true;
@@ -9272,7 +9114,7 @@ rec {
           "timeout" = [ "fork" "rusty-fork/timeout" ];
           "x86" = [ "dep:x86" ];
         };
-        resolvedDefaultFeatures = [ "alloc" "bit-set" "default" "fork" "lazy_static" "regex-syntax" "rusty-fork" "std" "tempfile" "timeout" ];
+        resolvedDefaultFeatures = [ "alloc" "lazy_static" "regex-syntax" "std" "tempfile" ];
       };
       "prost 0.12.3" = rec {
         crateName = "prost";
@@ -9844,18 +9686,6 @@ rec {
         ];
 
       };
-      "quick-error" = rec {
-        crateName = "quick-error";
-        version = "1.2.3";
-        edition = "2015";
-        sha256 = "1q6za3v78hsspisc197bg3g7rpc989qycy8ypr8ap8igv10ikl51";
-        libName = "quick_error";
-        authors = [
-          "Paul Colomiets <paul@colomiets.name>"
-          "Colin Kiegel <kiegel@gmx.de>"
-        ];
-
-      };
       "quick-xml" = rec {
         crateName = "quick-xml";
         version = "0.36.1";
@@ -10216,25 +10046,6 @@ rec {
           "serde1" = [ "serde" ];
         };
       };
-      "rand_xoshiro" = rec {
-        crateName = "rand_xoshiro";
-        version = "0.6.0";
-        edition = "2018";
-        sha256 = "1ajsic84rzwz5qr0mzlay8vi17swqi684bqvwqyiim3flfrcv5vg";
-        authors = [
-          "The Rand Project Developers"
-        ];
-        dependencies = [
-          {
-            name = "rand_core";
-            packageId = "rand_core";
-          }
-        ];
-        features = {
-          "serde" = [ "dep:serde" ];
-          "serde1" = [ "serde" ];
-        };
-      };
       "rayon" = rec {
         crateName = "rayon";
         version = "1.8.1";
@@ -11775,41 +11586,6 @@ rec {
         ];
 
       };
-      "rusty-fork" = rec {
-        crateName = "rusty-fork";
-        version = "0.3.0";
-        edition = "2018";
-        sha256 = "0kxwq5c480gg6q0j3bg4zzyfh2kwmc3v2ba94jw8ncjc8mpcqgfb";
-        libName = "rusty_fork";
-        authors = [
-          "Jason Lingle"
-        ];
-        dependencies = [
-          {
-            name = "fnv";
-            packageId = "fnv";
-          }
-          {
-            name = "quick-error";
-            packageId = "quick-error";
-          }
-          {
-            name = "tempfile";
-            packageId = "tempfile";
-          }
-          {
-            name = "wait-timeout";
-            packageId = "wait-timeout";
-            optional = true;
-          }
-        ];
-        features = {
-          "default" = [ "timeout" ];
-          "timeout" = [ "wait-timeout" ];
-          "wait-timeout" = [ "dep:wait-timeout" ];
-        };
-        resolvedDefaultFeatures = [ "timeout" "wait-timeout" ];
-      };
       "rustyline" = rec {
         crateName = "rustyline";
         version = "10.1.1";
@@ -16231,11 +16007,6 @@ rec {
             usesDefaultFeatures = false;
           }
           {
-            name = "imbl";
-            packageId = "imbl";
-            features = [ "serde" ];
-          }
-          {
             name = "itertools";
             packageId = "itertools 0.12.0";
           }
@@ -16359,7 +16130,7 @@ rec {
           }
         ];
         features = {
-          "arbitrary" = [ "proptest" "test-strategy" "imbl/proptest" ];
+          "arbitrary" = [ "proptest" "test-strategy" ];
           "default" = [ "impure" "arbitrary" "nix_tests" ];
           "proptest" = [ "dep:proptest" ];
           "test-strategy" = [ "dep:test-strategy" ];
@@ -17602,25 +17373,6 @@ rec {
         ];
 
       };
-      "wait-timeout" = rec {
-        crateName = "wait-timeout";
-        version = "0.2.0";
-        edition = "2015";
-        crateBin = [ ];
-        sha256 = "1xpkk0j5l9pfmjfh1pi0i89invlavfrd9av5xp0zhxgb29dhy84z";
-        libName = "wait_timeout";
-        authors = [
-          "Alex Crichton <alex@alexcrichton.com>"
-        ];
-        dependencies = [
-          {
-            name = "libc";
-            packageId = "libc";
-            target = { target, features }: (target."unix" or false);
-          }
-        ];
-
-      };
       "walkdir" = rec {
         crateName = "walkdir";
         version = "2.4.0";
diff --git a/tvix/eval/Cargo.toml b/tvix/eval/Cargo.toml
index f8ed80072095..364c97d82345 100644
--- a/tvix/eval/Cargo.toml
+++ b/tvix/eval/Cargo.toml
@@ -14,7 +14,6 @@ codemap = "0.1.3"
 codemap-diagnostic = "0.1.1"
 dirs = "4.0.0"
 genawaiter = { version = "0.99.1", default-features = false }
-imbl = { version = "3.0", features = [ "serde" ] }
 itertools = "0.12.0"
 lazy_static = "1.4.0"
 lexical-core = { version = "0.8.5", features = ["format", "parse-floats"] }
@@ -57,7 +56,7 @@ nix_tests = []
 impure = []
 
 # Enables Arbitrary impls for internal types (required to run tests)
-arbitrary = ["proptest", "test-strategy", "imbl/proptest"]
+arbitrary = ["proptest", "test-strategy"]
 
 # Don't leak strings (enable this if you care about peak memory usage of eval)
 #
diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 5fc995dc15c1..f130bbc5b15f 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -6,7 +6,6 @@
 use bstr::{ByteSlice, ByteVec};
 use builtin_macros::builtins;
 use genawaiter::rc::Gen;
-use imbl::OrdMap;
 use regex::Regex;
 use std::cmp::{self, Ordering};
 use std::collections::BTreeMap;
@@ -795,7 +794,7 @@ mod pure_builtins {
         }
         let mut right_keys = right_set.keys();
 
-        let mut out: OrdMap<NixString, Value> = OrdMap::new();
+        let mut out: BTreeMap<NixString, Value> = BTreeMap::new();
 
         // Both iterators have at least one entry
         let mut left = left_keys.next().unwrap();
@@ -998,7 +997,7 @@ mod pure_builtins {
         attrs: Value,
     ) -> Result<Value, ErrorKind> {
         let attrs = attrs.to_attrs()?;
-        let mut out = imbl::OrdMap::new();
+        let mut out: BTreeMap<NixString, Value> = BTreeMap::new();
 
         // the best span we can get…
         let span = generators::request_span(&co).await;
diff --git a/tvix/eval/src/value/arbitrary.rs b/tvix/eval/src/value/arbitrary.rs
index 380eda0d9601..49b9f2eea3fb 100644
--- a/tvix/eval/src/value/arbitrary.rs
+++ b/tvix/eval/src/value/arbitrary.rs
@@ -1,7 +1,6 @@
 //! Support for configurable generation of arbitrary nix values
 
-use imbl::proptest::ord_map;
-use proptest::collection::vec;
+use proptest::collection::{btree_map, vec};
 use proptest::{prelude::*, strategy::BoxedStrategy};
 use std::ffi::OsString;
 
@@ -34,16 +33,16 @@ impl Arbitrary for NixAttrs {
     fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
         prop_oneof![
             // Empty attrs representation
-            Just(Self(AttrsRep::Empty)),
+            Just(AttrsRep::Empty.into()),
             // KV representation (name/value pairs)
             (
                 any_with::<Value>(args.clone()),
                 any_with::<Value>(args.clone())
             )
-                .prop_map(|(name, value)| Self(AttrsRep::KV { name, value })),
+                .prop_map(|(name, value)| AttrsRep::KV { name, value }.into()),
             // Map representation
-            ord_map(NixString::arbitrary(), Value::arbitrary_with(args), 0..100)
-                .prop_map(|map| Self(AttrsRep::Im(map)))
+            btree_map(NixString::arbitrary(), Value::arbitrary_with(args), 0..100)
+                .prop_map(|map| AttrsRep::Map(map).into())
         ]
         .boxed()
     }
diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs
index 128e44a18b59..00b913347418 100644
--- a/tvix/eval/src/value/attrs.rs
+++ b/tvix/eval/src/value/attrs.rs
@@ -6,10 +6,11 @@
 //! Due to this, construction and management of attribute sets has
 //! some peculiarities that are encapsulated within this module.
 use std::borrow::Borrow;
+use std::collections::{btree_map, BTreeMap};
 use std::iter::FromIterator;
+use std::rc::Rc;
 
 use bstr::BStr;
-use imbl::{ordmap, OrdMap};
 use lazy_static::lazy_static;
 use serde::de::{Deserializer, Error, Visitor};
 use serde::Deserialize;
@@ -36,7 +37,7 @@ pub(super) enum AttrsRep {
     #[default]
     Empty,
 
-    Im(OrdMap<NixString, Value>),
+    Map(BTreeMap<NixString, Value>),
 
     /// Warning: this represents a **two**-attribute attrset, with
     /// attribute names "name" and "value", like `{name="foo";
@@ -48,28 +49,6 @@ pub(super) enum 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 OrdMap<NixString, Value> {
-        match self {
-            AttrsRep::Im(m) => m,
-
-            AttrsRep::Empty => {
-                *self = AttrsRep::Im(OrdMap::new());
-                self.map_mut()
-            }
-
-            AttrsRep::KV { name, value } => {
-                *self = AttrsRep::Im(ordmap! {
-                    NAME_S.clone() => name.clone(),
-                    VALUE_S.clone() => value.clone()
-                });
-
-                self.map_mut()
-            }
-        }
-    }
-
     fn select(&self, key: &BStr) -> Option<&Value> {
         match self {
             AttrsRep::Empty => None,
@@ -80,7 +59,7 @@ impl AttrsRep {
                 _ => None,
             },
 
-            AttrsRep::Im(map) => map.get(key),
+            AttrsRep::Map(map) => map.get(key),
         }
     }
 
@@ -88,18 +67,18 @@ impl AttrsRep {
         match self {
             AttrsRep::Empty => false,
             AttrsRep::KV { .. } => key == "name" || key == "value",
-            AttrsRep::Im(map) => map.contains_key(key),
+            AttrsRep::Map(map) => map.contains_key(key),
         }
     }
 }
 
 #[repr(transparent)]
 #[derive(Clone, Debug, Default)]
-pub struct NixAttrs(pub(super) AttrsRep);
+pub struct NixAttrs(pub(super) Rc<AttrsRep>);
 
-impl From<OrdMap<NixString, Value>> for NixAttrs {
-    fn from(map: OrdMap<NixString, Value>) -> Self {
-        NixAttrs(AttrsRep::Im(map))
+impl From<AttrsRep> for NixAttrs {
+    fn from(rep: AttrsRep) -> Self {
+        NixAttrs(Rc::new(rep))
     }
 }
 
@@ -112,7 +91,18 @@ where
     where
         T: IntoIterator<Item = (K, V)>,
     {
-        NixAttrs(AttrsRep::Im(iter.into_iter().collect()))
+        AttrsRep::Map(
+            iter.into_iter()
+                .map(|(k, v)| (k.into(), v.into()))
+                .collect(),
+        )
+        .into()
+    }
+}
+
+impl From<BTreeMap<NixString, Value>> for NixAttrs {
+    fn from(map: BTreeMap<NixString, Value>) -> Self {
+        AttrsRep::Map(map).into()
     }
 }
 
@@ -132,26 +122,10 @@ impl TotalDisplay for NixAttrs {
 
         f.write_str("{ ")?;
 
-        match &self.0 {
-            AttrsRep::KV { name, value } => {
-                f.write_str("name = ")?;
-                name.total_fmt(f, set)?;
-                f.write_str("; ")?;
-
-                f.write_str("value = ")?;
-                value.total_fmt(f, set)?;
-                f.write_str("; ")?;
-            }
-
-            AttrsRep::Im(map) => {
-                for (name, value) in map {
-                    write!(f, "{} = ", name.ident_str())?;
-                    value.total_fmt(f, set)?;
-                    f.write_str("; ")?;
-                }
-            }
-
-            AttrsRep::Empty => { /* no values to print! */ }
+        for (name, value) in self.iter_sorted() {
+            write!(f, "{} = ", name.ident_str())?;
+            value.total_fmt(f, set)?;
+            f.write_str("; ")?;
         }
 
         f.write_str("}")
@@ -195,25 +169,22 @@ impl<'de> Deserialize<'de> for NixAttrs {
 
 impl NixAttrs {
     pub fn empty() -> Self {
-        Self(AttrsRep::Empty)
+        AttrsRep::Empty.into()
     }
 
     /// Compare two attribute sets by pointer equality. Only makes
-    /// sense for some attribute set reprsentations, i.e. returning
+    /// sense for some attribute set representations, i.e. returning
     /// `false` does not mean that the two attribute sets do not have
     /// equal *content*.
     pub fn ptr_eq(&self, other: &Self) -> bool {
-        match (&self.0, &other.0) {
-            (AttrsRep::Im(lhs), AttrsRep::Im(rhs)) => lhs.ptr_eq(rhs),
-            _ => false,
-        }
+        Rc::ptr_eq(&self.0, &other.0)
     }
 
     /// Return an attribute set containing the merge of the two
     /// provided sets. Keys from the `other` set have precedence.
     pub fn update(self, other: Self) -> Self {
         // Short-circuit on some optimal cases:
-        match (&self.0, &other.0) {
+        match (self.0.as_ref(), other.0.as_ref()) {
             (AttrsRep::Empty, AttrsRep::Empty) => return self,
             (AttrsRep::Empty, _) => return other,
             (_, AttrsRep::Empty) => return self,
@@ -222,41 +193,44 @@ 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::Im(_), AttrsRep::Im(_))
-            | (AttrsRep::Im(_), AttrsRep::KV { .. })
-            | (AttrsRep::KV { .. }, AttrsRep::Im(_)) => {}
+            (AttrsRep::Map(_), AttrsRep::Map(_))
+            | (AttrsRep::Map(_), AttrsRep::KV { .. })
+            | (AttrsRep::KV { .. }, AttrsRep::Map(_)) => {}
         };
 
         // Slightly more advanced, but still optimised updates
-        match (self.0, other.0) {
-            (AttrsRep::Im(mut m), AttrsRep::KV { name, value }) => {
+        match (Rc::unwrap_or_clone(self.0), Rc::unwrap_or_clone(other.0)) {
+            (AttrsRep::Map(mut m), AttrsRep::KV { name, value }) => {
                 m.insert(NAME_S.clone(), name);
                 m.insert(VALUE_S.clone(), value);
-                NixAttrs(AttrsRep::Im(m))
+                AttrsRep::Map(m).into()
             }
 
-            (AttrsRep::KV { name, value }, AttrsRep::Im(mut m)) => {
+            (AttrsRep::KV { name, value }, AttrsRep::Map(mut m)) => {
                 match m.entry(NAME_S.clone()) {
-                    imbl::ordmap::Entry::Vacant(e) => {
+                    btree_map::Entry::Vacant(e) => {
                         e.insert(name);
                     }
 
-                    imbl::ordmap::Entry::Occupied(_) => { /* name from `m` has precedence */ }
+                    btree_map::Entry::Occupied(_) => { /* name from `m` has precedence */ }
                 };
 
                 match m.entry(VALUE_S.clone()) {
-                    imbl::ordmap::Entry::Vacant(e) => {
+                    btree_map::Entry::Vacant(e) => {
                         e.insert(value);
                     }
 
-                    imbl::ordmap::Entry::Occupied(_) => { /* value from `m` has precedence */ }
+                    btree_map::Entry::Occupied(_) => { /* value from `m` has precedence */ }
                 };
 
-                NixAttrs(AttrsRep::Im(m))
+                AttrsRep::Map(m).into()
             }
 
             // Plain merge of maps.
-            (AttrsRep::Im(m1), AttrsRep::Im(m2)) => NixAttrs(AttrsRep::Im(m2.union(m1))),
+            (AttrsRep::Map(mut m1), AttrsRep::Map(m2)) => {
+                m1.extend(m2);
+                AttrsRep::Map(m1).into()
+            }
 
             // Cases handled above by the borrowing match:
             _ => unreachable!(),
@@ -265,16 +239,16 @@ impl NixAttrs {
 
     /// Return the number of key-value entries in an attrset.
     pub fn len(&self) -> usize {
-        match &self.0 {
-            AttrsRep::Im(map) => map.len(),
+        match self.0.as_ref() {
+            AttrsRep::Map(map) => map.len(),
             AttrsRep::Empty => 0,
             AttrsRep::KV { .. } => 2,
         }
     }
 
     pub fn is_empty(&self) -> bool {
-        match &self.0 {
-            AttrsRep::Im(map) => map.is_empty(),
+        match self.0.as_ref() {
+            AttrsRep::Map(map) => map.is_empty(),
             AttrsRep::Empty => true,
             AttrsRep::KV { .. } => false,
         }
@@ -310,8 +284,8 @@ impl NixAttrs {
     /// Construct an iterator over all the key-value pairs in the attribute set.
     #[allow(clippy::needless_lifetimes)]
     pub fn iter<'a>(&'a self) -> Iter<KeyValue<'a>> {
-        Iter(match &self.0 {
-            AttrsRep::Im(map) => KeyValue::Im(map.iter()),
+        Iter(match &self.0.as_ref() {
+            AttrsRep::Map(map) => KeyValue::Map(map.iter()),
             AttrsRep::Empty => KeyValue::Empty,
 
             AttrsRep::KV {
@@ -339,10 +313,12 @@ impl NixAttrs {
 
     /// Construct an iterator over all the keys of the attribute set
     pub fn keys(&self) -> Keys {
-        Keys(match &self.0 {
+        Keys(match self.0.as_ref() {
             AttrsRep::Empty => KeysInner::Empty,
-            AttrsRep::Im(m) => KeysInner::Im(m.keys()),
             AttrsRep::KV { .. } => KeysInner::KV(IterKV::default()),
+
+            // TODO(tazjin): only sort when required, not always.
+            AttrsRep::Map(m) => KeysInner::Map(m.keys()),
         })
     }
 
@@ -361,7 +337,7 @@ impl NixAttrs {
 
         // Optimisation: Empty attribute set
         if count == 0 {
-            return Ok(Ok(NixAttrs(AttrsRep::Empty)));
+            return Ok(Ok(AttrsRep::Empty.into()));
         }
 
         // Optimisation: KV pattern
@@ -371,14 +347,14 @@ impl NixAttrs {
             }
         }
 
-        let mut attrs = NixAttrs(AttrsRep::Im(OrdMap::new()));
+        let mut attrs_map = BTreeMap::new();
 
         for _ in 0..count {
             let value = stack_slice.pop().unwrap();
             let key = stack_slice.pop().unwrap();
 
             match key {
-                Value::String(ks) => set_attr(&mut attrs, ks, value)?,
+                Value::String(ks) => set_attr(&mut attrs_map, ks, value)?,
 
                 Value::Null => {
                     // This is in fact valid, but leads to the value
@@ -393,13 +369,13 @@ impl NixAttrs {
             }
         }
 
-        Ok(Ok(attrs))
+        Ok(Ok(AttrsRep::Map(attrs_map).into()))
     }
 
     /// Construct an optimized "KV"-style attribute set given the value for the
     /// `"name"` key, and the value for the `"value"` key
     pub(crate) fn from_kv(name: Value, value: Value) -> Self {
-        NixAttrs(AttrsRep::KV { name, value })
+        AttrsRep::KV { name, value }.into()
     }
 }
 
@@ -408,12 +384,12 @@ impl IntoIterator for NixAttrs {
     type IntoIter = OwnedAttrsIterator;
 
     fn into_iter(self) -> Self::IntoIter {
-        match self.0 {
+        match Rc::unwrap_or_clone(self.0) {
             AttrsRep::Empty => OwnedAttrsIterator(IntoIterRepr::Empty),
             AttrsRep::KV { name, value } => OwnedAttrsIterator(IntoIterRepr::Finite(
                 vec![(NAME_REF.clone(), name), (VALUE_REF.clone(), value)].into_iter(),
             )),
-            AttrsRep::Im(map) => OwnedAttrsIterator(IntoIterRepr::Im(map.into_iter())),
+            AttrsRep::Map(map) => OwnedAttrsIterator(IntoIterRepr::Map(map.into_iter())),
         }
     }
 }
@@ -452,13 +428,17 @@ fn attempt_optimise_kv(slice: &mut [Value]) -> Option<NixAttrs> {
 
 /// Set an attribute on an in-construction attribute set, while
 /// checking against duplicate keys.
-fn set_attr(attrs: &mut NixAttrs, key: NixString, value: Value) -> Result<(), ErrorKind> {
-    match attrs.0.map_mut().entry(key) {
-        imbl::ordmap::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey {
+fn set_attr(
+    map: &mut BTreeMap<NixString, Value>,
+    key: NixString,
+    value: Value,
+) -> Result<(), ErrorKind> {
+    match map.entry(key) {
+        btree_map::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey {
             key: entry.key().to_string(),
         }),
 
-        imbl::ordmap::Entry::Vacant(entry) => {
+        btree_map::Entry::Vacant(entry) => {
             entry.insert(value);
             Ok(())
         }
@@ -496,7 +476,7 @@ pub enum KeyValue<'a> {
         at: IterKV,
     },
 
-    Im(imbl::ordmap::Iter<'a, NixString, Value>),
+    Map(btree_map::Iter<'a, NixString, Value>),
 }
 
 /// Iterator over a Nix attribute set.
@@ -510,7 +490,7 @@ impl<'a> Iterator for Iter<KeyValue<'a>> {
 
     fn next(&mut self) -> Option<Self::Item> {
         match &mut self.0 {
-            KeyValue::Im(inner) => inner.next(),
+            KeyValue::Map(inner) => inner.next(),
             KeyValue::Empty => None,
 
             KeyValue::KV { name, value, at } => match at {
@@ -535,7 +515,7 @@ impl<'a> ExactSizeIterator for Iter<KeyValue<'a>> {
         match &self.0 {
             KeyValue::Empty => 0,
             KeyValue::KV { .. } => 2,
-            KeyValue::Im(inner) => inner.len(),
+            KeyValue::Map(inner) => inner.len(),
         }
     }
 }
@@ -543,7 +523,7 @@ impl<'a> ExactSizeIterator for Iter<KeyValue<'a>> {
 enum KeysInner<'a> {
     Empty,
     KV(IterKV),
-    Im(imbl::ordmap::Keys<'a, NixString, Value>),
+    Map(btree_map::Keys<'a, NixString, Value>),
 }
 
 pub struct Keys<'a>(KeysInner<'a>);
@@ -563,7 +543,7 @@ impl<'a> Iterator for Keys<'a> {
                 Some(&VALUE_REF)
             }
             KeysInner::KV(IterKV::Done) => None,
-            KeysInner::Im(m) => m.next(),
+            KeysInner::Map(m) => m.next(),
         }
     }
 }
@@ -583,7 +563,7 @@ impl<'a> ExactSizeIterator for Keys<'a> {
         match &self.0 {
             KeysInner::Empty => 0,
             KeysInner::KV(_) => 2,
-            KeysInner::Im(m) => m.len(),
+            KeysInner::Map(m) => m.len(),
         }
     }
 }
@@ -592,7 +572,7 @@ impl<'a> ExactSizeIterator for Keys<'a> {
 pub enum IntoIterRepr {
     Empty,
     Finite(std::vec::IntoIter<(NixString, Value)>),
-    Im(imbl::ordmap::ConsumingIter<(NixString, Value)>),
+    Map(btree_map::IntoIter<NixString, Value>),
 }
 
 /// Wrapper type which hides the internal implementation details from
@@ -607,7 +587,7 @@ impl Iterator for OwnedAttrsIterator {
         match &mut self.0 {
             IntoIterRepr::Empty => None,
             IntoIterRepr::Finite(inner) => inner.next(),
-            IntoIterRepr::Im(inner) => inner.next(),
+            IntoIterRepr::Map(m) => m.next(),
         }
     }
 }
@@ -617,7 +597,7 @@ impl ExactSizeIterator for OwnedAttrsIterator {
         match &self.0 {
             IntoIterRepr::Empty => 0,
             IntoIterRepr::Finite(inner) => inner.len(),
-            IntoIterRepr::Im(inner) => inner.len(),
+            IntoIterRepr::Map(inner) => inner.len(),
         }
     }
 }
@@ -627,7 +607,7 @@ impl DoubleEndedIterator for OwnedAttrsIterator {
         match &mut self.0 {
             IntoIterRepr::Empty => None,
             IntoIterRepr::Finite(inner) => inner.next_back(),
-            IntoIterRepr::Im(inner) => inner.next_back(),
+            IntoIterRepr::Map(inner) => inner.next_back(),
         }
     }
 }
diff --git a/tvix/eval/src/value/attrs/tests.rs b/tvix/eval/src/value/attrs/tests.rs
index 534b78a00d10..b79f45a71b28 100644
--- a/tvix/eval/src/value/attrs/tests.rs
+++ b/tvix/eval/src/value/attrs/tests.rs
@@ -9,7 +9,7 @@ fn test_empty_attrs() {
         .unwrap();
 
     assert!(
-        matches!(attrs, NixAttrs(AttrsRep::Empty)),
+        matches!(attrs.0.as_ref(), AttrsRep::Empty),
         "empty attribute set should use optimised representation"
     );
 }
@@ -21,7 +21,7 @@ fn test_simple_attrs() {
         .unwrap();
 
     assert!(
-        matches!(attrs, NixAttrs(AttrsRep::Im(_))),
+        matches!(attrs.0.as_ref(), AttrsRep::Map(_)),
         "simple attribute set should use map representation",
     )
 }
@@ -45,8 +45,8 @@ fn test_kv_attrs() {
     .expect("constructing K/V pair attrs should succeed")
     .unwrap();
 
-    match kv_attrs {
-        NixAttrs(AttrsRep::KV { name, value })
+    match kv_attrs.0.as_ref() {
+        AttrsRep::KV { name, value }
             if name.to_str().unwrap() == meaning_val.to_str().unwrap()
                 || value.to_str().unwrap() == forty_two_val.to_str().unwrap() => {}
 
diff --git a/tvix/glue/benches/eval.rs b/tvix/glue/benches/eval.rs
index 0a27d9aa26fe..a0823d2e129b 100644
--- a/tvix/glue/benches/eval.rs
+++ b/tvix/glue/benches/eval.rs
@@ -60,7 +60,7 @@ fn interpret(code: &str) {
     let eval = eval_builder.build();
     let result = eval.evaluate(code, None);
 
-    assert!(result.errors.is_empty());
+    assert!(result.errors.is_empty(), "{:#?}", result.errors);
 }
 
 fn eval_nixpkgs(c: &mut Criterion) {