diff options
author | Vincent Ambo <mail@tazj.in> | 2023-03-11T22·21+0300 |
---|---|---|
committer | tazjin <tazjin@tvl.su> | 2023-03-13T20·30+0000 |
commit | 94513525b939a13fb19330fe74dd9f6860a854fe (patch) | |
tree | eef187c03a9c62f934dfb5784415f53691344a2b | |
parent | c37e41d58305bcc6f20a92eb35aaa9dea3a977f0 (diff) |
refactor(tvix/eval): reorder bytecode operations match by frequency r/5987
This reorders the operations in the VM's main `match` statement while evaluating bytecode according to the frequency with which these operations appear in some nixpkgs evaluations. I used raw data that looks like this: https://gist.github.com/tazjin/63d0788a78eb8575b04defaad4ef610d This has a small but noticeable impact on evaluation performance. No operations have changed in any way, this is purely moving code around. Change-Id: Iaa4ef4f0577e98144e8905fec88149c41e8c315c Reviewed-on: https://cl.tvl.fyi/c/depot/+/8262 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
-rw-r--r-- | tvix/eval/src/vm/mod.rs | 529 |
1 files changed, 264 insertions, 265 deletions
diff --git a/tvix/eval/src/vm/mod.rs b/tvix/eval/src/vm/mod.rs index e2ff4ea94573..ca974dff1262 100644 --- a/tvix/eval/src/vm/mod.rs +++ b/tvix/eval/src/vm/mod.rs @@ -382,105 +382,105 @@ impl<'o> VM<'o> { let op = frame.inc_ip(); self.observer.observe_execute_op(frame.ip, &op, &self.stack); - // TODO: might be useful to reorder ops with most frequent ones first match op { - // Discard the current frame. - OpCode::OpReturn => { - return Ok(true); - } + OpCode::OpThunkSuspended(idx) | OpCode::OpThunkClosure(idx) => { + let blueprint = match &frame.chunk()[idx] { + Value::Blueprint(lambda) => lambda.clone(), + _ => panic!("compiler bug: non-blueprint in blueprint slot"), + }; - OpCode::OpConstant(idx) => { - let c = frame.chunk()[idx].clone(); - self.stack.push(c); - } + let upvalue_count = blueprint.upvalue_count; + let thunk = if matches!(op, OpCode::OpThunkClosure(_)) { + debug_assert!( + upvalue_count > 0, + "OpThunkClosure should not be called for plain lambdas" + ); + Thunk::new_closure(blueprint) + } else { + Thunk::new_suspended(blueprint, frame.current_light_span()) + }; + let upvalues = thunk.upvalues_mut(); + self.stack.push(Value::Thunk(thunk.clone())); - OpCode::OpPop => { - self.stack.pop(); + // From this point on we internally mutate the + // upvalues. The closure (if `is_closure`) is + // already in its stack slot, which means that it + // can capture itself as an upvalue for + // self-recursion. + self.populate_upvalues(&mut frame, upvalue_count, upvalues)?; } - OpCode::OpAdd => { - let b = self.stack_pop(); - let a = self.stack_pop(); + OpCode::OpForce => { + if let Some(Value::Thunk(_)) = self.stack.last() { + let thunk = match self.stack_pop() { + Value::Thunk(t) => t, + _ => unreachable!(), + }; - let gen_span = frame.current_light_span(); - self.push_call_frame(span, frame); + let gen_span = frame.current_light_span(); - // OpAdd can add not just numbers, but also string-like - // things, which requires more VM logic. This operation is - // evaluated in a generator frame. - self.enqueue_generator("add_values", gen_span, |co| add_values(co, a, b)); - return Ok(false); + self.push_call_frame(span, frame); + self.enqueue_generator("force", gen_span, |co| thunk.force(co)); + return Ok(false); + } } - OpCode::OpSub => { - let b = self.stack_pop(); - let a = self.stack_pop(); - let result = arithmetic_op!(&a, &b, -).with_span(&frame)?; - self.stack.push(result); + OpCode::OpGetUpvalue(upv_idx) => { + let value = frame.upvalue(upv_idx).clone(); + self.stack.push(value); } - OpCode::OpMul => { - let b = self.stack_pop(); - let a = self.stack_pop(); - let result = arithmetic_op!(&a, &b, *).with_span(&frame)?; - self.stack.push(result); + // Discard the current frame. + OpCode::OpReturn => { + return Ok(true); } - OpCode::OpDiv => { - let b = self.stack_pop(); + OpCode::OpConstant(idx) => { + let c = frame.chunk()[idx].clone(); + self.stack.push(c); + } - match b { - Value::Integer(0) => return Err(frame.error(ErrorKind::DivisionByZero)), - Value::Float(b) if b == 0.0_f64 => { - return Err(frame.error(ErrorKind::DivisionByZero)) - } - _ => {} - }; + OpCode::OpCall => { + let callable = self.stack_pop(); + self.call_value(frame.current_light_span(), Some(frame), callable)?; - let a = self.stack_pop(); - let result = arithmetic_op!(&a, &b, /).with_span(&frame)?; - self.stack.push(result); + // exit this loop and let the outer loop enter the new call + return Ok(true); } - OpCode::OpInvert => { - let v = self.stack_pop().as_bool().with_span(&frame)?; - self.stack.push(Value::Bool(!v)); - } + // Remove the given number of elements from the stack, + // but retain the top value. + OpCode::OpCloseScope(Count(count)) => { + // Immediately move the top value into the right + // position. + let target_idx = self.stack.len() - 1 - count; + self.stack[target_idx] = self.stack_pop(); - OpCode::OpNegate => match self.stack_pop() { - Value::Integer(i) => self.stack.push(Value::Integer(-i)), - Value::Float(f) => self.stack.push(Value::Float(-f)), - v => { - return Err(frame.error(ErrorKind::TypeError { - expected: "number (either int or float)", - actual: v.type_of(), - })); + // Then drop the remaining values. + for _ in 0..(count - 1) { + self.stack.pop(); } - }, - - OpCode::OpEqual => { - let b = self.stack_pop(); - let a = self.stack_pop(); - let gen_span = frame.current_light_span(); - self.push_call_frame(span, frame); - self.enqueue_generator("nix_eq", gen_span, |co| { - a.nix_eq(b, co, PointerEquality::ForbidAll) - }); - return Ok(false); } - OpCode::OpLess => cmp_op!(self, frame, span, <), - OpCode::OpLessOrEq => cmp_op!(self, frame, span, <=), - OpCode::OpMore => cmp_op!(self, frame, span, >), - OpCode::OpMoreOrEq => cmp_op!(self, frame, span, >=), - - OpCode::OpAttrs(Count(count)) => self.run_attrset(&frame, count)?, + OpCode::OpClosure(idx) => { + let blueprint = match &frame.chunk()[idx] { + Value::Blueprint(lambda) => lambda.clone(), + _ => panic!("compiler bug: non-blueprint in blueprint slot"), + }; - OpCode::OpAttrsUpdate => { - let rhs = self.stack_pop().to_attrs().with_span(&frame)?; - let lhs = self.stack_pop().to_attrs().with_span(&frame)?; + let upvalue_count = blueprint.upvalue_count; + debug_assert!( + upvalue_count > 0, + "OpClosure should not be called for plain lambdas" + ); - self.stack.push(Value::attrs(lhs.update(*rhs))) + let mut upvalues = Upvalues::with_capacity(blueprint.upvalue_count); + self.populate_upvalues(&mut frame, upvalue_count, &mut upvalues)?; + self.stack + .push(Value::Closure(Rc::new(Closure::new_with_upvalues( + Rc::new(upvalues), + blueprint, + )))); } OpCode::OpAttrsSelect => { @@ -498,6 +498,17 @@ impl<'o> VM<'o> { } } + OpCode::OpJumpIfFalse(JumpOffset(offset)) => { + debug_assert!(offset != 0); + if !self.stack_peek(0).as_bool().with_span(&frame)? { + frame.ip += offset; + } + } + + OpCode::OpPop => { + self.stack.pop(); + } + OpCode::OpAttrsTrySelect => { let key = self.stack_pop().to_str().with_span(&frame)?; let value = match self.stack_pop() { @@ -512,121 +523,35 @@ impl<'o> VM<'o> { self.stack.push(value); } - OpCode::OpHasAttr => { - let key = self.stack_pop().to_str().with_span(&frame)?; - let result = match self.stack_pop() { - Value::Attrs(attrs) => attrs.contains(key.as_str()), - - // Nix allows use of `?` on non-set types, but - // always returns false in those cases. - _ => false, - }; - - self.stack.push(Value::Bool(result)); + OpCode::OpGetLocal(StackIdx(local_idx)) => { + let idx = frame.stack_offset + local_idx; + self.stack.push(self.stack[idx].clone()); } - OpCode::OpValidateClosedFormals => { - let formals = frame.lambda.formals.as_ref().expect( - "OpValidateClosedFormals called within the frame of a lambda without formals", - ); - - let args = self.stack_peek(0).to_attrs().with_span(&frame)?; - for arg in args.keys() { - if !formals.contains(arg) { - return Err(frame.error(ErrorKind::UnexpectedArgument { - arg: arg.clone(), - formals_span: formals.span, - })); - } + OpCode::OpJumpIfNotFound(JumpOffset(offset)) => { + debug_assert!(offset != 0); + if matches!(self.stack_peek(0), Value::AttrNotFound) { + self.stack_pop(); + frame.ip += offset; } } - OpCode::OpList(Count(count)) => { - let list = - NixList::construct(count, self.stack.split_off(self.stack.len() - count)); - - self.stack.push(Value::List(list)); - } - - OpCode::OpConcat => { - let rhs = self.stack_pop().to_list().with_span(&frame)?.into_inner(); - let lhs = self.stack_pop().to_list().with_span(&frame)?.into_inner(); - self.stack.push(Value::List(NixList::from(lhs + rhs))) + OpCode::OpJump(JumpOffset(offset)) => { + debug_assert!(offset != 0); + frame.ip += offset; } - OpCode::OpInterpolate(Count(count)) => self.run_interpolate(&frame, count)?, - - OpCode::OpCoerceToString => { - let value = self.stack_pop(); + OpCode::OpEqual => { + let b = self.stack_pop(); + let a = self.stack_pop(); let gen_span = frame.current_light_span(); self.push_call_frame(span, frame); - - self.enqueue_generator("coerce_to_string", gen_span, |co| { - value.coerce_to_string(co, CoercionKind::Weak) + self.enqueue_generator("nix_eq", gen_span, |co| { + a.nix_eq(b, co, PointerEquality::ForbidAll) }); - return Ok(false); } - OpCode::OpFindFile => match self.stack_pop() { - Value::UnresolvedPath(path) => { - let resolved = self - .nix_search_path - .resolve(&*self.io_handle, *path) - .with_span(&frame)?; - self.stack.push(resolved.into()); - } - - _ => panic!("tvix compiler bug: OpFindFile called on non-UnresolvedPath"), - }, - - OpCode::OpResolveHomePath => match self.stack_pop() { - Value::UnresolvedPath(path) => { - match dirs::home_dir() { - None => { - return Err(frame.error(ErrorKind::RelativePathResolution( - "failed to determine home directory".into(), - ))); - } - Some(mut buf) => { - buf.push(*path); - self.stack.push(buf.into()); - } - }; - } - - _ => { - panic!("tvix compiler bug: OpResolveHomePath called on non-UnresolvedPath") - } - }, - - OpCode::OpJump(JumpOffset(offset)) => { - debug_assert!(offset != 0); - frame.ip += offset; - } - - OpCode::OpJumpIfTrue(JumpOffset(offset)) => { - debug_assert!(offset != 0); - if self.stack_peek(0).as_bool().with_span(&frame)? { - frame.ip += offset; - } - } - - OpCode::OpJumpIfFalse(JumpOffset(offset)) => { - debug_assert!(offset != 0); - if !self.stack_peek(0).as_bool().with_span(&frame)? { - frame.ip += offset; - } - } - - OpCode::OpJumpIfNotFound(JumpOffset(offset)) => { - debug_assert!(offset != 0); - if matches!(self.stack_peek(0), Value::AttrNotFound) { - self.stack_pop(); - frame.ip += offset; - } - } - // These assertion operations error out if the stack // top is not of the expected type. This is necessary // to implement some specific behaviours of Nix @@ -641,29 +566,51 @@ impl<'o> VM<'o> { } } - // Remove the given number of elements from the stack, - // but retain the top value. - OpCode::OpCloseScope(Count(count)) => { - // Immediately move the top value into the right - // position. - let target_idx = self.stack.len() - 1 - count; - self.stack[target_idx] = self.stack_pop(); + OpCode::OpAttrs(Count(count)) => self.run_attrset(&frame, count)?, - // Then drop the remaining values. - for _ in 0..(count - 1) { - self.stack.pop(); - } + OpCode::OpAttrsUpdate => { + let rhs = self.stack_pop().to_attrs().with_span(&frame)?; + let lhs = self.stack_pop().to_attrs().with_span(&frame)?; + + self.stack.push(Value::attrs(lhs.update(*rhs))) } - OpCode::OpGetLocal(StackIdx(local_idx)) => { - let idx = frame.stack_offset + local_idx; - self.stack.push(self.stack[idx].clone()); + OpCode::OpInvert => { + let v = self.stack_pop().as_bool().with_span(&frame)?; + self.stack.push(Value::Bool(!v)); } - OpCode::OpPushWith(StackIdx(idx)) => self.with_stack.push(frame.stack_offset + idx), + OpCode::OpList(Count(count)) => { + let list = + NixList::construct(count, self.stack.split_off(self.stack.len() - count)); - OpCode::OpPopWith => { - self.with_stack.pop(); + self.stack.push(Value::List(list)); + } + + OpCode::OpJumpIfTrue(JumpOffset(offset)) => { + debug_assert!(offset != 0); + if self.stack_peek(0).as_bool().with_span(&frame)? { + frame.ip += offset; + } + } + + OpCode::OpHasAttr => { + let key = self.stack_pop().to_str().with_span(&frame)?; + let result = match self.stack_pop() { + Value::Attrs(attrs) => attrs.contains(key.as_str()), + + // Nix allows use of `?` on non-set types, but + // always returns false in those cases. + _ => false, + }; + + self.stack.push(Value::Bool(result)); + } + + OpCode::OpConcat => { + let rhs = self.stack_pop().to_list().with_span(&frame)?.into_inner(); + let lhs = self.stack_pop().to_list().with_span(&frame)?.into_inner(); + self.stack.push(Value::List(NixList::from(lhs + rhs))) } OpCode::OpResolveWith => { @@ -693,98 +640,150 @@ impl<'o> VM<'o> { return Ok(false); } - OpCode::OpAssertFail => { - return Err(frame.error(ErrorKind::AssertionFailed)); + OpCode::OpFinalise(StackIdx(idx)) => { + match &self.stack[frame.stack_offset + idx] { + Value::Closure(_) => panic!("attempted to finalise a closure"), + Value::Thunk(thunk) => thunk.finalise(&self.stack[frame.stack_offset..]), + + // In functions with "formals" attributes, it is + // possible for `OpFinalise` to be called on a + // non-capturing value, in which case it is a no-op. + // + // TODO: detect this in some phase and skip the finalise; fail here + _ => { /* TODO: panic here again to catch bugs */ } + } } - OpCode::OpCall => { - let callable = self.stack_pop(); - self.call_value(frame.current_light_span(), Some(frame), callable)?; + OpCode::OpCoerceToString => { + let value = self.stack_pop(); + let gen_span = frame.current_light_span(); + self.push_call_frame(span, frame); - // exit this loop and let the outer loop enter the new call - return Ok(true); - } + self.enqueue_generator("coerce_to_string", gen_span, |co| { + value.coerce_to_string(co, CoercionKind::Weak) + }); - OpCode::OpGetUpvalue(upv_idx) => { - let value = frame.upvalue(upv_idx).clone(); - self.stack.push(value); + return Ok(false); } - OpCode::OpClosure(idx) => { - let blueprint = match &frame.chunk()[idx] { - Value::Blueprint(lambda) => lambda.clone(), - _ => panic!("compiler bug: non-blueprint in blueprint slot"), - }; + OpCode::OpInterpolate(Count(count)) => self.run_interpolate(&frame, count)?, - let upvalue_count = blueprint.upvalue_count; - debug_assert!( - upvalue_count > 0, - "OpClosure should not be called for plain lambdas" + OpCode::OpValidateClosedFormals => { + let formals = frame.lambda.formals.as_ref().expect( + "OpValidateClosedFormals called within the frame of a lambda without formals", ); - let mut upvalues = Upvalues::with_capacity(blueprint.upvalue_count); - self.populate_upvalues(&mut frame, upvalue_count, &mut upvalues)?; - self.stack - .push(Value::Closure(Rc::new(Closure::new_with_upvalues( - Rc::new(upvalues), - blueprint, - )))); + let args = self.stack_peek(0).to_attrs().with_span(&frame)?; + for arg in args.keys() { + if !formals.contains(arg) { + return Err(frame.error(ErrorKind::UnexpectedArgument { + arg: arg.clone(), + formals_span: formals.span, + })); + } + } } - OpCode::OpThunkSuspended(idx) | OpCode::OpThunkClosure(idx) => { - let blueprint = match &frame.chunk()[idx] { - Value::Blueprint(lambda) => lambda.clone(), - _ => panic!("compiler bug: non-blueprint in blueprint slot"), - }; + OpCode::OpAdd => { + let b = self.stack_pop(); + let a = self.stack_pop(); - let upvalue_count = blueprint.upvalue_count; - let thunk = if matches!(op, OpCode::OpThunkClosure(_)) { - debug_assert!( - upvalue_count > 0, - "OpThunkClosure should not be called for plain lambdas" - ); - Thunk::new_closure(blueprint) - } else { - Thunk::new_suspended(blueprint, frame.current_light_span()) + let gen_span = frame.current_light_span(); + self.push_call_frame(span, frame); + + // OpAdd can add not just numbers, but also string-like + // things, which requires more VM logic. This operation is + // evaluated in a generator frame. + self.enqueue_generator("add_values", gen_span, |co| add_values(co, a, b)); + return Ok(false); + } + + OpCode::OpSub => { + let b = self.stack_pop(); + let a = self.stack_pop(); + let result = arithmetic_op!(&a, &b, -).with_span(&frame)?; + self.stack.push(result); + } + + OpCode::OpMul => { + let b = self.stack_pop(); + let a = self.stack_pop(); + let result = arithmetic_op!(&a, &b, *).with_span(&frame)?; + self.stack.push(result); + } + + OpCode::OpDiv => { + let b = self.stack_pop(); + + match b { + Value::Integer(0) => return Err(frame.error(ErrorKind::DivisionByZero)), + Value::Float(b) if b == 0.0_f64 => { + return Err(frame.error(ErrorKind::DivisionByZero)) + } + _ => {} }; - let upvalues = thunk.upvalues_mut(); - self.stack.push(Value::Thunk(thunk.clone())); - // From this point on we internally mutate the - // upvalues. The closure (if `is_closure`) is - // already in its stack slot, which means that it - // can capture itself as an upvalue for - // self-recursion. - self.populate_upvalues(&mut frame, upvalue_count, upvalues)?; + let a = self.stack_pop(); + let result = arithmetic_op!(&a, &b, /).with_span(&frame)?; + self.stack.push(result); } - OpCode::OpForce => { - if let Some(Value::Thunk(_)) = self.stack.last() { - let thunk = match self.stack_pop() { - Value::Thunk(t) => t, - _ => unreachable!(), - }; + OpCode::OpNegate => match self.stack_pop() { + Value::Integer(i) => self.stack.push(Value::Integer(-i)), + Value::Float(f) => self.stack.push(Value::Float(-f)), + v => { + return Err(frame.error(ErrorKind::TypeError { + expected: "number (either int or float)", + actual: v.type_of(), + })); + } + }, - let gen_span = frame.current_light_span(); + OpCode::OpLess => cmp_op!(self, frame, span, <), + OpCode::OpLessOrEq => cmp_op!(self, frame, span, <=), + OpCode::OpMore => cmp_op!(self, frame, span, >), + OpCode::OpMoreOrEq => cmp_op!(self, frame, span, >=), - self.push_call_frame(span, frame); - self.enqueue_generator("force", gen_span, |co| thunk.force(co)); - return Ok(false); + OpCode::OpFindFile => match self.stack_pop() { + Value::UnresolvedPath(path) => { + let resolved = self + .nix_search_path + .resolve(&*self.io_handle, *path) + .with_span(&frame)?; + self.stack.push(resolved.into()); } - } - OpCode::OpFinalise(StackIdx(idx)) => { - match &self.stack[frame.stack_offset + idx] { - Value::Closure(_) => panic!("attempted to finalise a closure"), - Value::Thunk(thunk) => thunk.finalise(&self.stack[frame.stack_offset..]), + _ => panic!("tvix compiler bug: OpFindFile called on non-UnresolvedPath"), + }, - // In functions with "formals" attributes, it is - // possible for `OpFinalise` to be called on a - // non-capturing value, in which case it is a no-op. - // - // TODO: detect this in some phase and skip the finalise; fail here - _ => { /* TODO: panic here again to catch bugs */ } + OpCode::OpResolveHomePath => match self.stack_pop() { + Value::UnresolvedPath(path) => { + match dirs::home_dir() { + None => { + return Err(frame.error(ErrorKind::RelativePathResolution( + "failed to determine home directory".into(), + ))); + } + Some(mut buf) => { + buf.push(*path); + self.stack.push(buf.into()); + } + }; + } + + _ => { + panic!("tvix compiler bug: OpResolveHomePath called on non-UnresolvedPath") } + }, + + OpCode::OpPushWith(StackIdx(idx)) => self.with_stack.push(frame.stack_offset + idx), + + OpCode::OpPopWith => { + self.with_stack.pop(); + } + + OpCode::OpAssertFail => { + return Err(frame.error(ErrorKind::AssertionFailed)); } // Data-carrying operands should never be executed, |