Haskell › Haskell - Glasgow-haskell-bugs

[GHC] #5970: Type checker hangs

Classic

List

Threaded

14 messages Options

GHC

[GHC] #5970: Type checker hangs

#5970: Type checker hangs
------------------------------------------+---------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: new
Priority: normal | Component: Compiler (Type checker)
Version: 7.4.1 | Keywords:
Os: Linux | Architecture: x86
Failure: Compile-time performance bug | Testcase:
Blockedby: | Blocking:
Related: |
------------------------------------------+---------------------------------
When compiling my synthesizer-llvm package, GHC-7.4.1 hangs in the type
checking phase for the module
http://code.haskell.org/synthesizer/llvm/src/Synthesizer/LLVM/Server/Packed/Instrument.hs

This module always needed more than a minute for type-checking in
GHC-7.2.2 and before. I guess this was because it is a module where
functions with a lot of type-level arithmetic from the type-level package
are applied to values of concrete types. Maybe with GHC-7.4.1 the
compilation time simply became even longer - at least several minutes.

I tried to simplify the example and reduce the dependencies. This is not
so simple because reducing the module size also decreases type checking
time and when drastically simplified the compilation time for that module
is ok. Now I am trying to construct an example where I repeat the same
(simple) function definition. I already observed that repeating a function
definition n times does not multiply the type checking by n but it needs
considerably more time. I think this can be considered a bug.

I am investigating further. If you have some advice, I like to know. Maybe
you remember a 'foldl' that should be a 'foldr' in the type checker, that
may cause a quadratic type checking time ... If so then this would be a
good opportunity to fix it. ;-)

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

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------
Changes (by simonpj):

* cc: dimitris@… (added)
* difficulty: => Unknown

Comment:

I already observed that repeating a function definition n times does not
multiply the type checking by n but it needs considerably more time. I
think this can be considered a bug.

Can you give a reproducible test case for that? Will also try to look at
your full example, but the cut-down versions are MUCH MUCH easier to deal
with. As it happens Dimitrios and I are back to looking at the
constraint solver at the moment, so the timing is good. In general, if
you can isolate any places where performance is unexpectedly non-linear,
we'd love to know. Thanks.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by Lemming):

So far I found out that adding type signatures to some functions that I
defined locally with 'let' reduces the type checking time considerably in
small tests, but I was not able to solve the original big problem this
way.

For reproducing my problem you may simply try to install synthesizer-
llvm-0.3 from Hackage, but it depends on a lot of other packages, e.g.
llvm. Nevertheless I try to reduce my problem to a handy test case.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by simonpj@…):

commit 516d3138473d7b097cc572901bd02fce9509f1b8
{{{
Author: Simon Peyton Jones <[hidden email]>
Date: Wed Mar 28 09:56:14 2012 +0100

Add a crucial forkM on the superclass context of IfaceClass in
tcIfaceDecl

The absence of this was causing a loop when typechecking an interface
where the superclass context mentioned an associated type
class C (T a) => D a where
data T a

Fixes Trac #5970

compiler/iface/BuildTyCl.lhs | 7 +++----
compiler/iface/LoadIface.lhs | 2 +-
compiler/iface/TcIface.lhs | 36
+++++++++++++++++++++++++-----------
compiler/typecheck/FamInst.lhs | 3 +++
4 files changed, 32 insertions(+), 16 deletions(-)
}}}

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: infoneeded
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by Lemming):

When trying to reduce the module to a small testcase I hit bug #5978. I
had a small hope that the type checking time issue would go away magically
when fixing #5978. Even if #5970 and #5978 are not related, hunting a
compiler bug in the presence of another one is a bit more complicated. The
testcase for this ticket is especially hard to simplify, since
simplification means reduction of type checking time and I can hardly
judge what type checking time is reasonable and what is too slow.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:7>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: infoneeded
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by simonpj):

But #5978 is a delicate point concerning exactly how a type error is
reported. It's irrelevant for a type-correct program. Nor is it a
performance question. I don't see how the two are connected.

We have fixed a lot of performance problems in the type checker recently,
so it would certainly be worth checking that HEAD still has the bad
behaviour you experienced.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: infoneeded
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by Lemming):

I have installed ghc-7.4.1.20120416 from
http://www.haskell.org/ghc/dist/stable/dist/ and the problem is still
there. It seems that I still have to prepare a testcase. :-(

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: infoneeded
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by simonpj):

I think that most of our most recent on improving the performance of type
checking is not in the 7.4 branch, but only on HEAD. You should be able
to pick up development snapshots here
http://www.haskell.org/ghc/dist/current/dist/?C=M;O=D

Simon

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: infoneeded
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by Lemming):

I invested some more hours in order to check whether the bug is still
present in ghc-7.5.20120510. Unfortunately, it is still there. I needed
most of the time to find out that I ran into a new Cabal bug
(http://hackage.haskell.org/trac/hackage/ticket/950).
Additionally I branched my repositories and converted most of the
functional dependencies to type families. GHC can compile all converted
modules as quickly as usually. So this ticket becomes less important for
me. I plan to prepare a small experience report for Haskell-Cafe.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:11>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
----------------------------------------+-----------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: infoneeded
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Keywords: | Os: Linux
Architecture: x86 | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
----------------------------------------+-----------------------------------

Comment(by simonpj):

OK so the situation seems to be:
* There is still a performance bug in the type checker
* It goes away if you don't use functional dependencies

If you feel like turning your example into a reproducible test case we can
follow it up; or we can just leave it since it's not now important for
you. It's up to you really. "Reproducible" doesn't necessarily mean
"small"; it just means a set of instructions that someone can follow, and
preferably no hard-to-install dependencies.

Simon

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5970: Type checker hangs

In reply to this post by GHC

#5970: Type checker hangs
-------------------------------------------+--------------------------------
Reporter: Lemming | Owner:
Type: bug | Status: closed
Priority: normal | Milestone:
Component: Compiler (Type checker) | Version: 7.4.1
Resolution: wontfix | Keywords:
Os: Linux | Architecture: x86
Failure: Compile-time performance bug | Difficulty: Unknown
Testcase: | Blockedby:
Blocking: | Related:
-------------------------------------------+--------------------------------
Changes (by pcapriotti):

* status: infoneeded => closed
* resolution: => wontfix

Comment:

Closing this ticket for now. Feel free to reopen if you can provide a
self-contained test case.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5970#comment:13>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs