Be less aggressive about the result discount
authorSimon Peyton Jones <simonpj@microsoft.com>
Mon, 28 May 2012 16:33:42 +0000 (17:33 +0100)
committerSimon Peyton Jones <simonpj@microsoft.com>
Mon, 28 May 2012 16:33:42 +0000 (17:33 +0100)
This patch fixes Trac #6099 by reducing the result discount in CoreUnfold.conSize.
See Note [Constructor size and result discount] in CoreUnfold.

The existing version is definitely too aggressive. Simon M found it an
"unambiguous win" but it is definitely what led to the bloat. In a function
with a lot of case branches, all returning a constructor, the discount could
grow arbitrarily large.

I also had to increase the -funfolding-creation-threshold from 450 to 750,
otherwise some functions that should inline simply never get an unfolding.
(The massive result discount was allow the unfolding to appear before.)

The nofib results are these, picking a handful of outliers to show.

        Program           Size    Allocs   Runtime   Elapsed  TotalMem
--------------------------------------------------------------------------------
         fulsom          -0.5%     -1.6%     -2.8%     -2.6%    +31.1%
       maillist          -0.2%     -0.0%      0.09      0.09     -3.7%
         mandel          -0.4%     +6.6%      0.12      0.12     +0.0%
       nucleic2          -0.2%    +18.5%      0.11      0.11     +0.0%
        parstof          -0.4%     +4.0%      0.00      0.00     +0.0%
--------------------------------------------------------------------------------
            Min          -0.9%     -1.6%    -19.7%    -19.7%     -3.7%
            Max          +0.3%    +18.5%     +2.7%     +2.7%    +31.1%
 Geometric Mean          -0.3%     +0.4%     -3.0%     -3.0%     +0.2%

