Opened 6 years ago

Closed 4 years ago

Last modified 4 months ago

#5030 closed bug (fixed)

Slow type checking of type-level computation heavy code.

Reported by: thesz Owned by:
Priority: normal Milestone: 7.2.1
Component: Compiler (Type checker) Version: 7.0.2
Keywords: Cc: dimitris@…, pho@…
Operating System: Unknown/Multiple Architecture: x86
Type of failure: Compile-time performance bug Test Case: T5030
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

It seems we encountered a highly non-linear complexity in type checking.

I attached a "simple" program that produces the effect.

The time needed to load complete file in ghci depending on number of lines in longCompilingProgram:

  • 4 lines - 2 secs,
  • 8 lines - 10 secs,
  • 12 lines - 27 secs,
  • 16 lines - 59 secs.

time = 0,0156lines3 - 0,0937lines2 + 1,375lines - 3

Attachments (1)

SlowComp.hs (6.0 KB) - added by thesz 6 years ago.
The program I created to reproduce the behavior

Download all attachments as: .zip

Change History (13)

Changed 6 years ago by thesz

Attachment: SlowComp.hs added

The program I created to reproduce the behavior

comment:1 Changed 6 years ago by simonpj

Cc: dimitris@… added

Wow. Thanks. Simon

Dimitrios: each line causes about 1500 solver steps!!!

comment:2 Changed 6 years ago by PHO

Cc: pho@… added

comment:3 Changed 6 years ago by igloo

Milestone: 7.2.1

comment:4 Changed 6 years ago by dimitris

Resolution: fixed
Status: newclosed

More sharing during flattening and constraint solving fixed this. I've pushed the changeds.

comment:5 Changed 6 years ago by dimitris

I've added a test for this in:

indexed-types/should_compile/SlowComp.hs

comment:6 Changed 6 years ago by dimitris

Resolution: fixed
Status: closednew
Test Case: indexed-types/should_compile/SlowComp.hs

comment:7 Changed 6 years ago by dimitris

Owner: set to igloo

Ian, I've added a testcase for this in indexed-types/should_compile. But could you add something (I don't know what exactly) so that we make sure that GHC does not take more than 3-4 seconds to compile this?

comment:8 Changed 6 years ago by igloo

Resolution: fixed
Status: newclosed
Test Case: indexed-types/should_compile/SlowComp.hsT5030

Done.

comment:9 Changed 5 years ago by simonpj

difficulty: Unknown
Owner: igloo deleted
Resolution: fixed
Status: closednew

I'm re-opening following a refactoring in the constraint solver.

commit dd7522c3b14bce1af94bffd61c4d38e670f53495
Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Mon May 7 17:40:34 2012 +0100

    Yet another major refactoring of the constraint solver
    
    This is the result of Simon and Dimitrios doing a code walk through.
    There is no change in behaviour, but the structure is much better.
    Main changes:
    
    * Given constraints contain an EvTerm not an EvVar
    
    * Correspondingly, TcEvidence is a recursive types that uses
      EvTerms rather than EvVars
    
    * Rename CtFlavor to CtEvidence
    
    * Every CtEvidence has a ctev_pred field.  And use record fields
      consistently for CtEvidence
    
    * The solved-constraint fields of InertSet (namely inert_solved and
      inert_solved_funeqs) contain CtEvidence, not Ct
    
    There is a long cascade of follow-on changes.

Generally speaking this refactoring is a win, but it makes this particular test get worse:

Baseline:             391M allocated
With this change:     479M allocated 

I'm sure it's not a big deal to fix, but I'm going to re-open the ticket so that Dimitrios and I look at it again.

comment:10 Changed 4 years ago by simonpj@…

commit 902a8632c627304bc553557c21263c591ae63428

Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Tue Oct 2 09:20:53 2012 +0100

    Improve (and simplify) the short-circuiting of Refl coercions
    
    The constraint solver sometimes goes to a lot of effort that turns
    out to be Refl in the end, and avoiding zonking those proofs is a
    useful optimisation. (Trac #5030)

 compiler/typecheck/TcHsSyn.lhs |   45 +++++++++++++++------------------------
 1 files changed, 17 insertions(+), 28 deletions(-)

comment:11 Changed 4 years ago by simonpj

Resolution: fixed
Status: newclosed

I think it's as good as it's going to get for now, and it's a bit of a corner case. The regression test (now reinstated) will keep an eye on it.

Simon

comment:12 Changed 4 months ago by Simon Peyton Jones <simonpj@…>

In 1f09b246/ghc:

Accept 20% dedgradation in Trac #5030 compile time

In commit

  31621b12 * A collection of type-inference refactorings.

I fixed a bug in the on-the-fly unifier.  Usually the
on-the-fly unifier (TcUnify) defers type function
applications to the constraint solver.  But in one situation
it inconsistently did not defer, so a unification happened
without reducing a type function.  By a fluke this makes
T5030 (specifcially the definition of cnst) much better.

It turns out that consistently non-deferring type functions
makes the test for #3064 go bad.  So somehow the current,
inconsistent situation was an accidental sweet spot.

But it's a horrible sweet spot, relying on what was essentially
a bug.  So I've accepted the worsening (it's an exotic case),
and opened #12724 to deal with the underlying cause.
Note: See TracTickets for help on using tickets.