Extremely long compile times

[hawkw]

I know this issue is a little vague, so please bear with me. As I've started using parser-combinators, I've noticed that the compile times for my project have sharply increased; more than I would expect from the amount of code I've written. cargo build now takes 8 to 11 minutes to complete. This is on a fairly new machine, too - I have a MacBook Pro with a 2.5GHz quad-core i7, and I've generally seen very good performance from cargo/rustc.

I guess I'm just curious to know what's causing these very long compile times. Is this to be expected when using this library, am I misusing it in some way that's confusing rustc, or is something else wrong? Of course, it's likely difficult to determine exactly what's going on, but I'd welcome any additional information.

[Marwes]

I thought I had an issue open for this but it appears I had forgotten open one.

rustc seems to have some issues with deeply nested types + associated types (see rust-lang/rust#21231).

To workaround it until it gets fixed you have to write smaller parsers, ie factor out parts into freestanding functions instead of storing them in local variables.

Example at: https://github.com/Marwes/parser-combinators/blob/master/benches/json.rs#L110-L128

(It might be possible to specialize the parsers directly as well, say

fn expr(input: State<&str>) -> ParseResult<Expr, &str>

instead of

fn expr<I: Stream>(input: State<I>) -> ParseResult<I, &str>

)

[hawkw]

@Marwes Excellent, thank you very much for the quick advice, I really appreciate that. I'll try refactoring some of my code and let you know if I'm still having problems.

[hawkw]

Okay, I did some refactoring (hawkw/seax@96af0b7) and compile times have reduced significantly. My laptop no longer smells like it's melting, and maybe I can even turn lint-on-save back on. Thanks so much.

[Marwes]

I happened upon a workaround to half of this problem, namely the part where functions need to be specialized.

Say you have a bunch of parser functions:

fn parse1<I>(input: State<I>) -> ParseResult<i32, I> where I: Stream { ... }
fn parse2<I>(input: State<I>) -> ParseResult<i32, I> where I: Stream  { ... }
fn parse3<I>(input: State<I>) -> ParseResult<i32, I> where I: Stream  { ... }

If you move all of these functions into an impl block for a type you can get the same compile times as with the specialized version like this:

struct P<I>(PhantomData<fn (I) -> I>);
impl <I> P<I>
    where I: Stream {
    fn parse1(input: State<I>) -> ParseResult<i32, I> { ... }
    fn parse2(input: State<I>) -> ParseResult<i32, I> { ... }
    fn parse3(input: State<I>) -> ParseResult<i32, I> { ... }
}

In addition to this, when these functions refer to each other they need to be specialized, i.e write P::<I>::parse1 and not P::parse1. The second form unfortunately triggers the slow behavior so make sure that all functions are specialized if it is still slow.

[hawkw]

Interesting! I don't think that will help my current situation particularly (all of my parsers are specialized and that's not particularly a problem; compile times are still slow since they're still somewhat complex), but it's good to know!

[tari]

rust-lang/rust#22204 might be related too.

[Marwes]

rust-lang/rust#20304 also seems to be an issue and reducing the nesting of types does not seem to workaround that problem either. After using the above techniques on https://github.com/Marwes/parser-combinators-language the trans phase still takes a very long time with about half the total time spent just normalizing associated types =/

[Marwes]

I guess it should also be mentioned that moving the parser implementation to a separate crate which only expose specialized parser functions can be used to avoid long compile times on every recompile as rustc can just link the the already compiled code in that case, avoiding a full recompilation.

[Ralle]

I have done things recommended here, but I still get a compile time > 1 minute. Do you know what I can do to improve on things?
https://gist.github.com/Ralle/ca7533ed8faa0bd788d8

[Marwes]

@Ralle Either wrap all your functions in a type as I suggested above or specialize all your I parameters to &str. If you are using a stable compiler you might want to change to nightly (even if you don't use any unstable features) since there are some significant performance improvements.

If you still find the compilation times move the parser to its own crate and you will at least avoid the compile times when you do not modify the parser.

[Marwes]

I have been meaning to add the project that I use combine and combine-language in pretty soon though I have not had the time to get it into proper shape yet. That should display what I have done to make it work with a large parser in a compiler.

[hawkw]

I would love to see that whenever it's ready to be shown to the public; I've been thinking about trying to refactor my Scheme parser some, and I'd like to see how you're using the library in your own code.