You can check out the fork that doesn't assume a specific encode_utf8 implementation and that favors ASCII input.

it's 10 times faster than the most popular solution

bouncing_ball(1., 0.5, 0.25) will return 5 instead of 3 here

this is a thousand times slower than it could be

When I run your benchmark with a 10M random file, I get 307.73ms, 37.92ms and 74.46ms, which is close to what I had. However, when I run it without --release, I get 7.26s, 319.00ms, 206.36ms, which is similar to your result. So maybe you were missing the compiler optimizations?

In my benchmark I get:

your regex solution: 20,933.28 ns/iter
your table solution: 2,174.62  ns/iter
my solution:         1,590.12  ns/iter

Here I see a 10x boost instead of a 90x boost.
So may I know how your benchmark is organized?
Mine is as follows:

#![feature(test)]

extern crate test;
use core::array;
use finding_arrows_in_a_string::arrow_search;
use rand::seq::SliceRandom;
use rand_pcg::Pcg64Mcg;
use test::{black_box, Bencher};

#[bench]
fn bench(bencher: &mut Bencher) {
    let mut rng = Pcg64Mcg::new(0xcafe_f00d_d15e_a5e5);
    let string: [_; 1024] = array::from_fn(|_| *b".-=<>".choose(&mut rng).unwrap());
    let string = core::str::from_utf8(&string).unwrap();
    bencher.iter(|| arrow_search(black_box(string)));
}

Nice. There is a typo though: in emit_instructions_recursive you have PO instead of PU. Also, move_immediate_to_rhs can swap the operands of division or subtraction.

It simplifies the code, of course, but it also makes it about 8 times slower.

Exponentiation is a difficult operation, I made it faster by introducing a 10 element table of precomputed powers.

Check out the improved version (the fork). It's 15 times faster than the format! way.

Nice. The 3 pushes make encoding 10 times slower though.