Opened 3 years ago

Closed 3 years ago

#6048 closed bug (fixed)

Exponential inlining code blowup

Reported by: simonpj Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.4.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: perf/compiler/T6048
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

(Transferring a new thread from #5539 to a new ticket, since it's really a separate problem.) kosmikus helpfully provided this program

module TestCase where

import Control.Applicative

data X = X
  (Maybe String)
  (Maybe String)
  (Maybe String)
  (Maybe String)
  (Maybe String)
  (Maybe String)
  (Maybe String)
  (Maybe String)
  (Maybe String)

mb :: (String -> Maybe a) -> String -> Maybe (Maybe a)
mb _ ""  = Just Nothing
mb _ "-" = Just Nothing
mb p xs  = Just <$> p xs

run :: [String] -> Maybe X
run
  [ x1
  , x2
  , x3
  , x4
  , x5
  , x6
  , x7
  , x8
  , x9
  ] = X
  <$> mb pure x1
  <*> mb pure x2
  <*> mb pure x3
  <*> mb pure x4
  <*> mb pure x5
  <*> mb pure x6
  <*> mb pure x7
  <*> mb pure x8
  <*> mb pure x9

Unless mb is marked as NOINLINE, it gets expanded in the body of run a number of times that seems to grow exponentially with the size of the list (9 in the example).

Change History (3)

comment:1 Changed 3 years ago by simonpj

I know what is going on. It's a consequence of Max's patch

commit dfe536be7d5d662ae75671797750b487c1ef59b7
Author: Max Bolingbroke <[email protected]>
Date:   Wed Mar 7 19:44:31 2012 +0000

    Give a unfolding argument discount proportional to the number of available arguments
    
    Ensures that h1 gets inlined into its use sites in cases like:
    
    """
    h1 k = k undefined undefined undefined
            undefined undefined undefined
            undefined undefined undefined
            undefined undefined undefined
            undefined undefined undefined
            undefined undefined undefined
    
    a = h1 (\x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
    b = h1 (\_ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
    """
    
    I've benchmarked this on nofib (albeit recompiling only the
    benchmarks, not the library) and it hardly shifts the numbers - binary
    size is up by 0.1% at most (average 0.0%) and the worst-case
    allocation increase is 0.2% (best case -0.1%, 0.0% average).
    
    If you also rebuild the libraries with this change, the only further
    change is a +0.2% allocation increase in cacheprof. So this looks like
    a pretty low-risk change that will considerably benefit certain
    programs.

In kosmikus's program we have lots of join points looking like

  $j x = case .. of
             p1 ->  Just (x 3)
             p2 ->  Just (x 4)

and stuff like that. Because of Max's patch, some very big join functions (size 350 or so) get very big discounts. The bigger the function, the more calls to 'x' there are, so the bigger the discount! So no matter how big the join point gets, it is still inlined. Hence the exponential behaviour, which starts with a case-of-case nest. No, this is not good.

Max's reasoning is describe in Note [Function application discount] in CoreUnfold, which I reproduce below for convenience. But the reasoning is flawed. Suppose we have

let  $j x = ....(x 3)...(x 4)....
     h y = <BIG EXPR>
in
...($j h)...

Then $j gets the massive discount for the applications of x. But when we inline $j we just get

    ....(....(h 3)...(h 4)....).....

and since h is big, there we stop. So the anticipated cancellation has not materialised. It really only materialises when

  • The parameter to $j is used once in $j's body.
  • The argument to the call of $j is a literal lambda.

Unless Max has a better idea I'm going to revert his change. BTW kudos to Max for a detailed comment so we can actually see the reasoning.

Simon

Max's comment:

Note [Function application discount]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I noticed that the output of the supercompiler generates a lot of code
with this form:

