#14693 closed bug (fixed)

Computing imp_finst can take up significant amount of time

Reported by: niteria Owned by:
Priority: normal Milestone:
Component: Compiler (Type checker) Version:
Keywords: Cc: simonmar
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): phab:D4369
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/typecheck/TcRnTypes.hs;575c009d9e4b25384ef984c09b2c54f909693e93$1398

Attachments (1)

generateModules (1.2 KB) - added by niteria 20 months ago.

Download all attachments as: .zip

Change History (7)

Changed 20 months ago by niteria

Attachment: generateModules added

comment:1 Changed 20 months ago 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        
     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/typecheck/FamInst.hs;575c009d9e4b25384ef984c09b2c54f909693e93$346-364

comment:2 Changed 20 months ago by niteria

Cc: simonmar added

comment:3 Changed 20 months ago by simonpj

Any progress?

comment:4 Changed 20 months ago by niteria

Differential Rev(s): phab:D4369
Status: newpatch

comment:5 Changed 20 months ago by Bartosz Nitka <niteria@…>

In d2511e3/ghc:

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

comment:6 Changed 20 months ago by niteria

Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.