[GHC] #14880: GHC panic: updateRole

[GHC]

#14880: GHC panic: updateRole
-------------------------------------+-------------------------------------
        Reporter:  RyanGlScott       |                Owner:  goldfire
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       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):

 I have a new hypothesis, provoked by this merge popping up
 in the statistics.

 * Previously, `tyCoVarsOfTypes` used `tyCoFVsOfTypes`, which
   in turn uses `unionFV` (from `utils/FV.hs`). This `FV` thing is
 relatively
   elaborate, maintaining a `VarSet` alongside a list.  Plus an
 "interesting"
   predicate which, in the case of `tyCoVarsOfType` is `const True`.

 * In the patch, `tyCoVarsOfType` switches to using `unionVarSet`.  This
 "obviously" shold be more efficient, because it just maintains a `VarSet`,
 with no list.

 * BUT `tyCoVarsOfType` does not use an accumulator; it just
 straightforwardly unions the free-vars in a tree-like way.  In contrast,
 `unionFV` does use accumulator style, behind the scenes.

 * Bottom line: in the old version we make many calls to `extendVarSet`; in
 the new one we make many calls to `unionVarSet`.

 It should jolly well be the case that inserting 100 things one by one into
 a set should be no faster than unioning a balanced tree of the same 100
 things.  But looking at `Data.Map.Internal.insert`, and comparing with
 `Data.Map.Internal.mergeWithKey'`, I bet the former is faster.

 This hypothesis is easy to test: just change the new `tcvs_of_type` to
 take an accumulator.

 If this turns out to make a difference, I think we should file a bug on
 `containers`.  Users should not have to worry about this!

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