[Haskell-cafe] Inline makes program slow?

[wren romano]

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