[Haskell-cafe] Question about memory usage

[Sebastian Fischer]

> 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

I'm not sure how to interpret "bytes allocated" and "maximum  
residency" especially because the program spends no time during GC.  
But the 97 MB "total memory" correspond to what my process monitor  
shows.

> I have now tried your code and I didn't find the memory usage too  
> extreme.
> Be aware that fib (10^8) requires about 70 million bits and you need
> several times that for the computation.

Then, roughly ten 70m bit numbers fit into the total memory used:

     ghci> (97 * 1024^2 * 8) / (70 * 10^6)
     11.624213942857143

I expected to retain about three of such large numbers, not ten, and  
although the recursion depth is not deep I expected some garbage. Both  
expectations may be a mistake, of course.

> If the relation is
>
> a_n = c_1*a_(n-1) + ... + c_k*a_(n-k)
>
> you have the k×k matrix [...]
> to raise to the n-th power, multiply the resulting matrix with the  
> vector
> of initial values (a_(k-1), a_(k-2), ..., a_0) and take the last  
> component

Interesting.

> (a propos of this, your Fibonacci numbers are off by one, fib 0 = 0,  
> fib 9
> = 34, fib 10 = 55).

Wikipedia also starts with zero but states that "some sources" omit  
the leading zero. I took the liberty to do the same (and documented it  
like this) as it seems to match the algorithm better. It also  
corresponds to the rabbit analogy.

> These matrices have a special structure
> that allows doing a multiplication in O(k^2).
> You might want to look into the Cayley-Hamilton theorem for the  
> latter.

I don't see the link to the CH theorem yet -- probably because I  
didn't know it. I did observe that all matrices during the computation  
have the form

     /a b\
     \b c/

which simplifies multiplications. Is this related to CH? Or can I  
further improve the multiplications using insights from CH?

Sebastian

-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)