#14880: GHC panic: updateRole -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: goldfire Type: bug | Status: new Priority: normal | Milestone: 8.6.2 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: 15592 Related Tickets: #15076 | Differential Rev(s): Phab:D4769, | Phab:D5141, Phab:D5147, Phab:D5150, Wiki Page: | Phab:D5208 -------------------------------------+------------------------------------- Comment (by Krzysztof Gogolewski <krz.gogolewski@…>): In [changeset:"08b3db7e670d7a142244466f1722cb48ab82f1f5/ghc" 08b3db7e/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="08b3db7e670d7a142244466f1722cb48ab82f1f5" Use an accumulator version of tyCoVarsOfType Summary: This is part 1 from #14880: factor out a worker for the tyCoVarsOf... family of function, implementing them in terms of VarSet, but with accumulator-style (like in `FV`) built in, and with the same kind of pre-insert lookup; this has shown to perform better than either FV or plain VarSet in this particular scenario. Original notes from simonpj: 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)? Becuase 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 speical purpose code. On the way I also simplified the (less used) coVarsOfType/Co family to use FV, by making serious use of the InterestingVarFun! Test Plan: validate, nofib Reviewers: simonpj, bgamari Reviewed By: simonpj Subscribers: rwbarton, carter GHC Trac Issues: #14880 Differential Revision: https://phabricator.haskell.org/D5141 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14880#comment:151> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler