
#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