Massive performance regression between `nightly-2022-08-12` and `nightly-2022-08-13`

[Robbepop]

Usually I develop on the stable channel and wanted to see how my project performs on the upcoming beta or nightly channels. I saw performance regressions between 30-80% across the board in native and Wasm targets. Those regressions were confirmed by our benchmarking CI as can be seen by the link.

Was it the LLVM 15 Update?

I conducted a bisect and found that the change happened between nightly-2022-08-12 and nightly-2022-08-13.
After short research I saw that Rust updated from LLVM 14 to 15 in exactly this time period: #99464 Other merged commits in this time period were not as suspicious to me.

Past Regressions

Also this unfortunately is not the first time we saw such massive regressions ....
It is extremely hard to craft a minimal code snippet out of wasmi since it is a very heavily optimized bunch of code with lots of interdependencies.
Unfortunately the wasmi project is incredibly performance critical to us. Even 10-15% performance regression are a disaster to us let alone those 30-80% we just saw ...

Hint for Minimal Code Example

I have one major suspicion: Due to missing guaranteed tail calls in Rust we are heavily reliant on a non-guaranteed optimization for our loop-switch based interpreter hot path that pulls jumps to the match arms which results to very similar code as what threaded-code interpreter code would produce. The code that depends on this particular optimization can be found here.
This suspicion is underlined by the fact that especially non call-intense workloads show most regressions in the linked benchmarks. This implies to me that the regressions have something to do with instruction dispatch.

Potential Future Solutions

• The Rust compiler could add a few benchmarks concerning those loop-switch optimizations to its set of benchmarks so that future LLVM updates won't invalidate those optimizations. I am not sure how viable this approach is to the Rust compiler developers though. Also this only works if we find all the fragile parts that cause these regressions.
• Ideally Rust offered abstractions that allow to develop efficient interpreters in Rust without relying on Rust/LLVM optimizations: for example guaranteed tail calls.

Reproduce

The current stable Rust channel is the following:

stable-x86_64-unknown-linux-gnu (default)
rustc 1.64.0 (a55dd71d5 2022-09-19)

In order to reproduce these benchmarks do the following:

1. git clone git@github.com:paritytech/wasmi.git
2. cd wasmi
3. git checkout 21e12da67a765c8c8b8a62595d2c9d21e1fa2ef6
4. rustup toolchain install nightly-2022-08-12
5. rustup toolchain install nightly-2022-08-13
6. git submodule update --init --recursive
7. cargo +stable bench --bench benches execute -- --save-baseline stable
8. cargo +nightly-2022-08-12 bench --bench benches execute -- --baseline stable
9. cargo +nightly-2022-08-13 bench --bench benches execute -- --baseline stable

[the8472]

That commit doesn't compile

error: couldn't read crates/wasmi/benches/wasm/wasm_kernel/res/revcomp-input.txt: No such file or directory (os error 2)
  --> crates/wasmi/benches/benches.rs:18:30
   |
18 | const REVCOMP_INPUT: &[u8] = include_bytes!("wasm/wasm_kernel/res/revcomp-input.txt");
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: this error originates in the macro `include_bytes` (in Nightly builds, run with -Z macro-backtrace for more info)

[apiraino]

Meanwhile I'll nominate this issue for T-compiler discussion, I think it's a wider topic that benefits from comments of the team. Wg-prioritization discussion on Zulip

@rustbot label i-compiler-nominated

[Robbepop]

@the8472 I am sorry, I forgot to mention that you need to initialize git submodules before running benchmarks.
Execute

git submodule update --init --recursive

before running the benchmarks. I will update my post above to include this information.

[Robbepop]

I don't know if this is related but today I removed 4 unnecessary instructions from the wasmi interpreter. My expectation was that the removal shouldn't change performance at all. However, there were massive regressions again. This time I took the cargo-asm tool to analyze the Executor::execute function I linked earlier in this thread just to see massive differences between the master branch and the PR branch:

• master: https://gist.github.com/Robbepop/cde5a25f00b78259a11170a6614aca90
  • Roughly 3.8k lines of assembly
• master + nightly: https://gist.github.com/Robbepop/a498308cd53c7e75c55f8342786f667d
  • Roughly 4.1k lines of assembly
• PR: https://gist.github.com/Robbepop/9df0eb661c5fcab9aa8391221fda7196
  • Roughly 5.9k lines of assembly

The diff between master on stable Rust and master on nightly Rust:
https://gist.github.com/Robbepop/88660d17ec1ede77562732bb68670c8c

So it indeed seems to be the culprit of the issue that Rust + LLVM easily fails to properly optimize this function using the threaded-code style branching technique when the stars are misaligned.

Reproduce

The PR that I created today can be found here: wasmi-labs/wasmi#518
In order to make cargo-asm able to display the function I had to insert the following code:

// wasmi/src/engine/executor.rs
pub trait Execute: Sized {
    fn execute_dummy(self) -> Result<CallOutcome, TrapCode>;
}

impl<'ctx, 'engine, 'func> Execute for Executor<'ctx, 'engine, 'func, ()> {
    fn execute_dummy(self) -> Result<CallOutcome, TrapCode> {
        self.execute()
    }
}

And also add

[profile.release]
lto = "fat"
codegen-units = 1

to the Cargo.toml of the workspace since cargo-asm does not yet support the --profile argument and we want to optimize with codegen-units=1 and lto="fat".

Install the cargo-asm tool via: cargo install cargo-show-asm.
Run the cargo-asm tool via: cargo asm -p wasmi --lib --release execute_dummy > execute_dummy.asm
We need to pipe it into a file since the output is quite large.

[the8472]

This indeed does look like the difference between tail calls vs. dispatching from a loop with computed jumps.

hottest instruction in the fast version. note the jmp %*rax

hottest instruction in the slow version. note all the jumps back to 24c0 and the incoming jumps at 24c5:

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

Discussed by T-compiler (notes), a smaller reproducible would probably help:

what tools LLVM has to minimize bug reports. Perhaps there's something that can be leveraged to extract just the IR from the interpreter loop function and dependencies?

As mentioned in the opening comment, a bisection seems to point at the LLVM15 upgrade (#99464), specifically between nightly-2022-08-12 and nightly-2022-08-13.

@rustbot label -I-prioritize +P-high E-needs-mcve -I-compiler-nominated