#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@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