[GHC] #11195: New pattern-match check can be non-performant

[GHC]

#11195: New pattern-match check can be non-performant
-------------------------------------+-------------------------------------
        Reporter:  goldfire          |                Owner:  goldfire
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.0.1
       Component:  Compiler          |              Version:  7.11
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  crash                              |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by gkaracha):

 Replying to [comment:1 bgamari]:
 > Looking at the code I'd suspect the problem is either `opt_trans_rule`
 or `opt_co4` as these both have a substantial number of patterns each with
 many guards. I'll try distilling a testcase from one of these.

 Yes, I think so too. For example, concerning this part:

 {{{#!hs
 -- Push transitivity inside forall
 opt_trans_rule is co1 co2
   | ForAllCo tv1 eta1 r1 <- co1
   , Just (tv2,eta2,r2) <- etaForAllCo_maybe co2 = undefined

   | ForAllCo tv2 eta2 r2 <- co2
   , Just (tv1,eta1,r1) <- etaForAllCo_maybe co1 = undefined
 }}}
 Considering only the guards `ForAllCo tv1 eta1 r1 <- co1` and `ForAllCo
 tv2 eta2 r2 <- co2`
 will generate as missing cases the following:
 {{{
 TcRefl         _ _ ~ co1
 TcTyConAppCo _ _ _ ~ co1
 TcAppCo        _ _ ~ co1
 TcCoVarCo        _ ~ co1
          ...
 TcCoercion       _ ~ co1

 ForAllCo tv1 eta1 r1 ~ co1, TcRefl         _ _ ~ co2
 ForAllCo tv1 eta1 r1 ~ co1, TcTyConAppCo _ _ _ ~ co2
 ForAllCo tv1 eta1 r1 ~ co1, TcAppCo        _ _ ~ co2
 ForAllCo tv1 eta1 r1 ~ co1, TcCoVarCo        _ ~ co2
                          ...
 ForAllCo tv1 eta1 r1 ~ co1, TcCoercion       _ ~ co2
 }}}
 This will be passed to the next clause and each one will be checked
 individually so the numbers
 will be multiplied and the sets will **really** grow exponentially. Guards
 are expensive by
 definition so I cannot think of a nice way out of this. Some options I can
 think of though are:
   1. Restructure the code to use less guards (or use them differently)
   2. See if I can make the check to eagerly solve some constraints to
 decrease the size of the
      sets it generates (I am not sure if it will be enough though, since,
 the above sets are all
      consistent for example so pruning eagerly wouldn't decrease the size
 of the above uncovered
      set)
   3. Oversimplify the check to drop all the guards

 I hate to admit it but after all these performance failures (#11160,
 #11161, ... and now this), I
 am really tempted to drop the guards. The new checker will still be
 accurate when it comes to GADTs
 but will have almost the same performance as the old checker, by not
 reasoning about guards at all,
 like it used to do. I am not sure about the price we are willing to pay
 for the additional
 reasoning (I feel that we are paying a lot) so I would like some input on
 this. What do you think?

 In any case I will investigate it more and see if this really has anything
 to do with the type=kind
 change or if it is inherent to the check. I assume the latter but if I am
 mistaken I am sure we can
 sort it out with Richard.

 George

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11195#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler