[Haskell-cafe] different performance of equivalent expression
alex at sectorb.msk.ru
Fri Jan 12 15:54:17 EST 2007
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.
I always thought that let a = b in x + a is just a syntactic sugar for x
+ b. Is it wrong?
Of course, this is just a toy example. In reality I was writing run-time
compilation. Suppose, you have an simple arithmetic expression with
data Expr = Var String | Add Expr Expr | Mul Expr Expr | ...
type Env = Map.Map String Double
compile :: Expr -> (Env -> Double)
compile e =
case e of
Var n -> \env -> env Map.! n
Add e1 e2 -> \env -> (compile e1) env + (compile e2) env
Mul e1 e2 -> \env -> (compile e1) env * (compile e2) env
The same thing occur here. Expressions (compile e1) and (compile e2) are
re-evaluated every time when compiled expression is run with some environment.
So, it is much more an interpretation than compilation. I want that compile
function returns expression that are pre-evaluated as much as possible to
maximally speed up subsequent evaluation in different environments. How can I
force (compile e1) to be evaluated eagerly in case line for Add/Mul?
P.S. I'm using GHC 6.6 on Debian Linux (x86 arch).
With best regards,
More information about the Haskell-Cafe