[GHC] #14693: Computing imp_finst can take up significant amount of time
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: (Type checker) | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Compile-time Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- I profiled a build of a production code base with thousands of modules and merging `imp_finsts` [1] from different imports came up on top taking up 9% of total compile time. I made a synthetic test case to reproduce the issue (see attached `generateModules`). The test case is basically multiple layers of modules where each module defines a type family instance through deriving Generic. The problem is quite obvious, `unionLists` is quadratic and `imp_finsts` just keeps growing with the size of the code base. [1] https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/typeche... -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by niteria): * Attachment "generateModules" added. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by niteria): The natural way to fix this would be to change the type of `imp_finst` to `ModuleSet`. `imp_finst` is converted back and forth from `dep_finst :: [Module]` and if I don't change the type of `dep_finst` to `ModuleSet` as well, the conversion costs 20% increase in allocations on the generated test case. If I want change the type of `dep_finst` then the way we ensure determinism in `checkFamInsts` [1] needs to be rethought. Because I like neither choice, I came up with a small workaround. The idea is to compute the `imp_finsts` for all the imports outside `plusImportAvails` using a set. Here's a hacky implementation of the idea: {{{ diff --git a/compiler/rename/RnNames.hs b/compiler/rename/RnNames.hs index ae3f75b1d0..2866113497 100644 --- a/compiler/rename/RnNames.hs +++ b/compiler/rename/RnNames.hs @@ -179,14 +179,17 @@ rnImports imports = do where combine :: [(LImportDecl GhcRn, GlobalRdrEnv, ImportAvails, AnyHpcUsage)] -> ([LImportDecl GhcRn], GlobalRdrEnv, ImportAvails, AnyHpcUsage) - combine = foldr plus ([], emptyGlobalRdrEnv, emptyImportAvails, False) + combine zs = + let (a, b, c,d,e) = foldr plus ([], emptyGlobalRdrEnv, emptyImportAvails, False, emptyModuleSet) zs + in (a, b, c { imp_finsts = moduleSetElts e }, d) plus (decl, gbl_env1, imp_avails1,hpc_usage1) - (decls, gbl_env2, imp_avails2,hpc_usage2) + (decls, gbl_env2, imp_avails2,hpc_usage2,finsts) = ( decl:decls, gbl_env1 `plusGlobalRdrEnv` gbl_env2, - imp_avails1 `plusImportAvails` imp_avails2, - hpc_usage1 || hpc_usage2 ) + imp_avails1 { imp_finsts = [] } `plusImportAvails` imp_avails2, + hpc_usage1 || hpc_usage2, + extendModuleSetList finsts (imp_finsts imp_avails1)) -- | Given a located import declaration @decl@ from @this_mod@, -- calculate the following pieces of information: }}} This makes the problem disappear from my profile and speeds up the test case from `10.7s` to `6.23s`. [1] https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/typeche... -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by niteria): * cc: simonmar (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Any progress? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): phab:D4369 Wiki Page: | -------------------------------------+------------------------------------- Changes (by niteria): * status: new => patch * differential: => phab:D4369 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): phab:D4369 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Bartosz Nitka <niteria@…>): In [changeset:"d2511e3b61563ed3fc2c9aec2c90a4156373a24c/ghc" d2511e3/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="d2511e3b61563ed3fc2c9aec2c90a4156373a24c" Compute the union of imp_finsts on the side I've explained most of the rationale in a new Note. I'd happily add a test for this, but the difference is only visible in run time, allocations remain more or less the same. FWIW running `generateModules` from #14693 with DEPTH=16, WIDTH=30 finishes in `23s` before, and `11s` after. Test Plan: ./validate Reviewers: simonpj, simonmar, bgamari Reviewed By: simonpj Subscribers: rwbarton, thomie, carter GHC Trac Issues: #14693 Differential Revision: https://phabricator.haskell.org/D4369 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14693: Computing imp_finst can take up significant amount of time -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler (Type | Version: checker) | Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): phab:D4369 Wiki Page: | -------------------------------------+------------------------------------- Changes (by niteria): * status: patch => closed * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC