I've got a Haskell program that is performing non linearly performance wise (worse then O(n)).
I'm trying to investigate whether memoization is taking place on a function, can I verify this? I'm familiar with GHC profiling - but I'm not too sure which values I should be looking at?
A work around is too just plug some values and observe the execution time - but it's not ideal.
As far as I know there is no automatic memoization in Haskell.
That said there seems to be an optimization in GHC that caches values for parameterless function like the following
rightTriangles = [ (a,b,c) |
c <- [1..],
b <- [1..c],
a <- [1..b],
a^2 + b^2 == c^2]
If you try out the following in GHCi twice, you'll see that the second call ist much faster:
ghci > take 500 rightTriangles
Not really an answer but should still be helpfull, memoization does not seem to make a difference in profiling output in terms of function "entries". Demonstrated with the following basic example:
module Main where
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibmemo = (map fib [0 ..] !!)
main :: IO ()
main = do
putStrLn "Begin.."
print $ fib 10
-- print $ fibmemo 10
With the above code the profiling output is:
individual inherited
COST CENTRE MODULE SRC no. entries %time %alloc %time %alloc
MAIN MAIN <built-in> 119 0 0.0 1.3 0.0 100.0
CAF Main <entire-module> 237 0 0.0 1.0 0.0 1.2
main Main Main.hs:(12,1)-(14,16) 238 1 0.0 0.2 0.0 0.2
fib Main Main.hs:(5,1)-(7,29) 240 177 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal <entire-module> 230 0 0.0 1.2 0.0 1.2
CAF GHC.IO.Encoding <entire-module> 220 0 0.0 5.4 0.0 5.4
CAF GHC.IO.Encoding.Iconv <entire-module> 218 0 0.0 0.4 0.0 0.4
CAF GHC.IO.Handle.FD <entire-module> 210 0 0.0 67.7 0.0 67.7
CAF GHC.IO.Handle.Text <entire-module> 208 0 0.0 0.2 0.0 0.2
main Main Main.hs:(12,1)-(14,16) 239 0 0.0 22.6 0.0 22.6
While if we comment out fib 10 and uncomment the fibmemo 10 we get:
individual inherited
COST CENTRE MODULE SRC no. entries %time %alloc %time %alloc
MAIN MAIN <built-in> 119 0 0.0 1.2 0.0 100.0
CAF Main <entire-module> 237 0 0.0 1.0 0.0 2.9
fibmemo Main Main.hs:9:1-29 240 1 0.0 1.6 0.0 1.6
fib Main Main.hs:(5,1)-(7,29) 242 177 0.0 0.0 0.0 0.0
main Main Main.hs:(12,1)-(15,20) 238 1 0.0 0.2 0.0 0.2
fibmemo Main Main.hs:9:1-29 241 0 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal <entire-module> 230 0 0.0 1.2 0.0 1.2
CAF GHC.IO.Encoding <entire-module> 220 0 0.0 5.3 0.0 5.3
CAF GHC.IO.Encoding.Iconv <entire-module> 218 0 0.0 0.4 0.0 0.4
CAF GHC.IO.Handle.FD <entire-module> 210 0 0.0 66.6 0.0 66.6
CAF GHC.IO.Handle.Text <entire-module> 208 0 0.0 0.2 0.0 0.2
main Main Main.hs:(12,1)-(15,20) 239 0 0.0 22.2 0.0 22.2