[GHC] #11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker
#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
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha 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 performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by hvr): * priority: normal => highest * related: => #11302 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha 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 performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): Another place "in the wild" where this appears to occur is `text-icu`. Attempting to compile `Data.Text.ICU.Regex.Internal` very quickly eats up all of my RAM. I tried waiting for about half an hour for it to finish before giving up (then again, I was using a laptop with "only" 4 GB of RAM). If pattern matching is the culprit, then [https://github.com/bos /text- icu/blob/bfe19b0b4214a586ebcaecc33d460e679a5133f6/Data/Text/ICU/Regex/Internal.hsc#L177 toURegexOpts] is the probable scene of the crime. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha 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 performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by rwbarton): In a way, the fact that memory usage explodes on such small inputs is encouraging: surely some mild effort on algorithms/data structures will have a massive effect here. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha 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 performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by gkaracha): Ahhhh, I see. This has been noticed before. Actually, I have added a note in `deSugar/Check.hs` about it: `Note [Literals in PmPat]`. My primary test case for this problem has been function `mkTextEncoding'` from `libraries/base/GHC/IO/Encoding.hs` until now but I guess your example stresses the same problem even more. The source of the problem lies in the way we translate literals: * In the paper, we treat them as guards: literal `l` gets translated to `x (True <- x == l)`. This allows the algorithm to work uniformly on everything but is too expensive, even for `mkTextEncoding'`. Essentially, the covered set contains `x |> {True ~ (x == l)}` and the uncovered contains `x |> {False ~ (x == l)}`. Hence, we explode first (everything is a guard) and then prune (use the term oracle to check the constraints) which is really exponential. * Hence, I changed the implementation and added literals in the pattern language. This means that for literal `l` the covered set contains `l |> {}` and the uncovered set contains `x |> {False ~ (x == l)}` like before. Since literals are patterns, more things can be checked eagerly, like with constructors where we can see immediately that e.g. `True` can not match `False`. Hence, we generate less from the start. The last thing to do (and I think this will address all performance issues concerning literals) is to completely add literals in the pattern language, that is, use a variant of Sestoft's negative patterns: {{{#!hs data PmPat :: PatTy -> * where PmCon :: { ... } -> PmPat t PmVar :: Id -> PmPat t PmLit :: PmLit -> PmPat t PmNLit :: Id -> [PmLit] -> PmPat VA -- add this constructor PmGrd :: { ... } -> PmPat PAT }}} The idea is that `PmNLit x lits` represents in a compact way __all literals `x` that are **not equal** to any of `lits`__. Hence, we generate much less and there is significantly less need for pruning. There is a slight possibility that this change will affect #322 and also I expect the size of the checker to increase 5-10% (LoC) but I have no better solution at the moment. Any ideas on this approach? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha 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 performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"fcc76493c8b35001fc1b22738cc64ff9506e278a/ghc" fcc76493/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="fcc76493c8b35001fc1b22738cc64ff9506e278a" Introduce negative patterns for literals (addresses #11303) Introduce negative patterns for literals. In addition to storing term constraints for literals (checked at the end by the term oracle), also check eagerly, using negative patterns. This means generation of smaller sets (covered, uncovered, and divergent), instead of generating big sets and pruning afterwards. Test Plan: validate Reviewers: austin, bgamari Reviewed By: bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1716 GHC Trac Issues: #11303 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha 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 performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"adcbc98f50cd6bb01dfcf4c98ad5fe414f7cc40c/ghc" adcbc98f/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="adcbc98f50cd6bb01dfcf4c98ad5fe414f7cc40c" Add regression test for #11303 Test Plan: Validate Reviewers: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1719 GHC Trac Issues: #11303 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: gkaracha Type: bug | Status: closed Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => closed * testcase: => T11303 * differential: => Phab:D1716, Phab:D1719 * resolution: => fixed Comment: The test case now compiles in less than a second. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Changes (by hvr): * owner: gkaracha => * status: closed => new * resolution: fixed => Comment: I just had matrix.h.h.o thrashing due to `text-icu` still requiring over 10GiB with yesterdays GHC 8.0 snapshot :-( I tried compiling `text-icu-0.7.0.1:Data.Text.ICU.Regex.Internal` on my workstation (with swap-space disabled) takes over 30GiB, until the OOM killer finally kicks in: {{{ [19687.231184] Out of memory: Kill process 18811 (ghc) score 929 or sacrifice child [19687.231186] Killed process 18811 (ghc) total-vm:1074146932kB, anon- rss:30410192kB, file-rss:0kB }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by gkaracha): Replying to [comment:8 hvr]:
I tried compiling `text-icu-0.7.0.1:Data.Text.ICU.Regex.Internal` on my workstation (with swap-space disabled) takes over 30GiB, until the OOM killer finally kicks in:
{{{ [19687.231184] Out of memory: Kill process 18811 (ghc) score 929 or sacrifice child [19687.231186] Killed process 18811 (ghc) total-vm:1074146932kB, anon- rss:30410192kB, file-rss:0kB }}}
Hmmmm, how come you consider this an instance of #11303 and not #11276? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by hvr): Replying to [comment:9 gkaracha]:
Hmmmm, how come you consider this an instance of #11303 and not #11276?
Mostly guessed so, because #11276 talks about exponential time, rather than exponential memory usage :-) Do you need me to provide you a smaller testcase? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by mpickering): I suspect #11276 is also a memory issue. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by RyanGlScott): Another reason it's probably #11276 instead is because the same workaround can be applied to `text-icu`: {{{#!diff index 38765d4..c31f4b6 100644 --- a/Data/Text/ICU/Regex/Internal.hsc +++ b/Data/Text/ICU/Regex/Internal.hsc @@ -174,6 +174,7 @@ toURegexpOpts = foldl go (0,-1,-1) where go (!flag,work,stack) opt = (flag+flag',work',stack') where + flag' :: URegexpFlag flag' = case opt of CaseInsensitive -> #const UREGEX_CASE_INSENSITIVE Comments -> #const UREGEX_COMMENTS }}} Adding a type signature makes the rest of `text-icu` compile. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by gkaracha): Replying to [comment:10 hvr]:
Mostly guessed so, because #11276 talks about exponential time, rather than exponential memory usage :-)
I see. Personally, I think that all the recent bug reports concerning the checker were not strictly speaking bugs, rather improvements needed to check realistic code. Yet, #11276 and the behaviour on `text-icu-0.7.0.1` seems like an actual bug and I feel they have the same source.
Do you need me to provide you a smaller testcase?
Yes, if it is not too much trouble! Even with Matthew's useful comments I still haven't found the source of #11276, maybe one more test case can shed some more light on this. :-) Thanks! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by gkaracha): Replying to [comment:12 RyanGlScott]:
Another reason it's probably #11276 instead is because the same workaround can be applied to `text-icu`: {...} Adding a type signature makes the rest of `text-icu` compile.
Ah, great! So `flag'` is the source of the problem. Then yes, they are definitely connected, probably something goes wrong with the types I assign to the initial uncovered set (I get it from the signature/inferred type). Thanks! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:14> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by gkaracha): Herbert, could you check again whether `text-icu` can be built with the current HEAD? My patch for #11276 has been merged so I expect `text-icu` to be built normally. If so, please also revert #11303 to closed. Thanks for the help! :-) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:15> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by RyanGlScott): Hm, for some reason, this program still seems to be blowing up GHC even with the latest changes: {{{#!hs {-# LANGUAGE TypeFamilies #-} module Slow where data family Letter a data instance Letter a = A | B | C | D | E | F | G | H | I | J f :: [Letter a] -> Int f = foldl go 0 where go n letter = n + n' where n' = case letter of A -> 0 B -> 1 C -> 2 D -> 3 E -> 4 F -> 5 G -> 6 H -> 7 I -> 8 J -> 9 }}} This time, adding explicit type signatures to `go` and/or `n'` does ''not'' make it work. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:16> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: 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 performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by gkaracha): Oh, yes, this is rather expected. I added a note in `deSugar/Check.hs` about the general case: `Note [Translate CoPats]`. As the note says, a `CoPat` is translated as follows: {{{ pat |> co ===> x (pat <- (x |> co)) }}} In the latest commit [changeset:"0acdcf2482d24903b504e6b34fa745ef855ff00d/ghc" 0acdcf24/ghc], I added two cases when translating `CoPat`s: * If `co` is refl we can drop it and do not generate the guard * If `co` is just a hole, we can also drop it. So, as the commit message says, we now generate **less** guards. For data families, this coercion is essential, because changes the representation tycon to the source tycon and I cannot drop it, that is, without changing the type of the pattern. The previous examples had `CoPat`s due to inference but your example above uses data families directly so the workaround does not apply. I can only hope that I will be able to come up with a better translation for `CoPat`s before the release but I do not know how to address this yet. Btw, I think we should move this whole discussion to #11276 since #11303 is rather irrelevant. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:17> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: closed Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Changes (by hvr): * status: new => closed * resolution: => fixed Comment: Replying to [comment:15 gkaracha]:
Herbert, could you check again whether `text-icu` can be built with the current HEAD? My patch for #11276 has been merged so I expect `text-icu` to be built normally. If so, please also revert #11303 to closed. Thanks for the help! :-)
I can confirm that `text-icu` now compiles with a more reasonable memory usage... :-) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:18> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: closed Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11276, #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Changes (by bgamari): * related: #11302 => #11276, #11302 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:19> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: | PatternMatchWarnings Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11276, #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => PatternMatchWarnings * status: closed => new * resolution: fixed => * milestone: 8.0.1 => 8.2.1 Comment: Re-opening because I think we can do better for 8.2. But ok for 8.0. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:20> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: | PatternMatchWarnings Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: T11303 Blocked By: | Blocking: Related Tickets: #11276, #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719 -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"28f951edfe50ea5182065144340061ec326781f5/ghc" 28f951e/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="28f951edfe50ea5182065144340061ec326781f5" Overhaul the Overhauled Pattern Match Checker Overhaul the Overhauled Pattern Match Checker * Changed the representation of Value Set Abstractions. Instead of using a prefix tree, we now use a list of Value Vector Abstractions. The set of constraints Delta for every Value Vector Abstraction is the oracle state so that we solve everything only once. * Instead of doing everything lazily, we prune at once (and in general everything is much stricter). Hence, an example written with pattern guards is checked in almost the same time as the equivalent with pattern matching. * Do not store the covered and the divergent sets at all. Since what we only need is a yes/no (does this clause cover anything? Does it force any thunk?) We just keep a boolean for each. * Removed flags `-Wtoo-many-guards` and `-ffull-guard-reasoning`. Replaced with `fmax-pmcheck-iterations=n`. Still debatable what should the default `n` be. * When a guard is for sure not going to contribute anything, we treat it as such: The oracle is not called and cases `CGuard`, `UGuard` and `DGuard` from the paper are not happening at all (the generation of a fresh variable, the unfolding of the pattern list etc.). his combined with the above seems to be enough to drop the memory increase for test T783 down to 18.7%. * Do not export function `dsPmWarn` (it is now called directly from within `checkSingle` and `checkMatches`). * Make `PmExprVar` hold a `Name` instead of an `Id`. The term oracle does not handle type information so using `Id` was a waste of time/space. * Added testcases T11195, T11303b (data families) and T11374 The patch addresses at least the following: Trac #11195, #11276, #11303, #11374, #11162 Test Plan: validate Reviewers: goldfire, bgamari, hvr, austin Subscribers: simonpj, thomie Differential Revision: https://phabricator.haskell.org/D1795 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:21> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.11 Resolution: fixed | Keywords: | PatternMatchWarnings Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: T11303, performance bug | T11303b Blocked By: | Blocking: Related Tickets: #11276, #11302 | Differential Rev(s): Phab:D1716, Wiki Page: | Phab:D1719, Phab:1795 -------------------------------------+------------------------------------- Changes (by gkaracha): * status: new => closed * testcase: T11303 => T11303, T11303b * differential: Phab:D1716, Phab:D1719 => Phab:D1716, Phab:D1719, Phab:1795 * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:22> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC