Garbage Collection

$Revision: 5.0.2.9 $

The document introduction.htm provides an overview of the Allegro CL documentation with links to all major documents. The document index.htm is an index with pointers to every documented object (operators, variables, etc.) The revision number of this document is below the title. These documents may be revised from time to time between releases.

1.0 Garbage collection introduction
     1.1 The garbage collection scheme
     1.2 How newspace is managed with scavenges
     1.3 The system knows the age of objects in newspace
     1.4 Objects that survive long enough are tenured to oldspace
     1.5 Placement of newspace and oldspace: the simple model
     1.6 Oldspace, newspace, and Lisp will grow when necessary
     1.7 The almost former gap problem
2.0 User control over the garbage collector
     2.1 Switches and parameters
     2.2 Triggering a scavenge
     2.3 Triggering a global gc
     2.4 Getting information on memory management
3.0 Tuning the garbage collector
     3.1 How do I find out when scavenges happen?
     3.2 How many bytes are being tenured?
     3.3 When there is a global gc, how many bytes are freed up?
     3.4 How many old areas are there after your application is loaded?
     3.5 Can other things be changed while running?
4.0 Initial sizes of old and new spaces
5.0 System parameters and switches
     5.1 Parameters that control generations and tenuring
     5.2 Parameters that control minimum size
     5.3 Parameters that control how big newly allocated spaces are
     5.4 Gsgc switches
     5.5 Gsgc functions and variables
6.0 Global garbage collection
     6.1 The tenuring macro
7.0 Gc cursors
8.0 Other gc information
9.0 gc errors
     9.1 Storage-condition errors
10.0 Weak vectors, finalizations, static arrays, etc.
     10.1 Weak arrays and hashtables
     10.2 Finalizations
     10.3 Example of weak vectors and finalizations
     10.4 Static arrays

1.0 Garbage collection introduction

Lisp does its own memory management. The garbage collector is part of the memory management system. It disposes of objects that are no longer needed, freeing up the space that they occupied. While the garbage collector is working, no other work can be done. Therefore, we have made the garbage collector as fast and unobtrusive as possible. Allegro CL uses a version of the generation-scavenging method of garbage collection. Because optimal performance of generation-scavenging garbage collection depends on the application, you have a great deal of control over how the garbage collector works. In this section, we will describe the user interface to the garbage collector, and suggest how to tune its performance for an application. In what follows, the generation-scavenging garbage collection system will be abbreviated gsgc, and the act of garbage collecting will be abbreviated gc.

1.1 The garbage collection scheme

