[GHC] #14693: Computing imp_finst can take up significant amount of time

[GHC]

#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/typecheck/FamInst.hs;575c009d9e4b25384ef984c09b2c54f909693e93$346-364

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14693#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler