{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/7462","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/7462/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/7462/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/7462/events","html_url":"https://github.com/rust-lang/rust/issues/7462","id":16160601,"number":7462,"title":"Code generated for match appears to have combinatorial problems","user":{"login":"graydon","id":14097,"avatar_url":"https://avatars.githubusercontent.com/u/14097?v=3","gravatar_id":"","url":"https://api.github.com/users/graydon","html_url":"https://github.com/graydon","followers_url":"https://api.github.com/users/graydon/followers","following_url":"https://api.github.com/users/graydon/following{/other_user}","gists_url":"https://api.github.com/users/graydon/gists{/gist_id}","starred_url":"https://api.github.com/users/graydon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/graydon/subscriptions","organizations_url":"https://api.github.com/users/graydon/orgs","repos_url":"https://api.github.com/users/graydon/repos","events_url":"https://api.github.com/users/graydon/events{/privacy}","received_events_url":"https://api.github.com/users/graydon/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/rust-lang/rust/labels/A-codegen","name":"A-codegen","color":"d7e102"},{"url":"https://api.github.com/repos/rust-lang/rust/labels/I-compiletime","name":"I-compiletime","color":"e11d21"},{"url":"https://api.github.com/repos/rust-lang/rust/labels/I-slow","name":"I-slow","color":"e10c02"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":9,"created_at":"2013-06-28T20:42:55Z","updated_at":"2016-01-05T05:41:09Z","closed_at":null,"body":"If you look at the trans-stats for some of our modules, some \"big functions\" really stand out:\r\n\r\n~~~~\r\nrustc:\r\n\r\n16838 insns, 67 ms, middle::trans::foreign::trans_intrinsic\r\n15988 insns, 145 ms, middle::typeck::check::check_expr_with_unifier\r\n11759 insns, 87 ms, middle::privacy::check_crate\r\n\r\nlibextra: \r\n\r\n5244 insns, 31 ms, terminfo::parm::expand\r\n5073 insns, 21 ms, time::do_strptime::parse_type\r\n4068 insns, 23 ms, time::do_strftime::parse_type\r\n3610 insns, 73 ms, terminfo::parser::compiled::parse\r\n2169 insns, 89 ms, net_tcp::listen_common\r\n1952 insns, 28 ms, getopts::getopts\r\n1937 insns, 193 ms, net_tcp::connect\r\n~~~~\r\n\r\nIf 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.\r\n\r\nInvestigate!"},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/168904677","html_url":"https://github.com/rust-lang/rust/issues/7462#issuecomment-168904677","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/7462","id":168904677,"user":{"login":"huonw","id":1203825,"avatar_url":"https://avatars.githubusercontent.com/u/1203825?v=3","gravatar_id":"","url":"https://api.github.com/users/huonw","html_url":"https://github.com/huonw","followers_url":"https://api.github.com/users/huonw/followers","following_url":"https://api.github.com/users/huonw/following{/other_user}","gists_url":"https://api.github.com/users/huonw/gists{/gist_id}","starred_url":"https://api.github.com/users/huonw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/huonw/subscriptions","organizations_url":"https://api.github.com/users/huonw/orgs","repos_url":"https://api.github.com/users/huonw/repos","events_url":"https://api.github.com/users/huonw/events{/privacy}","received_events_url":"https://api.github.com/users/huonw/received_events","type":"User","site_admin":false},"created_at":"2016-01-05T05:41:09Z","updated_at":"2016-01-05T05:41:09Z","body":"trans-ing a `match` appears to be quadratic in the number of arms (at least for integers and strings):\r\n\r\n```\r\n$ for N in 500 1000 2000 4000; do\r\n    echo $N\r\n    python -c \"print('fn main() { match 0 { %s _ => {} } }' % ''.join(' %s => {}' % n for n in range(0, $N)))\" | \r\n        rustc - -Z time-passes |\r\n        grep translation\r\n  done\r\n500\r\ntime: 0.030; rss: 65MB\ttranslation\r\n1000\r\ntime: 0.107; rss: 67MB\ttranslation\r\n2000\r\ntime: 0.427; rss: 70MB\ttranslation\r\n4000\r\ntime: 1.620; rss: 75MB\ttranslation\r\n```\r\n\r\n(The python invocation prints code like `fn main() { match 0 {  0 => {} 1 => {} 2 => {} 3 => {} 4 => {} _ => {} } }` with `$N + 1` arms.)"}}