Long compile/optimization times with chained Option iterators

[smangelsdorf]

When using chained option iterators to build a collection, I found that compile times in release mode were longer than I expected. Originally this was reported on the Gotham gitter channel, and I wrote the following PR which has drastically improved the compile times on my machine:

gotham-rs/gotham#194

To reproduce the issue in a more useful way, I've written the following which doesn't finish compiling in the rust playground:

https://play.rust-lang.org/?gist=de324d04c49e0702326210342a6e7d30&version=stable

This same code compiles on my machine in approximately 2 seconds (or 3.5 seconds with rustc -O), vs ~150ms for a simple "Hello, world!" style application.

Rightly or wrongly, I didn't expect the impact on compile times to be this drastic, though I feel that I've just hit an edge case and the easiest answer is to write better Rust code.

Compile time on Gotham's 0.2-maint branch, which didn't yet have the above PR merged:

(rustc CPU usage was sitting at 100% of a single core for the duration)

$ cargo build --release
   Compiling gotham v0.2.1-dev
    Finished release [optimized] target(s) in 1047.79 secs

Output with -Z time-passes

Compile time on the branch used to submit the above PR:

$ cargo build --release
   Compiling gotham v0.2.1-dev
    Finished release [optimized] target(s) in 5.38 secs

Output with -Z time-passes

On scanning the issue tracker, I found #22204 which may be the same problem, but I'm not entirely sure.

Meta

I tried this on my stable and nightly compilers, which both exhibited the same behaviour. The output above is from my nightly compiler.

$ rustc --version --verbose
rustc 1.26.0-nightly (482a913fb 2018-03-25)
binary: rustc
commit-hash: 482a913fb337855072a53c0d602cd19947f45285
commit-date: 2018-03-25
host: x86_64-apple-darwin
release: 1.26.0-nightly
LLVM version: 6.0

$ rustc +stable --version --verbose
rustc 1.24.0 (4d90ac38c 2018-02-12)
binary: rustc
commit-hash: 4d90ac38c0b61bb69470b61ea2cccea0df48d9e5
commit-date: 2018-02-12
host: x86_64-apple-darwin
release: 1.24.0
LLVM version: 4.0

[shepmaster]

I agree that it's most likely related to #22204, since chain has associated item equality clauses:

impl<A, B> Iterator for Chain<A, B> 
where
    A: Iterator,
    B: Iterator<Item = <A as Iterator>::Item>, 

I think the simpler reproduction is:

fn main() {
    let start: Option<u8> = None;

    let output = start
        .into_iter()
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .chain(None)
        .count();
}

[ishitatsuyuki]

Sounds like the comeback of exponential complexity. Can you do the following things:

1. Ensure you're using a recent nightly
2. Run rustc with gdb and interrupt during the long operation
3. Paste the stack trace of the compiler thread (we don't do work on main thread because stack limit)

[ishitatsuyuki]

@shepmaster Your example compiles reasonably fast with current nightly, and that should be exactly the case I've recently fixed.

[ishitatsuyuki]

@smangelsdorf, Please always use nightly when verifying the impact of this bug, because #48296 solves the typechecking side of this issue. Though, I agree that there seems to be something wrong during the LLVM passes from what I see from your timing information. I will try to reduce the cases.

[ishitatsuyuki]

Possible LLVM bugs:

https://bugs.llvm.org/show_bug.cgi?id=12218
https://bugs.llvm.org/show_bug.cgi?id=33880

[smangelsdorf]

Thanks @ishitatsuyuki

1. Ensure you're using a recent nightly
2. Run rustc with gdb and interrupt during the long operation
3. Paste the stack trace of the compiler thread (we don't do work on main thread because stack limit)

Do you still want this information? I haven't had a chance over the long weekend, but I'll try to get to it in the next few days if it's still needed after finding that LLVM bug report.

Please always use nightly when verifying the impact of this bug, because #48296 solves the typechecking side of this issue.

It might have been a little unclear from the structure of my top message here, but I was on a very recent (~48 hours old) nightly rust when I wrote the bug report up. Sorry for the confusion.

My understanding of this fix is that it would have definitely been included in the 2018-03-25 nightly. I'm happy to update and try again if that's useful.

[ishitatsuyuki]

Do you still want this information? I haven't had a chance over the long weekend, but I'll try to get to it in the next few days if it's still needed after finding that LLVM bug report.

I've already have been doing this, so no need to bother. BTW: opt-level=1 compiles in acceptable time.

My understanding of this fix is that it would have definitely been included in the 2018-03-25 nightly. I'm happy to update and try again if that's useful.

I think your playground examples is using stable; with nightly it compiles in time limit with debug, but not release. But the example compiles in seconds on local, so I'm having a hard time finding a minimal reproduction example.

[smangelsdorf]

This is an old issue and I've just confirmed that it's still fixed in the latest stable release, so closing. 🏆