#1969: enormous compile times
---------------------------------------------+------------------------------
Reporter: duncan | Owner: igloo
Type: compile-time performance bug | Status: new
Priority: normal | Milestone: 6.10.2
Component: Compiler | Version: 6.8.1
Severity: normal | Resolution:
Keywords: performance | Difficulty: Difficult (1 week)
Testcase: | Os: Unknown/Multiple
Architecture: Unknown/Multiple |
---------------------------------------------+------------------------------
Comment (by simonpj):
Ian diagnosed the problem. Basically we're compiling lots of things like:
{{{
data A24 = A24
instance C A24 where
c A24 = "A24"
}}}
where
{{{
class C a where
c :: a -> String
d :: a -> String
d x = c x
e :: a -> String
e x = c x
}}}
In the ticket 1000 instances are generated, but when I tried that the
compiler was using 1.5G of RAM before I killed it. 100 instances is
plenty to show a problem:
{{{
...
doPassM SimplCore 36599 6 0.0
0.0
simplifyPgmIO SimplCore 36605 12 0.0
0.0
OccAnal SimplCore 37381 10 0.0
0.0
occurAnalysePgm OccurAnal 37399 10 0.0
0.0
occAnalBind OccurAnal 37400 3018 0.0
0.0
occAnalRec OccurAnal 37680 2717 0.0
0.0
reOrderRec OccurAnal 43292 502 0.0
0.0
reOrderCycle OccurAnal 43310 200 1.0
0.3
stronglyConnCompFromEdgedVerticesR Digraph 43342 200 0.0
0.0
graphFromEdgedVertices Digraph 43343 200 32.3
42.0
}}}
It looks to me like the problem is:
There's a binder
{{{
(J.$dmd,
\ (@ a_aue) ($dC_azi :: J.C a_aue) (x_auh :: a_aue) ->
J.c @ a_aue $dC_azi x_auh)
}}}
in the (Rec pairs) being passed to `occAnalBind`, which, via its
`idRuleVars`, ties everything in a big knot. I assume that what's going on
here is that this is the "normal" c, and there are specialisation rules
for uses of c at the various A* types? And to make things worse, I guess
`J.$dmd` is not allowed to be a loop breaker, as then the interaction of
rules and inlining could lead to an infinite loop?
So with 100 class instances, we end up with a 500 node SCC being given
to `reOrderRec`/`reOrderCycle`. This finds a loop breaker, which
presumably
removes at most one instance's worth of definitions from the SCC. Then
it calls `stronglyConnCompFromEdgedVerticesR` to recompute the scc, and we
go round again. `reOrderCycle` gets called 200 times, building a new SCC
each time round, with size decreasing roughly linearly from 500 down to
3.
I'm not sure why the space usage is so high; I haven't really looked at
that. I guess we're probably holding on to the old SCCs or something for
some reason. Biographical profiling says that the space is all VOID, but
I'm not convinced that's trustworthy.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1969#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
