[GHC] #12754: Adding an explicit export list halves compilation time.

[GHC]

#12754: Adding an explicit export list halves compilation time.
-------------------------------------+-------------------------------------
        Reporter:  mpickering        |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      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):

 I stupidly missed Matthew's original insight in the Description.  He's
 absolutely right; the current thing is stupid.

 There should be nothing non-linear about this.  We have a `[GRE]` and we
 want a `[AvailInfo]`.  Very well: do
 {{{
 gresToAvailInfo :: [GRE] -> [AvailInfo]
 gresToAvailInfo gres
   = nameEnvElts avail_env
   where
     avail_env :: NameEnv AvailInfo   -- Keyed by the parent
     avail_env = foldr add emptyNameEnv gres

     add :: GRE -> NameEnv AvailInfo -> NameEnv AvailInfo
     add gre env = ... very like availFromGRE, but instead of returning
                       an AvailInfo, it extends the appropriate AvailInfo
                       in the env ...
 }}}
 Each GRE should take constant time to add.  Each GRE deals with a
 different Name, so there is no need to check for duplicates.

 Needed in two places

 * `TcRnExports.exports_from_avail`, the `Nothing` case.

 * Same function, the `IEModuleContents` case of `exports_from_item`

 Hmm.  The use of `nubAvails` is still needed though, in case you say
 {{{
 module M( T( D, D3 ), T( D, D2 ) )
 }}}
 when we should combine the two export items to `T( D, D2, D3 )`.  So we
 might still get the non-linear cost if you have very many manually-written
 items, which is at least better.

 So an alternative, perhaps better, would be to rewrite `nubAvails` to use
 code very like the above function, so that each `Name` in the
 `[AvailInfo]` takes linear time to add.  That's be more robust I guess.

 Finally, the other use of `nubAvails` is in `RnNames,findImportUsage`.  I
 think `extendImportMap` could return a `[GRE]` as the second element of
 its result pair, instead of `[AvailInfo]`, and then we could use
 `gresToAvailInfo` again; but this time we'd need to worry about
 duplicates.

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