[Haskell-cafe] Question about memory usage

[Sebastian Fischer]

On Aug 17, 2010, at 12:33 AM, Jason Dagit wrote:

> So next I would use heap profiling to find out where and what type  
> of data the calculation is using.

I did.

> I would do heap profiling and look at the types.

All retained data is of type ARR_WORDS. Retainer profiling shows that  
the majority is retained by the cost center SYSTEM.

I suspected that a strict, tail recursive version of `matrixPower` may  
be more efficient and implemented it:

     http://github.com/sebfisch/fibonacci/blob/tailrec/Data/Numbers/Fibonacci.hs

But it's worse. Still, the only retained data is of type ARR_WORDS  
mostly retained by SYSTEM but even more of it now. Additional bang  
patterns on `square` and `times` make no difference.

I wonder whether the numbers in a single step of the computation  
occupy all the memory or whether old numbers are retained although  
they shouldn't be. Are (even large) Integers evaluated completely when  
forcing their head-normal form?

Any insight of a performance guru is welcome ;)

Cheers,
Sebastian

[off topic post scriptum]

On Aug 16, 2010, at 6:03 PM, Jacques Carette wrote:

> Any sequence of numbers given by a linear recurrence equation with  
> constant coefficients can be computed quickly using asymptotically  
> efficient matrix operations.  In fact, the code to do this can be  
> derived automatically from the recurrence itself.

This is neat. Is it always M^n for some matrix M? How does it work?

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



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100817/3cf71b15/attachment-0001.html