Opened 3 years ago

Closed 19 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 Difficulty: Unknown
Test Case: T5030 Blocked By:
Blocking: Related Tickets:

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 3 years ago.
The program I created to reproduce the behavior

Download all attachments as: .zip

Change History (12)

Changed 3 years ago by thesz

The program I created to reproduce the behavior

comment:1 Changed 3 years ago by simonpj

  • Cc dimitris@… added

Wow. Thanks. Simon

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

comment:2 Changed 3 years ago by PHO

  • Cc pho@… added

comment:3 Changed 3 years ago by igloo

  • Milestone set to 7.2.1

comment:4 Changed 3 years ago by dimitris

  • Resolution set to fixed
  • Status changed from new to closed

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

comment:5 Changed 3 years ago by dimitris

I've added a test for this in:

indexed-types/should_compile/SlowComp.hs

comment:6 Changed 3 years ago by dimitris

  • Resolution fixed deleted
  • Status changed from closed to new
  • Test Case set to indexed-types/should_compile/SlowComp.hs

comment:7 Changed 3 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 3 years ago by igloo

  • Resolution set to fixed
  • Status changed from new to closed
  • Test Case changed from indexed-types/should_compile/SlowComp.hs to T5030

Done.

comment:9 Changed 2 years ago by simonpj

  • Difficulty set to Unknown
  • Owner igloo deleted
  • Resolution fixed deleted
  • Status changed from closed to new

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 19 months 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 19 months ago by simonpj

  • Resolution set to fixed
  • Status changed from new to closed

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

Note: See TracTickets for help on using tickets.