[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       |           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/typecheck/TcRnTypes.hs;575c009d9e4b25384ef984c09b2c54f909693e93$1398

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