Haha, seems correct 🙈

fn main() {
    let string = std::fs::read_to_string("string.txt").unwrap();
    let time_before = std::time::Instant::now();
    // Benchmarked block
    {
        let answer = arrow_search(&string);
        println!("Answer: {}", answer);
    }
    println!("Elapsed time: {:.2?}", time_before.elapsed());
}

I wasn't actually very experienced at this stuff, so I used plain std::time and manually ran the code multiple times to check the variance. Benchmarking println!("Answer: {}", answer); looks very weird, but I probably didn't know about black_box and needed to make sure that the code actually did the work.

I don't remember why I saved a fixed generated string to disk. I don't have the code that generated it, but I still have string.txt. It looks like it was the same b".-=<>".choose(&mut rng), but 10 MB in size rather than 1 KiB.

On my current machine, here are the timings from this bench:

• My regex solution: 29.35s
• My table solution: 347ms
• Your solution: 223ms

The speedup is still 84x, even though I'm on a different machine now

Ah, hence the inline.
I was wondering what it was for, thanks :)

I guess the compiler automatically changes 21**n in the result.

Approved by someone

Thank you for your observation

OK, it's all good when applied consistently at all stages. But if usage of panic needs to be documented (so it kind of is a part of an interface?) and usage of unreachable isn't and the task doesn't specify actions expected for invalid input (so it doesn't expect panicking), doesn't it mean that using panic changes the interface in a way?

that a branch is unreachable given any arguments

Arguments of the match expression, as I can see, because this example already requires knowing the expression and not just patterns. So what scope would you consider for this proof? Would

let t = s % 4;
match t {

already not be qualified for unreachable with this definition? unreachable in necessary for the cases when the set of rules for checking reachability used by the compiler is different from the set of rules used by the user. Compiler/language rules are chosen with some balance between complexity/performance/impact in mind and can be extended in the future. What are the criteria for user's rules? If this boundary isn't just arbitrary, what's the reason for it to be exactly when it is?

Agree. Now I would have written it differently.

I think it's better to use it where you can replace unreachable! with unreachable_unchecked without making the function unsafe.

... which is always the case with ideal code without bugs and never otherwise, unless the compiler can prove that it's unreachable, but then there would be no need in explicit unreachable!/unreachable_unchecked in the first place.

For example, with patterns that can never be matched.

I assume you mean the cases when it can be proven based on the patterns alone, but the compiler is unable to prove it (yet) and the user doesn't want to rewrite the code in a way that proves it? But "based on the patterns alone" seems like a pretty arbitrary restriction and other than that it's the same case here: input constraints are specified, so input is already validated, so this pattern is unreachable, but the compiler can't prove it and the user doesn't want to prove it (for example, by accepting an already parsed pair of enums).

It may not be a good idea in a real world scenario to specify such input constraints and still pass a plain &str, but if they've done it, I consider it as-if properly proven, so if anything happens, it's their problem. (Except maybe choosing to use the English alphabet while the exact alphabet is unspecified here.)

to indicate that there's a bug when it's reached

Do you mean some specific kind of bug, like a bug in a pattern? Because if there's malformed input, it's a bug somewhere in input validation code.

I've updated the description rather than mess with the tests (I'm no good at rust, I didnt wanna break anything). Thanks for pointing it out.

About difficulty, yeah I've heard its noticeably more difficult in rust than in the original language.

I'm afraid you are correct. My new solution using your idea is asymptotically faster.

Where does the heap allocation occur?

I don't know Rust :(

How did you measure that?