"""
module Inlining where

h1 k = k undefined undefined undefined
        undefined undefined undefined
        undefined undefined undefined
        undefined undefined undefined
        undefined undefined undefined
        undefined undefined undefined

a = h1 (\x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
b = h1 (\_ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
c = h1 (\_ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
d = h1 (\_ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
e = h1 (\_ _ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
f = h1 (\_ _ _ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ -> x)
g = h1 (\_ _ _ _ _ _ x _ _ _ _ _ _ _ _ _ _ _ -> x)
h = h1 (\_ _ _ _ _ _ _ x _ _ _ _ _ _ _ _ _ _ -> x)
i = h1 (\_ _ _ _ _ _ _ _ x _ _ _ _ _ _ _ _ _ -> x)
j = h1 (\_ _ _ _ _ _ _ _ _ x _ _ _ _ _ _ _ _ -> x)
k = h1 (\_ _ _ _ _ _ _ _ _ _ x _ _ _ _ _ _ _ -> x)
l = h1 (\_ _ _ _ _ _ _ _ _ _ _ x _ _ _ _ _ _ -> x)
m = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ x _ _ _ _ _ -> x)
n = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ x _ _ _ _ -> x)
o = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ x _ _ _ -> x)
p = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x _ _ -> x)
q = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x _ -> x)
r = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x -> x)
"""

With GHC head the applications of h1 are not inlined, which hurts the
quality of the generated code a bit. I was wondering why h1 wasn't
getting inlined into each of "a" to "i" - after all, it has a manifest
lambda argument.

It turns out that the code in CoreUnfold gives a fixed discount of
opt_UF_FunAppDiscount to a function argument such as "k" if it applied
to any arguments. This is enough to ensure that h1 is inlined if the number
of arguments applied to k is below a certain limit, but if many arguments are
applied to k then the fixed discount can't overcome the size of the
chain of apps, and h1 is never inlined.

My proposed solution is to change CoreUnfold.funSize so that longer
chains of arguments being applied to a lambda-bound function give a
bigger discount. The motivation for this is that we would *generally*
expect that the lambda at the callsite has enough lambdas such that
all of the applications within the body can be beta-reduced away. This
change might lead to over eager inlining in cases like this, though:

{{{
h1 k = k x y z

{-# NOINLINE g #-}
g = ...

main = ... h1 (\x -> g x) ...
}}}

In this case we aren't able to beta-reduce away all of the
applications in the body of h1 because the lambda at the call site
only binds 1 argument, not the 3 allowed by the type. I don't expect
this case to be particularly common, however.

I chose the bonus to be (size - 20) so that application to 1 arg got
same bonus as the old fixed bonus (i.e. opt_UF_FunAppDiscount, which is 60).
If you have the bonus being (size - 40) then $fMonad[]_$c>>= with interesting
2nd arg doesn't inline in cryptarithm2 so we lose some deforestation, and
overall binary size hardly falls.

comment:2 Changed 3 years ago by simonpj@…

commit 980372f357667c1ba63b28acbf5798826890b7a5

Author: Simon Peyton Jones <[email protected]>
Date:   Wed May 9 16:22:49 2012 +0100

    Re-do the "function application discount" (fixes Trac #6048)
    
    * Undoes Max's very aggressive function-inlining change
      (see comments with Trac #6048)
    
    * Resticts function application discount to functions
      that occur just once in the body. It was the multiple
      occurrences that led to the exponential behavour in
      Trac #6048.
    
    See Note [Function application discount] in CoreUnfold.
    
    Module binary sizes are down 2% on average, which is good.
    Allocations wobble about a bit, but only on a few benchmarks
    and not by much, so it seems a price worth paying to avoid
    exponential behaviour!
    
                             Allocs
                Min           -1.2%
                Max           +2.8%
     Geometric Mean           +0.0%

 compiler/coreSyn/CoreUnfold.lhs |  122 +++++++++++----------------------------
 1 files changed, 35 insertions(+), 87 deletions(-)

comment:3 Changed 3 years ago by simonpj

  • Resolution set to fixed
  • Status changed from new to closed
  • Test Case set to perf/compiler/T6048

Really nice example. Thank you for making it so compelling. Fixed!

Note: See TracTickets for help on using tickets.