Optimize MBE (macro by example) performance

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]

Start in crates/mbe/src/expander/matcher.rs around the referenced expander code, then run the release benchmark command to establish the baseline. Use profiling as suggested and run the full crates/mbe test suite after changes; done means the benchmark improves without breaking the compliance tests.