Thursday, July 9, 2009

GAMS: Mystery Memory

Q: When I use profiling I sometimes see memory usage I cannot explain.

I suspect this is related to the following. Consider the model:

set i/i1*i500/;
alias (i,j,k);
parameter a(i,j,k);
a(i,j,k)$(uniform(0,1)<0.1) = uniform(0,1);

parameter b1(i),b2(j),b3(k);
b1(i) =
sum((j,k),a(i,j,k));
b2(j) =
sum((i,k),a(i,j,k));
b3(k) =
sum((i,j),a(i,j,k));

When we run this with profiling on we see:

----      1 ExecInit                 0.000     0.000 SECS      3 Mb
----      4 Assignment a            20.779    20.779 SECS    410 Mb  12501427
----      7 Assignment b1            0.999    21.778 SECS    410 Mb    500
----      8 Assignment b2           11.544    33.322 SECS  1,216 Mb    500
----      9 Assignment b3           12.948    46.270 SECS  1,216 Mb    500

The assignment to a is somewhat expensive: we can do this faster (see http://yetanothermathprogrammingconsultant.blogspot.com/2009/07/fill-parameters-with-random-sparse-data.html). The memory use seems correct: 407 MB for 12501427 elements, which is about 34 bytes per nonzero element. We use the 64-bit version of GAMS. With the 32-bit we will see smaller numbers: 304 MB or about 25 bytes per element. (That explains why 64-bit versions are not faster as 32-bit version: they have to drag more Mb around as pointers use up more memory: 8 bytes vs. 4 bytes). This is all ok.

The assignment of b1 is also ok. It is fast and only adds 500 elements, so it does not even register in the total memory usage.

The assignment of b2 is strange. It is understandable it is slower: the summation is using indices in the “wrong” order. The sudden spike in memory usage is less obvious. The additional hefty 806 MB (approximately twice what is needed to store parameter a itself) is used internally to create faster access to parameter a. This automatic reordering option can be turned off with OPTION SYS11=1;. If we use this option the profile report looks like:

----      1 ExecInit                 0.000     0.000 SECS      3 Mb
----      1 Other                    0.000     0.000 SECS      4 Mb
----      5 Assignment a            20.467    20.467 SECS    410 Mb  12501427
----      8 Assignment b1            0.998    21.465 SECS    410 Mb    500
----      9 Assignment b2            7.925    29.390 SECS    410 Mb    500
----     10 Assignment b3           55.911    85.301 SECS    410 Mb    500

This report has the memory profile we expected. Note that the assignment b2 is actually faster without reordering. The assignment b3 however shows why reordering though expensive (in memory and CPU time) can really pay off. Note: the “Other” in the table is related to the handling of the OPTION SYS11.

So if you see unexpected large spikes in memory usage, this may well be related to the automatic reordering of symbols that can take place when assignments are not in the “correct” index order.