Strange compile time with a huge `match` block

I'm telling joke with friends, when we are asked to do some task with a given amount of input, a simple solution is record all the output in the program, then use a match block to choose the right one.

Here comes the question, it seems match block would take more than O(N) time to compile with N arms.

Is it normal?

Test case:

use std::{io::Write,fs::File};
fn main()->Result<(),Box<dyn std::error::Error>>{
    let mut f=File::create("wtf.rs")?;
    writeln!(&mut f,"{}","\nfn main(){\n    match std::env::args().nth(1).unwrap_or(\"\".to_string()).as_str() {")?;
    for i in 0..1000 {
        writeln!(&mut f,"        \"{}\" => println!(\"found {}, rev {}\"),",i,i,i.to_string().chars().rev().collect::<String>())?
    }
    writeln!(&mut f,"        any => println!(\"input `{}` outside the range\",any)","{}")?;
    writeln!(&mut f,"{}","    }\n}")?;
    Ok(())
}

compile instruction:

rustc --edition 2021 test.rs  -o test && ./test && time rustc --edition 2021 wtf.rs  -o wtf

it takes:

real    0m0.797s
user    0m0.754s
sys     0m0.107s

to finish the computing, but if we use 10000 rather than 1000 arms, it would take

real    0m18.451s
user    0m17.963s
sys     0m0.537s

to finish compile. to compare fairly, use 5000 arms would get:

real    0m5.752s
user    0m5.527s
sys     0m0.293s

It seems that, match block consume O(N^2) compile time with N arms, is this time cost normal? Why it is so slow?

3 Likes

For this particular case, I don't know; could be an artifact of optimizing a lookup table or something. Perhaps it could be targeted for improvement.

Fun fact though: in the general case, exhaustiveness checking is NP-hard. Even though that's technically not required with a catch-all arm, it's going to do some analysis so it can find unreachable patterns. (No idea which is the slow part here, just spitballing.)

5 Likes

A couple of things you could try:

  • Time the cargo check time, to see whether the non-linear behaviour is in rustc's code or in the LLVM codegen. (If it's in rust it's more likely something that rustc-perf could track improving.)

  • Refactor the code to avoid calling the println! macro in every line. You might get much better compilation performance if you use the match to return a tuple of stuff, then only have one println! to show the result of a successful lookup.

  • Or, since you're just matching over sequential natural numbers from zero, generate a big

static PRECOMPUTED: &[&str] = &[
    "0",
    "1",
    …
    "9",
    "01",
    "11",
    …
];

and use PRECOMPUTED.get(…) instead of the match. (You can see versions of this in core, such as rust/validations.rs at aeb5067967ef58e4a324b19dd0dba2f385d5959f · rust-lang/rust · GitHub)

1 Like

Congratulations, this is the 5th oldest open issue:

https://github.com/rust-lang/rust/issues/7462

8 Likes

It's NP-Hard with regards to the complexity of the pattern matched (in the linked article: the number of elements in a tuple) not the number of patterns (like in this case).

1 Like

I recognize that, but was just pointing it out as (1) a fun fact and (2) due to the O(_) comment (in a general sense, not this specific case).

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.