#1969: enormous compile times
---------------------------------+------------------------------------------
Reporter: duncan | Owner: igloo
Type: merge | 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 |
---------------------------------+------------------------------------------
Changes (by simonpj):
* owner: simonpj => igloo
* type: compile-time performance bug => merge
Comment:
OK the patch is this
{{{
Mon Mar 23 10:38:26 GMT 2009 [email protected]
* Avoid quadratic complexity in occurrence analysis (fix Trac #1969)
The occurrence analyser could go out to lunch in bad cases, because
of its clever loop-breaking algorithm. This patch makes it bale out
in bad cases. Somewhat ad-hoc: a nicer solution would be welcome.
See Note [Complexity of loop breaking] for the details.
M ./compiler/simplCore/OccurAnal.lhs -22 +71
}}}
The fix is still not perfect, because it simply bales out in the tricky
case. My feeling is that there is probably a good algorithm somewhere for
"find the minimal set of nodes whose removal will make the graph acyclic",
but I don't know of it. Furthermore, the problem is made tricker by the
presence of RULES etc; see extensive comments in `OccurAnal`.
Anyway, baling out certainly fixes the bad complexity.
I think this could merge into 6.10.
Ian: what about a test-suite example? Maybe just a big enough instance to
trip the timeout?
Simon
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1969#comment:14>
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
