refactor(tvix/eval): remove use of imbl::Vector r/8520

This vector type has served us well for now, but it contains internal refcounts
which are incompatible with upcoming changes related to garbage collection.

The performance impact of this change within all benchmarks I ran was within the
margin of error:

[nix-shell:/tmp/perf]$ hyperfine "./before -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings"
Benchmark 1: ./u64 -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings
  Time (mean ± σ):      7.528 s ±  0.272 s    [User: 6.578 s, System: 0.631 s]
  Range (min … max):    7.160 s …  8.012 s    10 runs

nix-shell:/tmp/perf]$ hyperfine "./std-vec -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings"
Benchmark 1: ./std-vec -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings
  Time (mean ± σ):      7.515 s ±  0.178 s    [User: 6.508 s, System: 0.652 s]
  Range (min … max):    7.276 s …  7.861 s    10 runs

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

1 files changed, 32 insertions, 28 deletions

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index e961738e3653..5fc995dc15c1 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -85,7 +85,6 @@ mod pure_builtins {
     use std::ffi::OsString;
 
     use bstr::{BString, ByteSlice, B};
-    use imbl::Vector;
     use itertools::Itertools;
     use os_str_bytes::OsStringBytes;
     use rustc_hash::FxHashSet;
@@ -246,7 +245,7 @@ mod pure_builtins {
 
     #[builtin("concatLists")]
     async fn builtin_concat_lists(co: GenCo, lists: Value) -> Result<Value, ErrorKind> {
-        let mut out = imbl::Vector::new();
+        let mut out = Vec::new();
 
         for value in lists.to_list()? {
             let list = try_value!(generators::request_force(&co, value).await).to_list()?;
@@ -259,7 +258,7 @@ mod pure_builtins {
     #[builtin("concatMap")]
     async fn builtin_concat_map(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> {
         let list = list.to_list()?;
-        let mut res = imbl::Vector::new();
+        let mut res = Vec::new();
         for val in list {
             let out = generators::request_call_with(&co, f.clone(), [val]).await;
             let out = try_value!(generators::request_force(&co, out).await);
@@ -387,13 +386,13 @@ mod pure_builtins {
     #[builtin("filter")]
     async fn builtin_filter(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> {
         let list: NixList = list.to_list()?;
-        let mut out = imbl::Vector::new();
+        let mut out = Vec::new();
 
         for value in list {
             let result = generators::request_call_with(&co, pred.clone(), [value.clone()]).await;
             let verdict = try_value!(generators::request_force(&co, result).await);
             if verdict.as_bool()? {
-                out.push_back(value);
+                out.push(value);
             }
         }
 
@@ -481,7 +480,7 @@ mod pure_builtins {
 
         let operator = attrs.select_required("operator")?;
 
-        let mut res = imbl::Vector::new();
+        let mut res = Vec::new();
         let mut done_keys: Vec<Value> = vec![];
 
         while let Some(val) = work_set.pop_front() {
@@ -499,7 +498,7 @@ mod pure_builtins {
                 continue;
             }
 
-            res.push_back(val.clone());
+            res.push(val.clone());
 
             let op_result = generators::request_force(
                 &co,
@@ -520,14 +519,18 @@ mod pure_builtins {
         #[lazy] generator: Value,
         length: Value,
     ) -> Result<Value, ErrorKind> {
-        let mut out = imbl::Vector::<Value>::new();
         let len = length.as_int()?;
+        let mut out = Vec::with_capacity(
+            len.try_into()
+                .map_err(|_| ErrorKind::Abort(format!("can not create list of size {}", len)))?,
+        );
+
         // the best span we can get…
         let span = generators::request_span(&co).await;
 
         for i in 0..len {
             let val = Value::Thunk(Thunk::new_suspended_call(generator.clone(), i.into(), span));
-            out.push_back(val);
+            out.push(val);
         }
 
         Ok(Value::List(out.into()))
@@ -548,7 +551,7 @@ mod pure_builtins {
 
     #[builtin("groupBy")]
     async fn builtin_group_by(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut res: BTreeMap<NixString, imbl::Vector<Value>> = BTreeMap::new();
+        let mut res: BTreeMap<NixString, Vec<Value>> = BTreeMap::new();
         for val in list.to_list()? {
             let key = try_value!(
                 generators::request_force(
@@ -559,7 +562,7 @@ mod pure_builtins {
             )
             .to_str()?;
 
-            res.entry(key).or_default().push_back(val);
+            res.entry(key).or_default().push(val);
         }
         Ok(Value::attrs(NixAttrs::from_iter(
             res.into_iter()
@@ -625,7 +628,7 @@ mod pure_builtins {
         let elements = groups
             .into_iter()
             .map(|(key, group)| {
-                let mut outputs: Vector<NixString> = Vector::new();
+                let mut outputs: Vec<NixString> = Vec::new();
                 let mut is_path = false;
                 let mut all_outputs = false;
 
@@ -638,7 +641,7 @@ mod pure_builtins {
 
                         NixContextElement::Single { name, derivation } => {
                             debug_assert!(derivation == key, "Unexpected group containing mixed keys, expected: {:?}, encountered {:?}", key, derivation);
-                            outputs.push_back(name.clone().into());
+                            outputs.push(name.clone().into());
                         }
 
                         NixContextElement::Derivation(drv_path) => {
@@ -665,7 +668,7 @@ mod pure_builtins {
                     vec_attrs.push(("outputs", Value::List(outputs
                                 .into_iter()
                                 .map(|s| s.into())
-                                .collect::<Vector<Value>>()
+                                .collect::<Vec<Value>>()
                                 .into()
                     )));
                 }
@@ -973,15 +976,16 @@ mod pure_builtins {
     }
 
     #[builtin("map")]
-    async fn builtin_map(co: GenCo, #[lazy] f: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut out = imbl::Vector::<Value>::new();
+    async fn builtin_map(co: GenCo, #[lazy] f: Value, list_val: Value) -> Result<Value, ErrorKind> {
+        let list = list_val.to_list()?;
+        let mut out = Vec::with_capacity(list.len());
 
         // the best span we can get…
         let span = generators::request_span(&co).await;
 
-        for val in list.to_list()? {
+        for val in list {
             let result = Value::Thunk(Thunk::new_suspended_call(f.clone(), val, span));
-            out.push_back(result)
+            out.push(result)
         }
 
         Ok(Value::List(out.into()))
@@ -1040,7 +1044,7 @@ mod pure_builtins {
                         // and then a compressor name will be extracted from that.
                         grp.map(|g| Value::from(g.as_str())).unwrap_or(Value::Null)
                     })
-                    .collect::<imbl::Vector<Value>>()
+                    .collect::<Vec<Value>>()
                     .into(),
             )),
             None => Ok(Value::Null),
@@ -1083,17 +1087,17 @@ mod pure_builtins {
 
     #[builtin("partition")]
     async fn builtin_partition(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut right: imbl::Vector<Value> = Default::default();
-        let mut wrong: imbl::Vector<Value> = Default::default();
+        let mut right: Vec<Value> = Default::default();
+        let mut wrong: Vec<Value> = Default::default();
 
         let list: NixList = list.to_list()?;
         for elem in list {
             let result = generators::request_call_with(&co, pred.clone(), [elem.clone()]).await;
 
             if try_value!(generators::request_force(&co, result).await).as_bool()? {
-                right.push_back(elem);
+                right.push(elem);
             } else {
-                wrong.push_back(elem);
+                wrong.push(elem);
             };
         }
 
@@ -1248,12 +1252,12 @@ mod pure_builtins {
         let re = Regex::new(re.to_str()?).unwrap();
         let mut capture_locations = re.capture_locations();
         let num_captures = capture_locations.len();
-        let mut ret = imbl::Vector::new();
+        let mut ret = Vec::new();
         let mut pos = 0;
 
         while let Some(thematch) = re.captures_read_at(&mut capture_locations, text, pos) {
             // push the unmatched characters preceding the match
-            ret.push_back(Value::from(NixString::new_inherit_context_from(
+            ret.push(Value::from(NixString::new_inherit_context_from(
                 &s,
                 &text[pos..thematch.start()],
             )));
@@ -1262,7 +1266,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: imbl::Vector<Value> = (1..num_captures)
+            let v: Vec<Value> = (1..num_captures)
                 .map(|i| capture_locations.get(i))
                 .map(|o| {
                     o.map(|(start, end)| {
@@ -1273,7 +1277,7 @@ mod pure_builtins {
                     .unwrap_or(Value::Null)
                 })
                 .collect();
-            ret.push_back(Value::List(NixList::from(v)));
+            ret.push(Value::List(NixList::from(v)));
             if pos == text.len() {
                 break;
             }
@@ -1283,7 +1287,7 @@ mod pure_builtins {
         // push the unmatched characters following the last match
         // Here, a surprising thing happens: we silently discard the original
         // context. This is as intended, Nix does the same.
-        ret.push_back(Value::from(&text[pos..]));
+        ret.push(Value::from(&text[pos..]));
 
         Ok(Value::List(NixList::from(ret)))
     }