The Allegro CL garbage collector is a two-space, generation-scavenging system. The two spaces are called newspace and oldspace. Note that, as we describe below, newspace is divided into two pieces, called areas, and oldspace may be divided into a number of pieces, also called areas. Generally, when we say newspace, we mean both newspace areas and when we say oldspace, we mean all oldspace areas. We try to use the word area when we want to refer to a single area, but please note that this naming convention is new and you may run into text that uses `oldspace' to refer to an oldspace area. Usually, the context should make this clear.

1.2 How newspace is managed with scavenges

The two pieces of newspace are managed as a stop-and-copy garbage collector system. The two areas are the same size. At any one time, one area is active and the other is not. A newspace area is filled from one end to the other. Imagine, for example, a book shelf. Existing books are packed together on the right side. Each new book is placed just to the left of the leftmost book. It may happen that books already placed are removed, leaving gaps, but these gaps are ignored, with each new book still being placed to the left of the location of the last new book. When the shelf fills up, the other shelf (newspace area) is used. First, all books remaining are moved to the other shelf, packed tight to one side, and new books are placed in the next free location.

So with Lisp objects in newspace areas. All existing objects are packed together on one side of the area and new objects are placed in the free space next to the existing objects, with gaps left by objects which are no longer alive being ignored. When the area fills up, Lisp stops and copies all live objects to the other area, packing them tight. Then the process is repeated.

The process of copying objects from one newspace area to the other is called a scavenge. We will discuss the speed of scavenges below, but scavenges are supposed to be so fast that humans usually barely notice them.

1.3 The system knows the age of objects in newspace

The system keeps track of the age of objects in newspace by counting the number of scavenges that the object has survived. The number of scavenges survived is called the generation of an object. When objects are created, they have generation 1, and the generation is increased by 1 at each scavenge.

Of course, many objects become garbage as time passes. (An object is garbage when there are no pointers to it from any other live object. If there are no pointers to an object, nothing can reference or access it and so it is guaranteed never to be looked at again. Thus, it is garbage.) The theory of a generation scavenging garbage collector is that most objects that will ever become garbage will do so relatively quickly and so will not survive many scavenges.

1.4 Objects that survive long enough are tenured to oldspace

The problem with a stop-and-copy system is that objects that survive have to be moved and moving objects takes time. If an object is going to be around for a while (or for the entire Lisp session), it should be moved out of newspace to some place where it does not have to be moved (or is moved much less often). This is where the other half of the generation scavenging algorithm comes into play. Once an object has survived enough scavenges, it is assumed to be long-lived and is moved to oldspace. Oldspace is not touched during scavenges and so objects in oldspace are not moved during scavenges, thus saving considerable time over a pure stop-and-copy system.

Part of a scavenge is checking the age (generation) of surviving objects and moving those that are old enough to oldspace. The remaining objects are moved to the other newspace area. The age at which objects are tenured is user-settable. Its initial value is 4 and that seems to work for many applications. We will discuss below how changing that (and many other) settings can affect gc performance.

The process of moving an object to oldspace is called tenuring and the object moved is said to be tenured. At one point, oldspace was also called tenured space and you may see that term occasionally in Allegro CL documents.

Note the assumption: objects that survive a while are likely to survive a long while

If one could know exactly how long an object is going to survive, one could provide the best possible garbage collection scheme. But that knowledge is not available. Objects are created all the time by different actions and users and even application writers typically do not know what actions create objects or how long those objects will live. Indeed, that information often depends on future events that are hard to control -- such as the behavior of the person running the application.

So the algorithm makes an assumption: if an object survives for a while, it is likely to survive for a long while, perhaps forever (forever means the length of the Lisp session). Of course, for many objects this assumption may be wrong: the object may become garbage soon after it is tenured. However, as we said above, scavenges (which are automatic and cannot be prevented by a user although they can be triggered by a user) do not touch oldspace. In order to clear garbage from oldspace, a global garbage collection (global gc) must be done. An interface for automating global gc's is provided in Allegro CL and different interfaces are easy to implement (see below for more information), but the two important points about global gc's are:

1. in most cases, they should be done from time to time; and
2. when and if they happen can be wholly under your control.

1.5 Placement of newspace and oldspace: the simple model

The Lisp heap grows upwards (to higher addresses). Oldspaces are at low addresses and newspace occupies addresses higher that any oldspace area. This means that newspace can grow without affecting oldspace and oldspace can grow (usually by creating a new oldspace area) by having newspace move up as far as necessary.

Why might newspace grow? Suppose, for example, an newspace area is 600 Kbytes and you want to allocate a 1 Mbyte array. Newspace has to grow to accommodate this.

Why might oldspace grow? As objects are tenured to oldspace, it slowly fills up. Even with regular global gc's, it can fill up. When it does, newspace moves up and a new old area is created. (New areas are created rather than a single area being expanded for various technical reasons. We discuss below how to compactify dynamically. See 3.5 Can other things be changed while running?.)

We will not describe the internal algorithms of the garbage collector because they cannot be changed or modified by users in any way. But let us consider how newspace might be moved, as this might make the process clearer. Suppose the current scavenge is about to move live objects to the high address area. Before anything is moved, Lisp can compute how much space the live objects need, how much space objects waiting to be allocated need, and how much space a new old area needs. From that information, it can compute the highest address of the high address newspace area. It requests from the Operating System that the area be allocated (using malloc or sbrk), and once the Operating System confirms the allocation, starts copying the live objects to that high address, filling toward lower addresses. When all live objects have been moved and new objects are allocated in the high address newspace area, the new oldspace area (if one is required) can be created and the location of the low address newspace area can be determined. Recall that high address newspace area is active so the low address newspace area does not contain anything of importance.

1.6 Oldspace, newspace, and Lisp will grow when necessary

A consequence of what we just said about newspace moving when it has to grow or when a new oldspace area is needed is that the size of the Lisp image can grow while it is running. This is usually normal, indeed what you want. It allows images to start small and grow as much (but no more) than they need. It also allows the same image to run effectively on machines with different configurations.

But, sometimes growth can be unexpected and the image can want to grow to a size larger than the Operating System can handle (usually because there is not enough swap space).

The growth is often necessary, because of the type of application being run. What is important is that the growth be managed and be no more than is really needed.

1.7 The almost former gap problem

Changes in the memory management scheme in 5.0 (compared to earlier releases) means that there is almost no gap problem. In earlier releases, space for foreign code loaded into the image, space for foreign objects, and direct calls to malloc all could cause a gap to be placed above newspace. If a new oldspace or a larger newspace was needed, it had to be placed above the gap, causing in some cases a small need for additional space to result in a multimegabyte increase in image size. In 5.0, malloc space is placed away from the new and old spaces and so the lisp heap (new and old spaces together) are unaffected and can grow incrementally as needed, but only up to the Lisp heap limit. This value is set by the lisp-heap-size argument to build-lisp-image (see building_images.htm). The Lisp heap limit is reported in a (room t) output. If the heap grows larger than that size (which is not a true limit in that, except in certain free sample images, the heap can grow larger), gaps may appear. If you see gaps in your application, you should consider starting with an image with a larger heap size.

2.0 User control over the garbage collector

Application writers and users can control the behavior of the garbage collector in order to make their programs run more efficiently. This is not always easy, since getting optimal behavior depends on knowing how your application behaves and that information may be difficult to determine. Also, there are various paths to improvement, some of which work better than others (but different paths work better for different applications).

One thing to remember is that (unless the image needs to grow larger than available swap space), things will work whether or not they work optimally. You cannot expect optimal gc behavior at the beginning of the development process. Instead, as you gather information about your application and gc behavior, you determine ways to make it work better.

2.1 Switches and parameters

The automated gc system is controlled by switches and parameters. There is not much difference between a switch and a parameter (a switch is usually true or false, a parameter usually has a value) and there probably should not be a distinction, but these things are hard to change after they are implemented. The functions sys:gsgc-switch and sys:gsgc-parameter can be used to poll the current value and (with setf) to set the value of switches and parameters.

The function sys:gsgc-parameters prints out the values of all switches and parameters:

sys:gsgc-switch can poll and set switches while sys:gsgc-parameter can poll and set parameters: Here we poll and set the :print switch.

The excl:gc function can be used to toggle some of the switches.

2.2 Triggering a scavenge

The system will cause a scavenge whenever it determines that one is necessary. there is no way to stop scavenges from occurring at all or even to stop them from occurring for a specified period of time.

However, you can cause a scavenge by calling the excl:gc function with no arguments:

(excl:gc) ;; triggers a scavenge

You can also cause a scavenge and have all live objects tenured by calling the excl:gc function with the argument :tenure, like this

(excl:gc :tenure)

2.3 Triggering a global gc

Global gc's (a gc of old and new space) are not triggered automatically (but triggering can be automated). You can trigger a global gc by calling excl:gc with the argument t:

(excl:gc t) ;; triggers a global gc

See section 6.0 Global garbage collection for information on other ways to trigger a global gc and ways to automate global gc's.

2.4 Getting information on memory management

The function cl:room provides information on current usage (it identifies oldspaces and newspace and free and used space in each). Setting the :print switch and perhaps the :stats and :verbose switches causes the system to print information while gc's are occurring. See 5.4 Gsgc switches and 3.1 How do I find out when scavenges happen?.

Evaluating (room t) provides the most information about the current state of memory management. Here is a (room t) output from a freshly started Allegro CL on Windows with the Integrated Development Environment loaded (with added notes in bold):

USER(1): (room t)
area  address(bytes)        cons        symbols        other bytes
                        8 bytes each  24 bytes each
                        (free:used)   (free:used)      (free:used)
Top #x308d8000
New #x3084a000(581632)    935:10274     178:76        144008:287832
New #x307bc000(581632)     -----         -----            -----
Old #x30000c38(8106952)   235:127140    320:21037     519056:6041480
Root pages: 116
 Lisp heap base: #x30000000  position: #x308d8000 reserved: 67108864
 C heap    base: #x54000000  position: #x54005000 reserved: 1024000

code   type                                items    bytes   
108: (simple-array code)                      7301   2841568 35.9%
 96: (simple-array t)                        28624   2069760 26.2%
  1: cons                                   135021   1080168 13.6%
101: (simple-array character)                30613    735864  9.3%
  7: symbol                                  21113    506712  6.4%
  8: function                                 7938    478440  6.0%
 15: structure                                1773     77680  1.0%
 12: standard-instance                        4504     72064  0.9%
  9: closure                                  2192     36592  0.5%
 10: hash-table                                162      5184  0.1%
100: (simple-array (unsigned-byte 32))           7      4304  0.1%
 18: bignum                                    205      2072  0.0%
 17: double-float                              107      1712  0.0%
 16: single-float                              121       968  0.0%
 97: (simple-array bit)                         14       320  0.0%
 64: (array t)                                   8       192  0.0%
 20: complex                                    11       176  0.0%
111: (simple-array foreign)                      7       168  0.0%
 11: readtable                                   6        96  0.0%
107: (simple-array (signed-byte 32))             1        88  0.0%
 98: (simple-array (unsigned-byte 8))            1        40  0.0%
 13: sysvector                                   2        32  0.0%
 69: (array character)                           1        24  0.0%

 total bytes = 7914224
aclmalloc arena:
   max size  free bytes  used bytes     total
       496       3968          0         3968
      1008       4032          0         4032
      2032       4064          0         4064
      4080          0       8160         8160
 total bytes:   12064       8160        20224

Newspace is divided into two equal size parts (only one of which is used at any time). There is one oldspaces.

Root pages: 116

Root pages contain information about pointers from oldspace to newspace.

 Lisp heap base: #x30000000  position: #x308d8000 reserved: 67108864
 C heap    base: #x54000000  position: #x54005000 reserved: 1024000

In these two lines (new in the 5.0.1 room output, compared to 5.0),

base is the starting address of the heap in memory, hexidecimal;

position: the highest-use location; this is one byte larger than the highest memory used by the lisp. Some operating systems will only commit (assign physical pages) to memory between base (inclusive) and position (exclusive). This is a hexidecmal address value.

reserved: the number of bytes lisp thinks is reserved to it in virtual memory space (this was called lisp-heap-limit in 5.0). On operating systems which support it, addresses greater than position, but less than base+reserved, will no be overwritten by shared-libraries, other memory mapping operations, etc. [we should be careful to say that whether this is true or not depends on the operating system]

The lisp heap reserved size is a true limit only for certain free products. With paid license images (and some free products), this value is important only because if the heap grows larger than this limit, gaps in the heap may appear. See 1.7 The almost former gap problem for more information. This value is not a limit in any sense on how big the image can grow.

The type counts are as if printed by excl:print-type-counts.htm:

code   type                                items    bytes   
  1: cons                                   324509   2596072 26.0%
108: (simple-array code)                      8547   2018984 20.2%
 96: (simple-array t)                        29169   1668152 16.7%
  8: function                                21005   1205648 12.1%
  7: symbol                                  32729    785496  7.9%
101: (simple-array character)                23309    739936  7.4%
 12: standard-instance                       30847    493552  5.0%
  9: closure                                 13007    229656  2.3%
 97: (simple-array bit)                        346    107840  1.1%
 15: structure                                2401     66480  0.7%
 98: (simple-array (unsigned-byte 8))          136     19280  0.2%
111: (simple-array foreign)                    638     15304  0.2%
 18: bignum                                    631      5704  0.1%
 10: hash-table                                140      4480  0.0%
107: (simple-array (signed-byte 32))             5      3272  0.0%
 66: (array (unsigned-byte 8))                 135      3240  0.0%
100: (simple-array (unsigned-byte 32))           5      2280  0.0%
 17: double-float                              132      2112  0.0%
 16: single-float                              209      1672  0.0%
 65: (array bit)                                22       528  0.0%
 64: (array t)                                   9       216  0.0%
 20: complex                                    11       176  0.0%
 99: (simple-array (unsigned-byte 16))          21       168  0.0%
 13: sysvector                                   4       160  0.0%
 69: (array character)                           5       120  0.0%
 11: readtable                                   7       112  0.0%
 19: ratio                                       2        32  0.0%

 total bytes = 9970672

The malloc arena describes allocation of space for mallocs and foreign data. There is no user interface to this area in 5.0 but information, if needed, may appear in the Allegro CL FAQ (see introduction.htm).

malloc arena:
   max size  free bytes  used bytes     total
        16       1456       2640 *       4096
        48       2496      28224 *      30720
       112       3472        112 *       3584
       240       3600        240         3840
       496       2976      20832        23808
      1008       4032          0         4032
      2032       2032      10160        12192
      4080       4080       8160        12240
      9200      27600       9200        36800
     36848          0      36848        36848
 total bytes:   51744     116416       168160
 * = contains non-relocatable data

3.0 Tuning the garbage collector

As a user, or as an application writer, how can you get the garbage collector to work best for you? At first, you do not have to do anything. The system is set up to work as delivered. You will not run out of space, global gc's will happen from time to time (as described below, see 6.0 Global garbage collection), the image will grow as necessary, and assuming you do not run out of swap space, everything will work.

Of course, it will not necessarily work as well as it could. As delivered, the garbage collector is set to work best with what we assume is a typical application: objects, none of which are too big, are created as needed. Most objects that survive a while are likely to survive a long while or perhaps forever, and so on. If your or your application's use of Lisp has different behavior, performance may be suboptimal.

So what to do? One problem is that optimizing gc behavior is a multidimensional problem. Factors that affect it include

1. things internal to Lisp (the initial sizes of oldspace and newspace, the various products included in the image, whether shared libraries or static text is used for certain constants or whether the constants are part of the Lisp heap);
2. environmental factors (amount of physical memory, amount of swap space, usual running environment -- i.e. runs with lots of other programs or runs on a dedicated machine, whether paging is done over the network); and
3. details of what your code or application does.

Optimization in a multidimensional environment is always complicated.

The first step is always to gather the information necessary to do the tuning. Information like:

3.1 How do I find out when scavenges happen?
3.2 How many bytes are being tenured?
3.3 When there is a global gc, how many bytes are freed up?
3.4 How many old areas are there after your application is loaded?
3.5 Can other things be changed while running?

3.1 How do I find out when scavenges happen?

There are three gsgc switches (these control the behavior of the garbage collector) that affect printing information about the garbage collector: :print, :stats, and :verbose. Doing

(setf (sys:gsgc-switch :print) t)

will cause a short message to be printed whenever a scavenge happens. Unless the :print switch is t, no message will be printed.

The :stats and :verbose switches control the amount of information printed. If the :stats switch is true, the message contains more information but the information is compact. If the :verbose switch is also true, a longer, more easily understood message is printed.

With just :print true, a very short message is printed. With :stats true, the message contains much more information, but it is coded -- E means Efficiency, N means bytes copied in newspace, O means bytes copied to oldspace. With :verbose also true, the same information is displayed in expanded form and additional information (about page faults) is provided.

Efficiency is defined as the ratio of cpu time not associated with gc to total cpu time. Efficiency should typically be 75% or higher, but the efficiencies in the example are low because we triggered gc's without doing anything else of significance.

It is usually desirable to have :print and :stats true while developing software. This allows you to monitor gc behavior and see if there seems to be a problem.

3.2 How many bytes are being tenured?

That information is shown when :print and :stats are true, but perhaps the real question is whether things are being tenured that would be better left in newspace (because they will soon become garbage). This often happens when a complex operation (like a compile of a large file) is being carried out. This question, in combination with the next can tell you if that is the case.

In the following, copied from above, 0 bytes are tenured in the first gc (O+=0) and 16064 in the second (old: 16064):

user(9): (gc)
gc: E=17% N=17536 O+=0
user(10): (setf (sys:gsgc-switch :verbose) t)
t
user(11): (gc)
scavenging...done eff: 15%, copy new: 1664 + old: 16064 = 17728
Page faults: gc = 0 major + 2 minor
user(12):

3.3 When there is a global gc, how many bytes are freed up?

If the :print and :stats switches are true, the amount of space freed by a global gc is printed at the end of the report. Here is an example. The form (gc t) triggers a global gc.

The next to last line reports on what was recovered from oldspace (9672 bytes). The value is often much higher. It is low in this example because we have not in fact done anything significant other than test gc operations.

There is plenty of other information but we will not describe its meaning in detail. It is typically useful in helping us help you work out complicated gc problems.

The amount of space freed is a rough measure of how many objects are being tenured that perhaps should be left for a while longer in newspace. If the number if high, perhaps things are being tenured too quickly (increasing the value of the :generation-spread switch will keep objects in newspace longer, as will a larger newspace).

3.4 How many old areas are there after your application is loaded?

The output of (cl:room) shows the two newspace areas and the various oldspace areas. Here is an example of room output. (room takes an argument to indicate how much information should be displayed). The following is the output of (room), which causes the most information to be displayed.

> (room t)
area  address(bytes)        cons        symbols        other bytes
                        8 bytes each  24 bytes each
                        (free:used)   (free:used)      (free:used)
Top #x20cd0000
New #x20ba0000(1245184)    -----         -----            -----
New #x20a70000(1245184)   676:28875     191:63        494040:453552
Old #x20a20000(327680)      0:0           0:0         327256:0
Old #x20000d40(10613440)  879:297688    217:32666    1240600:6172608
Tot (Old Areas)           879:297688    217:32666    1567856:6172608
Root pages: 293 

Newspace is divided into two equal size parts (only one of which is used at any time). There are two oldspaces. Root pages contain information about pointers from oldspace to newspace.

The structure of newspace and the oldspace areas is shown at the top. Then information is printed about other objects (a root page keeps information on pointers from oldspace to newspace -- these pointers must be updated after a scavenge). Reserved foreign space is space saved for foreign functions that may be loaded subsequently. Then, there is a table showing the types and numbers of objects. Finally, used and available malloc space is displayed.

3.5 Can other things be changed while running?

Yes. The function sys:resize-areas can be used to rearrange things while running. It is typically useful to call this function, for example, after loading a large application. If you know desirable old and new space sizes for your application, it is preferable to build an image with those sizes (using the :oldspace and :newspace arguments to build-lisp-image, see building_images.htm for more information). However, you may not know until runtime what the best sizes are, in which case you can call sys:resize-areas on application startup. Be warned that it may take some time.

Another use of sys:resize-areas is when you wish to dump an image (with excl:dumplisp) that has your application loaded. You call sys:resize-areas just before dumplisp in that case.

4.0 Initial sizes of old and new spaces

The initial sizes of new space and oldspace are determined when the image is built with excl:build-lisp-image. See building_images.htm (where excl:build-lisp-image is fully documented – the page on it is brief to avoid two sources for the same complex discussion) The :newspace argument to build-lisp-image controls the initial size of newspace and the :oldspace argument the initial size of oldspace.

An image dumped with excl:dumplisp inherits new and oldspace sizes from the dumping image. See dumplisp.htm.

sys:resize-areas will restructure old and newspace sizes in a running image.

The garbage collector will automatically resize old and newspace when it needs to. The amount of resizing depends on space required to allocate or move to oldspace live objects, and also on the parameters that relate to sizes.

5.0 System parameters and switches

The parameters and switches described under the next set of headings control the action of the garbage collector. You may change them during run time to optimize the performance of the Lisp process. All parameters and switches values may be set with setf. However, some values should not be changed by you. The descriptions of the parameters say whether you should change their values. By default, the system does automatically increase the generation number. You may find that it is useful to step it yourself at appropriate times with a call to sys:gsgc-step-generation.

There is really no difference between a parameter and a switch other than the value of switches is typically t or nil while parameters often have numeric values. However, once both were implemented, it became difficult to redo the design.

The function sys:gsgc-parameters prints the values of all parameters and switches. Sys:gsgc-switch and sys:gsgc-parameter retrieve the value of, respectively, a single switch or a single parameter, and with setf can set the value as follows.

(setf (sys:gsgc-parameter parameter) i>value)
(setf (sys:gsgc-switch switch) value)

Switches and parameters are named by keywords.

5.1 Parameters that control generations and tenuring

The first three parameters relate to the generation number and when objects are tenured. Please note that of the three parameters, you should only set the value of :generation-spread.

5.2 Parameters that control minimum size

The following parameters control the minimum size of newspace and when the system will allocate a new newspace. At the end of a scavenge, at least :free-bytes-new-pages plus :free-bytes-new-other bytes must be free, and at least :free-percent-new percent of newspace must be free. If these conditions are not met, the system will allocate a new newspace, large enough for these conditions to be true after allocating the object that caused the scavenge, if there is one. (Unless explicitly called by the user, a scavenge occurs when the system is unable to allocate a new object.) Note that there is no system reason why there are two parameters, :free-bytes-new-pages and :free-bytes-new-other . Their values are added to get total free space required.

5.3 Parameters that control how big newly allocated spaces are

The final two parameters control how large new newspace (and new oldspace) will be. If newspace is expanded or a new oldspace is allocated, then at least the percentage specified by the appropriate parameter shall be free, after, in the case of newspace, the object that caused the scavenge has been allocated, and after, in the case of oldspace, all objects due for tenuring have been allocated. There are different concerns for the newspace parameter and the oldspace parameter.

Let us consider the oldspace parameter first. In the case where no foreign code is loaded, then oldspaces are carved out of newspace, and newspace grows up into memory as needed. If each new oldspace is just large enough, the next time an object is tenured, another oldspace, again just large enough, will be created, and the result will be a bunch of small oldspaces, rather than a few larger ones. This problem will not occur if there is foreign code, since some oldspaces will be as large as previous newspaces. If the function room shows a bunch of little oldspaces, you might try increasing the :expansion-free-percent-old parameter to cure the problem. However, sys:resize-areas can be used instead to coalesce the oldspaces into one.

The newspace parameter is more complicated, since newspace can grow incrementally (assuming growth is not blocked by foreign code). Since growing newspace takes time, you want to ensure that when newspace grows, it grows enough. Therefore, it is essential that :expansion-free-percent-new be larger than :free-percent-new. Otherwise, you might find newspace growing just enough to satisfy :free-percent-new, and then having to grow again at the next scavenge, since allocating a new object again reduced the free space below the :free-percent-new threshold.

5.4 Gsgc switches

There are several switches which control the action of gsgc. The value of a switch must be t or nil. The function sys:gsgc-switch takes a switch name as an argument and returns its value or with setf, sets its value. sys:gsgc-parameters also prints out their values. The switches can be set by evaluating the form

(setf (sys:gsgc-switch switch-name) nil-or-non-nil)

These examples show the effect on gc messages of :stats and :verbose being true. When :print is true but both :stats and :verbose are nil, a message like the following is printed during a scavenge:

gc: done

When :verbose is also true but :stats nil, the message is:

scavenging...done

When :stats is true and :verbose nil, the message is similar to:

gc: E=34% N=30064 O+=872 pfu=0+101 pfg=1+0

The same message with :verbose true would be:

scavenging...done eff: 34%, copy new: 30064 + old 872 = 30936
Page faults: non-gc = 0 major + 101 minor, gc = 1 major + 0 minor

When :verbose is nil, abbreviations are used. Their meanings are explained when :verbose is true. E or eff. is efficiency: the ratio of non-gc time and all time (the efficiency is low in our example because we forced gc's in order to produce the example; as we say elsewhere, efficiencies of less than 75% are a cause for concern when the gc is triggered by the system). The copy figures are the number of bytes copied within newspace and to oldspace. Page faults are divided between user (pfu or non-gc) caused and gc (pfg or gc) caused. See the Unix man page for getrusage for a description of the difference between major and minor page faults.

5.5 Gsgc functions and variables

6.0 Global garbage collection

In a global garbage collection (global gc), objects in oldspace are garbage collected. Doing so frees up space in oldspace for newly tenured objects. Global gc's are time consuming (they take much longer than scavenges) and they are not necessary for Lisp to run.

The effect of never doing a global gc is the Lisp process will slowly grow larger. The rate of growth depends on what you are doing. The costs of growth are that the paging overhead increases and, if the process grows too much, swap space is exhausted, perhaps causing Lisp to stop or fail.

You have complete control over global gc's. The system will keep track of how many bytes have been tenured since the last global gc. You can choose one of these options for global gc:

1. you can cause the system to print a message when a specified number of bytes have been tenured recommending that you cause a global gc;
2. you can cause the system to trigger a global gc automatically when that number of bytes have been tenured;
3. you can have the system trigger a global gc and print a message (the default behavior); or
4. you can have the system do nothing at all about global garbage collection.

This behavior is controlled by the global variable excl:*global-gc-behavior*.

The variable excl:*tenured-bytes-limit* is used in conjunction with excl:*global-gc-behavior*. The number of bytes tenured (moved to oldspace) since the last global gc is remembered and the excl:*global-gc-behavior* depends on when excl:*tenured-bytes-limit* is exceeded.

6.1 The tenuring macro

The excl:tenuring macro causes the immediate tenuring (moving to oldspace) of all objects allocated while within the scope of it body. This is normally used when loading files, or performing some other operation where the objects created by forms will not become garbage in the short term. This macro is very useful for preventing newspace expansion.

7.0 Gc cursors

It is useful if possible to provide some sort of cue while garbage collections are occurring. This allows users to know that a pause is caused by a gc (and not by an infinite loop or some other problem). Typical cues include changing the mouse cursor, printing a message, or displaying something in a buffer as Emacs does when the emacs-lisp interface is running.

Unfortunately, providing such a cue for every scavenge is a difficult problem and if it is done wrong, the consequences to Lisp can be fatal. However, we have provided an interface for the brave. The functions excl:gc-before-c-hooks and excl:gc-after-c-hooks return settable lists of addresses of C functions to be called before and after a gc.

Luckily, scavenges are usually fast and so failing to provide a cue may not be noticeable. Global gc's, however can be slow but it is possible to provide a cue for a global gc even without using C functions. There are two strategies: (1) determine when a global gc is necessary and either schedule it when convenient or warn the user that one is imminent; (2) do not give advance warning but provide a cue when it happens. Looking at these examples, you can probably craft your own method of warning or cue.

Note that in these examples, we replace the value of excl:*gc-after-hook* with a new value, destroying the current value (which provides for the default automated behavior). We save the default function so it can be restored if desired.

(setf old-gc-after-hook-fun excl:*gc-after-hook*)

One way to implement the first strategy is to set a flag when a global gc is needed and then have code that acts on that flag. This code can be run at your choosing -- but be sure that it is run at some point. You might do this:

Make sure you compile my-gc-after-hook before making it the value of excl:*gc-after-hook*. Now, define a function that triggers a global gc (calls (gc t)) when *time-for-gc-p* is true. This function can be called by a user of your application, or when your application is about to do something that the user expects to wait for anyway, or whenever, so long as it is called at some point.

In the second strategy, we provide some cue to the user that a global gc is occurring. We have not included the code for the cue (you should supply that) and notice we have gone to some pains to avoid a recursive error (where the garbage collector calls itself).

Note:

• Because the after hook is called whenever a gc (including a global gc) occurs, one wants to be sure that the code doesn't get into some kind of recursive loop. *prevent-gc-recursion-problem* achieves that.
• You replace these lines:

with whatever code you want, but be careful that there is no possibility of waiting (for user input, e.g.) or going into an infinite loop because you are in a without-interrupts form and waiting is wrong and an infinite loop is fatal in that case.

8.0 Other gc information

The following list contains information and advice concerning gsgc. Some of the information has already been provided above, but is given again here for emphasis.

1. While a garbage collection is happening, the handling of asynchronous signals (such as results from entering the Unix interrupt character or from certain mouse actions in a window system) is blocked. The signals are queued (with duplicated signals thrown out) until the garbage collection has completed.
2. Do not set the :auto-step switch to nil unless some other method of stepping the generation is enabled (including specific action by you). If objects are not tenured, newspace will grow, filling up with long-lived objects, and performance will degrade significantly.
3. There is no way for you directly to cause a specific new object to be tenured immediately except by calling excl:gc with the argument :tenure (which will cause all live objects to be tenured). There is no way to prevent a specific object from ever being tenured except by disabling generation stepping and thus preventing all objects from being tenured.
4. Users should not set the value of the current generation or the tenure limit. The behavior of these values is algorithm-dependent in a non-intuitive way. Control is exercised with generation stepping and setting :generation-spread.

9.0 gc errors

It is not easy to cause a gsgc error. Such errors are usually catastrophic (often Lisp dies either without warning or with a brief message that some unrecognizable object was discovered). Once the garbage collector becomes confused, it cannot be straightened out.

Such errors can be caused when Lisp code is compiled with the compiler optimizations set so that normal argument and type checking is disabled. For example, if a function is compiled with the values of speed and safety such that the compiler:verify-argument-count-switch is nil, and that function is passed the wrong number of arguments (usually too few), it can trigger a fatal gsgc error. Before you report a gsgc error as a bug (and please do report them), please recompile any code where checking was disabled with settings of speed and safety which allow checking. See if the error repeats itself. See 8.0 Declarations and optimizations  in compiling.htm for more information on compiler optimization switches and values of speed and safety.

Garbage collector errors may also be caused by foreign code signal handlers. Note that foreign code signal handlers should not call lisp_call_address or lisp_value. See foreign_functions.htm for more information on signals.

See the information on the :dump-on-error gsgc-switch in 5.4 Gsgc switches above.

9.1 Storage-condition errors

The Allegro CL image will grow as necessary while running. If it needs to grow and it cannot, a storage-condition type error is signaled (storage-condition is a standard Common Lisp condition type). These errors can arise from insufficient swap space. If Lisp requests that the Lisp process be allocated more swap space but the Operating System does not allocate the space, an error similar to the following is signaled:

A global gc may free up enough space within Lisp to continue without growing. Killing processes other than Lisp may free enough swap space for Lisp to grow. But it may be the case that your system has insufficient swap space for your Lisp application. If that is the case, you will have to exit from Lisp, increase the swap space on your machine, and try Lisp and your application again. You trigger a global gc by evaluating

(excl:gc t)

9.2 Gsgc failure

When the garbage collector gets confused, usually by following what it believes to be a valid pointer, but one that does not point to an actual Lisp object, Lisp fails with a message like:

system error (gsgc): Unknown object type at (0xc50ec9a)
The internal data structures in the running Lisp image have been
corrupted and execution cannot continue.  Check all foreign functions
and any Lisp code that was compiled with high speed and/or low safety,
as these are two common sources of this failure.  If you cannot find
anything incorrect in your code you should contact technical support
for Allegro Common Lisp, and we will try to help determine whether
this is a coding error or an internal bug.
Would you like to dump core for debugging before exiting(y or n)? 

There is no recovery.

The causes of such errors can be a bad pointer introduced from foreign code, incorrectly declared code when declarations are trusted (recompile at low speed, high safety and see whether the problem persists), or a gc bug. You can get a core file, as indicated. As also indicated, if there is no obvious problem (such as foreign code overwriting the Lisp heap), contact Franz Inc. technical support at bugs@franz.com.

10.0 Weak vectors, finalizations, static arrays, etc.

A Lisp object becomes garbage when nothing points to or references it. The way the garbage collector works is it finds and identifies live objects (and, typically, moves them somewhere). Whatever is left is garbage. Finalizations and weak vectors allow pointers to objects which will not, however, keep them alive. If one of these pointers exists, the garbage collector will see the item and (depending on the circumstances), either keep it alive (by moving it) or abandon it.

It is useful to distinguish two actions of the garbage collector. When the only pointers to an object are weak pointers or finalizations, the garbage collector follows those pointers and `identifies the object as garbage'. If it decides not to keep the object alive, it `scavenges the object away'. Note that any Lisp object can be scavenged away - that just means that the memory it used is freed and (eventually) overwritten with new objects. Only objects pointed to by a weak vector or a finalization can be identified as garbage, however. Live objects are not garbage and objects with nothing pointing to them are not even seen by the garbage collector.

