[GHC] #11822: Pattern match checker exceeded (2000000) iterations

[GHC]

#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