Increase in compilation times with newest beta & nightly

[fengalin]

Description

This was initially reported in Marwes/combine#278.

I hit an important increase in compilation times on beta & nightly with a
particular configuration using combine-3.8.1 since the recent version updates
in the Rust toolchains.

I tried building an example without combine in order to submit it to rustc
but it turns out not to be trivial. I ran into this as a side effect in CI and
can't spend much time investigating ATM, sorry.

From the CI logs I have at hand, the issue was not present as of:
rustc 1.41.0-nightly (fdc0011 2019-12-02).

Reduced example

Here is an example with which I was able to reproduce the issue:

use combine::byte::hex_digit;
use combine::{choice, token};
use combine::{ParseError, Parser, RangeStream};

fn parse<'a, I: 'a>() -> impl Parser<Input = I, Output = u8>
where
    I: RangeStream<Item = u8, Range = &'a [u8]>,
    I::Error: ParseError<I::Item, I::Range, I::Position>,
{
    choice!(
        token(b'A').map(|_| 1),
        token(b'B').map(|_| 2),
        token(b'C').map(|_| 3),
        token(b'D').map(|_| 4),
        token(b'E').map(|_| 5),
        token(b'F').map(|_| 6),
        token(b'G').map(|_| 7),
        token(b'H').map(|_| 8),
        token(b'I').map(|_| 9),
        token(b'J').map(|_| 10),
        token(b'K').map(|_| 11),
        token(b'L').map(|_| 12),
        token(b'M').map(|_| 13),
        token(b'N').map(|_| 14),
        token(b'O').map(|_| 15),
        token(b'P').map(|_| 16),
        token(b'Q').map(|_| 17),
//        token(b'R').map(|_| 18)
        (hex_digit(), hex_digit()).map(|(u, l)| {
            let val = (u << 4) | l;
            val
        })
    )
    .message("while parsing")
}

Toolchain versions

The toolchain used for these tests are those available as of 2019/12/20:

• stable: rustc 1.40.0 (73528e3 2019-12-16)
• beta: rustc 1.41.0-beta.1 (eb3f7c2 2019-12-17)
• nightly: rustc 1.42.0-nightly (0de96d3 2019-12-19)

Compilation times

For each test, cargo clean was run before building in debug mode.

With message(..)

Configuration	stable	beta	nightly
15 tokens	12.79s	26.83s	25.38s
17 tokens	12.69s	2m 20s	2m 20s
18 tokens	12.89s	6m 50s	6m 55s
17 tokens + (hex_digit, hex_digit)	12.84s	15m 57s	16m 54s

Without message(..)

"Interestingly", removing the .message(..) line reduces compilation times
significantly.

Configuration	stable	beta	nightly
15 tokens	12.67s	19.89s	16.14s
18 tokens	12.67s	4m 11s	2m 34s
17 tokens + (hex_digit, hex_digit)	12.78s	5m 00s	4m 35s

[sdroege]

Thanks to cargo-bisect-rustc, the first nightly with the regression is nightly-2019-12-14. nightly-2019-12-13 was still working fine.

[sdroege]

I.e. somewhere between 3eeb8d4 and ff15e96

[sdroege]

And we have a winner:

[...]
searched toolchains 3eeb8d4 through ff15e96
regression in 9409c20

I.e. #66405

[nnethercote]

Thanks for the report! I'm about to go on vacation for 6 weeks, so I will file a PR to back out #66405 before I go.

[sdroege]

Thanks, and enjoy your holidays!