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

1 files changed, 39 insertions, 50 deletions

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";