 Classic List Threaded 27 messages 12
Open this post in threaded view
|

 I was reading this article:http://scienceblogs.com/goodmath/2009/11/writing_basic_functions_in_has.php And came to the part where it shows:``` > fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist)) ```Very interesting stuff for somebody who comes from an imperative world of course.But then I read that "Once it's been referenced, then the list up to where you looked is concrete - the computations won't be repeated." and I started wondering how that works.Because this seems to mean that functions could have unknown (to the caller) memory requirements. How does one, programming in Haskell, keep that in check?And when does that memory get reclaimed?Cheers,-Tako _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 Tako Schotanus wrote: > > fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist)) >   > > Very interesting stuff for somebody who comes from an imperative world > of course. Oh yes, that old chestnut. There's a page on the wiki somewhere with a whole collection of these cryptic one-liners - Pascal's triangle, the prime numbers, the Fibonacci numbers, etc. > But then I read that "Once it's been referenced, then the list up to > where you looked is concrete - the computations /won't/ be repeated." > and I started wondering how that works. fiblist is a global variable. It points to a list calculation expression. When a list cell is calculated, the calculation node is overwritten with the result of the calculation. When you access the list, you look at each cell; if it's already done, you just use it. If it's not done, execute it and then use it. (How it actually works below that is a problem for the runtime engine to figure out, and varies by Haskell implementation. For example, GHC uses the spineless tagless G-machine.) > Because this seems to mean that functions could have unknown (to the > caller) memory requirements. Yes. > How does one, programming in Haskell, keep that in check? ...and here begins an entire textbook that nobody has published yet. > And when does that memory get reclaimed? It's called "garbage collection". The memory is reclaimed when it becomes unreachable becuase there are no pointers to it left. In the example above, fiblist is a global variable, so the answer to "when does it get freed?" would be "never". (I believe it's called a CAF leak.) Whether this is very cool or a major performance issue depends on your point of view; you're trading space for time. (Then again, the Fibonacci numbers can be computed in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so this is obviously example code.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Andrew Coppin In the example above, fiblist is a global variable, so the answer to "when does it get freed?" would be "never". (I believe it's called a CAF leak.)  Is that actually true? I've heard lots of references to this, but I'm not sure it is true. Sure, it's harder for it to get collected when everyone can potentially access it, but the mechanisms for checking who holds pointers to a value are still valid for CAFS, and collection can still work on them, I think. The commentary at http://is.gd/ehEuL seems to suggest that CAFs can be garbage collected, too. My apologies for confusing the issue, if this is not correct, though!Dan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Andrew Coppin On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin <[hidden email]> wrote: >  (Then again, the Fibonacci numbers can be computed > in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so > this is obviously example code.) A bit off-topic, but I don't think there exists a function that computes fibonacci numbers in O(1) time. There exists a closed-form expression to calculate the nth Fibonacci number, but the complexity of that expression is not O(1): phi = (1 + sqrt 5) / 2 fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 The use of (**) should make the complexity at least O(n). Please correct me if I'm wrong (or sloppy). Regards, Roel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 On Monday 16 August 2010 14:37:34, Roel van Dijk wrote: > On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin > > <[hidden email]> wrote: > >  (Then again, the Fibonacci numbers can be computed > > in O(1) time, and nobody ever needs Fibonacci numbers in the first > > place, so this is obviously example code.) > > A bit off-topic, but I don't think there exists a function that > computes fibonacci numbers in O(1) time. There exists a closed-form > expression to calculate the nth Fibonacci number, but the complexity > of that expression is not O(1): > > phi = (1 + sqrt 5) / 2 > fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 > > The use of (**) should make the complexity at least O(n). Using Double for phi and  n, that expression is calculated in constant time. If you use (^) or (^^) instead of (**) and use Int [or Integer and neglect the compexity of Integer arithmetic, assuming additions and divisions of Integers to be O(1)] for n, it's O(log n). However, whether using (**), (^) or (^^), with Double for phi, that formula gives wrong results even for rather small n (> 70 resp. > 75). You can calculate the n-th Fibonacci number in O(log n) steps using Integer arithmetic to get correct results. Multiplying two Integers with k bits takes O(k^(1+ x)) with 0 < x <= 1, the exact value of x depends on the used algorithm of course. I don't remember what's the best found so far, but x < 0.5 is reached. Since the abovementioned O(log n) steps algorithm includes multiplication of Integers with Theta(n) bits, its complexity is O(n^(1 + y)) for some y >= x. > Please correct me if I'm wrong (or sloppy). > > Regards, > Roel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 [continuing off topic] On Aug 16, 2010, at 3:13 PM, Daniel Fischer wrote: > You can calculate the n-th Fibonacci number in O(log n) steps using   > Integer > arithmetic to get correct results. Yes, I was delighted when I saw this for the frist time. It works be   computing      /1 1\^n      \1 0/ (This is meant to be a matrix to the nth power) by repeated squaring.   Wikipedia knows the details:      http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_formMy Haskell implementation of this approach is on Hackage:      http://hackage.haskell.org/package/fibonacciand github:      http://github.com/sebfisch/fibonacci/blob/master/Data/Numbers/Fibonacci.hsWith this implementation,  printing  the result of a call to, say      fib 100000000 takes *much* longer than  computing  it. [almost on topic again] I am a bit concerned about the memory usage. If you know how to fix   it, please send me patches (ideally via github)! Cheers, Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 [CC-ing café again] On Aug 16, 2010, at 5:52 PM, Daniel Fischer wrote: >> I am a bit concerned about the memory usage. > > Of your implementation of the matrix power algorithm? Yes. > Making the fields of Matrix strict should help: > > data Matrix a = Matrix !a !a !a Making all fields strict makes memory usage worse. When making only   the first field strict, memory usage hardly differs (from the current   implementation without strictness annotations). Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Sebastian Fischer Since we're off-topic... 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. Here is what you get for Fibonacci (using Maple):  > re := {fib(n+2) = fib(n+1) + fib(n)}; inits := {fib(0) = 1, fib(1) = 1};                      {fib(n + 2) = fib(n + 1) + fib(n)}                           {fib(0) = 1, fib(1) = 1}  > gfun[rectoproc](re union inits, fib(n)); proc (n)     local i1, loc0, loc1, loc2, tmp2, tmp1, i2;     if n <= 44 then         loc0 := 1; loc1 := 1;         if n < 0 then error "index must be %1 or greater", 0         elif n = 0 then return loc0         elif n = 1 then return loc1         end if;         for i1 to n-1 do loc2 := loc0+loc1; loc0 := loc1; loc1 := loc2 end do;         loc1     else         tmp2 := Matrix(2, 2, {(1, 1) = 1, (1, 2) = 1, (2, 1) = 1, (2, 2) = 0});         tmp1 := Vector(2, {(1) = 1, (2) = 1});         i2 := convert(n-1, base, 2);         if i2 = 1 then tmp1 := Vector(2, {(1) = 2, (2) = 1}) end if;         for i1 in subsop(1 = (), i2) do             tmp2 := LinearAlgebra:-MatrixMatrixMultiply(tmp2, tmp2);             if i1 = 1 then tmp1 := LinearAlgebra:-MatrixVectorMultiply(tmp2, tmp1) end if         end do;         tmp1     end if end proc Direct computation is done for small n, and then asymptotically fast linear algebra is used for larger n. This should be a nice Template Haskell exercise. Jacques Sebastian Fischer wrote: > [continuing off topic] > > On Aug 16, 2010, at 3:13 PM, Daniel Fischer wrote: > >> You can calculate the n-th Fibonacci number in O(log n) steps using >> Integer >> arithmetic to get correct results. > > Yes, I was delighted when I saw this for the frist time. It works be > computing > >     /1 1\^n >     \1 0/ > > (This is meant to be a matrix to the nth power) by repeated squaring. > Wikipedia knows the details: > >     http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form> > My Haskell implementation of this approach is on Hackage: > >     http://hackage.haskell.org/package/fibonacci> > and github: > >     > http://github.com/sebfisch/fibonacci/blob/master/Data/Numbers/Fibonacci.hs  > > > With this implementation,  printing  the result of a call to, say > >     fib 100000000 > > takes *much* longer than  computing  it. > > [almost on topic again] > > I am a bit concerned about the memory usage. If you know how to fix > it, please send me patches (ideally via github)! > > Cheers, > Sebastian > > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Roel van Dijk-3 Roel van Dijk wrote: > On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin > <[hidden email]> wrote: >   >>  (Then again, the Fibonacci numbers can be computed >> in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so >> this is obviously example code.) >>     > > A bit off-topic, but I don't think there exists a function that > computes fibonacci numbers in O(1) time. There exists a closed-form > expression to calculate the nth Fibonacci number, but the complexity > of that expression is not O(1): > > phi = (1 + sqrt 5) / 2 > fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 > > The use of (**) should make the complexity at least O(n). Please > correct me if I'm wrong (or sloppy). >   This depends on your definition of "operation". As somebody else pointed out, if you're only dealing with limited-precision arithmetic, you can probably consider all the arithmetic operations to be O(1), in which case the Nth Fibonacci number is O(1). Only if you're dealing with utterly huge numbers do you need to even care about how long it takes to add two numbers. This neatly leads us back to my second assertion: In all my years of computer programming, I've never seen one single program that actually *needs* the Fibonacci numbers in the first place (let alone in arbitrary-precision). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 On Mon, Aug 16, 2010 at 1:37 PM, Andrew Coppin <[hidden email]> wrote: > > This neatly leads us back to my second assertion: In all my years of > computer programming, I've never seen one single program that actually > *needs* the Fibonacci numbers in the first place (let alone in > arbitrary-precision). > I think there are variants on AVL trees that use something related to a Fibonacci sequence for balancing. I don't remember the details, though. Antoine _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Sebastian Fischer On Mon, Aug 16, 2010 at 9:00 AM, Sebastian Fischer wrote: [CC-ing café again] On Aug 16, 2010, at 5:52 PM, Daniel Fischer wrote: I am a bit concerned about the memory usage. Of your implementation of the matrix power algorithm? Yes. Making the fields of Matrix strict should help: data Matrix a = Matrix !a !a !a Making all fields strict makes memory usage worse. When making only the first field strict, memory usage hardly differs (from the current implementation without strictness annotations).That's interesting.  So next I would use heap profiling to find out where and what type of data the calculation is using.  I would do heap profiling and look at the types.  The strictness above should when there are lots of thunks in memory for computing the values in the Matrix. To get started at this task, I recommend the chapter on performance from Real-World Haskell:http://book.realworldhaskell.org/read/profiling-and-optimization.html I'd love to hear what you learn as I probably won't have time to poke at it.Jason _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Antoine Latter-2 There's a Fibonacci Heap: http://en.wikipedia.org/wiki/Fibonacci_heapNot sure what else though :)On Mon, Aug 16, 2010 at 11:14 PM, Antoine Latter wrote: On Mon, Aug 16, 2010 at 1:37 PM, Andrew Coppin <[hidden email]> wrote: > > This neatly leads us back to my second assertion: In all my years of > computer programming, I've never seen one single program that actually > *needs* the Fibonacci numbers in the first place (let alone in > arbitrary-precision). > I think there are variants on AVL trees that use something related to a Fibonacci sequence for balancing. I don't remember the details, though. Antoine _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Roel van Dijk-3 On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote: > > phi = (1 + sqrt 5) / 2 > fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 > > The use of (**) should make the complexity at least O(n). Please > correct me if I'm wrong (or sloppy). Using the classic         x**0 = 1         x**1 = x         x**(2k+0) = (x**2)**k k > 0         x**(2k+1) = (x**2)**k + x k > 1 powers of smallish numbers or matrices can be computed in logarithmic time. Using x**n = exp(n*log(x)) and floating point arithmetic, the whole thing can be done in O(1) time, and the price of some inaccuracy.  Using double precision arithmetic, I get fib(52) = 32951280099.0001 which is clearly wrong.  Truncation will save you, up to fib(72) = 498454011879265.1875 which is wrong in the units place. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 On Tue, Aug 17, 2010 at 3:53 AM, Richard O'Keefe <[hidden email]> wrote: > On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote: >> >> phi = (1 + sqrt 5) / 2 >> fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 >> >> The use of (**) should make the complexity at least O(n). Please >> correct me if I'm wrong (or sloppy). > > Using the classic >        x**0 = 1 >        x**1 = x >        x**(2k+0) = (x**2)**k           k > 0 >        x**(2k+1) = (x**2)**k + x       k > 1 > powers of smallish numbers or matrices can be computed in logarithmic > time. That is an interesting trick. So there exists an algorithm that calculates Fibonacci numbers in O(log n) time. > Using x**n = exp(n*log(x)) and floating point arithmetic, > the whole thing can be done in O(1) time, and the price of > some inaccuracy. It will calculate a subset of the Fibonacci numbers in O(1) time. Thinking about it I think you can easily calculate subsets of any function in O(1) time, as long as the function is guaranteed to terminate. Simply precompute the answers and store them in an array. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Jason Dagit-2 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: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.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 In reply to this post by Roel van Dijk-3 On Aug 17, 2010, at 8:39 AM, Roel van Dijk wrote: > That is an interesting trick. So there exists an algorithm that > calculates Fibonacci numbers in O(log n) time. This is what my program does. But it's only O(long n) if you assume   multiplication is constant time (which it is not for large numbers). Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Question about memory usage

 Sebastian Fischer <[hidden email]> writes: > On Aug 17, 2010, at 8:39 AM, Roel van Dijk wrote: > >> That is an interesting trick. So there exists an algorithm that >> calculates Fibonacci numbers in O(log n) time. > > This is what my program does. But it's only O(long n) [snip] Are you getting Haskell mixed up with C or something?  We don't have a "long" value type... ;-) -- Ivan Lazar Miljenovic [hidden email] IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe