> < ^ Date: Fri, 03 Dec 1993 03:54:00 +0100
> < ^ From: Mark Short <short@jordan.murdoch.edu.au >
> ^ Subject: space management

Dear GAP forum,

Recently I have been using GAP in circumstances where space conservation is all
important. I have three separate comments arising out of my experiences.

Comment 1
----------
The GAP function Profile() is very helpful for finding out where GAP spends all
its time. I wish there was a SpaceProfile() function that would give you some
idea of how much space is being used by various areas of your code. It would be
nice to be able find out how much space is being used by each and every
variable, but perhaps that's asking for too much. Anyway, is there any chance
of getting a function along these lines in the future?

Comment 2
----------
One of the tricks I tried in order to conserve space was to Unbind
space-expensive variables as soon as I had finished with them.
This presumably de-references a chunk of memory and so makes
it available for new variables. However, I found the behaviour of Unbind to be
rather puzzling. In the following simple example I create a long list, list1,
of integers and then Unbind it. Then I do the same thing but with a different
variable name, list2. I would expect GAP to be able to create list2 in no more
space than it needed for list1, but this doesn't seem to happen. Here is the
code:

-------------GAP input------------

# To test storage manager

big := 1000000;;

Print( "Making 1st list\n" );
list1 := [ ];;
list1[ big ] := 1;;
for i in [1..big] do
   list1[ i ] := 1;
od;
Print( "Done\n" );

Print( "Unbinding 1st list\n" );
Unbind( list1 );
Print( "Done\n" );

Print( "Making 2nd list\n" );
list2 := [ ];;
list2[ big ] := 1;;
for i in [1..big] do
   list2[ i ] := 1;
od;
Print( "Done\n" );

Print( "Unbinding 2nd list\n" );
Unbind( list2 );
Print( "Done\n" );

Print( "Making 3rd list\n" );
list3 := [ ];;
list3[ big ] := 1;;
for i in [1..big] do
   list3[ i ] := 1;
od;
Print( "Done\n" );

Print( "Unbinding 3rd list\n" );
Unbind( list3 );
Print( "Done\n" );

Print( "Making 4th list\n" );
list4 := [ ];;
list4[ big ] := 1;;
for i in [1..big] do
   list4[ i ] := 1;
od;
Print( "Done\n" );

Print( "Unbinding 4th list\n" );
Unbind( list4 );
Print( "Done\n" );

Print( "Making 5th list\n" );
list5 := [ ];;
list5[ big ] := 1;;
for i in [1..big] do
   list5[ i ] := 1;
od;
Print( "Done\n" );

-----------End GAP input---------------

If I call ``gap -q -g -m 1m'' I get the following.

-----------GAP output------------

Making 1st list
#G  collect garbage,   2547 used,    509 dead,    668 KB free,   1024 KB total
Done
Unbinding 1st list
Done
Making 2nd list
#G  collect garbage,   2550 used,     22 dead,   1065 KB free,   5327 KB total
Done
Unbinding 2nd list
Done
Making 3rd list
#G  collect garbage,   2551 used,     23 dead,   5948 KB free,  10210 KB total
Done
Unbinding 3rd list
Done
Making 4th list
#G  collect garbage,   2552 used,     23 dead,   5948 KB free,  10210 KB total
Done
Unbinding 4th list
Done
Making 5th list
#G  collect garbage,   2553 used,     23 dead,   5948 KB free,  10210 KB total
Done

-----------End GAP output----------

It seems that GAP doesn't discover the space freed up by Unbinding list1,
list2 or list3 until it creates list4. Yet after that it seems happy to work
in the space it has, namely 10210 KB. However, this is 10 times more space than
was needed for the first list. (Though I realise that not all of the 10210 is
necessarily being used.)
Am I interpreting the garbage collection messages wrongly?

Another, less elegant, way to (almost) get rid of unwanted variables is to
give them trivial values. In the above example, instead of Unbinding list1 I
could set list1 := [ ] and similarly for the other lists. This gives
improved performance (at least in this example): The first two garbage
collection messages are the same as above, but the next three are the same as
the second one. That is, GAP's final workspace is 5327 KB. This is much better
than before. Nevertheless, seeing as list1 fits in 1 Meg, shouldn't the second
one too?

Are there other ways to reclaim space used by unwanted variables?

Comment 3
----------
My GAP code was unexpectedly using vast quantities of space. I finally tracked
down the problem to RankMat(). After further experiments I realised that the
problem wasn't actually RankMat() at all, but my poor understanding of how
much space some of GAP's data structures use. Now I'm wiser, but I hope this
third comment can help some other users.

Basically, I had some very large square matrices of zeros and ones, and I
needed to find their ranks. However, I actually needed their ranks over the
field GF(2), and so I couldn't call RankMat() directly. By reading the code
for RankMat() I learned that it is clever enough to cope with matrices over
various fields.
[By the way, giving users the source code for functions is a fantastic idea, as
this illustrates.]
So I made my matrices into ones over GF(2) by saying mat := mat * Z(2), and
then called RankMat( mat ). More experienced users may now see the problem:
A 1000 by 1000 matrix of entries from GF(2) takes up **much** more space than a
1000 by 1000 matrix of zeros and ones. (Workspaces of 31559 KB and 4929 KB,
respectively.) Once I had figured this out (it took a long time), the solution
was easy: I wrote my own RankMat2() which is just the same as RankMat but
customized to accept only integer matrices and to do all arithmetic modulo 2.
There! Problem fixed, and lots of space saved.

As I said, this problem occurred because I didn't realise there would be such a
difference in space usage for the two different matrices. In hindsight, I
should have known that integers are cheaper to store than field elements.
However, if I were comparing more complicated data structures I probably would
have no idea what differences there might be in space usage. Hence my request
in Comment 1 for a SpaceProfile() command.

Well, that's all from me. Sorry for taking up so much space!

Mark Short
Mathematics Programme
Murdoch University
Perth, Western Australia


> < [top]