lazy vs ST

lazy_vs_st.hs

{-# LANGUAGE BangPatterns, ViewPatterns #-}
import System.Environment (getArgs)
import Control.Monad
import Control.Monad.ST
import Data.STRef
import GHC.Int

fib1 :: Int -> Integer
fib1 n = fibs !! n
  where fibs = 1:1:zipWith (+) fibs (tail fibs)

-- def fib2(n):
--   a = b = 1
--   for i in range(n-1):
--       (a, b) = (b, a + b)
--   return b

fib2 :: Int -> Integer
fib2 n = runST $ do
    a <- newSTRef 1
    b <- newSTRef 1
    replicateM_ (n-1) $ do
        !a' <- readSTRef a
        !b' <- readSTRef b
        writeSTRef a b'
        writeSTRef b $! a'+b'
    readSTRef b

main = do
  [flag, read -> n] <- getArgs
  case flag of
    "lazy" -> print $ fib1 n
    _      -> print $ fib2 n

{-
$ time python fibs.py 100000 > /dev/null

real    0m0.190s
user    0m0.179s
sys     0m0.009s
$ time ./fibsst lazy 100000 > /dev/null

real    0m0.326s
user    0m0.300s
sys     0m0.025s
$ time ./fibsst st 100000 > /dev/null

real    0m0.061s
user    0m0.055s
sys     0m0.005s

$ ./fibsst lazy 100000 +RTS -s
     453,614,712 bytes allocated in the heap
     228,994,336 bytes copied during GC
       4,295,208 bytes maximum residency (222 sample(s))
      18,073,696 bytes maximum slop
              56 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       678 colls,     0 par    0.04s    0.05s     0.0001s    0.0020s
  Gen  1       222 colls,     0 par    0.20s    0.21s     0.0009s    0.0058s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.06s  (  0.06s elapsed)
  GC      time    0.24s  (  0.26s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.29s  (  0.32s elapsed)

  %GC     time      80.6%  (81.4% elapsed)

  Alloc rate    7,942,963,665 bytes per MUT second

  Productivity  19.3% of total user, 18.0% of total elapsed

$ ./fibsst st 100000 +RTS -s
     441,543,056 bytes allocated in the heap
         799,496 bytes copied during GC
           3,520 bytes maximum residency (1 sample(s))
          23,120 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       878 colls,     0 par    0.00s    0.01s     0.0000s    0.0000s
  Gen  1         1 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.04s  (  0.05s elapsed)
  GC      time    0.00s  (  0.01s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.05s  (  0.05s elapsed)

  %GC     time       9.3%  (10.5% elapsed)

  Alloc rate    10,007,548,695 bytes per MUT second

  Productivity  90.4% of total user, 86.0% of total elapse
-}