The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
(compiled with ghc --make -O2) Mattias
Hello Mattias, I think you will find this thread from the haskell-cafe mailing list quite helpful. Re: [Haskell-cafe] Memoization http://www.mail-archive.com/haskell-cafe@haskell.org/msg09924.html Also, the Haskell wiki contains comments about techniques for memoization along with references at the bottom. Haskell wiki Memoization: http://www.haskell.org/haskellwiki/Memoization Hope that helps. __ Donnie Jones On Thu, Dec 11, 2008 at 10:18 AM, Mattias Bengtsson < moonlite@dtek.chalmers.se> wrote:
The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
(compiled with ghc --make -O2)
Mattias
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Am Donnerstag, 11. Dezember 2008 16:18 schrieb Mattias Bengtsson:
The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
(compiled with ghc --make -O2)
Mattias
Not an expert, so I may be wrong. The way you wrote your function, you made it clear to the compiler that you want sharing, so it shares. With g 0 = 1 g n = g (n-1)*g (n-1) it doesn't, because the type of g is Num t => t -> t, and you might call it with whatever weird Num type, for which sharing might be a bad idea (okay, for this specific function I don't see how I would define a Num type where sharing would be bad). If you give g a signature like g :: Int -> Int, the compiler knows that sharing is a good idea and does it (cool thing aside: with module Main where f 0 = 1 f n = let a = f (n-1) in a*a main = do print (f 27) print (g 30) g 0 = 1 g n = g (n-1)*g (n-1) main still runs instantaneously, but g n takes exponential time at the ghci prompt. That's because in main the argument of g is defaulted to Integer, so it's shared.)
Hello Daniel, Thursday, December 11, 2008, 11:09:46 PM, you wrote: you is almost right. but ghc don't share results of function calls despite their type. it just assumes that value of any type may use a lot of memory even if this type is trivial :) example when automatic sharing is very bad idea is: main = print (sum[1..10^10] + sum[1..10^10])
Am Donnerstag, 11. Dezember 2008 16:18 schrieb Mattias Bengtsson:
The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
(compiled with ghc --make -O2)
Mattias
Not an expert, so I may be wrong. The way you wrote your function, you made it clear to the compiler that you want sharing, so it shares. With
g 0 = 1 g n = g (n-1)*g (n-1)
it doesn't, because the type of g is Num t => t -> t, and you might call it with whatever weird Num type, for which sharing might be a bad idea (okay, for this specific function I don't see how I would define a Num type where sharing would be bad). If you give g a signature like g :: Int ->> Int, the compiler knows that sharing is a good idea and does it (cool thing aside: with module Main where
f 0 = 1 f n = let a = f (n-1) in a*a
main = do print (f 27) print (g 30)
g 0 = 1 g n = g (n-1)*g (n-1)
main still runs instantaneously, but g n takes exponential time at the ghci prompt. That's because in main the argument of g is defaulted to Integer, so it's shared.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Am Donnerstag, 11. Dezember 2008 21:11 schrieb Bulat Ziganshin:
Hello Daniel,
Thursday, December 11, 2008, 11:09:46 PM, you wrote:
you is almost right. but ghc don't share results of function calls despite their type. it just assumes that value of any type may use a lot of memory even if this type is trivial :)
I may misunderstand you here. But if you give a type signature specifying a nice known type, I'm pretty sure ghc _does_ sharing (tried with Int -> Int and Integer -> Integer, g 200 instantaneous), at least with -O2. Without sharing, it would require 2^(n+1) - 1 calls to evaluate g n, that wouldn't be nearly as fast. Without the type signature, it must assume the worst, so it doesn't share.
example when automatic sharing is very bad idea is:
main = print (sum[1..10^10] + sum[1..10^10])
Depends on what is shared. Sharing the list would be a very bad idea, sharing sum [1 .. 10^10] would probably be a good idea.
Am Donnerstag, 11. Dezember 2008 16:18 schrieb Mattias Bengtsson:
The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
(compiled with ghc --make -O2)
Mattias
Not an expert, so I may be wrong. The way you wrote your function, you made it clear to the compiler that you want sharing, so it shares. With
g 0 = 1 g n = g (n-1)*g (n-1)
it doesn't, because the type of g is Num t => t -> t, and you might call it with whatever weird Num type, for which sharing might be a bad idea (okay, for this specific function I don't see how I would define a Num type where sharing would be bad). If you give g a signature like
g :: Int ->> Int,
the compiler knows that sharing is a good idea and does it (cool thing aside: with module Main where
f 0 = 1 f n = let a = f (n-1) in a*a
main = do print (f 27) print (g 30)
g 0 = 1 g n = g (n-1)*g (n-1)
main still runs instantaneously, but g n takes exponential time at the ghci prompt. That's because in main the argument of g is defaulted to Integer, so it's shared.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hello Daniel, Thursday, December 11, 2008, 11:49:40 PM, you wrote: sorry fo r noise, it seems that i know ghc worse than you
Am Donnerstag, 11. Dezember 2008 21:11 schrieb Bulat Ziganshin:
Hello Daniel,
Thursday, December 11, 2008, 11:09:46 PM, you wrote:
you is almost right. but ghc don't share results of function calls despite their type. it just assumes that value of any type may use a lot of memory even if this type is trivial :)
I may misunderstand you here. But if you give a type signature specifying a nice known type, I'm pretty sure ghc _does_ sharing (tried with Int -> Int and Integer ->> Integer, g 200 instantaneous), at least with -O2. Without sharing, it would require 2^(n+1) - 1 calls to evaluate g n, that wouldn't be nearly as fast. Without the type signature, it must assume the worst, so it doesn't share.
example when automatic sharing is very bad idea is:
main = print (sum[1..10^10] + sum[1..10^10])
Depends on what is shared. Sharing the list would be a very bad idea, sharing sum [1 .. 10^10] would probably be a good idea.
Am Donnerstag, 11. Dezember 2008 16:18 schrieb Mattias Bengtsson:
The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
(compiled with ghc --make -O2)
Mattias
Not an expert, so I may be wrong. The way you wrote your function, you made it clear to the compiler that you want sharing, so it shares. With
g 0 = 1 g n = g (n-1)*g (n-1)
it doesn't, because the type of g is Num t => t -> t, and you might call it with whatever weird Num type, for which sharing might be a bad idea (okay, for this specific function I don't see how I would define a Num type where sharing would be bad). If you give g a signature like
g :: Int ->> Int,
the compiler knows that sharing is a good idea and does it (cool thing aside: with module Main where
f 0 = 1 f n = let a = f (n-1) in a*a
main = do print (f 27) print (g 30)
g 0 = 1 g n = g (n-1)*g (n-1)
main still runs instantaneously, but g n takes exponential time at the ghci prompt. That's because in main the argument of g is defaulted to Integer, so it's shared.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Am Donnerstag, 11. Dezember 2008 21:56 schrieb Bulat Ziganshin:
Hello Daniel,
Thursday, December 11, 2008, 11:49:40 PM, you wrote:
sorry for noise, it seems that i know ghc worse than you
If only that were true. I just know that GHC's optimiser can do some rather impressive stuff when given appropriate types, so I tried. Meanwhile, I've confirmed that it does share (for Int and Integer) with -O1 and -O2, but not with -O0, by looking at the generated core. Cheers, Daniel
Mattias Bengtsson wrote:
The program below computes (f 27) almost instantly but if i replace the definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it takes around 12s to terminate. I realize this is because the original version caches results and only has to calculate, for example, (f 25) once instead of (i guess) four times. There is probably a good reason why this isn't caught by the compiler. But I'm interested in why. Anyone care to explain?
GHC does "opportunistic CSE", when optimizations are enabled. See http://www.haskell.org/haskellwiki/GHC:FAQ#Does_GHC_do_common_subexpression_... (http://tinyurl.com/33q93a) I've found it very hard to predict whether this will happen or not, from a given source code, because the optimizer will transform the program a lot and the "opportunistic CSE" rule may apply to one of the transformed versions. It's best to make sharing explicit when you need it, as you did below.
main = print (f 27)
f 0 = 1 f n = let f' = f (n-1) in f' * f'
Bertram
participants (5)
-
Bertram Felgenhauer -
Bulat Ziganshin -
Daniel Fischer -
Donnie Jones -
Mattias Bengtsson