Match checking has quadratic average complexity

[graydon]

If you look at the trans-stats for some of our modules, some "big functions" really stand out:

rustc:

16838 insns, 67 ms, middle::trans::foreign::trans_intrinsic
15988 insns, 145 ms, middle::typeck::check::check_expr_with_unifier
11759 insns, 87 ms, middle::privacy::check_crate

libextra: 

5244 insns, 31 ms, terminfo::parm::expand
5073 insns, 21 ms, time::do_strptime::parse_type
4068 insns, 23 ms, time::do_strftime::parse_type
3610 insns, 73 ms, terminfo::parser::compiled::parse
2169 insns, 89 ms, net_tcp::listen_common
1952 insns, 28 ms, getopts::getopts
1937 insns, 193 ms, net_tcp::connect

If you look at the code generating them, they don't immediately look like they should be taking 10x as long as other functions; but they do all seem to use match somewhat heavily. This suggests to me that we're still compiling matches in some way that causes a combinatorial explosion of basic blocks, or something.

Investigate!

[emberian]

/cc @toddaaro

[emberian]

/cc @msullivan
I don't think it was actually toddaaro I was talking to about this...

[toddaaro]

I have whined a lot about match implementations that suffer from combinatorial explosion, so maybe that is why you thought of me.

This Scala issue is probably unrelated, but maybe reading about the experience will prove useful to a Rust developer someday.

https://issues.scala-lang.org/browse/SI-1133

[steveklabnik]

Triage: did anyone determine if match was still the issue here? I'd imagine codegen has gotten better since 2013...

[emberian]

@steveklabnik I don't know of any changes to match codegen that would have alleviated this, re-running the measurements...

[emberian]

Yes, match is still generating more code than anything else, by a significant margin.

[steveklabnik]

@cmr if you have a moment, can you explain how you checked this out? Future triage-rs will be thankful 😄

[emberian]

make RUSTFLAGS="-Z count-llvm-insns" | tee output, followed by sort -n < output > output2, then look at the bottom of output2 (ctrl-f for "trans_match")

[huonw]

trans-ing a match appears to be quadratic in the number of arms (at least for integers and strings):

$ for N in 500 1000 2000 4000; do
    echo $N
    python -c "print('fn main() { match 0 { %s _ => {} } }' % ''.join(' %s => {}' % n for n in range(0, $N)))" | 
        rustc - -Z time-passes |
        grep translation
  done
500
time: 0.030; rss: 65MB  translation
1000
time: 0.107; rss: 67MB  translation
2000
time: 0.427; rss: 70MB  translation
4000
time: 1.620; rss: 75MB  translation

(The python invocation prints code like fn main() { match 0 { 0 => {} 1 => {} 2 => {} 3 => {} 4 => {} _ => {} } } with $N + 1 arms.)

[brson]

Results of @huonw's script above with rustc 1.11.0-nightly (34505e222 2016-06-08):

500
time: 0.088; rss: 97MB  translation
1000
time: 0.308; rss: 100MB translation
2000
time: 1.247; rss: 101MB translation
4000
time: 4.723; rss: 106MB translation

With -Z orbit:

500
time: 0.009; rss: 95MB  translation
1000
time: 0.015; rss: 97MB  translation
2000
time: 0.017; rss: 101MB translation
4000
time: 0.030; rss: 104MB translation

MIR trans looks to be a lot better at this case.

[arielb1]

@brson

MIR trans's algorithm is indeed very careful to generate a linear number of basic blocks.