CODEWITHSUNDEEP
haskellmemoization
Chris Stryczynski
Chris Stryczynski

Reputation: 33881

How can I determine if a function is being memoized in Haskell?

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.

Upvotes: 5

Views: 228

Answers (2)

Chris Stryczynski
Chris Stryczynski

Reputation: 33881

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

Upvotes: 0

Thomas Mahler
Thomas Mahler

Reputation: 180

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

Upvotes: 1

Related Questions