Garbage Collection for ISE Eiffel

Contents

1 ABSTRACT
2 MAJOR PROPERTIES
3 GENERAL PRINCIPLES
4 OBJECT DISPLACEMENT
5 USE OF THE STANDARD MALLOC
6 THE GARBAGE COLLECTOR

6.1 Structure
6.2 Generation scavenging
6.3 Mark-and-sweep
6.4 Memory compaction

7 THE GARBAGE COLLECTOR IN ACTION

This is ISE Technical Report TR-EI-56/GC, version 3.3.9. Copyright Interactive Software Engineering Inc., 1991-1997.

Disclaimer: this note is an informal description made available to the Internet community as a service to people interested in Eiffel and memory management techniques. It is a working paper, not a contractual document, and is not part of the documentation of ISE Eiffel. None of what it describes is binding on ISE, and all the information presented is subject to change without notice.

1 ABSTRACT

Running a program written with an object-oriented language means creating and destroying myriad run-time objects. If dead objects are not collected, they pollute memory and shorten the execution of the program.

Eiffel fundamentally relies on the existence of a Garbage Collector (GC). The next sections describe the essential properties of the ISE Eiffel's sophisticated garbage collection mechanism.

2 MAJOR PROPERTIES

A crucial property of the ISE Eiffel garbage collector is that it not only frees memory for reuse by further object allocations, but actually returns memory to the operating system, freeing it for reuse by not just by Eiffel itself but by any other part of the application or even another program.

This property (although difficult to implement and for that reason seldom found in commercial garbage-collecting implementations) is indispensable for mission-critical developments, in particular systems that need to run for a long time, or permanently. Without it, a long-running system is bound, especially in a paged environment, inexorably to fill up available memory resources.

The following additional engineering goals presided over the garbage collector design:

Efficient memory collection.

Small memory overhead.

Incremental behavior (in other words, the garbage collector must not block the application for any significant period of time).

All available evidence shows that these goals have been met. For many users, the garbage collector is invisible; unused objects just go away. We have actually had users call customer support and ask how to turn on garbage collection in the event their systems grow bigger -- only to be told that the GC was already turned on by default, although they could turn it off it they wished to.

3 GENERAL PRINCIPLES

The design of a garbage collector must take into account the memory allocation mechanism. In fact they are intimately connected: the garbage collector uses memory allocation, and memory allocation calls the garbage collector when needed.

Three major requirements make the memory management for Eiffel programs a difficult task:

In Eiffel, one can call C functions, which have their own needs for memory allocation. We must therefore consider that there are two distinct kinds of memory: Eiffel memory and C memory.

All objects are not created equal.We must distinguish normal objects from special objects. The former have a steady size, statically determined by the number of attributes; the latter have a variable size (arrays, strings).

Finally, as noted above, it is not enough to free memory for reuse by Eiffel: we must also be able to give it back for good to the operating system.

For these reasons, Eiffel memory allocation cannot rely on the standard malloc() system call (which, among other limitations, does not return memory to the operating system).

ISE Eiffel uses its own memory management mechanism. Instead of directly mallocing objects from the operating system, an application asks the kernel for memory chunks and allocates objects in these chunks.

4 OBJECT DISPLACEMENT

For Eiffel users, the principally relevant property of the garbage collector is that objects can move. If you are doing pure Eiffel development, this is totally invisible. But if you are combining Eiffel with C, you must be careful if the C code both:

Keeps references to Eiffel objects.

Performs its own object allocations (malloc).

If your C software fits this pattern you must take a few simple precautions to protect the Eiffel objects remembered on the C side. The CECIL library offers the necessary primitives. See Eiffel: The Language, chapter 24, and the complementary information available on-line at ftp://ftp.eiffel.com/pub/examples/cecil.

5 USE OF THE STANDARD MALLOC

The ISE Eiffel replacement for malloc is fully compatible with the default version, causing no particular problem even if the C side, or existing libraries, make extensive use of malloc.

In some exceptional cases, an external tool may require not only the specification of the default malloc but its exact implementation. Projects that need this facility may be able to obtain from ISE a special version of the run-time that uses the default malloc. (This possibility may be available on some platforms only, and assumes an up-to-date maintenance contract.) Future versions of the environment may include this possibility as a Lace option.

If standard malloc is used, it will clearly be impossible to return memory to the operating system.

6 THE GARBAGE COLLECTOR

6.1 Structure

Given the intricacy of the problem and the specificities of Eiffel, there was no ready-made algorithm.

The garbage collector actually uses several basic algorithms that can be used together (for some of them) or independently. The right algorithm is determined by the circumstances of each call, including for example the urgency of the memory need.

6.2 Generation scavenging

Generation scavenging, one of the algorithms, relies on the experimental observation that young objects have a smaller probability of surviving than old objects. Hence the idea of splitting objects into several generations. The young generations will be collected more often than the old ones. Since most of the objects have a short life, it is likely that the biggest part of recycled memory will be obtained from the young generations.

A main advantage of this technique is that a collection need not explore all the objects. Only old objects with references to young ones and local variables are recursively followed.

A generation is collected when its occupation has reached a given value. When a generation is collected, all the surviving objects become older. When they have reached a given age, they are tenured to the next generation.

The algorithm achieves the right tradeoff between low tenure age (meaning that the old generation becomes too big) and high tenure age (meaning too frequent scavenging).

6.3 Mark-and-sweep

The mark-and-sweep, another of the basic algorithms, consists of two steps. The first step recursively explores the live objects and marks them. The second step collects dead objects.

The roots are the root object of the system and local entities.

6.4 Memory compaction

The memory compaction algorithm compacts memory, returning unused parts to the operating system, at the lowest possible cost. It uses a mix of mark-and-sweep and scavenging.

The algorithm divides the memory into n blocks and takes n-1 cycles to compact them all.

7 THE GARBAGE COLLECTOR IN ACTION

When the primary area is full, a cycle of garbage collection (generation scavenging) occurs. In the worst case, this cycle does not collect enough memory and a full collection (mark-and-sweep) is launched, possibly with a memory compaction step. Only as a last resort will the application asks the operating system for more memory, if it is still not possible to allocate a new object.

The main algorithms are incremental, and their time consumption is negligible compared to the program run-time. Internal statistics keep track of the memory allocated and helps to determine the proper algorithm to call.

The garbage collector can be diverted from its normal behavior through the speed option. In this case, instead of trying to collect all the available memory, it will ask for more memory earlier. It is thus fully under the developer's control to decide how best to resolve the space-time tradeoff involved.

By default, each Eiffel application includes the garbage collector and uses it. But you can control the behavior of the memory management mechanism and tune it to fit your specific needs through a set of procedures available from class MEMORY, which enable you to turn the garbage collector on and off, and launch full collection cycles at specific times.

© 1985-2012 Eiffel Software. All rights reserved. -- Privacy Policy