[GHC] #5075: CPR optimisation for sum types if only one constructor is used

[GHC]

#5075: CPR optimisation for sum types if only one constructor is used
-------------------------------------+------------------------------------
        Reporter:  batterseapower    |            Owner:  simonpj
            Type:  feature request   |           Status:  new
        Priority:  normal            |        Milestone:  7.6.2
       Component:  Compiler          |          Version:  7.0.3
      Resolution:                    |         Keywords:
Operating System:  Unknown/Multiple  |     Architecture:  Unknown/Multiple
 Type of failure:  None/Unknown      |       Difficulty:  Unknown
       Test Case:                    |       Blocked By:
        Blocking:                    |  Related Tickets:
-------------------------------------+------------------------------------

Comment (by nomeata):

 In that case, let me add some numbers related to sum type CPR in local
 functions.

 With current master [4d70840d/ghc], enabling CPR for sum types has this
 effect:

 {{{
 --------------------------------------------------------------------------------
         Program           Size    Allocs   Runtime   Elapsed  TotalMem
 --------------------------------------------------------------------------------
            ansi          +8.6%     +0.5%      0.00      0.00     +0.0%
          awards          +8.6%     +0.2%      0.00      0.00     +0.0%
       cacheprof          +8.0%     +0.2%     -3.1%     -3.1%     +0.0%
        calendar          +8.6%     +0.2%      0.00      0.00     +0.0%
         circsim          +8.5%     +1.1%     -8.7%     -8.7%     -2.0%
    cryptarithm1          +8.7%     -3.8%     +0.5%     +0.5%     +0.0%
             cse          +8.6%     +0.2%      0.00      0.00     +0.0%
        fibheaps          +8.6%     -0.3%      0.02      0.02     +0.0%
           fluid          +7.7%     +3.4%      0.01      0.01     +0.0%
          fulsom          +8.3%     +0.1%      0.19      0.19    -31.2%
          hidden          +8.3%     +1.8%     +3.4%     +6.2%     +0.0%
           kahan          +8.1%     +0.1%      0.17      0.17     +0.0%
       listcompr          +8.6%     +0.4%      0.06      0.05     +0.0%
        listcopy          +8.6%     +0.4%      0.07      0.06     +0.0%
          mandel          +7.5%     +0.3%      0.05      0.05     +0.0%
         mandel2          +8.7%    +33.8%      0.00      0.00     +0.0%
          parser          +8.1%     +1.7%      0.02      0.02     +0.0%
       primetest          +8.7%     -0.2%      0.07      0.07     +0.0%
         reptile          +8.5%     +0.2%      0.01      0.01     +0.0%
         rewrite          +8.5%     +0.1%      0.02      0.02     +0.0%
            rfib          +8.7%     +0.6%      0.02      0.02     +0.0%
   spectral-norm          +8.5%     +0.7%     -0.6%     -0.6%     +0.0%
          symalg          +8.3%     +0.2%      0.01      0.01     +0.0%
             tak          +8.6%     +1.3%      0.01      0.01     +0.0%
       transform          +8.3%     +0.1%     +0.0%     +0.0%     +0.0%
 --------------------------------------------------------------------------------
             Min          +6.8%     -3.8%    -11.3%    -11.3%    -31.2%
             Max          +8.7%    +33.8%     +3.9%     +6.2%     +6.1%
  Geometric Mean          +8.4%     +0.4%     -1.8%     -1.8%     -0.4%
 }}}

 So one quite extreme degradation, and otherwise minor losses.

 If I make sure that join points do not get the CPR information unless the
 expression they are a join point for does, we get this change (relative to
 the same baseline):

 {{{
 --------------------------------------------------------------------------------
         Program           Size    Allocs   Runtime   Elapsed  TotalMem
 --------------------------------------------------------------------------------
       cacheprof          +8.0%     +0.3%     -4.7%     -4.7%     +1.8%
        calendar          +8.6%     +0.1%      0.00      0.00     +0.0%
         circsim          +8.5%     +0.2%     -8.4%     -8.4%     -2.0%
    cryptarithm1          +8.6%     -3.8%     +1.5%     +1.5%     +0.0%
             cse          +8.6%     +0.2%      0.00      0.00     +0.0%
        fibheaps          +8.5%     -0.3%      0.03      0.03     +0.0%
          fulsom          +8.2%     -3.7%      0.19      0.19    -31.2%
           kahan          +8.1%     -0.2%      0.17      0.17     +0.0%
       listcompr          +8.6%     +0.4%      0.07      0.06     +0.0%
        listcopy          +8.6%     +0.4%      0.07      0.06     +0.0%
        maillist          +8.6%     +0.0%      0.04      0.04    +16.0%
          mandel          +7.4%     +0.2%      0.05      0.05     +0.0%
          parser          +8.1%     +1.7%      0.02      0.02     +0.0%
       primetest          +8.6%     -0.2%      0.07      0.07     +0.0%
         rewrite          +8.5%     +0.1%      0.01      0.01     +0.0%
 --------------------------------------------------------------------------------
             Min          +6.8%     -3.8%     -8.4%     -8.4%    -31.2%
             Max          +8.7%     +1.7%     +3.2%     +3.4%    +16.0%
  Geometric Mean          +8.3%     -0.0%     -2.0%     -1.9%     -0.2%
 }}}

 This looks quite different now: A few losses, but much smaller than
 before. A mean of zero, and more gains than before. Unfortunately, the
 code size increase is still there...

 If it were not for the code size increase, I’d suggest to merge these
 changes: Fewer special cases in transformations is a good thing. But it is
 probably not worth the code size increase, is it?

 (Just for the record: In theory it is possible that CPR’ing a non-sum-type
 can destroy the join-point-property of a let. But it does not seem to
 happen: If I enable the cpr-join-point-fix, but keep CPR for sum types
 disabled, nofib does not record any change whatsoever.)

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