From: Ritwik Banerjee Date: 2010-11-01T14:18:55+09:00 Subject: Re: Ruby 1.9.1 linear memory increase in a simple for loop. Calamitas wrote in post #958323: > On Sat, Oct 30, 2010 at 12:12 PM, Ritwik Banerjee > wrote: >> I had thought of that too. But, as you can see, in this particular >> example I only raise it to the 100th power with an initial binary >> matrix. The numbers don't get big enough to explain the kind of memory >> increase I see. Also, an increase in the size of integers should not >> increase the number of objects in classes like T_ARRAY, T_HASH, >> T_STRUCT, right? > > Ruby's garbage collector is triggered by the number of objects > exceeding a threshold, and not their total size. So it is entirely > possible for a Ruby process to eat up all your computer's memory > without Ruby's garbage collector ever kicking in because the process > allocates few large objects rather than many small objects. This has > been a problem for libraries such as RMagick (Google for RMagick and > memory leaks), and they mitigate it by triggering garbage collection > explicitly. > >> Another point: If I use a matrix from my actual project, however, even >> going up to 25 iterations consumes almost my entire 2GB RAM. There too, >> the initial matrix consists only of 0/1 entries. In 25 iterations, I >> don't think it should be anywhere near 2GB! > > Hmmm, I never ran your program to check the actual memory consumption, > I just looked at the matrix and the entries. On my machine I don't see > the memory usage growing for your example. And you are right, for your > example the numbers aren't that large yet. > > Note though that even if it is a binary matrix, the entries do grow > exponentially depending on the number of 1's per row/column and the > size of the matrix. In the example you gave the entries increase by a > factor of a bit more than 5. If you had all ones, the factor would > have been 8 which is the size of the matrix. How close it is to this > maximum depends on the fraction of ones in the matrix and on their > distribution (or rather their pattern). > >> Even so, do you think it is a good idea to cast into float at every >> iteration to see if that helps? I've avoided floats because of problems >> such as (0.3 - 0.2 == 0.1) returns false. > > It depends on what you want to do with the result. Matrix > multiplication where the entries are all non-negative is stable (your > binary matrix satisfies this condition, as well as any powers of that > matrix). This does not mean that the results will be exact, but it > does mean that rounding errors only grow slowly. > > Personally, I would just try floats for your specific case and see if > you can use the results. Note that "zeroness" will always be exact, so > if the matrix happens to represent an adjacency matrix and you are > mostly interested in which entries are zero and which are not, then > you can safely use floats. > > Note that you can speed up calculating a specific power of a matrix > more efficiently as outlined in here: > http://en.wikipedia.org/wiki/Exponentiation#Efficiently_computing_an_integer_power > . The advantage of this is that you do fewer multiplications and you > will have smaller rounding errors in the case of floats. > > Peter Thanks a lot for this detailed reply, Peter. I did, however, try the same for-loop with explicit calls to the garbage collector. That slowed down the increase in memory usage, but negligibly. I also restricted the number of decimal places of each float to 6 (just to see whether the number of bits taken up by each number can collectively matter so much), but that didn't change anything. So, to sum it up, the memory usage can't be reduced by explicit calls to the garbage collector at each iteration, and it can't be reduced by restricting the number of bits used by each number. -- Posted via http://www.ruby-forum.com/.