Compile times: Average vs worst case runtime

[Andreas Klebinger]

Simon Peyton Jones schrieb:
> 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.
As it stands it's a regular flag and hence per Module (just like worker 
wrapper or similar) and user controlled.
In the code example I have in my head it was a large case that get's 
desugared to a larger chain of if/elseif/elseif/..../else.
So it's not strictly large cases but usually it is.

I actually didn't consider doing a "dynamic" fall back so far. That's a 
great idea!
If we are lucky we can use the ratio of edges to blocks, and fall back 
to the old one if we are above a certain function size and ratio.
With the threshold in turn depending on the optimization level.

But not sure if that's good design as we then end up with cases where 
performance suddenly gets 5% worse if
people add a constructor or code get's slightly larger for some reason.
>
> The only other potential worry is how tricky/understandable is your patch.  Hopefully it's not hard.
I hope so, the algorithm itself isn't that complicated to some of the 
stuff in GHC and I tried to document it well.
But it's also far from being trivial code.
>
> | 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?
Guess I will have to see how well the edge/block ratio correlates with 
compile time blowups. If we can use that to rule out the really bad 
cases then (1) should be fine.
If not I will have to come back to the question.

Cheers
Andreas
>
> 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