Previous Contents Next

Memory Management by Objective CAML

Objective CAML's garbage collector combines the various techniques described above. It works on two generations, the old and the new. It mainly uses a Stop&Copy on the new generation (a minor garbage collection) and an incremental Mark&Sweep on the old generation (major garbage collection).

A young object that survives a minor garbage collection is relocated to the old generation. The Stop&Copy uses the old generation as the to-space. When it is finished, the entire from-space is completely freed.

When we presented generational garbage collectors, we noted the difficulty presented by impure functional languages: an old-generation value may reference an object of the new generation. Here is a small example. 

# let older = ref [1] ;;
val older : int list ref = {contents=[1]}
(* ... *)
# let newer = [2;5;8] in
   older := newer ;;
- : unit = ()
The comment (* ... *) replaces a long sequence of code in which older passes into the older generation. The minor garbage collection must take account of certain old generation values. Therefore we must keep an up-to-date table of the references from the old generation to the new that becomes part of the set of roots for the minor garbage collection. This table of roots grows very little and becomes empty just after a minor garbage collection.

It is to be noted that the Mark&Sweep of the old generation is incremental, which means that a part of the major garbage collection happens during each minor garbage collection. The major garbage collection is a Mark&Sweep that follows the algorithm presented on page ??. The relevance of this incremental approach is the reduction of waiting time for a major garbage collection by advancing the marking phase with each minor garbage collection. When a major garbage collection is activated, the marking of the unprocessed regions is finished, and the reclamation phase is begun. Finally, as Mark&Sweep may fragment the old generation significantly, a compaction algorithm may be activated after a major garbage collection.

Putting this altogether, we arrive at the following stages:
  1. minor garbage collection: perform a Stop&Copy on the young generation; age the surviving objects by having them change zone; and then do part of the Mark&Sweep of the old generation.

    It fails if the zone change fails, in which case we go to step 2.
  2. end of the major garbage collection cycle.

    When this fails go on to step 3.
  3. another major garbage collection, to see if the objects counted as used during the incremental phases have become free.

    When this fails, go on to step 4.
  4. Compaction of the old generation in order to obtain maximal contiguous free space. If this last step does not succeed, there are no other possibilities, and the program itself fails.
The GC module allows activation of the various phases of the garbage collector.

A final detail of the memory management of Objective CAML is that the heap space is not allocated once and for all at the beginning of the program, but evolves with time (increasing or decreasing by a given size).

Previous Contents Next