GAP

Main Branches

Downloads  Installation  Overview  Data Libraries  Packages  Documentation  Contacts  FAQ  GAP 3 

Frequently Asked Questions

General Obtaining GAP Installation Hardware/OS Usage Complaints Computing with GAP Programming GAP


6. Complaints

6.2: My calculation does not finish (or GAP runs out of memory).

Depending on the size or representation of objects, some harmless-looking commands can involve very expensive (in terms of runtime and of memory use) routines. Typical examples are (without any claim towards completeness):

  • Isomorphism tests,
  • Calculation of all subgroups,
  • Calculations with finitely presented structures.

In these cases the calculation might seemingly run forever or terminate after a while with an error message that GAP could not get more memory.

The first thing to check is the error message you got, as there are two variants:

cannot extend the workspace any more
You have hit a hard limit of how much memory is available. This could be due to physical memory in the machine, the operating system used, or the way how GAP was compiled (32 bit versus 64 bit). If you need lots of memory (and have it physically in the machine) you should run a 64 bit binary of GAP (which might require using a 64 bit version of the operating system as well).
exceeded the permitted memory (-o command line option)
This (far more frequent) error is a safety device to stop GAP from allocating so much memory to bring a machine (probably used for other tasks or by other users as well) to its knees. (A typical situation of this might be if GAP cannot do better at some task than enumerating all elements of a huge group, but the user did not realize this.) In this case an error is triggered and the trigger limit increased by a factor of 2. You could either just type return; and restart the calculation, or exit the break loop and restart the calculation anew. In either case more memory is made available. In case of running a batch job (or being irritated by this error message), you can use the -o command line option to set this trigger limit to a higher default level, e.g. the amount of physical memory your machine has. See the section Command Line Options in the Reference Manual for more detail.

Assuming that neither of these fixes is available (your job is using all the physical memory you can have), it often is possible to recast the task in a different way to get the result more efficiently: A few approaches for this are:

  • Is there a better representation? Typically PcGroups (only possible for solvable groups) are more efficient than permutation groups are more efficient than matrix groups are more efficient than Fp groups. Use IsomorphismPermGroup (or similar) to transfer the calculation into a group in a better representation.
  • Is there another operation (probably not as general as the one you are using) whose result would be sufficient? (For example it is sufficient to search for p-subgroups inside a Sylow subgroup.)
  • Is there information you have about the object that GAP will have to find out? Good candidates are the size of a group (use SetSize) or solvability (use SetIsSolvableGroup).
  • Is the amount of data produced by the calculation feasible for the machine you are using?
  • Does your computation use mutable lists when immutable lists might be better?

    In some cases, this can slow down your computation so much that it doesn't finish. Using immutable lists allows computed properties to be cached, so that further checking of the property is instantaneous. In the example below, the comments were introduced after the interaction.

    # create a mutable, sorted list
    gap> a:=List([0..20000],i->WordAlp("a",i));;
    gap> IsSortedList(a);
    true
    gap> time;
    256
    gap> IsSortedList(a);
    true
    gap> time;
    260
    
    # Time to check if it is sorted is about the same every occasion
    gap> KnownPropertiesOfObject(a);
    [ "IsFinite", "IsSmallList" ]
    
    # not much is known about a
    gap> b:=Immutable(a);;
    gap> KnownPropertiesOfObject(b);
    [ "IsFinite", "IsSmallList" ]
    
    # also not much is known about b # check sortedness for the first time
    gap> IsSortedList(b);
    true
    gap> time;
    284
    
    # about the same time it took for a. now, check again
    gap> IsSortedList(b);
    true
    gap> time;
    0
    
    # caching miracle! In this process, a lot was learned about b:
    gap> KnownPropertiesOfObject(b);
    [ "IS_SSORT_LIST", "IsFinite", "IsSmallList", "IsSortedList", "IsDuplicateFree" ]
    

    This example point to an important consequence: lookup in b is much faster than searching in a, since, as b is known to be sorted, binary search is used for the lookup. An amusing instance of a painful learning experience in the subject appears in the Forum thread starting in http://mail.gap-system.org/pipermail/forum/2008/002169.html.