#2092: Quadratic amount of code generated
-----------------------------------------+----------------------------------
Reporter: igloo | Owner:
Type: run-time performance bug | Status: closed
Priority: normal | Milestone: 6.10 branch
Component: Compiler | Version: 6.9
Severity: normal | Resolution: fixed
Keywords: | Difficulty: Unknown
Testcase: | Os: Unknown/Multiple
Architecture: Unknown/Multiple |
-----------------------------------------+----------------------------------
Comment (by simonpj):
Although this bug is closed, I'm not convinced we're done. Some time ago
I stopped the simplifier creating quite so many join points. The patch
that closed this bug narrowed the cases for which my heuristic applied.
And with good reason. But I think that if we had bad cases before adding
the "don't create a joint point" heuristic, we'll get bad cases with
Simon's change too.
Looking at the comments, though, I can't see a compelling case for ''not''
always doing the case-of-case and creating a join point. I think it arose
in a program that Roman cared about, so I asked him. He replies:
{{{
This is what I can find in my archives:
> I think this is what happens. We start out with (essentially)
>
> primes n = f (g h (abs n)))
>
> where h is a function (which is passed as an argument to g) and f, g and
> h are all inlined at some point.
>
> We end up with
>
> primes n = let j = \h m -> <inlined f> (<inlined g> h m)
> in
> case n >= 0 of
> True -> j <inlined h> n
> False -> j <inlined h> (-n)
>
> This is bad because we really want the code for f, g and h to be
> combined to produce an efficient loop. So what we want is probably
>
> primes n = let j = \m -> <inlined f> (<inlined g> <inlined h> m)
> in
> case n >= 0 of
> True -> j n
> False -> j (-n)
and:
> PROBLEM.
> Suppose we have
>
> f (abs x `div` y)
>
> and a RULE
>
> f (a `div` b) = ...
>
> Then you'd expect the RULE to fire.
> But if we inline abs, then, because div is strict, we'll get>
> f (case x>0 of
> T -> x `div` y
> F -> negate x `div y)
>
> (or, worse, a join point might created if the code was bigger).
> Anyway, the f/div RULE can't fire any more.
>
> Roman also thinks there may be a problem even in the absence
> of RULES, but we're not sure it's real. See message attached.
> ***Roman will try to find an example***
>
> POSSIBLE SOLUTION.
>
> a) Never push strict functions inside case
>
> f (case .. of alts)
> stays just like that.
> b) Only push strict functions inside a case with one alternative
> f (case … of p -> e) è case … of p -> f e
>
> (b) seems less draconian, but if f is lazy and g is strict then
> f (g (case…)) è f (case .. of p-> g..)
> and now an f/g rule won’t fire.
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2092#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
