This section describes the garbage collector (GC) in 32-bit LispWorks 8.0.
In LispWorks for Macintosh, the implementation is not significantly different to that in LispWorks 4.x, LispWorks 5.x or LispWorks 6.x.
In LispWorks for Windows and LispWorks for Linux, the implementation has changed since LispWorks 4.x and you may notice performance improvements relative to those versions.
In memory, a generation consists of a chain of segments. Each segment is a contiguous block of memory, beginning with a header and followed by the allocation area.
The first generation normally consists of two segments: the first segment is relatively small, and is where most of the allocation takes place. The second segment is called the big-chunk area, and is used for allocating large objects and when overflow occurs (see below for a discussion of overflow).
The second generation (generation 1) is an intermediate generation, for objects that have been promoted from generation 0 (typically for objects that live for some minutes).
Long-lived objects are eventually promoted to generation 2. Note that generation 2 is not scanned automatically. Therefore these objects will not be reclaimed (even if they are not referenced) until an explicit call to a GC function (for example gc-generation on t, or clean-down) or when the image is saved. Normally, objects are not promoted from generation 2 to generation 3, except when the image is saved.
Generation 3 normally contains only objects that existed at startup time, that is those were saved in the image. Normally it is not scanned at all, except when an image is saved.
Note that the division between the generations is a result of the promotion mechanism, and is not a property of a piece of code itself. A piece of system software code that is loaded in the system (for example, a patch) is treated the same as any other code. The garbage collection code is explicitly loaded in the static area using the function switch-static-allocation.
Normal allocation is done from a buffer, called the small objects buffer. The GC maintains a pointer to the beginning and end of the buffer, and allocates from it by moving one of the boundaries. When the buffer becomes too small the GC finds another free block and makes that the buffer.
In non-SMP LispWorks there is only one global small objects buffer. In SMP LispWorks, each process may have its own "local" small objects buffer (in addition to the global one). The system decides dynamically which process should have a local buffer and which not. In general processes that do any significant amount of work have a local buffer, and most of their allocation would be from local buffers.
When there is an overflow the small object buffer is allocated in the big-chunk area, and then a bigger buffer is allocated (see below).
Objects that cannot be moved are allocated in special segments, called static segments. These can be in any generation, but are in generation 2 by default.
Such objects include:
:static. This is the preferred way to allocate a static array.
Because static objects are not allowed to move, the static segments are not allowed to move. This implies that if there is a static segment in a high address the image size cannot be reduced below this size. Applications that use a lot of static area normally allocate additional static segments, and thus grow without being able to shrink again. This can be prevented by enlarging the initial static segment, which is in a low address. Use the function enlarge-static to increase the size of the initial static segment. (Use (room t) to find its current size.)
Objects that are known to have long life can be allocated directly in a higher generation, by using allocation-in-gen-num and set-default-generation. Note that both these functions have a global effect, that is any object allocated after a call to set-default-generation or within the body of allocation-in-gen-num is allocated in the specified generation, unless it is explicitly allocated in a different generation. Therefore careless use of these functions may lead to allocation of ephemeral garbage in high generations, which is very inefficient. Conversely, if a long-lasting object is allocated to a low generation, it has to survive several garbage collections before being automatically promoted to the next generation.
The best way to control the allocation generation for an array is to call make-array with allocation :long-lived or a number.
See also 11.6.3 Allocation of interned symbols and packages and 11.6.4 Allocation of stacks.
Mark and sweep is the basic operation of reclaiming memory, and it is done in two stages:
| Mark |
All objects that are alive in the generation being garbage collected and in younger generations are marked as alive. (Alive means pointed to by some other live object.) |
| Sweep |
All unmarked objects in the generations being garbage collected are added to the free blocks, and all marked objects are unmarked. |
A mark and sweep operation is always on all the generations from 0 to a specific number.
A mark and sweep operation can be caused explicitly by calling gc-generation.
Promotion is the process of moving objects from one generation to the next generation. An object is marked for promotion after surviving a specific number of mark and sweep operations, but may be promoted before that. The number of survivals is specific to each segment.
Promotion does not free objects.
When the GC runs out of memory, it has to find more memory. Normally (that is, when allocating in generation 0) the first operation is a mark and sweep. Before performing the mark and sweep, the GC compares the amount of memory allocated since the previous mark and sweep with the minimum-free-space value, which is set by set-gc-parameters. If the amount allocated is less than minimum-for-sweep the GC does not do a mark and sweep, but causes an overflow (described below). This prevents an excessive number of mark and sweep operations in periods when the program allocates a large amount of data which stays alive.
If more than minimum-for-sweep has been allocated, a mark and sweep operation takes place. After this operation the GC checks that the segment it was trying to allocate to has more free space than the minimum free space for this segment. If the remaining free space is less than minimum-free-space, the GC tries to create more free space by promoting objects from the segment.
Before promoting, the GC performs two checks. First, it checks that there are enough objects marked for promotion to justify a promotion operation. The minimum-free-space for a segment is set by set-minimum-free-space, and can be shown by (room t).
Second, the GC checks that there is enough free space in the next generation to accommodate the promoted objects. If there is insufficient space, the GC tries to free some, either by a mark and sweep on the next generation, promoting the next generation, or by enlarging the generation.
The minimum amount of space for promotion is the value minimum-for-promote, which is set by set-gc-parameters.
If there is insufficient space, and there are not enough objects marked for promotion, the GC increases the size of the image, by overflow, as described below.
On Motif only, note that the GC monitor window does not indicate a mark and sweep of generation 0, as this operation takes a small amount of time (it would take longer to change the display of the window). The GC monitor window appears only in the Motif IDE.
On Linux, the default initial heap is mapped at address #x20000000 (0.5 GB). LispWorks then tries to locate the location of dynamic libraries, and marks a region around these libraries that should not be used (by default 64 MB from the bottom). In most cases this suffices to avoid clashes.
Problems can arise if the memory at #x20000000 or above is already used by another part of the software. If that memory gets used before LispWorks is mapped, LispWorks must be relocated elsewhere, typically to a higher address, as described in 27.6.2 Startup relocation of 32-bit LispWorks.
If the memory above LispWorks gets used by other parts of the software after LispWorks was mapped, it may be possible to avoid the problem by reserving some memory above LispWorks by supplying ReserveSize.
The location of dynamic libraries differs between Linux configurations, and that needs to be taken into account. For most cases, including the cases where the libraries are mapped at #x40000000 or somewhere above #x28000000, the mechanism for detecting libraries works and no action is required.
In principle LispWorks (32-bit) for Linux can grow up to some distance below #xF7F00000 (almost 3.4 GB), though this depends on the OS kernel allowing this size.
Note: In LispWorks 5.0 and previous, we told some customers to relocate above the libraries, for example at #x50000000 or #x48000000, but this should not be needed in LispWorks 8.0.
By default, LispWorks is mapped at #x30000000.
Problems may arise if something uses memory above #x30000000. If this memory is used before LispWorks is mapped, LispWorks must be relocated elsewhere, typically to a higher address, as described in 27.6.2 Startup relocation of 32-bit LispWorks.
If the memory above LispWorks gets used by other parts of the software after LispWorks was mapped, it may be possible to avoid the problem by reserving some memory above LispWorks by using ReserveSize.
Normally the dynamic libraries are mapped at #x28000000, and therefore LispWorks can grow without a problem.
In principle LispWorks can grow up to some distance below #xC0000000 (almost 2.25 GB), though this depends on the OS kernel allowing this size and how many threads you have running.
The default initial heap is mapped at address #x10000000 (0.25 GB). LispWorks then tries to locate the location of dynamic libraries, and marks a region around these libraries that should not be used (by default 64 MB from the bottom). In most cases this suffices to avoid clashes.
Problems can arise if the memory at #x10000000 or above is already used by another part of the software. If that memory gets used before LispWorks is mapped, LispWorks must be relocated elsewhere, typically to a higher address, as described in 27.6.2 Startup relocation of 32-bit LispWorks.
If the memory above LispWorks gets used by other parts of the software after LispWorks was mapped, it may be possible to avoid the problem by reserving some memory above LispWorks by supplying ReserveSize.
LispWorks (32-bit) for Windows can map by default at #x20000000. Since this platform supports reservation, normally you will not need to do anything special about this.
Problems may however arise if LispWorks operates in conjunction with non-relocatable software which insists on using addresses at #x20000000 or some distance above, in which case you will need to relocate LispWorks, as described in 27.6.2 Startup relocation of 32-bit LispWorks.
LispWorks (32-bit) for Windows can in principle grow up to some distance below #x80000000 (almost 1.5 GB) but there is always the possibility that some DLL will be mapped in this region. On startup, it reserves 0.5 GB above its location, so that much is guaranteed.
If your program allocates a lot you may reach the limit of memory that LispWorks can use. The limit depends on the architecture as described in 11.3.5 Memory layout.
When LispWorks actually reaches the limit it will fail to communicate with the user due to allocation errors. To avoid this situation, LispWorks informs the user earlier that it is approaching the limit of memory. It first checks whether you set the approaching memory callback (by set-approaching-memory-limit-callback), and if there is a callback calls it. If there is no callback or the callback returns, LispWorks signals an error of type approaching-memory-limit (which is a subclass of cl:storage-condition).
The function memory-growth-margin can be used to see how much LispWorks "believes" that it can grow.
The callback can be used to effectively ignore the condition, but this is a bad idea in general, because it will probably lead to an error later when LispWorks actually reaches the limit, and then it may crash in a bad way. To be safe, the callback should either cleanup and exit, or free a substantial amount of memory. You can reasonably continue only if a crash is not going to cause a serious damage.
If the amount allocated from the previous mark and sweep operation is less than :minimum-for-sweep, the GC does not perform a mark and sweep. Instead it allocates a small-objects buffer in the big-chunk area (the second segment in the first generation). The minimum and maximum sizes of this buffer are specified by :minimum-overflow and :maximum-overflow, which can be set by set-gc-parameters. If the GC fails to find a buffer of this size, it looks for a smaller buffer, and if that fails it enlarges the big-chunk area (and the process size) by the amount needed to allocate a buffer of the size of the currently allocated area in generation 0, up to a maximum amount specified by :maximum-overflow.
When objects are promoted from generation 0 to 1, and there is not enough space in generation 1, the GC tries to free space in generation 1. The first step is to check whether sufficient space can be freed by promoting the objects marked for promotion. If this is the case the GC promotes these objects from generation 1 to generation 2. (In practice, this rarely happens.) If this check fails the GC marks and sweeps generation 1. If not enough space is freed by this mark and sweep, than either all the objects in generation 1 are promoted, or generation 1 is expanded. This is controlled by expand-generation-1, which specifies whether expansion or promotion takes place.
If generation 1 is expanded, the amount it tries to expand by is the value :new-generation-size (set by set-gc-parameters) in words (that is, multiples of 4 bytes), or the amount of free space needed, whichever is bigger. If :new-generation-size is 0, it is not expanded. In this case part of the objects marked for promotion are not promoted.
Normally generation 2 is not garbage collected. If the system runs out of space in this generation, it expands it, using the value of :new-generation-size multiplied by two. Garbage collection of generation 2 can be caused by calling the function collect-generation-2 with appropriate argument.
If you know that a given generation will need to grow, you can save the GC the work by calling enlarge-generation to expand the generation in advance.
Some applications periodically free (that is, stop using) a substantial amount of data that lived for long enough to reach generation 2 (use room or room-values and generation-number to follow the behavior of objects). In this case, gc-generation should be called on generation 2, to collect these data and re-use the memory. Repeated cycles like this may cause fragmentation, which will slow down promotion into generation 2. This manifests itself in significant pauses, typically of a few seconds. try-move-in-generation or try-compact-in-generation can be used to reduce the fragmentation, and hence to reduce the pauses. Because these functions themselves take some time, they should be called when such a pause is acceptable.
'Moving' a segment means moving objects out of the segment to another segment, leaving the segment empty. This reduces the fragmentation in the generation, and it is normally much faster than compact. Therefore in almost all cases, try-move-in-generation is better than try-compact-in-generation.
The actual decision to use these functions will be typically based on the results of check-fragmentation. For example, the following function checks whether there is more than 10 MB free area in generation 2 in blocks of 4096 bytes or larger (tlb, third return value of check-fragmentation). If there is not, and the free area in generation 2 (tf) is more than four times the free area in large blocks, it calls try-move-in-generation. Because try-move-in-generation gets a time-threshold of 0, it returns after moving at most one segment. (It will not move any segments if none of them looks fragmented.)
(defun call-memory-functions()
(gc-generation t) ; first collect all dead objects
(multiple-value-bind (tf tsb tlb)
(check-fragmentation 2) ; check the fragmentation
(when (and (> 10000000 tlb)
(> (ash tf -2) tlb))
(try-move-in-generation 2 0))))
A function such as this can be called at times when a pause of a few seconds is acceptable, and it will keep the memory of generation 2 less fragmented.
It is not possible to give definitive guidance here on how to use try-move-in-generation or try-compact-in-generation, because it depends on the way the application uses memory. In general, these functions will always improve the behavior of the application. Therefore the main problem is to identify points in the execution of the application where they can be called without causing unacceptably long pauses.
The remainder of this chapter summarizes which functions are useful in which circumstances. See also 11.6 Common Memory Management Features. For full details of these functions, see their reference entries.
To determine memory usage (useful when benchmarking), use the functions room, total-allocation and find-object-size. The function room-values is suitable for programmatic use: it returns the values that room prints.
In 32-bit LispWorks, memory-growth-margin returns the amount by which the Lisp heap can grow, if set-maximum-memory has been called.
Arrays can be allocated static or in a higher generation using the allocation argument in make-array.
To control the allocation of other objects to generations, use allocation-in-gen-num, get-default-generation, set-default-generation and *symbol-alloc-gen-num*.
To control the behavior of a specific generation, use clean-generation-0, collect-generation-2, collect-highest-generation, expand-generation-1 and set-minimum-free-space.
The functions that are most likely to be useful for controlling the GC are room, check-fragmentation, gc-generation and try-move-in-generation.
Other potentially useful functions and macros are avoid-gc, get-gc-parameters, gc-if-needed, enlarge-generation, normal-gc, set-gc-parameters, with-heavy-allocation and try-compact-in-generation.
LispWorks® User Guide and Reference Manual - 01 Dec 2021 19:30:20