From 5d73c06b1a67bce68dcc0b2bd5f087ce00ab6317 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Thu, 29 Dec 2022 14:44:09 +0300 Subject: refactor(tvix/eval): use im::Vector for NixList representation This is a persistent, structurally sharing data structure which is more efficient in some of our use-cases. I have verified the efficiency improvement using `hyperfine` repeatedly over expressions on nixpkgs. Lists are not the most performance-critical structure in Nix (that would be attribute sets), but we can already see a small (~5-10%) improvement. Note that there are a handful of cases where we still go via `Vec` that need to be fixed, most notable for `builtins.sort` which can not currently be implemented directly using `im::Vector` because of a restrictive type bound. Change-Id: I237cc50cbd7629a046e5a5e4601fbb40355e551d Reviewed-on: https://cl.tvl.fyi/c/depot/+/7670 Tested-by: BuildkiteCI Reviewed-by: sterni --- tvix/eval/src/builtins/mod.rs | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'tvix/eval/src/builtins/mod.rs') diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs index 3c635eb364ca..709d2918f3c0 100644 --- a/tvix/eval/src/builtins/mod.rs +++ b/tvix/eval/src/builtins/mod.rs @@ -772,7 +772,12 @@ mod pure_builtins { #[builtin("sort")] fn builtin_sort(vm: &mut VM, comparator: Value, list: Value) -> Result { - let mut list = list.to_list()?.into_vec(); + // TODO: the bound on the sort function in + // `im::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. + let mut list = list.to_list()?.into_iter().collect::>(); // Used to let errors "escape" from the sorting closure. If anything // ends up setting an error, it is returned from this function. -- cgit 1.4.1