> < ^ Date: Thu, 16 Dec 1993 15:27:00 +0100
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: space management
In his e-mail message of 1993/12/03 Mark Short wrote

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?

The new GAP storage manager (Gasman), which will be part of version 4,
has support for this. There will not be a separate function, though.
'Profile' will profile both time and storage usuage. 'Profile' will
hopefully also be faster, i.e., have less influence on the measured code.

Mark Short continues

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:

[I took the freedom to replace this by the following code, which shows
the same effect, but is shorter]

mschoene@bert.math.rwth-aachen.de> gap -b -m 6m
gap> N:=1000000;  GASMAN("message"); GASMAN("collect");
#G  collect garbage,   2552 used,    526 dead,   4509 KB free,   6144 KB total
gap> list1:=[];; list1[N]:=1;; Unbind(list1); GASMAN("collect");
#G  collect garbage,   2554 used,      8 dead,    602 KB free,   6144 KB total
gap> list2:=[];; list2[N]:=1;; Unbind(list2); GASMAN("collect");
#G  collect garbage,   2555 used,      5 dead,    602 KB free,   6144 KB total
#G  collect garbage,   2555 used,      4 dead,   6268 KB free,  11810 KB total
gap> list3:=[];; list3[N]:=1;; Unbind(list3); GASMAN("collect");
#G  collect garbage,   2556 used,      9 dead,   6268 KB free,  11810 KB total
gap> list4:=[];; list4[N]:=1;; Unbind(list4); GASMAN("collect");
#G  collect garbage,   2557 used,      9 dead,   6268 KB free,  11810 KB total
gap> list5:=[];; list5[N]:=1;; Unbind(list5); GASMAN("collect");
#G  collect garbage,   2558 used,      9 dead,   6268 KB free,  11810 KB total

A sidenote. The garbage collection messages can be sometimes confusing.
For example, suppose 'list1[N]:=1;' is executed. No space is available
for this. So a garbage collection is performed. After that a certain
amount of space is free. This amount is printed. But this may still not
be enough, so the workspace is enlarged. But this is done after the
garbage collection message is printed. It would clearly be better if
Gasman did whatever it has to do to satisfy the current request for
storage, and after that printing how much memory will be available after
that request is satisfied.

The problem here is not 'Unbind'. 'Unbind' really removes the value from
'list1'. The problem is that the list to which 'list1' pointed cannot be
collected, because it is still accessible via 'last2'.

So if you changebe vectors, not only do they have the flag set, but also are
they represented differently. This representation is much more compact.
Instead of storing every element separately and storing for every element
separately in which field it lies, the field is only stored once. This
representation takes up to 10 times less memory.

The problem is with the operation '<int-vec> * <fin-fld-elm>'. The
result is not *known* to be a vector over a finite field (this probably
is a bug). So the result is represented as a list where each entry is a
finite field element (which takes about 24 bytes).

If you now apply 'IsVector' to the result, GAP suddenly notices that this
is a vector, and changes the representation to the compact format (which
takes about 2 bytes per element, so is 2 times better than the
representation of integer vectors).

So to modify your statement. A 1000 x 1000 matrix of entries from GF(2)
takes up about 12 times more space than a 1000 x 1000 matrix of zeroes
and ones if the rows are not known to be vectors. If they are it takes
about half as 2 times less space.

So the best way to convert your matrix would be to write

mat2 := [];
for row  in mat  do
    row2 := row * Z(2)^0;
    IsVector( row2 );
    Add( mat2, row2 );

The result will be more compact than the matrix with zeroes and ones.
And arithmetic on this will also be quite a bit faster.

Note that we plan to introduce another special type, *vector over GF(2)*,
which will be represented even more compact, using only 1 bit per entry.
So a 1000 x 1000 matrix in this representation will use only 130 KByte.

Mark Short closes

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

You are most certainly wellcome. This gives us the opportunity to
explain some of the more complicated ``features'' of GAP.


-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]