Rust: Exponential trait selection when compiling a crate using combine 4

[Marwes]

Originally reported in https://github.com/Marwes/combine/issues/284 . It appears that the changes made between version 3 and 4 in https://github.com/Marwes/combine . Made trait selection exponential in some cases. The main change that I would suspect causing this is that combine-3 had Input as an associated type whereas combine-4 uses a type parameter.

The following minimized repo reproduces the slowdown, removing a few arguments from the choice! macro makes it compile quickly https://github.com/Marwes/combine-slow-compile . The commit before master contains a version with combine-3 which compiles instantaneously (after dependencies are compiled). (diff https://github.com/Marwes/combine-slow-compile/commit/21cf38a5429e32a703c2bc2ea02cbcbaf2985b01)

[sdroege]

The E-needs-mcve label seems wrong, there's a minimal testcase linked in the initial description :)

[sdroege]

This is btw the same function as in https://github.com/rust-lang/rust/issues/67454, just that with combine 3 this works fine again now while with combine 4 it exposes the same behaviour

[jonas-schievink]

I tagged it needs-MCVE because the reproduction above still pulls in 2 dependencies. It would be helpful to get it down to a single file.

[Marwes]

Minimized, add more token parsers to get more of a slowdown.

use std::marker::PhantomData;

pub trait Parser<Input> {
    type Output;

    fn or<P2>(self, p: P2) -> Or<Self, P2>
    where
        Self: Sized,
        P2: Parser<Input, Output = Self::Output>,
    {
        Or(self, p)
    }
}

#[macro_export]
macro_rules! choice {
    ($first : expr) => {
        $first
    };
    ($first : expr, $($rest : expr),+) => {
        $first.or(choice!($($rest),+))
    }
}

pub struct Or<P1, P2>(P1, P2);
impl<Input, P1, P2> Parser<Input> for Or<P1, P2>
where
    P1: Parser<Input, Output = P2::Output>,
    P2: Parser<Input>,
{
    type Output = P2::Output;
}

pub struct P<I, O>(PhantomData<fn(I) -> O>);
impl<Input, O> Parser<Input> for P<Input, O> {
    type Output = O;
}

pub fn token<I>(_: u8) -> impl Parser<I, Output = u8> {
    P(PhantomData)
}

fn mcc_payload_item<I>() -> impl Parser<I, Output = u8> {
    choice!(
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G'),
        token(b'G')
    )
}

fn main() {}

[nnethercote]

This was fixed by #67471, which reverted the regressing code from #66405.

[Marwes]

No, this isn't fixed by #67471 . This is a separate issue (even if the reproductions are really similar).

[nnethercote]

Ok, sorry for the confusion. Just to clarify: there is no rustc regression involved here, right?

[Marwes]

No, i looked back a few versions and it was always slow.

[nnethercote]

I increased the size of the benchmark from 16 tokens to 19 and did some profiling.

register_obligation_at is called 3.4M times. It accounts for most of the runtime.

The length of self.nodes gets up to 1.4M.

Worst of all, the length of at least one node.dependents gets up to 131k, which is extraordinary. This results in quadratic behaviour, because of this code, because contains does a linear search:

    if !node.dependents.contains(&parent_index) {
        node.dependents.push(parent_index);
    }

I.e. the length of this node.dependents grows from 0 to 131k one at a time, with a failing linear search on every push.

I printed out the predicates being added, there are a lot (786k) of these ones:

Binder(TraitPredicate(<impl Parser<_> as std::marker::Sized>))

I don't really understand the predicate stuff, but maybe @nikomatsakis has some thoughts about this?

[Marwes]

@nnethercote Got a big PR in the works which rewrites most of ObligationForest. It doesn't affect this particular issue (sadly) but it is likely to collide with any changes to fix this issue.

https://github.com/rust-lang/rust/pull/69218

[Marwes]

Seeing what looks like this issue in futures heavy code as well (in two different projects). Root issue is that there are just too many obligations generated, nothing can be done to ObligationForest itself to speed this up, I think. Selection just need to generate fewer obligations, or at least they must be memoized better.