#11822: Pattern match checker exceeded (2000000) iterations -------------------------------------+------------------------------------- Reporter: j.waldmann | Owner: gkaracha Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1-rc3 Resolution: | Keywords: | PatternMatchWarnings Operating System: Unknown/Multiple | Architecture: x86_64 Type of failure: Compile-time | (amd64) performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by gkaracha): Replying to [comment:15 niteria]:
Is it quadratic even for the simplest case?
Yes, indeed it is, but I don't think that this is the problem here (the previous algorithm is quadratic in this case too, yet lazily). From all the problems we have seen I think that the number of iterations is not a good metric to use to kill the checker: checking a guard counts as a single iteration, yet it calls the (rather expensive) term oracle `solveOneEq`. Similarly, matching against a GADT constructor calls the type oracle `tyOracle`. All in all, not all iterations cost the same. I will build the HEAD one of these days and start looking into it myself but can you check for me how much time is needed to compile your example for 4000 (+1) constructors (increase the -fmax-pmcheck-iterations sufficently so that the checker can run)? I have the impression that it will not take forever, it's just that the number of iterations is a bad metric and makes the checker give up even in cases where there is no need to. Could you check that for me? Replying to [comment:16 simonpj]:
It would be great if someone had time to really look at this. I think gkaracha has probably now moved on; is that true George?
It's not just a question of making a one-line fix; you'd have to dig into the algorithm.
Hi Simon, I will happily look into this. I have been busy researching other stuff but the performance of the checker is still a challenge I wish to address (and the recent comments in bug reports like this one show that it is of great importance for GHC users). Starting next week I will start spending time on it to see what can be done. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler