[Haskell-cafe] Question about memory usage

[John van Groningen]

Sebastian Fischer wrote:
>>BTW, what sort of memory usage are we talking about here?
>
>I was referring to the memory usage of this program
>
>    import System.Environment
>    import Data.Numbers.Fibonacci
>
>    main :: IO ()
>    main = do n <- (read . head) `fmap` getArgs
>              (fib n :: Integer) `seq` return ()
>
>compiled with -O2 and run with +RTS -s:
>
>    ./calcfib 100000000 +RTS -s
>         451,876,020 bytes allocated in the heap
>              10,376 bytes copied during GC
>          19,530,184 bytes maximum residency (9 sample(s))
>          12,193,760 bytes maximum slop
>                  97 MB total memory in use (6 MB lost due to fragmentation)
>
>      Generation 0:    40 collections,     0 parallel,  0.00s,  0.00s elapsed
>      Generation 1:     9 collections,     0 parallel,  0.00s,  0.00s elapsed
>
>      INIT  time    0.00s  (  0.00s elapsed)
>      MUT   time   12.47s  ( 13.12s elapsed)
>      GC    time    0.00s  (  0.00s elapsed)
>      EXIT  time    0.00s  (  0.00s elapsed)
>      Total time   12.47s  ( 13.13s elapsed)
>
>      %GC time       0.0%  (0.0% elapsed)
>
>      Alloc rate    36,242,279 bytes per MUT second
>
>      Productivity 100.0% of total user, 95.0% of total elapsed
>..

You could try:

fibo :: Int -> Integer
fibo n
  = if n<=1 then fromIntegral n else
      if even n
         then let (f_nd2m1,f_nd2) = dfibo (n `quot` 2-1) in f_nd2 * (f_nd2 + (f_nd2m1+f_nd2m1))
         else let (f_nd2,f_nd2p1) = dfibo (n `quot` 2)   in f_nd2*f_nd2 + f_nd2p1*f_nd2p1
  where
    dfibo :: Int -> (Integer,Integer)
    dfibo n
      = if n<=1 then (fromIntegral n,1) else
          let (f_nd2,f_nd2p1) = dfibo (n `quot` 2) in
            if even n
              then let f_n = (f_nd2p1 + (f_nd2p1-f_nd2)) * f_nd2
                       f_np1 = f_nd2*f_nd2 + f_nd2p1*f_nd2p1
                   in  seq f_n (seq f_np1 (f_n,f_np1))
              else let f_n = f_nd2*f_nd2 + f_nd2p1*f_nd2p1
                       f_np1 = f_nd2p1 * (f_nd2p1 + (f_nd2+f_nd2))
                   in  seq f_n (seq f_np1 (f_n,f_np1))

It allocates less and has a smaller maximum residency: (ghc 6.12.2,windows 7 64)

     292,381,520 bytes allocated in the heap
          15,200 bytes copied during GC
      13,020,308 bytes maximum residency (8 sample(s))
       6,423,332 bytes maximum slop
              99 MB total memory in use (9 MB lost due to fragmentation)


  Generation 0:    29 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     8 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.02s elapsed)
  MUT   time    5.85s  (  5.88s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    5.85s  (  5.90s elapsed)

  %GC time       0.0%  (0.0% elapsed)

  Alloc rate    49,979,430 bytes per MUT second

  Productivity 100.0% of total user, 99.2% of total elapsed

instead of:

    451,864,588 bytes allocated in the heap
           8,600 bytes copied during GC
      17,362,424 bytes maximum residency (8 sample(s))
      11,332,592 bytes maximum slop
              99 MB total memory in use (9 MB lost due to fragmentation)

  Generation 0:    41 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     8 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.02s elapsed)
  MUT   time    9.11s  (  9.14s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    9.11s  (  9.16s elapsed)

  %GC time       0.0%  (0.0% elapsed)

  Alloc rate    49,598,449 bytes per MUT second

  Productivity 100.0% of total user, 99.5% of total elapsed

Kind regards.

John van Groningen