Opened 7 years ago

Closed 7 years ago

#5970 closed bug (wontfix)

Type checker hangs

Reported by: Lemming Owned by:
Priority: normal Milestone:
Component: Compiler (Type checker) Version: 7.4.1
Keywords: Cc: dimitris@…
Operating System: Linux Architecture: x86
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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. ;-)

Change History (13)

comment:1 Changed 7 years ago by simonpj

Cc: dimitris@… added
difficulty: Unknown

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.

comment:2 Changed 7 years ago 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.

comment:3 Changed 7 years ago by simonpj

Can you boil down the "repeat n times gives non-linear behaviour" part?

comment:4 Changed 7 years ago by simonpj@…

commit 516d3138473d7b097cc572901bd02fce9509f1b8

Author: Simon Peyton Jones <simonpj@microsoft.com>
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(-)

comment:5 Changed 7 years ago by simonpj

Darn. This commit doesn't fix this ticket (#5970). It fixes #5955. So ignore teh above commit. Sorry.

comment:6 Changed 7 years ago by simonpj

Status: newinfoneeded

OK, so we are stalled on this ticket pending a test case.

comment:7 Changed 7 years ago 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.

comment:8 Changed 7 years ago 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.

comment:9 Changed 7 years ago 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. :-(

comment:10 Changed 7 years ago 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

comment:11 Changed 7 years ago 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.

comment:12 Changed 7 years ago 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

comment:13 Changed 7 years ago by pcapriotti

Resolution: wontfix
Status: infoneededclosed

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

Note: See TracTickets for help on using tickets.