Re: speed versus C

From: Anton Moscal (msk@post.tepkom.ru)
Date: Mon Oct 11 1999 - 11:08:01 MET DST


Date: Mon, 11 Oct 1999 13:08:01 +0400 (MSD)
From: Anton Moscal <msk@post.tepkom.ru>
To: skaller <skaller@maxtal.com.au>
Subject: Re: speed versus C
In-Reply-To: <38001B53.BD6283EE@maxtal.com.au>

On Sun, 10 Oct 1999, skaller wrote:

> > Assignment to array element can be very ineffictive in O'Caml due to the
> > following reasons:
> >
> > 1)O'Caml uses generational GC.
>
> Can you explain what a 'generational' collector is?

http://www.iecc.com/gclist/GC-faq.html

This page contains very good introduction into main garbage collection
algorithms. From this FAQ:

-------------------------
 Generational collection

Based on the observation that most objects have short lifetimes, it is
useful to restrict garbage collection to the most recently allocated objects.

A generational collector maintains several ``generations'' of objects.
Newly created objects are all put in the ``youngest'' generation, and
when the space allocated for that generation is full, the collector will
use the root set (and any pointers from older generations to the youngest
generation -- see below) to reclaim dead objects from the youngest
generation only, leaving the ``older'' generations untouched. Objects
that survive after several (perhaps just one) collection of the youngest
generation are ``promoted'' to the next older generation, and when that
generation becomes full, it and all the generations younger than it are
collected.

The difficulty with generational collectors is the identification of
pointers from older generations into younger ones. An observation is that
such references are uncommon in most programs: new objects typically
point to older objects; this is clearly true in pure functional languages
where assignment is prohibited, but is common for many programs and
languages. Nonetheless, such references do exist, and a collector must
handle them. When a pointer to a younger generation object is written
into an old object, the pointer (or just the old object) is recorded so
it can be scanned when the younger generation is collected.
------------------------

O'Caml uses simple algorithm with two generations: young & old objects.

Regards,
Anton Moscal



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:26 MET