10.1 Weak arrays and hashtables

Weak arrays are similar to simple arrays (that is, it may not have a fill pointer and its elements can be any Lisp objects). They are created with the standard Common Lisp function make-array (using the non-standard weak keyword argument) or (if a vector is desired) with the function excl:weak-vector. As we said in the brief description above, the most important feature about weak arrays is that being pointed to by a weak array does not prevent an object from being identified as garbage and scavenged away. When an object is scavenged away, the entry in a weak array that points to the object will be replaced with nil.

Weak arrays allow you to keep track of objects and to discover when they have become garbage and disposed of. An application of weak arrays might be determining when some resource external to Lisp can be flushed. Suppose that all references to a file external to Lisp are made through a specific pathname. It may be that once all live references to that pathname are gone (i.e. the pathname has become garbage) the file itself is no longer needed and it can be removed from the filesystem. If you have a weak array which points to the pathname, when the reference is replaced by nil by the garbage collector, you can tell the system to kill the file.

It is important to remember that objects which have been tenured will not be identified as garbage unless a global gc is performed. If you use weak arrays, you should either arrange that global gc's are done regularly or that you do an explicit global gc before checking the status of an element of the weak array.

Weak vectors are created by the function excl:weak-vector. Weak arrays are created by make-array using the non-standard weak argument. See the discussion of extensions to make-array (in implementation.htm) for restrictions on other arguments when weak is true. (In short, the array cannot have a specialized type, cannot be displaced, and cannot have its allocation specified.)

