Compile times: Average vs worst case runtime

Simon Peyton Jones simonpj at microsoft.com
Thu Aug 30 21:07:12 UTC 2018


Good work.

| However it will also be possible to fall back to the old behavior to
| avoid the large compile times for modules known to trigger this
| edge case.

Not for specific modules, I hope; rather fall back when the number of cases becomes large, or something like that?  That'd be fine.

The only other potential worry is how tricky/understandable is your patch.  Hopefully it's not hard.

| 1. Always since on average both compile and runtime is faster.
| 2. -O1/O2 since users often use this when performance matters.
| 3. -O2 since users expect compilation times to blow up with it?
| 4. Never as users experience compile time slowdowns when they hit these
| edge cases.

Well, if you can robustly fall back in edge cases, you'll never hit the blow-ups.  So then (1) would be fine would it not?

Simon




| -----Original Message-----
| From: ghc-devs <ghc-devs-bounces at haskell.org> On Behalf Of Andreas
| Klebinger
| Sent: 30 August 2018 18:08
| To: ghc-devs at haskell.org
| Subject: Compile times: Average vs worst case runtime
| 
| Hello Devs,
| 
| I developed a patch improving on GHC's code layout during GSoC:
| https://ghc.haskell.org/trac/ghc/ticket/15124
| The gains are pretty nice with most library benchmarks showing
| improvments in the 1-2% range or more.
| 
| Even compile times went down comparing head vs stage2 built with, and
| using my patch!
| Making compilation of nofib overall faster by 0.5-1% depending on the
| exact setup.
| 
| Now the bad news:
| In some cases the algorithm has bad big O performance, in practice this
| seems to be code with
| things like cases with 200+ alternatives. Where these cases also
| represent most of the code compiled.
| 
| The worst case I saw was doubled compile time in a Module which only
| consisted of a 500 deep if/else chain only selecting
| an value.
| 
| While there are some small optimizations possible to improve on this I
| don't expect to make these edge cases much faster overall.
| However it will also be possible to fall back to the old behavior to
| avoid the large compile times for modules known to trigger this
| edge case.
| 
| Which brings me to my main question: When should we use the new code
| layout.
| 1. Always since on average both compile and runtime is faster.
| 2. -O1/O2 since users often use this when performance matters.
| 3. -O2 since users expect compilation times to blow up with it?
| 4. Never as users experience compile time slowdowns when they hit these
| edge cases.
| 
| I'm would prefer 2. 3. 1. 4. in that order but I wonder what the wider
| community is thinking.
| 
| Cheers
| Andreas
| _______________________________________________
| ghc-devs mailing list
| ghc-devs at haskell.org
| http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


More information about the ghc-devs mailing list