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.

[Ralle]

Thank you for all your help so far.

I upgraded to the latest Rust and did the struct thing that you showed here. Still 1m 20s, I shaved off 20s. Any more suggestions?
https://gist.github.com/Ralle/6eb3234c665a4dde8940

[Marwes]

Reducing how many levels you nest parsers can reduce the typechecking times a bit but unfortunately the compile times will always be quite long compared to other rust code.

I did some modifications to your gist, changing or to choice and using tuple parsers instead of chaining skip/with. I got it down about 10-15 more seconds, shrinking a few of the other parsers should maybe shave of 10 more seconds. After that most time will be spent in translation which I think we need to wait for rust-lang/rust#20304 to see some lower times.

The best thing really, is to have the parser in separate crate as mentioned above. In the project I mentioned above it takes about 2m30s to compile (4m30s really since I specialize it for two different outputs) (EDIT: I do something weird with my parser tests since compiling the rest of the compiler, including the parser but not the parser tests, takes 3m11s) it but by keeping it in a separate crate I don't actually notice it since it rarely needs a full recompilation. I seem to remember it being shorter though so maybe there has been a regression in a recent nightly, might need to investigate.

Gist

EDIT: When I compile without needing to recompile the parser a compilation takes just 20s.

[hawkw]

Reducing how many levels you nest parsers can reduce the typechecking times a bit

Which is a shame, because of how one is generally kind of intended to use parser combinators. :)

[Marwes]

Its a shame that its necessary to reduce some nesting of the types but I'd say its generally a good idea to create many small parsers anyway. If really need to create a large parser you either have to wrap it in a closure (parser(|input| large_parser.parse_state(input)) or cast the parser to a trait object let parser: Parser<Input=I, Output=O> = &mut large_parser. Its not ideal but at least it works in the interim.

[Ralle]

Your suggestions helped me a lot. Thank you!

[Marwes]

I finally got the compiler into bit better shape and so I moved it to github. You can find it here. The parser is found in the parser folder for anyone looking for how I use combine. The full compile times are indeed long but as long as the parser is not modified it is as fast as any other rust program.

[Marwes]

There seems to be a regression in typechecking in recent nightlies as well as the 1.7.0 beta. If you are using a nightly version I really recommend using one before these regressions as compiletimes are really bad regardless of the workarounds. My 6 year old laptop takes 35 minutes when compiling tests (for combine) vs 2 minutes before the regression.

Rust issue: rust-lang/rust#31157

[pepyakin]

It seems to be better on the latest nightly-2016-06-06. I see 4х improvement in compile time.

[Marwes]

@pepyakin Thanks for reminding me to post here! Yeah, with rust-lang/rust#33816 merged I recommend using a nightly after 2016-06-05 until the release trains catch up.

[Marwes]

Closing this as with the release of rust 1.11 there is no longer an exponential compile time problem (compiling can still be a little slow due the the amount of types created but its no longer critical issue that has to be worked around).