Optimize MBE (macro by example) performance

[edwin0cheng]

Recently (#7513) we implemented a new NFA based expander for MBE which is quite slow compared to the old one (based on recursive descent). It would be nice if someone could optimize it to run as fast as possible.

Benchmark

We already have a benchmark for it, to run the benchmark :

$ RUN_SLOW_TESTS=1 cargo test --release --package mbe -- benchmark::benchmark_expand_macro_rules --nocapture

Output should be something like:

running 1 test
mbe expand macro rules: 2.21s, 8464minstr
test benchmark::benchmark_expand_macro_rules ... ok

Source

The corresponding source code of mbe expander is at :

https://github.com/rust-analyzer/rust-analyzer/blob/3b507aa90fca9618ddbe0667e245ef4766aa96b5/crates/mbe/src/expander/matcher.rs#L148-L151

And we have a bunch of compliance tests related to mbe, to run these test :

$  cargo test --package mbe -- --nocapture

Tips

By default, RA turn off the debug information in Cargo.toml :

https://github.com/rust-analyzer/rust-analyzer/blob/3b507aa90fca9618ddbe0667e245ef4766aa96b5/Cargo.toml#L18-L20

You may need to set it to debug = 2
And here is how I run perf in linux:

$ RUN_SLOW_TESTS=1 perf record --call-graph dwarf  cargo test --release --package mbe -- benchmark::benchmark_expand_macro_rules --nocapture
$ perf report --call-graph

[EDIT: added --release flag]

[edwin0cheng]

CC #5549

[jonas-schievink]

It's probably better to run the benchmark with --release, otherwise it doesn't get optimized and you'll optimize for the wrong thing.

[edwin0cheng]

Good point ! Edited for --release

[dzmitry-lahoda]

if this is root cause of #7934 , than it is on linux also, and really slow on diesel compilation (diesel is very very meta template heavy)

[flodiebold]

See also #4186.

[TimoFreiberg]

For me, the benchmark showed improvements when replacing most of the SmallVecs in match_loop and mach_loop_inner with Vecs. I don't know whether my local benchmarks are meaningful though...
Do you want me to create a PR for this? master...TimoFreiberg:7857-benchmark

For the benefit of other readers, here's a flamegraph from my machine.
It looks like cloning the MatchState is the most expensive operation...

[edwin0cheng]

For the benefit of other readers, here's a flamegraph from my machine.
It looks like cloning the MatchState is the most expensive operation...

Yeah, and specially cloning for Bindings , I implemented #7994 for that, but in general it still needed to improve a lot.