Skip to content

Commit db5048f

Browse files
morealmoreal
committed
vm: let boolean producers run the branch that follows them
`TO_BOOL*`, `COMPARE_OP*`, `CONTAINS_OP*` and `IS_OP` materialised a bool only for the `POP_JUMP_IF_*` one dispatch later to pop and test it, and the compiler's `NOT_TAKEN` marker cost a third dispatch on the fall-through edge. Generalise the `COMPARE_OP_INT`-only jump fusion so every boolean producer resolves the jump itself, and step over `NOT_TAKEN` from there and from the plain `POP_JUMP_IF_*` handlers. Both back off to ordinary dispatch when the successor is an instrumented opcode or while tracing, so `sys.monitoring` branch events and `sys.settrace` opcode events are unaffected. Dispatches over 13 standalone pyperformance benchmarks: -5.0% total (richards -11.7%, unpickle_pure_python -8.9%, sympy -8.4%, hexiom -8.1%, django_template -7.1%, go -6.1%; nbody unchanged). Times, best of 7 interleaved rounds: deltablue -4.0%, hexiom -3.5%, go -3.4%, unpickle_pure_python -3.3%, richards -3.2%, raytrace -3.0%, nqueens -1.9%, geomean -1.0%; a branch-heavy microbenchmark -4.7% against a straight-line control at 0%. Assisted-by: Claude Code:claude-fable-5-1
1 parent bee10b8 commit db5048f

1 file changed

Lines changed: 143 additions & 38 deletions

File tree

‎crates/vm/src/frame.rs‎

Lines changed: 143 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -3091,6 +3091,21 @@ fn compactlongs_guard(lhs: &PyObject, rhs: &PyObject, vm: &VirtualMachine) -> bo
30913091
compact_int_from_obj(lhs, vm).is_some() && compact_int_from_obj(rhs, vm).is_some()
30923092
}
30933093

