Haskell: can't use getCPUTime

Question

Hi

I have:

main :: IO ()
main = do
     iniciofibonaccimap <- getCPUTime
     let fibonaccimap = map fib listaVintesete
     fimfibonaccimap <- getCPUTime
     let difffibonaccimap = (fromIntegral (fimfibonaccimap - iniciofibonaccimap)) / (10^12)
     printf "Computation time fibonaccimap: %0.3f sec\n" (difffibonaccimap :: Double)

listaVintesete :: [Integer]
listaVintesete = replicate 100 27

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

But

*Main> main
Computation time fibonaccimap: 0.000 sec

I do not understand why this happens. Help-me thanks.

Answer 1

10^12 is an integer, which forces the value of fromIntegral to be an integer, which means difffibonaccimap is assigned a rounded value, so it's 0 if the time is less than half a second. (That's my guess, anyway. I don't have time to look into it.)

Answer 2

Haskell is lazy. The computation you request in the line

let fibonaccimap = map fib listaVintesete

doesn't actually happen until you somehow use the value of fibonaccimap. Thus to measure the time used, you'll need to introduce something that will force the program to perform the actual computation.

ETA: I originally suggested printing the last element to force evaluation. As TomMD points out, this is nowhere near good enough -- I strongly recommend reading his response here for an actually working way to deal with this particular piece of code.

Answer 3

I suspect you are a "victim" of lazy evaluation. Nothing forces the evaluation of fibonaccimap between the timing calls, so it's not computed.

Edit I suspect you're trying to benchmark your code, and in that case it should be pointed out that there are better ways to do this more reliably.

Answer 4

As others have said, this is due to lazy evaluation. To force evaluation you should use the deepseq package and BangPatterns:

{-# LANGUAGE BangPatterns #-}
import Control.DeepSeq
import Text.Printf
import System.CPUTime

main :: IO ()
main = do
 iniciofibonaccimap <- getCPUTime
 let !fibonaccimap = rnf $ map fib listaVintesete
 fimfibonaccimap <- getCPUTime
 let difffibonaccimap = (fromIntegral (fimfibonaccimap - iniciofibonaccimap)) / (10^12)
 printf "Computation time fibonaccimap: %0.3f sec\n" (difffibonaccimap :: Double)
...

In the above code you should notice three things:

1. It compiles (modulo the ... of functions you defined above). When you post code for questions please make sure it runs (iow, you should include imports)
2. The use of rnf from deepseq. This forces the evaluation of each element in the list.
3. The bang pattern on !fibonaccimap, meaning "do this now, don't wait". This forces the list to be evaluated to weak-head normal form (whnf, basically just the first constructor (:)). Without this the rnf function would itself remain unevaluated.

Resulting in:

$ ghc --make ds.hs
$ ./ds
Computation time fibonaccimap: 6.603 sec

If you're intending to do benchmarking you should also use optimization (-O2) and the Criterion package instead of getCPUTime.

Answer 5

Lazy evaluation has in fact bitten you, as the other answers have said. Specifically, 'let' doesn't force the evaluation of an expression, it just scopes a variable. The computation won't actually happen until its value is demanded by something, which probably won't happen until an actual IO action needs its value. So you need to put your print statement between your getCPUTime evaluations. Of course, this will also get the CPU time used by print in there, but most of print's time is waiting on IO. (Terminals are slow.)