Section List Assignment told you (among other things) that it is possible to assign beyond the logical end of a mutable list, automatically enlarging the list. This section tells you how this is done for internally represented lists.
It would be extremely 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 of a list
may be larger than 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 (see 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.
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual