[GHC] #3064: Very long compile times with type functions

[GHC]

#3064: Very long compile times with type functions
-------------------------------------------------+-------------------------
        Reporter:  simonpj                       |            Owner:
            Type:  bug                           |           Status:
        Priority:  low                           |  closed
       Component:  Compiler (Type checker)       |        Milestone:  7.6.1
      Resolution:  fixed                         |          Version:
Operating System:  Unknown/Multiple              |  6.10.1
 Type of failure:  Compile-time performance bug  |         Keywords:
       Test Case:  perf/compiler/T3064           |     Architecture:
        Blocking:                                |  Unknown/Multiple
                                                 |       Difficulty:
                                                 |  Unknown
                                                 |       Blocked By:
                                                 |  Related Tickets:
-------------------------------------------------+-------------------------

Comment (by Simon Peyton Jones <simonpj@…>):

 In [changeset:"a6f0f5ab45b2643b561e0a0a54a4f14745ab2152/ghc"]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="a6f0f5ab45b2643b561e0a0a54a4f14745ab2152"
 Eliminate so-called "silent superclass parameters"

 The purpose of silent superclass parameters was to solve the
 awkward problem of superclass dictinaries being bound to bottom.
 See THE PROBLEM in Note [Recursive superclasses] in TcInstDcls

 Although the silent-superclass idea worked,

   * It had non-local consequences, and had effects even in Haddock,
     where we had to discard silent parameters before displaying
     instance declarations

   * It had unexpected peformance costs, shown up by Trac #3064 and its
     test case.  In monad-transformer code, when constructing a Monad
     dictionary you had to pass an Applicative dictionary; and to
     construct that you neede a Functor dictionary. Yet these extra
     dictionaries were often never used.  (All this got much worse when
     we added Applicative as a superclass of Monad.) Test T3064
     compiled *far* faster after silent superclasses were eliminated.

   * It introduced new bugs.  For example SilentParametersOverlapping,
     T5051, and T7862, all failed to compile because of instance overlap
     directly because of the silent-superclass trick.

 So this patch takes a new approach, which I worked out with Dimitrios
 in the closing hours before Christmas.  It is described in detail
 in THE PROBLEM in Note [Recursive superclasses] in TcInstDcls.

 Seems to work great!

 Quite a bit of knock-on effect

  * The main implementation work is in tcSuperClasses in TcInstDcls
    Everything else is fall-out

  * IdInfo.DFunId no longer needs its n-silent argument
    * Ditto IDFunId in IfaceSyn
    * Hence interface file format changes

  * Now that DFunIds do not have silent superclass parameters, printing
    out instance declarations is simpler. There is tiny knock-on effect
    in Haddock, so that submodule is updated

  * I realised that when computing the "size of a dictionary type"
    in TcValidity.sizePred, we should be rather conservative about
    type functions, which can arbitrarily increase the size of a type.
    Hence the new datatype TypeSize, which has a TSBig constructor for
    "arbitrarily big".

  * instDFunType moves from TcSMonad to Inst

  * Interestingly, CmmNode and CmmExpr both now need a non-silent
    (Ord r) in a couple of instance declarations. These were previously
    silent but must now be explicit.

  * Quite a bit of wibbling in error messages
 }}}

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