February 2016 - ghc-tickets

[GHC] #11528: Representation of value set abstractions as trees causes performance issues
by GHC 02 Feb '16

02 Feb '16

#11528: Representation of value set abstractions as trees causes performance issues -------------------------------------+------------------------------------- Reporter: gkaracha | Owner: gkaracha Type: task | Status: new Priority: lowest | Milestone: Research needed Component: Compiler | Version: Keywords: | Operating System: Unknown/Multiple PatternMatchWarnings | Architecture: | Type of failure: Compile-time Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- The new exhaustiveness checker has been originally designed to use a prefix tree representation of value set abstractions. Unfortunately, this resulted in huge performance problems (see for example #11160, #11161, #11162, #11163, #11195, #11276, #11303, #11374, #11302) and we had to switch to a representation of value set abstractions as a list of value vector abstractions. It would be nice to switch back to the prefix tree representation but the performance problems with it are yet to be characterized so I have created a branch using this representation (`wip/gadtpm-prefix-tree`) to further investigate this approach. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11528> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

[GHC] #11100: Remote GHCi
by GHC 02 Feb '16

02 Feb '16

#11100: Remote GHCi -------------------------------------+------------------------------------- Reporter: simonmar | Owner: simonmar Type: task | Status: new Priority: normal | Milestone: 8.0.1 Component: GHCi | Version: 7.10.2 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- This task is to implement Remote GHCi, i.e. running interpreted code in a separate process. For more details see [wiki:RemoteGHCi]. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11100> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 21

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by goldfire): Replying to [comment:11 niteria]: > It's always been 100: [0b7e538a09bc958474ec704063eaa08836e9270e]. > No. Before that commit, `checkRecTc` allowed one unwrapping. The second failed (because the `TyCon` was in the `NameSet` nearby. But there's also a reference to the ticket that inspired the increase, which is helpful. I guess, in the end, we're never going to get this number correct. We could just have a flag for it, as suggested in the code there. Then, for this test, we use the flag. In the end, we're talking about a slowdown that affect only `DEBUG` compilers, yes? So I'm more worried about getting the test to pass before the end of the universe than in actually removing the exponential behavior -- especially given that the user's program indeed introduces the exponential behavior. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by niteria): It's always been 100: [0b7e538a09bc958474ec704063eaa08836e9270e]. > why doesn't checkRecTc cut off the unwrapping? It *does* (or would if we run it long enough), but 100 is way too big in case of a type that's growing exponentially. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by goldfire): And why is it checking for unwrapping 100 times? I thought `checkRecTc` stopped at 2, not 100. Was there a reason to increase it? Maybe we've gone too far. Nice analysis, by the way. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by simonpj): But the question is: why doesn't `checkRecTc` cut off the unwrapping? That's what you seemed to say in comment:6 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

[GHC] #11480: UndecidableSuperClasses causes the compiler to spin with UndecidableInstances
by GHC 01 Feb '16

01 Feb '16

#11480: UndecidableSuperClasses causes the compiler to spin with UndecidableInstances -------------------------------------+------------------------------------- Reporter: ekmett | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (Type checker) | Keywords: PolyKinds, | Operating System: Unknown/Multiple UndecidableSuperClasses | Architecture: | Type of failure: GHC rejects Unknown/Multiple | valid program Test Case: | Blocked By: Blocking: | Related Tickets: #10318 Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Looks like I spoke too soon when I said all my examples worked in #10318 -- it doesn't seem to work when the superclass cycle gets sufficiently interesting, possibly caused by the use of `PolyKinds` in the style mentioned in #9201. I took my `hask` code, and removed the shimming hacks above, and the following stripped down example sends the compiler into an infinite loop, which I believe should be able to work: {{{#!hs {-# language KindSignatures, PolyKinds, TypeFamilies, NoImplicitPrelude, FlexibleContexts, MultiParamTypeClasses, GADTs, ConstraintKinds, FlexibleInstances, FunctionalDependencies, UndecidableSuperClasses #-} import GHC.Types (Constraint) import qualified Prelude data Nat (c :: i -> i -> *) (d :: j -> j -> *) (f :: i -> j) (g :: i -> j) class Functor p (Nat p (->)) p => Category (p :: i -> i -> *) class (Category dom, Category cod) => Functor (dom :: i -> i -> *) (cod :: j -> j -> *) (f :: i -> j) | f -> dom cod instance (Category c, Category d) => Category (Nat c d) instance (Category c, Category d) => Functor (Nat c d) (Nat (Nat c d) (->)) (Nat c d) instance (Category c, Category d) => Functor (Nat c d) (->) (Nat c d f) instance Category (->) instance Functor (->) (->) ((->) e) instance Functor (->) (Nat (->) (->)) (->) }}} Sorry for the largish example, but I don't know how to strip it down smaller than the 6 instances that remain. One potentially telling observation is that without the instances it compiles, and produces what I expect, so the `UndecidableSuperClasses` part seems to be letting the classes compile, but there seems to be a bad interaction with the way the instances work. Also, in this stripped down form, I can remove the use of `UndecidableInstances` and that avoids the spinning problem, but once I flesh it out further I need `UndecidableInstances` in the "real" version of the problem. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11480> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 14

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by niteria): If you unwrap it 100 times you end up with a type that has size `2^100`. Computing free vars of such type would take forever. And the ASSERT in `substTy` does exactly that. It's enough to unwrap it 30 times for it to become unbearably slow. That type is very regular and a very compact representation because of sharing. The type is essentially: {{{ a0 = () a1 = (a0, a0) -- note the sharing, but when free vars are -- computed they are computed for fst and snd independently a2 = (a1, a1) a3 = (a2, a2) a100 = (a99, a99) -- this has size 2^100, O(2^n) when naively explored, -- but it's represented as a sequence of O(n) pointers. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by simonpj): OK, but even with the new ASSERT, `checkRecTc` will cut off the recursion and so will not unwrap the newtype 100 times. So where is the big type coming from? I'm still missing that. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

Re: [GHC] #11518: Test TcCoercibleFail hangs with substitution sanity checks enabled
by GHC 01 Feb '16

01 Feb '16

#11518: Test TcCoercibleFail hangs with substitution sanity checks enabled -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Comment (by niteria): > But what's odd is that it doesn't bomb out on us when the ASSERT is not there. That seems odd to me -- if the types get very large I'd expect the type checker to fail even in the absence of the ASSERT. I think I can explain this. The [https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/types/… unwrapNewTypeStepper] is protected by a [https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/types/… checkRecTc] which will cause an abort if the same newtype constructor is unwrapped 100 times. The difference I believe is due to laziness and sharing, it's easy to create an exponentially big type by repeated substitution into `(a, a)` and unless `a` is (deeply) forced at some point you can do it in sub-exponential time. So when `substTy` began to force it by computing the free variables for the sanity check the problem became visible. In other words the recursion check in `checkRecTc` didn't need to force the type to decide it was a loop, so it wasn't bothered by it growing exponentially (made possible by sharing and laziness) before. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11518#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0