3094+
/// A conditional jump the instruction ahead of it can perform itself.
3095+
///
3096+
/// Built by [`ExecutingFrame::fused_bool_jump`] and consumed by
3097+
/// [`ExecutingFrame::take_fused_bool_jump`].
3098+
#[derive(Clone, Copy)]
3099+
struct FusedBoolJump {
3100+
/// Boolean value that takes the branch.
3101+
jump_on: bool,
3102+
/// Code-unit index the branch lands on when taken.
3103+
taken: u32,
3104+
/// Code-unit index just past the jump and its cache, where the compiler
3105+
/// puts the `NOT_TAKEN` marker.
3106+
fallthrough: u32,
3107+
}
3108+
30943109
macro_rules! bitwise_longs_action {
30953110
($name:ident, $op:tt) => {
30963111
#[inline]
@@ -4260,7 +4275,7 @@ impl ExecutingFrame<'_> {
42604275
bytecode::Invert::No => self._in(vm, &a, &b)?,
42614276
bytecode::Invert::Yes => self._not_in(vm, &a, &b)?,
42624277
};
4263-
self.push_value(vm.ctx.new_bool(value).into());
4278+
self.push_bool_or_fused_jump(instruction.cache_entries(), value, vm);
42644279
Ok(None)
42654280
}
42664281
Instruction::ConvertValue { oparg: conversion } => {
@@ -4649,7 +4664,7 @@ impl ExecutingFrame<'_> {
46494664
bytecode::Invert::No => res,
46504665
bytecode::Invert::Yes => !res,
46514666
};
4652-
self.push_value(vm.ctx.new_bool(value).into());
4667+
self.push_bool_or_fused_jump(instruction.cache_entries(), value, vm);
46534668
Ok(None)
46544669
}
46554670
Instruction::JumpForward { .. } => {
@@ -5273,13 +5288,17 @@ impl ExecutingFrame<'_> {
52735288
let value = self.pop_stackref();
52745289
if vm.is_none(&value) {
52755290
self.jump_relative_forward(u32::from(arg), 1);
5291+
} else {
5292+
self.skip_fallthrough_not_taken(vm, 1);
52765293
}
52775294
Ok(None)
52785295
}
52795296
Instruction::PopJumpIfNotNone { .. } => {
52805297
let value = self.pop_stackref();
52815298
if !vm.is_none(&value) {
52825299
self.jump_relative_forward(u32::from(arg), 1);
5300+
} else {
5301+
self.skip_fallthrough_not_taken(vm, 1);
52835302
}
52845303
Ok(None)
52855304
}
@@ -5534,7 +5553,7 @@ impl ExecutingFrame<'_> {
55345553
self.adaptive(|s, ii, cb| s.specialize_to_bool(vm, ii, cb));
55355554
let obj = self.pop_stackref();
55365555
let bool_val = obj.try_to_bool(vm)?;
5537-
self.push_value(vm.ctx.new_bool(bool_val).into());
5556+
self.push_bool_or_fused_jump(instruction.cache_entries(), bool_val, vm);
55385557
Ok(None)
55395558
}
55405559
Instruction::UnpackEx { counts: args } => {
@@ -7338,9 +7357,7 @@ impl ExecutingFrame<'_> {
73387357
let result = op.eval_ord(a_val.cmp(&b_val));
73397358
self.pop_stackref();
73407359
self.pop_stackref();
7341-
if !self.try_fused_compare_int_jump(result, vm) {
7342-
self.push_value(vm.ctx.new_bool(result).into());
7343-
}
7360+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
73447361
Ok(None)
73457362
} else {
73467363
self.execute_compare(vm, arg)
@@ -7362,7 +7379,7 @@ impl ExecutingFrame<'_> {
73627379
};
73637380
self.pop_stackref();
73647381
self.pop_stackref();
7365-
self.push_value(vm.ctx.new_bool(result).into());
7382+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
73667383
Ok(None)
73677384
} else {
73687385
self.execute_compare(vm, arg)
@@ -7385,7 +7402,7 @@ impl ExecutingFrame<'_> {
73857402
};
73867403
self.pop_stackref();
73877404
self.pop_stackref();
7388-
self.push_value(vm.ctx.new_bool(result).into());
7405+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
73897406
Ok(None)
73907407
} else {
73917408
self.execute_compare(vm, arg)
@@ -7394,12 +7411,19 @@ impl ExecutingFrame<'_> {
73947411
Instruction::ToBoolBool => {
73957412
let obj = self.top_value();
73967413
if obj.class().is(vm.ctx.types.bool_type) {
7397-
// Already a bool, no-op
7414+
// Already a bool, so normally a no-op — but when a
7415+
// POP_JUMP_IF_* follows, branching on it here retires both
7416+
// instructions in one dispatch.
7417+
if let Some(jump) = self.fused_bool_jump(instruction.cache_entries(), vm) {
7418+
let result = obj.is(&vm.ctx.true_value);
7419+
self.pop_stackref();
7420+
self.take_fused_bool_jump(jump, result);
7421+
}
73987422
Ok(None)
73997423
} else {
74007424
let obj = self.pop_stackref();
74017425
let result = obj.try_to_bool(vm)?;
7402-
self.push_value(vm.ctx.new_bool(result).into());
7426+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74037427
Ok(None)
74047428
}
74057429
}
@@ -7408,25 +7432,25 @@ impl ExecutingFrame<'_> {
74087432
if let Some(int_val) = obj.downcast_ref_if_exact::<PyInt>(vm) {
74097433
let result = !int_val.as_bigint().is_zero();
74107434
self.pop_stackref();
7411-
self.push_value(vm.ctx.new_bool(result).into());
7435+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74127436
Ok(None)
74137437
} else {
74147438
let obj = self.pop_stackref();
74157439
let result = obj.try_to_bool(vm)?;
7416-
self.push_value(vm.ctx.new_bool(result).into());
7440+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74177441
Ok(None)
74187442
}
74197443
}
74207444
Instruction::ToBoolNone => {
74217445
let obj = self.top_value();
74227446
if obj.class().is(vm.ctx.types.none_type) {
74237447
self.pop_stackref();
7424-
self.push_value(vm.ctx.new_bool(false).into());
7448+
self.push_bool_or_fused_jump(instruction.cache_entries(), false, vm);
74257449
Ok(None)
74267450
} else {
74277451
let obj = self.pop_stackref();
74287452
let result = obj.try_to_bool(vm)?;
7429-
self.push_value(vm.ctx.new_bool(result).into());
7453+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74307454
Ok(None)
74317455
}
74327456
}
@@ -7435,12 +7459,12 @@ impl ExecutingFrame<'_> {
74357459
if let Some(list) = obj.downcast_ref_if_exact::<PyList>(vm) {
74367460
let result = !list.borrow_vec().is_empty();
74377461
self.pop_stackref();
7438-
self.push_value(vm.ctx.new_bool(result).into());
7462+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74397463
Ok(None)
74407464
} else {
74417465
let obj = self.pop_stackref();
74427466
let result = obj.try_to_bool(vm)?;
7443-
self.push_value(vm.ctx.new_bool(result).into());
7467+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74447468
Ok(None)
74457469
}
74467470
}
@@ -7449,12 +7473,12 @@ impl ExecutingFrame<'_> {
74497473
if let Some(s) = obj.downcast_ref_if_exact::<PyStr>(vm) {
74507474
let result = !s.is_empty();
74517475
self.pop_stackref();
7452-
self.push_value(vm.ctx.new_bool(result).into());
7476+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74537477
Ok(None)
74547478
} else {
74557479
let obj = self.pop_stackref();
74567480
let result = obj.try_to_bool(vm)?;
7457-
self.push_value(vm.ctx.new_bool(result).into());
7481+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74587482
Ok(None)
74597483
}
74607484
}
@@ -7468,12 +7492,12 @@ impl ExecutingFrame<'_> {
74687492
if cached_version != 0 && obj.class().tp_version_tag.load(Acquire) == cached_version
74697493
{
74707494
self.pop_stackref();
7471-
self.push_value(vm.ctx.new_bool(true).into());
7495+
self.push_bool_or_fused_jump(instruction.cache_entries(), true, vm);
74727496
Ok(None)
74737497
} else {
74747498
let obj = self.pop_stackref();
74757499
let result = obj.try_to_bool(vm)?;
7476-
self.push_value(vm.ctx.new_bool(result).into());
7500+
self.push_bool_or_fused_jump(instruction.cache_entries(), result, vm);
74777501
Ok(None)
74787502
}
74797503
}
@@ -7490,7 +7514,7 @@ impl ExecutingFrame<'_> {
74907514
bytecode::Invert::No => found,
74917515
bytecode::Invert::Yes => !found,
74927516
};
7493-
self.push_value(vm.ctx.new_bool(value).into());
7517+
self.push_bool_or_fused_jump(instruction.cache_entries(), value, vm);
74947518
Ok(None)
74957519
} else {
74967520
let b = self.pop_value();
@@ -7501,7 +7525,7 @@ impl ExecutingFrame<'_> {
75017525
bytecode::Invert::No => self._in(vm, &a, &b)?,
75027526
bytecode::Invert::Yes => self._not_in(vm, &a, &b)?,
75037527
};
7504-
self.push_value(vm.ctx.new_bool(value).into());
7528+
self.push_bool_or_fused_jump(instruction.cache_entries(), value, vm);
75057529
Ok(None)
75067530
}
75077531
}
@@ -7520,7 +7544,7 @@ impl ExecutingFrame<'_> {
75207544
bytecode::Invert::No => found,
75217545
bytecode::Invert::Yes => !found,
75227546
};
7523-
self.push_value(vm.ctx.new_bool(value).into());
7547+
self.push_bool_or_fused_jump(instruction.cache_entries(), value, vm);
75247548
Ok(None)
75257549
} else {
75267550
let b = self.pop_value();
@@ -7531,7 +7555,7 @@ impl ExecutingFrame<'_> {
75317555
bytecode::Invert::No => self._in(vm, &a, &b)?,
75327556
bytecode::Invert::Yes => self._not_in(vm, &a, &b)?,
75337557
};
7534-
self.push_value(vm.ctx.new_bool(value).into());
7558+
self.push_bool_or_fused_jump(instruction.cache_entries(), value, vm);
75357559
Ok(None)
75367560
}
75377561
}
@@ -8966,6 +8990,33 @@ impl ExecutingFrame<'_> {
89668990
self.update_lasti(|i| *i = target);
89678991
}
89688992

