From 3a2fcc8bc2eb3895a5dfdb268869d550e359ffe7 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Fri, 26 Aug 2022 19:22:18 +0300 Subject: refactor(tvix/eval): avoid cloning in NixAttrs::update if possible Refactors the update function to take the attribute sets by value instead. To facilitate this, we use an equivalent of the currently unstable `Rc::clone_or_unwrap` in the VM when encountering attribute sets, so that in cases where the only references to the attrs being updated are the ones on the stack those clones are avoided completely. This does make update() a little bit more tricky internally, as some optimised branches can directly return the moved value, and others need to destructure with ownership. For this reason there are now two different match statements handling the different ownership cases. Change-Id: Ia77d3ba5c86afb75b9f1f51758bda61729ba5aab Reviewed-on: https://cl.tvl.fyi/c/depot/+/6279 Tested-by: BuildkiteCI Reviewed-by: sterni --- tvix/eval/src/value/attrs.rs | 47 +++++++++++++++++++++++++------------------- tvix/eval/src/vm.rs | 12 ++++++++--- 2 files changed, 36 insertions(+), 23 deletions(-) diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs index 922aa0c0d37a..62fb9b710c4f 100644 --- a/tvix/eval/src/value/attrs.rs +++ b/tvix/eval/src/value/attrs.rs @@ -151,28 +151,34 @@ impl PartialEq for NixAttrs { impl NixAttrs { // Update one attribute set with the values of the other. - pub fn update(&self, other: &Self) -> Self { + pub fn update(self, other: Self) -> Self { + // Short-circuit on some optimal cases: match (&self.0, &other.0) { - // Short-circuit on some optimal cases: - (AttrsRep::Empty, AttrsRep::Empty) => NixAttrs(AttrsRep::Empty), - (AttrsRep::Empty, _) => other.clone(), - (_, AttrsRep::Empty) => self.clone(), - (AttrsRep::KV { .. }, AttrsRep::KV { .. }) => other.clone(), - - // Slightly more advanced, but still optimised updates - (AttrsRep::Map(m), AttrsRep::KV { name, value }) => { - let mut m = m.clone(); - m.insert(NixString::NAME, name.clone()); - m.insert(NixString::VALUE, value.clone()); + (AttrsRep::Empty, AttrsRep::Empty) => return self, + (AttrsRep::Empty, _) => return other, + (_, AttrsRep::Empty) => return self, + (AttrsRep::KV { .. }, AttrsRep::KV { .. }) => return other, + + // 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(_)) => {} + }; + + // Slightly more advanced, but still optimised updates + match (self.0, other.0) { + (AttrsRep::Map(mut m), AttrsRep::KV { name, value }) => { + m.insert(NixString::NAME, name); + m.insert(NixString::VALUE, value); NixAttrs(AttrsRep::Map(m)) } - (AttrsRep::KV { name, value }, AttrsRep::Map(m)) => { - let mut m = m.clone(); - + (AttrsRep::KV { name, value }, AttrsRep::Map(mut m)) => { match m.entry(NixString::NAME) { btree_map::Entry::Vacant(e) => { - e.insert(name.clone()); + e.insert(name); } btree_map::Entry::Occupied(_) => { /* name from `m` has precedence */ } @@ -180,7 +186,7 @@ impl NixAttrs { match m.entry(NixString::VALUE) { btree_map::Entry::Vacant(e) => { - e.insert(value.clone()); + e.insert(value); } btree_map::Entry::Occupied(_) => { /* value from `m` has precedence */ } @@ -190,12 +196,13 @@ impl NixAttrs { } // Plain merge of maps. - (AttrsRep::Map(m1), AttrsRep::Map(m2)) => { - let mut m1 = m1.clone(); - let mut m2 = m2.clone(); + (AttrsRep::Map(mut m1), AttrsRep::Map(mut m2)) => { m1.append(&mut m2); NixAttrs(AttrsRep::Map(m1)) } + + // Cases handled above by the borrowing match: + _ => unreachable!(), } } diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs index 65534006d0e1..6de9cd03c49c 100644 --- a/tvix/eval/src/vm.rs +++ b/tvix/eval/src/vm.rs @@ -203,10 +203,10 @@ impl VM { OpCode::OpAttrPath(count) => self.run_attr_path(count)?, OpCode::OpAttrsUpdate => { - let rhs = self.pop().to_attrs()?; - let lhs = self.pop().to_attrs()?; + let rhs = unwrap_or_clone_rc(self.pop().to_attrs()?); + let lhs = unwrap_or_clone_rc(self.pop().to_attrs()?); - self.push(Value::Attrs(Rc::new(lhs.update(&rhs)))) + self.push(Value::Attrs(Rc::new(lhs.update(rhs)))) } OpCode::OpAttrsSelect => { @@ -414,6 +414,12 @@ impl VM { } } +// TODO: use Rc::unwrap_or_clone once it is stabilised. +// https://doc.rust-lang.org/std/rc/struct.Rc.html#method.unwrap_or_clone +fn unwrap_or_clone_rc(rc: Rc) -> T { + Rc::try_unwrap(rc).unwrap_or_else(|rc| (*rc).clone()) +} + pub fn run_lambda(lambda: Lambda) -> EvalResult { let mut vm = VM { frames: vec![], -- cgit 1.4.1