[GHC] #14880: GHC panic: updateRole

[GHC]

#14880: GHC panic: updateRole
-------------------------------------+-------------------------------------
        Reporter:  RyanGlScott       |                Owner:  goldfire
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.8.1
       Component:  Compiler (Type    |              Version:  8.2.2
  checker)                           |
      Resolution:                    |             Keywords:  TypeInType
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  crash or panic                     |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #15076            |  Differential Rev(s):  Phab:D4769
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 OK, I think I have finally nailed what is going on.

 '''I have pushed my work to `wip/T1448-accum`.  NB Missing "0" in the
 branch name, sorry.'''

 The key insight is in the commit message of the top patch on that branch,
 which is the only patch that isn't in master, I think:
 {{{
 commit a4e7a912ff426ef9cb968ea21d1a514f203a7ea5
 Author: Simon Peyton Jones <simonpj at microsoft.com>
 Date:   Fri Aug 31 14:18:55 2018 +0100

     Use an accumulator version of tyCoVarsOfType

     In TyCoRep we now have tyCoVarsOfType implemented

     1) Using FV -- this is the baseline version in GHC today

     2) Using VarSets via unionVarSet

     3) Using VarSets in accumulator-style

     In this patch (3) is enabled.

     When compiling perf/compiler/T5631 we get

              Compiler allocs
        (1)   1,144M
        (2)   1,175M
        (3)   1,142M

     The key new insight in (3) is this:

       ty_co_vars_of_type (TyVarTy v) is acc
         | v `elemVarSet` is  = acc
         | v `elemVarSet` acc = acc   <---- NB!
         | otherwise          = ty_co_vars_of_type (tyVarKind v) is
 (extendVarSet acc v)

     Notice the second line! If the variable is already in the
     accumulator, don't re-add it.  This makes big difference.
     Without it, allocation is 1,169M or so.

     One cause is that we only take the free vars of its kind once;
     that problem will go away when we do the main part of #14088 and
     close over kinds /afterwards/.  But still, another cause is perhaps
     that every insert into a set overwrites the previous item, and so
     allocates a new path to the item; it's not a no-op even if the
     item is there already.

     Why use (3) rather than (1)?  Because it just /has/ to
     be better;

     * FV carries around an InterestingVarFun, which does nothing
       useful here, but is tested at every variable

     * FV carries around a [Var] for the deterministic version.

     For this very hot operation (finding free vars) I think it
     makes sense to have special purpose code.

     On the way I also simplified the (less used) coVarsOfType/Co family
     to use FV, by making serious use of the InterestingVarFun!
 }}}
 It was this check against the accumulator, which FV has always performed,
 which is responsible for how FV mysteriously out-performed all other
 contenders.  Once that is done, a stripped-down version of FV
 (implemented as (3) in the code above) slightly out-performs FV.

 All of this is relative to `wip/T14880-baseline`.

 Therefore I suggest

 1. Apply my patch to HEAD (and check for no regressions)
 2. Apply the rest of the #14880 patch to that

 By "the rest" I mean everything in the original patch
 [http://git.haskell.org/ghc.git/log/refs/heads/wip/T14880]
 ''except'' the implementation of `tcvs_of_type`.
 Specifically, doing `closeOverKinds` at the end, rather
 than at each leaf.  Doubtless other stuff too.

 There are a number of other tickets that are waiting for this
 one to be finished: #14040, #15076, #14887.

 Tobias can you do this?

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