#11822: Pattern match checker exceeded (2000000) iterations -------------------------------------+------------------------------------- Reporter: j.waldmann | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1-rc3 Resolution: | Keywords: 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 carter): That's a pretty large data type! Does seem like an example where checking the coverage should work fine as is.... Especially since this isn't a gadt and doesn't have pattern guards right? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11822: Pattern match checker exceeded (2000000) iterations -------------------------------------+------------------------------------- Reporter: j.waldmann | Owner: 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 NeilMitchell): I've ran into this two times, both regressions since GHC rc3. The two cases are: * https://github.com/ndmitchell/hlint/blob/master/src/HSE/Bracket.hs needBracket (currently at a438ba0e45697e65bbcd9fb996d350b07394a45f) * https://github.com/ndmitchell/derive/blob/master/src/Language/Haskell/TH/Pee... peep (currently at 6a703a9f71986232bbb1e54853a548af2b53b706) Is there any recommendation on how I can avoid this warning without CPP in a way that works on older versions of GHC? In contrast to the original reporter, I do not welcome that GHC emits this warning. It seems a warning about GHC, not my code, and not something that I can do much about, other than turn off warnings, which seems a little sad. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 thomie): Replying to [comment:4 simonpj]:

why has it regressed since 8.0?

Herbert made the following change recently, in Phab:D2095: {{{#!diff - maxPmCheckIterations = 10000000, + maxPmCheckIterations = 2000000, }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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): Apologies for the late (and long) response. You can find below some explanation about the behavior of the checker, which I hope to clear things out a bit. == Why does this example exceed the limit == In principle, the match of `sameAttribute` gives rise to 161*161 = 25,921 cases. Also, the counter takes into account the arguments too and most constructors have at least one. Yet, the most important reason that the match iterates >2000000 times is that **all** unmatched cases from the first clause are checked with the second, and the resulting ones are checked with the third, etc. {{{#!hs data T = A | B | C f :: T -> () f A = () f B = () -- (*) f C = () }}} That being said, for `f` above, the second clause will be checked against missing cases `B` and `C`. This is a pretty small example, but in general this gives rise to (something like) a quadratic number of checks. That's why the iteration counter goes over the roof. == General Comments on Performance == About the general performance of the algorithm, there are some things worth mentioning: 1. In principle, the new checker is slower than the previous one on average. This makes sense because we check term and type constraints, that the previous checker didn't, so we have to pay something for that. Nevertheless, the main reason that it's slower on average is that the new checker checks uncovered matches eagerly, while the past checker did it lazily (whether the specific match has GADTs or not, the new checking function is in `TcM` also, to be able to call the type-checker). 2. Neither I or Simon were happy about the above, but (that's why we opened #11528 but it still needs a lot of work to figure out how to change) the constraint-based approach grew really fast, unless we performed constraint solving as soon as possible, to remove useless cases (as I said above, what is generated from one clause is passed to the next one so this was devastating). 3. The takeaway is that, in order to avoid extreme cases (like #11195 which is really difficult for the checker), we chose to have predictable behavior for all (with/without guards or GADTs) but a bit slower. The other result is that since the checker is now strict, it had to be bounded, to avoid memory-issues. I dislike the exceeded-iterations-warning too, but I know no better solution at the moment. My original limit was 10000000, which even worked on #11195 and gave no such warning. However, as Herbert said, memory consumption can be too high, if we let it. The best solution, the way I see it would be to collect statistics (like the examples from Neil or this whole bug report) and fine-tune it. Maybe 10000000 was too high but 2000000 seems to be too low. I do not have anything better to offer at the moment, but I am open to suggestions. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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): But if we do this silently, we may get no warning at all for non- exhaustive matches, even with `-Wall` on. Don't you think that this is much worse in terms of safety? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 carter): I guess one question I have here is whether we can improve the approximation here to have better bounds in the non gadt case? I do like having informative coverage warnings rather than silent anything or resource blowups on my lap top (though 8.0 does claim 1tb of virtual memory either way :)) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 NeilMitchell): Note that in getting to 2M iterations it took 35s (timings are from loading into ghci). That's a significant slowdown in overall compilation time. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 niteria): Is it quadratic even for the simplest case? I have `A.gen.sh`: {{{ N=$1 echo "module A where" echo echo "data X = X" for i in $(seq 1 $N); do echo " | X$i"; done echo echo "instance Enum X where" for i in $(seq 1 $N); do echo " toEnum $i = X$i"; done for i in $(seq 1 $N); do echo " fromEnum X$i = $i"; done }}} Trying to compile for a datatype with 4000 constructors gives me: {{{ $ ./A.gen.sh 4000 > A.hs && ./inplace/bin/ghc-stage2 -dno-debug-output A.hs [1 of 1] Compiling A ( A.hs, A.o ) A.hs:8006:3: warning: Pattern match checker exceeded (2000000) iterations in an equation for ‘fromEnum’. (Use -fmax-pmcheck-iterations=n to set the maximun number of iterations to n) }}} This is not a made up example, we actually have enumeration types with 10k constructors. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

A.hs && (time ~/local/third-

#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 niteria): Ok, it doesn't look like the asymptotics changed between `7.10.3` and `8.0`. Numbers from `7.10.3`: {{{ $ for i in 1 10 100 1000 2000 4000 10000 20000; do echo $i; ./A.gen.sh $i party2/ghc/7.10.3/gcc-4.9-glibc-2.20-fb/e0e26d4/bin/ghc -dno-debug-output A.hs) 2>&1 | grep real; done 1 real 0m0.126s 10 real 0m0.161s 100 real 0m0.207s 1000 real 0m1.428s 2000 real 0m3.875s 4000 real 0m11.783s 10000 real 1m13.631s }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 simonpj):

Starting next week I will start spending time on it to see what can be done.

George, how's it going? I've just noticed that in the compiler itself `PrelRules.hs` doesn't currently blow the limit, but the changes in [Phab:D2858] require `-fmax- pmcheck-iterations=6000000`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11822#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler