idea: opcode dispatch performance improvements

[zhuzhu81998]

Just started looking into boa's VM. It appears that boa uses call threading for opcode dispatch via function pointers:

boa/core/engine/src/vm/mod.rs

Lines 876 to 891 in 75c0a75

	while let Some(byte) = self
	.vm
	.frame
	.code_block
	.bytecode
	.bytecode
	.get(self.vm.frame.pc as usize)
	{
	let opcode = Opcode::decode(*byte);
	match self.execute_one(Self::execute_bytecode_instruction, opcode) {
	ControlFlow::Continue(()) => {}
	ControlFlow::Break(value) => return value,
	}
	}

There should be room for measurable improvements according to https://github.com/tipo159/rust-instruction-dispatch .
Running the experiments with rustc 1.93.0 on my machine (Lunar Lake, Q3 2024):

Approach	Average of 100 results (ns)
direct-call-threading	2_947_553
switch-dispatch	2_469_013
direct-tail-call-threading	1_594_078

While tipo159/rust-instruction-dispatch does have some implementation inconsistencies (which perhaps caused switch-dispatch to be better than direct-call-threading), it would appear that direct-tail-call-threading is more superior and does not require writing ASM by hand either.

[zhuzhu81998]

Some more reports on the tail call approach:
CPython: https://lwn.net/Articles/1010905/ (PR: python/cpython#128563)
QuickJS: bellard/quickjs#466
Random Reddit comment: https://www.reddit.com/r/rust/comments/1nt8enz/preserve_nonelike_calling_convention/

Rust stable compiler unfortunately does not support guranteed tail call right now. nightly does have it (rust-lang/rust#144232) so maybe some experimental work and/or refactoring as preparations might be nice.

[hansl]

There are some very interesting points in here. That sounds like a good starting point for exploration.

[zhuzhu81998]

I will look more into it then : )

[shreyadesai20042009]

Hi, I’m interested in exploring the direct tail-call dispatch approach.

Before starting implementation, would you prefer:

• An experimental branch for benchmarking?
• A feature-gated prototype?
• Or performance measurement improvements first?

I’d be happy to start with a small benchmarking comparison inside the repo.

[jedel1043]

@zhuzhu81998 is already working on this.

[zhuzhu81998]

So switch for boa is definitely slower. Perhaps the toy benchmark showed switch to be faster is partially due to how little instructions there are (like 4).

To test out tail call i need to do a bit more playing around (currently it just goes stack overflow, because apparently you can not let rust handle the destructor calls if you want tail call + other caveats i need to sort out)

[zhuzhu81998]

Trying to imitate tailcall via a trampoline-like loop does not improve peformance (actually 2% regression right now), ie something like this:

                fn [<handle_ $Variant:snake>](context: &mut Context, pc: usize) -> ControlFlow<CompletionRecord, OpcodeHandler> {
                    // Order of operations very important here. (e.g. some operations may change pc too)
                    let bytes = &context.vm.frame().code_block.bytecode.bytes;
                    let (args, next_pc) = <($($($FieldType),*)?)>::decode(bytes, pc + 1);

                    context.vm.frame_mut().pc = next_pc as u32;
                    let result = $Variant::operation(args, context);

                    let completion_record = IntoCompletionRecord::into_completion_record(result, context);
                    match completion_record {
                        ControlFlow::Continue(()) => context.next_opcode_handler(),
                        ControlFlow::Break(value) => ControlFlow::Break(value),
                    }
                }

and then the main loop is

    pub(crate) fn run(&mut self) -> CompletionRecord {
        #[cfg(feature = "trace")]
        if self.vm.trace {
            self.trace_call_frame();
        }

        let mut handler = match self
            .vm
            .frame()
            .code_block
            .bytecode
            .bytes
            .get(self.vm.frame().pc as usize)
        {
            Some(byte) => OPCODE_HANDLERS[Opcode::decode(*byte) as usize],
            None => return CompletionRecord::Throw(JsError::from_native(JsNativeError::error())),
        };

        loop {
            let pc = self.vm.frame().pc as usize;
            match self.execute_one(handler, pc) {
                ControlFlow::Continue(next) => handler = next,
                ControlFlow::Break(value) => return value,
            }
        }
    }

I think this is not actually "teaching" the compiler which opcode comes after which.

I will try nightly toolchain to see if real tailcall is actually an improvement.

[zhuzhu81998]

With nightly compiler and using become, I was still getting very very tall towers (and stack overflow for anything that is a bit long):

So I thought maybe tail call was not working and rust didnt say anything. Now I realize that it might have just been my skill issue 😂 . Hope to be able to post some benchmark results soon.

[zhuzhu81998]

So benchmark against the base of my branch (faaf64d):

strings/split/Execution time:   [2.8639 ms 2.8693 ms 2.8753 ms]
                        change: [−0.1579% +0.1108% +0.3823%] (p = 0.40 > 0.05)
                        No change in performance detected.
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe

strings/slice/Execution time:   [763.94 µs 765.90 µs 767.79 µs]
                        change: [−18.676% −18.150% −17.637%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
  1 (1.00%) high mild
  1 (1.00%) high severe

v8-benches/raytrace/Execution
                        time:   [5.1561 µs 5.1767 µs 5.1968 µs]
                        change: [−6.1589% −5.2602% −4.3695%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  1 (10.00%) high mild
  1 (10.00%) high severe

v8-benches/deltablue/Execution
                        time:   [5.2232 µs 5.2462 µs 5.2763 µs]
                        change: [−5.3572% −4.6667% −4.1321%] (p = 0.00 < 0.05)
                        Performance has improved.

v8-benches/navier-stokes/Execution
                        time:   [5.2028 µs 5.2213 µs 5.2339 µs]
                        change: [−6.1365% −5.4486% −4.8434%] (p = 0.00 < 0.05)
                        Performance has improved.

v8-benches/splay/Execution
                        time:   [5.1369 µs 5.1644 µs 5.1887 µs]
                        change: [−6.0422% −5.4366% −4.8904%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  2 (20.00%) high mild

v8-benches/regexp/Execution
                        time:   [5.1396 µs 5.1568 µs 5.1728 µs]
                        change: [−6.6215% −5.1710% −3.9132%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe

Benchmarking v8-benches/crypto/Execution: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 116.3s.
v8-benches/crypto/Execution
                        time:   [11.584 s 11.600 s 11.621 s]
                        change: [−11.472% −11.246% −10.990%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild

v8-benches/richards/Execution
                        time:   [5.1290 µs 5.1374 µs 5.1471 µs]
                        change: [−7.5720% −6.3361% −5.2532%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe

v8-benches/earley-boyer/Execution
                        time:   [5.5884 µs 5.6957 µs 5.8260 µs]
                        change: [−6.8867% −5.3498% −3.8235%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe

The results are quite happy i would say. I would say this optimization particularly benefits programs with a lot of opcodes, hence the more significant improvement with crypto.

@jedel1043 @hansl do you think it would make sense to maybe add a nightly feature to boa_engine and add this optimization there? Unfortunately this takes advantage of 2 nightly feature flags (and who knows when they will be stabilized)

(e.g. [smallvec](https://docs.rs/smallvec/latest/smallvec/) does nightly features)