[GHC] #11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker

[GHC]

#11303: Pattern matching against sets of strings sharing a prefix blows up pattern
checker
-------------------------------------+-------------------------------------
           Reporter:  bgamari        |             Owner:  gkaracha
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:  8.0.1
          Component:  Compiler       |           Version:  7.11
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  Compile-time
  Unknown/Multiple                   |  performance bug
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 hvr stumbled upon this issue while attempting to bootstrap GHC with GHC
 HEAD. In so doing he found that GHC HEAD required more than 10 GB of
 memory while compiling `genprimopcode` (and never completed).

 It appears that this blow-up is due to the new pattern checker. In
 particular it appears that the pattern checker is affected quite adversely
 by sets of patterns sharing a prefix. For instance, this example,
 {{{#!hs
 import System.Environment

 main :: IO ()
 main = do
   args <- getArgs
   print $ case head args of
                       "--primop-primop-info"  -> "turtle"
                       "--primop-tag" -> "asdf"
                       "--primop-list"  -> "casdhf"
                       "--primop-vector-uniques"  -> "this"
                       "--primop-vector-tys"  -> "is"
                       "--primop-vector-tys-exports"  -> "silly"
                       "--primop-vector-tycons"  -> "hmmm"
                       "--make-haskell-wrappers" -> "123512"
                       "--make-haskell-source"  -> "as;dg"
                       "--make-latex-doc" -> "adghiw"
                       _ -> error "Should not happen, known_args out of
 sync?"
 }}}

 As written GHC requires over ten gigabytes of heap and several minutes to
 compile the example. If one perform `s/--primop-//` to this example it
 takes 500ms to compile. Alternatively, if on replace the first `-` in each
 of the `--primop` strings with a unique character (thus breaking the
 shared prefixes) compilation time is a bit shy of a second.

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