[Haskell-cafe] different performance of equivalent expression

[Matthew Brecknell]

> I've run into strange effect that I can not explain. I have simple
> expression that can be written by two equivalent ways. However one way
> give much performance gain over another. Here is an example:
> 
> -- apply function many times (tail-recursive)
> many n f x = if n == 0 then x else many (n-1) f $! (f x)
> 
> -- first adder function
> adder1 = let r = many 5000000 sin 1.0 in \x -> x + r
> 
> -- second adder function
> adder2 = \x -> x + many 5000000 sin 1.0
> 
> main = do
>   putStrLn $ show $ adder1 1
>   putStrLn $ show $ adder1 2
>   putStrLn $ show $ adder1 3
>   putStrLn $ show $ adder1 4
>   putStrLn $ show $ adder2 1
>   putStrLn $ show $ adder2 2
>   putStrLn $ show $ adder2 3
>   putStrLn $ show $ adder2 4
> 
> If you run program it think some seconds performing math, and them
> prints 4 results immediately. But with adder2 function, it perform
> calculation in every call, which can be seen visually.
> 
> It seems that compiler is able to "cache" in some way long computation
> in first case, but not in second.

Haskell implementations are allowed, but not required, to make use of
referential transparency to substitute expressions for their results
(and vice versa). The way I understand your example, it is entirely
implementation dependent whether the result of "many 5000000 sin 1.0" is
reused from one application to the next. Certainly, with GHC it does
depend on the amount of optimisation applied. With -O, GHC spits out all
8 results at once.

I agree that Haskell, and laziness in particular, does require you to
have some appreciation for the way the implementation performs. I can
only guess that in the unoptimised case, it's easy for GHC to see the
common subexpression in adder1, because you've given it a name, but it's
not looking hard enough to find it in adder2. With optimisation, it's
smart enough to resuse the result across both functions.

So my advice here would be: always try the optimiser before you worry
too much about strange performance!

> I always thought that let a = b in x + a is just a syntactic sugar for x
> + b. Is it wrong?

In general, let expressions are more than simple syntactic sugar. Let
expressions introduce lexical scope, allow mutually recursive bindings,
and use irrefutable (lazy) pattern matching. See the report, section
3.12 for the details.

The part that is probably most surprising to the unaware is that let
bindings always use lazy pattern matching. The Gentle Introduction,
section 4.4, explains lazy pattern matching better than I can:

http://www.haskell.org/tutorial/