Turns out that nucleic2 has a function
  Main.$wabsolute_pos =
    \ (ww_s4oj :: Types.Tfo) (ww1_s4oo :: Types.FloatT)
      (ww2_s4op :: Types.FloatT) (ww3_s4oq :: Types.FloatT) ->
      case ww_s4oj
      of _
      { Types.Tfo a_a1sS b_a1sT c_a1sU d_a1sV e_a1sW f_a1sX g_a1sY h_a1sZ i_a1t0 tx_a1t1 ty_a1t2 tz_a1t3 ->
      (# case ww1_s4oo of _ { GHC.Types.F# x_a2sO ->
         case a_a1sS of _ { GHC.Types.F# y_a2sS ->
         case ww2_s4op of _ { GHC.Types.F# x1_X2y9 ->
         case d_a1sV of _ { GHC.Types.F# y1_X2yh ->
         case ww3_s4oq of _ { GHC.Types.F# x2_X2yj ->
         case g_a1sY of _ { GHC.Types.F# y2_X2yr ->
         case tx_a1t1 of _ { GHC.Types.F# y3_X2yn ->
         GHC.Types.F#
           (GHC.Prim.plusFloat#
              (GHC.Prim.plusFloat#
                 (GHC.Prim.plusFloat#
                    (GHC.Prim.timesFloat# x_a2sO y_a2sS)
                    (GHC.Prim.timesFloat# x1_X2y9 y1_X2yh))
                 (GHC.Prim.timesFloat# x2_X2yj y2_X2yr))
              y3_X2yn)
         } } }}}}},

        <similar>,
        <similar> )

This is pretty big, but inlining it does get rid of that F# allocation.
But we'll also get rid of it with deep CPR: Trac #2289. For now we just
accept the change.

compiler/coreSyn/CoreUnfold.lhs
compiler/main/StaticFlags.hs

index 5817669..c717e4b 100644 (file)
@@ -570,17 +570,51 @@ conSize :: DataCon -> Int -> ExprSize
 conSize dc n_val_args
   | n_val_args == 0 = SizeIs (_ILIT(0)) emptyBag (_ILIT(10))    -- Like variables
 
--- See Note [Unboxed tuple result discount]
+-- See Note [Unboxed tuple size and result discount]
   | isUnboxedTupleCon dc = SizeIs (_ILIT(0)) emptyBag (iUnbox (10 * (1 + n_val_args)))
 
--- See Note [Constructor size]
-  | otherwise = SizeIs (_ILIT(10)) emptyBag (iUnbox (10 * (10 + n_val_args)))
-     -- discont was (10 * (1 + n_val_args)), but it turns out that
-     -- adding a bigger constant here is an unambiguous win.  We
-     -- REALLY like unfolding constructors that get scrutinised.
-     -- [SDM, 25/5/11]
+-- See Note [Constructor size and result discount]
+  | otherwise = SizeIs (_ILIT(10)) emptyBag (iUnbox (10 * (1 + n_val_args)))
 \end{code}
 
+Note [Constructor size and result discount]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Treat a constructors application as size 10, regardless of how many
+arguments it has; we are keen to expose them (and we charge separately
+for their args).  We can't treat them as size zero, else we find that
+(Just x) has size 0, which is the same as a lone variable; and hence
+'v' will always be replaced by (Just x), where v is bound to Just x.
+
+The "result discount" is applied if the result of the call is
+scrutinised (say by a case).  For a constructor application that will
+mean the constructor application will disappear, so we don't need to
+charge it to the function.  So the discount should at least match the
+cost of the constructor application, namely 10.  But to give a bit
+of extra incentive we give a discount of 10*(1 + n_val_args).
+
+Simon M tried a MUCH bigger discount: (10 * (10 + n_val_args)), 
+and said it was an "unambiguous win", but its terribly dangerous
+because a fuction with many many case branches, each finishing with
+a constructor, can have an arbitrarily large discount.  This led to
+terrible code bloat: see Trac #6099.
+
+Note [Unboxed tuple size and result discount]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+However, unboxed tuples count as size zero. I found occasions where we had 
+       f x y z = case op# x y z of { s -> (# s, () #) }
+and f wasn't getting inlined.
+
+I tried giving unboxed tuples a *result discount* of zero (see the
+commented-out line).  Why?  When returned as a result they do not
+allocate, so maybe we don't want to charge so much for them If you
+have a non-zero discount here, we find that workers often get inlined
+back into wrappers, because it look like
+    f x = case $wf x of (# a,b #) -> (a,b)
+and we are keener because of the case.  However while this change
+shrank binary sizes by 0.5% it also made spectral/boyer allocate 5%
+more. All other changes were very small. So it's not a big deal but I
+didn't adopt the idea.
+
 Note [Function application discount]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 We want a discount if the function is applied. A good example is
@@ -607,31 +641,6 @@ through n's unfolding.  Nor will a big size inhibit unfoldings functions
 that mention a literal Integer, because the float-out pass will float
 all those constants to top level.
 
-Note [Constructor size]
-~~~~~~~~~~~~~~~~~~~~~~~
-Treat a constructors application as size 1, regardless of how many
-arguments it has; we are keen to expose them (and we charge separately
-for their args).  We can't treat them as size zero, else we find that
-(Just x) has size 0, which is the same as a lone variable; and hence
-'v' will always be replaced by (Just x), where v is bound to Just x.
-
-However, unboxed tuples count as size zero. I found occasions where we had 
-       f x y z = case op# x y z of { s -> (# s, () #) }
-and f wasn't getting inlined.
-
-Note [Unboxed tuple result discount]
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-I tried giving unboxed tuples a *result discount* of zero (see the
-commented-out line).  Why?  When returned as a result they do not
-allocate, so maybe we don't want to charge so much for them If you
-have a non-zero discount here, we find that workers often get inlined
-back into wrappers, because it look like
-    f x = case $wf x of (# a,b #) -> (a,b)
-and we are keener because of the case.  However while this change
-shrank binary sizes by 0.5% it also made spectral/boyer allocate 5%
-more. All other changes were very small. So it's not a big deal but I
-didn't adopt the idea.
-
 \begin{code}
 primOpSize :: PrimOp -> Int -> ExprSize
 primOpSize op n_val_args
index cfbd4ba..4c78070 100644 (file)
@@ -345,7 +345,12 @@ opt_UF_CreationThreshold, opt_UF_UseThreshold :: Int
 opt_UF_DearOp, opt_UF_FunAppDiscount, opt_UF_DictDiscount :: Int
 opt_UF_KeenessFactor :: Float
 
-opt_UF_CreationThreshold = lookup_def_int "-funfolding-creation-threshold" (450::Int)
+opt_UF_CreationThreshold = lookup_def_int "-funfolding-creation-threshold" (750::Int)
+  -- This threshold must be reasonably high to take 
+  -- account of possible discounts.  
+  -- E.g. 450 is not enough in 'fulsom' for Interval.sqr to inline into Csg.calc
+  --      (The unfolding for sqr never makes it into the interface file.)
+
 opt_UF_UseThreshold      = lookup_def_int "-funfolding-use-threshold"      (60::Int)
 opt_UF_FunAppDiscount    = lookup_def_int "-funfolding-fun-discount"       (60::Int)