We provide a simple example of weak vectors (weak arrays differ from weak vectors only in having more dimensions) and finalizations in 10.3 Examples of weak vectors and finalizations below.

Weak hashtables are also supported. See implementation.htm for information on an extension to cl:make-hash-table that creates weak hashtables.

10.2 Finalizations

A finalization associates an object with a function. If the object is identified as garbage by the garbage collector, the function is called with the object as its single argument before the object is scavenged away.

The timing is important here. While the garbage collector is running, nothing else can be done in Lisp. In particular, functions (except those internal to the garbage collector itself) cannot be called. Therefore, finalizations require two passes of the garbage collector. In the first pass, the object is identified as garbage. The garbage collector sees the finalization and so, instead of immediately scavenging the object away, it keeps it alive and makes a note to call the finalization function as soon as it finishes the current scavenge (or global gc). The finalization is removed from the object after the function is run so during the next garbage collection, the object is either garbage or, if a weak vector points to it, again identified as garbage and (since it no longer has a finalization) scavenged away. See the example in 10.3 Examples of weak vectors and finalizations below.

A finalization is not a type of Lisp object. Finalizations are implemented as vectors (but that may change in a later release). You should not write any code which depends on the fact that finalizations are implemented as vectors.

You schedule a finalization with the function excl:schedule-finalization. The function excl:unschedule-finalization removes the finalization from the object. Finalizations are only run once, immediately after the garbage collection which identified the object as garbage. The object is not scavenged away during the garbage collection in which it is identified as garbage (since it must be around to be the argument to the finalization function).

