#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: | Architecture: Unknown
Os: Unknown |
--------------------------------------+-------------------------------------
Changes (by simonmar):
* status: new => closed
* resolution: => fixed
Comment:
I looked into this, it's not as straightforward as it seems. In the
second example given above, the amount of code generated is not in fact
quadratic: try adding another constructor. GHC is making sensible choices
about when to inline and duplicate code; in this case in fact the code it
generates is about as good as you can get.
However, in the first example, we got this:
{{{
M1.== =
\ (x_a5J :: M1.U) (y_a5L :: M1.U) ->
case case y_a5L of tpl_B2 {
M1.Mk1 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4;
M1.Mk2 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4
}
of wild_B1 { __DEFAULT ->
case case x_a5J of tpl_B2 {
M1.Mk1 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4;
M1.Mk2 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4
}
of wild1_Xk { __DEFAULT ->
GHC.Prim.==# wild1_Xk wild_B1
}
}
}}}
which is in fact quite bad. There's an unnecessary case-of-case, where
the outer case is doing nothing at all except serving as a join point.
This leads to an extra call/return in the generated code compared to the
second example where the case-of-case has been expanded out. Even if we
were to express the join point as a let(-no-escape), that would be better
than the case-of-case.
The problem was that GHC has some heuristics to avoid expanding case-of-
case in some cases (see `Note single-alternative` in
`compiler/simplCore/Simplify.lhs`), and it was also catching this example.
I've now fixed it:
{{{
Tue Jun 17 05:35:10 PDT 2008 Simon Marlow <[EMAIL PROTECTED]>
* Fix an example where we weren't doing case-of-case when we should
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2092#comment:1>
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
