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