#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: | -------------------------------------+------------------------------------- Changes (by bgamari): * cc: gkaracha (added) * failure: None/Unknown => Compile-time crash * owner: => goldfire * milestone: => 8.0.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 bgamari): {{{ $ inplace/bin/ghc-stage2 Test.hs -package ghc -O +RTS -s [1 of 1] Compiling Test ( Test.hs, Test.o ) 22,902,711,336 bytes allocated in the heap 33,446,941,712 bytes copied during GC 2,960,993,984 bytes maximum residency (21 sample(s)) 15,073,104 bytes maximum slop 7835 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 530 colls, 0 par 16.236s 61.556s 0.1161s 29.5767s Gen 1 21 colls, 0 par 8.853s 69.183s 3.2944s 61.3812s TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1) SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) INIT time 0.001s ( 0.001s elapsed) MUT time 6.645s ( 60.820s elapsed) GC time 25.089s (130.739s elapsed) EXIT time 0.251s ( 1.432s elapsed) Total time 31.996s (192.991s elapsed) Alloc rate 3,446,736,733 bytes per MUT second Productivity 21.6% of total user, 3.6% of total elapsed gc_alloc_block_sync: 0 whitehole_spin: 0 gen[0].sync: 0 gen[1].sync: 0 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

#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 Ben Gamari ): In [changeset:"bec5350da09fde51231004b1b7d33641ac51800e/ghc" bec5350d/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="bec5350da09fde51231004b1b7d33641ac51800e" Adding flags: -ffull-guard-reasoning and too-many-guards Introduction of two new flags, for more precise control over the new pattern match checker's behaviour when reasoning about guards. This is supposed to address #11195 (and maybe more performance bugs related to the NP-Hardness of coverage checking). Expected behaviour: * When `-ffull-guard-reasoning` is on, run the new pattern match checker in its full power * When `-ffull-guard-reasoning` is off (the default), for every match, check a metric to see whether pattern match checking for it has high probability of being non performant (at the the moment we check whether the number of guards is over 20 but I would like to use a more precise measure in the future). If the probability is high: - Oversimplify the guards (less expressive but more performant) and run the checker, and - Issue a warning about the simplification that happened. A new flag `-Wtoo-many-guards/-Wno-too-many-guards` suppresses the warning about the simplification (useful when combined with -Werror). Test Plan: validate Reviewers: goldfire, austin, hvr, bgamari Reviewed By: bgamari Subscribers: mpickering, thomie Differential Revision: https://phabricator.haskell.org/D1676 GHC Trac Issues: #11195 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11195: New pattern-match check can be non-performant -------------------------------------+------------------------------------- Reporter: goldfire | 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 crash | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1676 Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => PatternMatchWarnings * status: closed => new * resolution: fixed => * owner: goldfire => * milestone: 8.0.1 => 8.2.1 Comment: Re-opening for 8.2. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11195: New pattern-match check can be non-performant -------------------------------------+------------------------------------- Reporter: goldfire | 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 crash | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1676 Wiki Page: | -------------------------------------+------------------------------------- Comment (by gkaracha): I think that commit 28f951edfe50ea5182065144340061ec326781f5 addresses this completely: {{{ Author: George Karachalias Date: Wed Feb 3 19:06:45 2016 +0100 Overhaul the Overhauled Pattern Match Checker }}} Hence, I am closing this. Feel free to reopen in case performance issues arise again due to pattern match checking. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11195: New pattern-match check can be non-performant -------------------------------------+------------------------------------- Reporter: goldfire | 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 crash | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1676, Wiki Page: | Phab:D1795 -------------------------------------+------------------------------------- Changes (by simonpj): * status: closed => new * resolution: fixed => Comment: I'm re-opening this because compilation still takes a ridiculously long time (minutes) and memory (6.7G allocated). Almost all of this is in the pattern-match checking. It can't be right! Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11195: New pattern-match check can be non-performant -------------------------------------+------------------------------------- Reporter: goldfire | 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 crash | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1676, Wiki Page: | Phab:D1795 -------------------------------------+------------------------------------- Comment (by simonpj): Replying to [comment:13 bgamari]:

simonpj, are you referring to the compilation of `OptCoercion` again?

I think so. It was careless of me not to be more specific. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11195: New pattern-match check can be non-performant -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: | PatternMatchWarnings Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple crash | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1676, Wiki Page: | Phab:D1795 -------------------------------------+------------------------------------- Comment (by rwbarton): It's very strange. I also see `OptCoercion` taking several minutes and gobs of memory to compile, when I copy it somewhere and build it with `-package ghc`; but according to my logs from investigating join points it never takes particularly long to compile as part of the ghc build. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11195: New pattern-match check can be non-performant -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: | PatternMatchWarnings Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple crash | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1676, Wiki Page: | Phab:D1795 -------------------------------------+------------------------------------- Comment (by bgamari): I also noticed while looking at the early inline patch that `T11195`, which is derived from `OptCoercion`, also seems to take quite a long time (and consequently occasionally fails). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11195#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler