[GAP Forum] Immutable lists and memory usage

[Frank Lübeck]

On Tue, Feb 08, 2011 at 11:35:22AM +0800, Keshav Rao Kini wrote:
> Here is the result of some experimentation I did:
> 
> gap> x := [];; for i in [1..100] do Add(x, i); od; MemoryUsage(x); MakeImmutable(x);; MemoryUsage(x); ShrinkAllocationPlist(x); MemoryUsage(x);
> 512
> 512
> 416
> 
> I'm wondering why ShrinkAllocationPlist isn't called automatically by MakeImmutable, since once I use MakeImmutable() it should be impossible to extend x or even to shrink it, if I understand correctly...

Dear Keshav, dear Forum,

The function MakeImmutable is for expert usage only. The idea is that it is
very cheap, it essentially just flips a bit in an object and its subobjects.
It is on purpose that it does exactly what its name says and nothing else.

When you add objects to a list and there is no space for it in the list
object, then GAP enlarges the space for the list by about 25% of its current
length (for efficiency reasons). So, the worst waste of memory you can 
have in an example as above is about 25% (probably negligible in most 
cases).

If you care about this memory then ShrinkAllocationPlist is provided to
collect it (can also be sensible for mutable plain lists). 

If you know the length of the lists you want to create in advance (this is
often the case where MakeImmutable is used), you can be even more efficient
by creating the empty list in the beginning with the correct amount of
memory:

gap> x := EmptyPlist(100);; for i in [1..100] do Add(x, i); od; MemoryUsage(x); MakeImmutable(x);; MemoryUsage(x); ShrinkAllocationPlist(x); MemoryUsage(x);
832
832
832


With best regards,
    Frank

-- 
///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\