Better eta reduction gains asymptotic performance
Here is a remarkable program, from #7436 (closed)
data Nat = Z | S Nat mkNat :: Int -> Nat mkNat 0 = Z mkNat n = S (mkNat (n-1)) unNat :: Nat -> () unNat Z = () unNat (S n) = unNat n fast :: (b -> b) -> b -> Nat -> b fast s z Z = z fast s z (S n) = s (fast s z n) slow :: (b -> b) -> b -> Nat -> b slow s z Z = z slow s z (S n) = s (slow (\e -> s e) z n) main :: IO () --main = print $ unNat . fast S Z . mkNat $ n main = print $ unNat . slow S Z . mkNat $ n where n = 100000
slow it takes 8 seconds to run; using
fast it is instantaneous.
The only difference between
fast is the eta-expansion in
yet it causes an asymptotic slowdown! See this comment
for how this very surprising behaviour occurs.
Why can't GHC eta-reduce the lambda in
- It does not know that
- It worries that
slow(the function to which
(\e -> s e)is passed) migth do a
seqon the argument.
Indeed (1) might happen. But (2) does not! So eta-reduction would be valid.
Moreover, the demand analyser discovers this signature for
C(U) says that
s is only called, not seq'd. If we change
slow s z Z = s `seq` z
then we get
So the opportunity is to somehow make eta-reduction sensitive to the enclosing demand. I had a quick look at the Simplifier, and while I think it's possible, I don't think it's especially easy. Something like:
- Put the demand in the
- Pass the continuation to
SimplUtils.mkLamin the call in
That is quite a lot of fiddling for a relatively narrow case. But still, it hurts to lose asymptotic perf from something so trivial.