[Haskell-cafe] Inline makes program slow?

[Simon Peyton Jones]

Dominick's program is very delicate:

	fibonacci :: (Integral a) => [a]
	fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

Remember, the "(Integral a) =>" thing is very like "Integral a ->"; it's an extra value  argument.  Would you expect this program to be fast?

	foo :: Int -> [Int]
	foo n = 0 : 1 : zipWith (+) (foo n) (tail (foo n))

Perhaps, but it depends on common sub-expression analysis which is on with -O.

Anyway it is not related to INLINE or eta-expansion/contraction.

Simon

| -----Original Message-----
| From: Haskell-Cafe [mailto:haskell-cafe-bounces at haskell.org] On Behalf
| Of Dominick Samperi
| Sent: 30 March 2014 17:58
| To: wren romano
| Cc: haskell
| Subject: Re: [Haskell-cafe] Inline makes program slow?
| 
| Compiler optimization levels are also important. The attached program
| compiles and runs ok using:
| 
| ghc -O fibmustopt.hs
| ./fibmustopt
| 
| But if the '-O' option is omitted all of the available memory is used
| and it fails.
| 
| 
| On Sun, Mar 30, 2014 at 2:56 AM, wren romano <winterkoninkje at gmail.com>
| wrote:
| > On Fri, Mar 28, 2014 at 9:43 PM, Kai Zhang <kai at kzhang.org> wrote:
| >> Without inline (remove the inline pragma), "slow" would be much
| >> faster. I suspect this is because ghc can build a "persistent
| >> structure" for the partial applied function. After inline, each call
| >> of "g" will try to build a new vector. How can I tell ghc not to
| >> inline some specific functions? Or are there other ways to resolve
| this issue?
| >
| > For what it's worth, I don't think this is an inlining issue, per se;
| > rather, it's an issue with the fact that eta-conversion does not
| > preserve performance characteristics. That is, when we inline h and
| > perform as much beta-reduction as we can, we're left with the lambda
| > expression:
| >
| >     \i -> (V.fromList $ sort str) V.! i
| >
| > Which is not necessarily the same thing, performance-wise, as:
| >
| >     ((V.fromList $ sort str) V.!)
| >
| > The problem is that, implicitly, the whole body of the lambda
| > abstraction (might) depend on the value of i and therefore cannot be
| > performed until we know what i is. If we wanted to make it explicit
| > that sorting the string is independent of the value of i, we could
| > write:
| >
| >     let s = V.fromList $ sort str in \i -> s V.! i
| >
| > By using let-binding to lift most of the computation out of the body
| > of the lambda abstraction, we ensure that the sorting will only be
| > done once, rather than (possibly) being done every time this function
| > is called.
| >
| > The reason I say "might" and "possibly" is because, in theory, the
| > compiler could choose to perform this transformation for you. And
| > sometimes it does (as apparently it does in your fast code). The
| > problem is that, in practice, performing this transformation
| > everywhere can slow things down horribly by taking too much memory
| > because you're trying to hold onto too many things. Thus, the
| compiler
| > must rely on heuristics to decide when it should float computations
| > out from under lambdas and when it shouldn't.
| >
| > --
| > Live well,
| > ~wren
| > _______________________________________________
| > Haskell-Cafe mailing list
| > Haskell-Cafe at haskell.org
| > http://www.haskell.org/mailman/listinfo/haskell-cafe