8993+
/// Step over the `NOT_TAKEN` marker on a conditional jump's fall-through edge.
8994+
///
8995+
/// The compiler plants `NOT_TAKEN` after every conditional jump purely as the
8996+
/// anchor `sys.monitoring` swaps for `INSTRUMENTED_NOT_TAKEN` when branch
8997+
/// events are on. Left alone it is a no-op, so land past it instead of
8998+
/// spending a whole dispatch on it. `caches` is the jump's own inline-cache
8999+
/// count, which the fall-through path would otherwise leave for the dispatch
9000+
/// loop to add.
9001+
///
9002+
/// Skipped while tracing, where the dispatch loop is what emits per-opcode
9003+
/// `sys.settrace` events and every executed instruction has to be seen.
9004+
#[inline]
9005+
fn skip_fallthrough_not_taken(&mut self, vm: &VirtualMachine, caches: u32) {
9006+
if self.specialization_eval_frame_active(vm) {
9007+
return;
9008+
}
9009+
let next = self.lasti() + caches;
9010+
if (next as usize) < self.code.instructions.len()
9011+
&& matches!(
9012+
self.code.instructions.read_op(next as usize),
9013+
Instruction::NotTaken
9014+
)
9015+
{
9016+
self.update_lasti(|i| *i = next + 1);
9017+
}
9018+
}
9019+
89699020
#[inline]
89709021
fn pop_jump_if_relative(
89719022
&mut self,
@@ -8978,6 +9029,8 @@ impl ExecutingFrame<'_> {
89789029
let value = obj.try_to_bool(vm)?;
89799030
if value == flag {
89809031
self.jump_relative_forward(u32::from(arg), caches);
9032+
} else {
9033+
self.skip_fallthrough_not_taken(vm, caches);
89819034
}
89829035
Ok(None)
89839036
}
@@ -11035,31 +11088,83 @@ impl ExecutingFrame<'_> {
1103511088
/// the comparison result as a Python bool. This is the adaptive interpreter
1103611089
/// equivalent of keeping the result virtual across the two-opcode trace.
1103711090
#[inline]
11038-
fn try_fused_compare_int_jump(&mut self, result: bool, vm: &VirtualMachine) -> bool {
11091+
/// A `POP_JUMP_IF_TRUE`/`POP_JUMP_IF_FALSE` sitting immediately after the
11092+
/// running instruction, resolved so the boolean's producer can branch on it
11093+
/// without the jump being dispatched at all.
11094+
///
11095+
/// `None` when the successor is anything else -- its instrumented form
11096+
/// included, so `sys.monitoring` branch events still fire -- or while
11097+
/// tracing, where the dispatch loop has to see every instruction to report
11098+
/// it.
11099+
fn fused_bool_jump(&self, caches: usize, vm: &VirtualMachine) -> Option<FusedBoolJump> {
1103911100
if self.specialization_eval_frame_active(vm) {
11040-
return false;
11101+
return None;
1104111102
}
1104211103

11043-
let jump_idx = self.lasti() as usize + Instruction::CompareOpInt.cache_entries();
11104+
let jump_idx = self.lasti() as usize + caches;
1104411105
if jump_idx >= self.code.instructions.len() {
11045-
return false;
11106+
return None;
1104611107
}
1104711108

11048-
let jump_op = self.code.instructions.read_op(jump_idx);
11049-
let jump_on = match jump_op {
11109+
// One Acquire load for opcode and delta together. A jump needing
11110+
// EXTENDED_ARG has that prefix at `jump_idx` instead, so the match
11111+
// rejects it and this single byte is the whole delta.
11112+
let jump = self.code.instructions.read_unit(jump_idx);
11113+
let jump_on = match jump.op {
1105011114
Instruction::PopJumpIfFalse { .. } => false,
1105111115
Instruction::PopJumpIfTrue { .. } => true,
11052-
_ => return false,
11116+
_ => return None,
1105311117
};
11054-
let jump_delta = self.code.instructions.read_arg(jump_idx).as_u32();
11055-
let after_jump = jump_idx as u32 + 1 + jump_op.cache_entries() as u32;
11056-
let result == jump_on {
11057-
after_jump + jump_delta
11118+
debug_assert_eq!(jump.op.cache_entries(), 1);
11119+
let fallthrough = jump_idx as u32 + 2;
11120+
Some(FusedBoolJump {
11121+
jump_on,
11122+
taken: fallthrough + jump.arg.as_u32(),
11123+
fallthrough,
11124+
})
11125+
}
11126+
11127+
/// Land on the edge `result` selects, stepping over the fall-through
11128+
/// `NOT_TAKEN` marker. The marker is only probed when the branch is not
11129+
/// taken, keeping the taken edge to a single instruction-array read.
11130+
#[inline]
11131+
fn take_fused_bool_jump(&mut self, jump: FusedBoolJump, result: bool) {
11132+
let result == jump.jump_on {
11133+
jump.taken
1105811134
} else {
11059-
after_jump
11135+
self.not_taken_skipped(jump.fallthrough)
1106011136
};
11061-
self.update_lasti(|i| *i = target);
11062-
true
11137+
self.lasti.store(target, Relaxed);
11138+
}
11139+
11140+
/// Push `result` as the running instruction's boolean output, or branch on it
11141+
/// directly when a `POP_JUMP_IF_*` follows. See [`Self::fused_bool_jump`].
11142+
#[inline]
11143+
fn push_bool_or_fused_jump(&mut self, caches: usize, result: bool, vm: &VirtualMachine) {
11144+
match self.fused_bool_jump(caches, vm) {
11145+
Some(jump) => self.take_fused_bool_jump(jump, result),
11146+
None => self.push_value(vm.ctx.new_bool(result).into()),
11147+
}
11148+
}
11149+
11150+
/// `next`, advanced past a `NOT_TAKEN` marker sitting there.
11151+
///
11152+
/// The fused-jump paths land directly on the successor, so they step over
11153+
/// the marker themselves rather than going through
11154+
/// [`Self::skip_fallthrough_not_taken`]; the tracing guard is the caller's,
11155+
/// since fusion is already disabled while tracing.
11156+
#[inline]
11157+
fn not_taken_skipped(&self, next: u32) -> u32 {
11158+
if (next as usize) < self.code.instructions.len()
11159+
&& matches!(
11160+
self.code.instructions.read_op(next as usize),
11161+
Instruction::NotTaken
11162+
)
11163+
{
11164+
next + 1
11165+
} else {
11166+
next
11167+
}
1106311168
}
1106411169

1106511170
/// Recover the BinaryOperator from the instruction arg byte.

0 commit comments

Comments
 (0)