10.3 Example of weak vectors and finalizations

;; We define a weak vector and a function to be called by finalizations.
USER(10): (setq wv (weak-vector 1))
#(nil)
USER(11): (defun foo (x) (format t "I am garbage!~%"))
foo
;; We create an object and put it in the weak vector:
USER(12): (setq a (cons 1 2))
(1 . 2)
USER(13): (setf (aref wv 0) a)
(1 . 2)
;; We schedule a finalization.
USER(14): (schedule-finalization a 'foo)
#((1 . 2) foo nil)
;; We remove the reference to the cons by setting the value of A to NIL.
USER(15): (setq a nil)
nil
;; We evaluate unrelated things to ensure that the object
;; is not the value of *, **, or ***.
USER(16): 1
1
USER(17): 2
2
USER(18): 3
3
;; We trigger a scavenge. The finalization function is called.
USER(19): (gc)
I am garbage!
 
;; At this point, the weak vector still points to the object:
USER(20): wv
#((1 . 2))
;; The next gc causes the value in the weak vector to
;; be changed.
USER(21): (gc)
USER(22): wv
#(nil)

10.4 Static arrays

The data in a static array is placed in an area that is not garbage collected. This means that the data is never moved and, therefore, pointers to it can be safely stored in foreign code. (Generally, Lisp objects are moved about by the garbage collector so a pointer passed to foreign code is only guaranteed to be valid during the call. See foreign_functions.htm for more information on this point.) Only certain element types are permitted (listed below). General arrays (whose elements can be any Lisp object) can not be created as static arrays.

The primary purpose of static arrays is for use with foreign code. They may also be useful with pure Lisp code but only if the array is needed for the whole Lisp run and the array never has to be significantly changed. The problem is the array is not garbage collected and there is no way (within Lisp) to free up the space.

Static arrays are returned by cl:make-array with the (Allegro CL-specific) allocation keyword argument specified. The data is stored in an area which is not garbage collected but the header (if any) is stored in standard Lisp space. The following element types are supported in static arrays.

bit
(signed-byte 8)
(unsigned-byte 4)
(unsigned-byte 8)
(signed-byte 16)
(unsigned-byte 16)
(signed-byte 32)
(unsigned-byte 32)
character
single-float
double-float
(complex single-float)
(complex double-float)

See implementation.htm for information on this extension to cl:make-array. See excl:lispval-other-to-address for information on freeing static arrays.

Copyright (C) 1998-1999, Franz Inc., Berkeley, CA. All Rights Reserved.