The previous section (see List Assignment) told you (among other things), that it is possible to assign beyond the logical end of a list, automatically enlarging the list. This section tells you how this is done.
It would be extremly wasteful to make all lists large enough so that there is room for all assignments, because some lists may have more than 100000 elements, while most lists have less than 10 elements.
On the other hand suppose every assignment beyond the end of a list would be done by allocating new space for the list and copying all entries to the new space. Then creating a list of 1000 elements by assigning them in order, would take half a million copy operations and also create a lot of garbage that the garbage collector would have to reclaim.
So the following strategy is used. If a list is created it is created
with exactly the correct size. If a list is enlarged, because of an
assignment beyond the end of the list, it is enlarged by at least
length/8 + 4 entries. Therefore the next assignments beyond the end
of the list do not need to enlarge the list. For example creating a list
of 1000 elements by assigning them in order, would now take only 32
enlargements.
The result of this is of course that the physical length, which is also
called the size, of a list may be different from the logical length,
which is usually called simply the length of the list. Aside from the
implications for the performance you need not be aware of the physical
length. In fact all you can ever observe, for example by calling
Length is the logical length.
Suppose that Length would have to take the physical length and then
test how many entries at the end of a list are unassigned, to compute the
logical length of the list. That would take too much time. In order to
make Length, and other functions that need to know the logical length,
more efficient, the length of a list is stored along with the list.
A note aside. In the previous version 2.4 of GAP a list was indeed enlarged every time an assignment beyond the end of the list was performed. To deal with the above inefficiency the following hacks where used. Instead of creating lists in order they were usually created in reverse order. In situations where this was not possible a dummy assignment to the last position was performed, for example
l := [];
l[1000] := "dummy";
l[1] := first_value();
for i from 2 to 1000 do l[i] := next_value(l[i-1]); od;
GAP 3.4.4