[Haskell-cafe] Why doesn't GHC optimize recursive functions by converting them into `let`?

[Carter Schonwald]

Hey Petr, interesting post! (and links)
I imagine that one issue that would make it not a default activity by GHC
is that this sort of strategy has the following implications:

1) ghc in general doesn't always want to inline.... in general, inlining
increases the size of code! and depending on how that happens that can
increase compilation time and sometime decrease performance. That said,
there are many instances where perfomance is

2) This approach *can* be extended to mutually recursive functions, but
again, the naive inlining to "depth k" would have on the order of ~ 2^k
code blow up potentially (or so I think offhand)

theres probably a few other problems with doing this automatically, but it
looks like a nice performance trick I may consider using time.

cheers
-Carter



On Thu, Nov 8, 2012 at 10:00 AM, Petr P <petr.mvd at gmail.com> wrote:

>   Hi,
>
> recently I found out that some recursive functions can be greatly
> optimized just by rewriting them using `let` so that they're not recursive
> themselves any more (only the inner let is). To give an example:
>
> > fix :: (a -> a) -> a
> > fix f = f (fix f)
>
> isn't optimized, because it's a recursive function and so it isn't inlined
> or anything. However, defining it as
>
> > fix f = let x = f x in x
>
> makes it much more efficient, since `fix` is not recursive any more, so it
> gets inlined and then optimized for a given argument `f`.
> (See
> http://stackoverflow.com/questions/12999385/why-does-ghc-make-fix-so-confounding
> )
>
> Another example is the well-known generic catamorphism function:
>
> > newtype Fix f = Fix { unfix :: f (Fix f) }
> >
> > catam :: (Functor f) => (f a -> a) -> (Fix f -> a)
> > catam f = f . fmap (catam f) . unfix
>
> is not optimized. When `catam` is used on a data structure such as [] or a
> tree, at each level `fmap` creates new constructors that are immediately
> consumed by `f`. But when written as
>
> > catam f = let u = f . fmap u . unfix in u
>
> this gets inlined and then optimized, and constructor creation/consumption
> is fused into very effective code.
> (See http://stackoverflow.com/q/13099203/1333025)
>
> As one comment asked, this seems like something GHC could do
> automatically. Would it be difficult? Is there a reason against it? I
> suppose in cases where it doesn't help, the additional `let` would get
> optimized away, so no harm would be done. And in cases like `fix` or
> `catam` the gain would be substantial.
>
>   Best regards,
>    Petr
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121108/148bb24b/attachment.htm>