Re: Ruby 1.9.1 linear memory increase in a simple for loop.

On Sat, Oct 30, 2010 at 12:12 PM, Ritwik Banerjee
<[e-mail]> 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