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

[Petr P]

 Hi Carter,

2012/11/8 Carter Schonwald <carter.schonwald at gmail.com>

> 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
>

I'd say converting a recursive function into a non-recursive one using
`let` doesn't necessarily mean that it will get inlined. It's up to GHC if
it inlines the function or not, just as with other functions. So I don't
think this would be a problem.


>
> 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)
>

I didn't think of mutually recursive functions before. But I'd say they
could be optimized the same way, without an exponential code blowup, just
by creating more complex `let` expressions:

f u = somethingF u (f u) (g u)
g u = somethingG u (f u) (g u)

could be optimized as

fg u = let x = somethingF u x y ; y = somethingG u x y in (x,y)
f u = fst (fg u)
g u = snd (fg u)

So again, no recursion is at the top level, only within `let`, so both `f`
and `g` can be inlined if desired (and fst/snd/(,) will then get fused
away).

  Best regards,
  Petr


>
>
>
> 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/20121109/74b24516/attachment.htm>