GC and Mercury

[Fergus Henderson]

On 14-Mar-1998, Darius Blasband <darius at phidani.be> wrote:
> The questions I would be led to ask are the following:
> 
> - Do you have to go for compaction ?

No, not necessarily (e.g. the current conservative garbage collector
does not compact).  However, compaction does have a major advantage
for logic programming languages: if you compact, then you can get
cheap memory reclamation on failure, e.g. by simply resetting
the heap pointer.

> - Do you have to go for incremental Gc ?

Some applications need it, some don't.
Ideally the Mercury implementation would offer a choice of
garbage collectors, including at least one incremental
and at least one non-incremental collector.

> - Do you have measured data about the distribution of the allocation sizes
>   in Mercury systems ?

Yes, we do have some.  The latest development release of Mercury includes
support for memory profiling.  Unfortunately the data is classified by
type rather than by allocation size, and for some types the
allocation size can vary, so the data is not exactly what we want here,
but it's close enough to be useful.

For the Mercury compiler itself, the figures are as follows.

	avg size     frequency	description
	--------     ---------	-----------
	2.000000     54.2%	types with only 2 word cells (mostly list cons)
	1.000000     14.6%	types with only 1 word cells (mostly io__result)
	5.319964     10.4%	tree234 -- a mixture of
				4, 7, and 10-word cells
	5.000000      6.4%	types with only 5 word cells
				(mostly parser__state)
	2.894984      2.5%	term
	3.000000      1.6%	types with only 3 word cells (mostly varset)

Actually that's slightly out-of-date data, since we made a few
changes to reduce the amount of memory allocation in a couple
of hot spots in the compiler.

Also note that the figures are a bit different if you consider
the amount of memory allocated rather than the number of allocations.

> If applicable (as it is the case for most systems I have
>   encountered so far), a fixed size slot allocation scheme could provide
>   top performance for over 80% of the allocations, without extra
>   fragmentation, thereby reducing the need for a compacting gc. 

The Boehm (at al) conservative GC that we are currently using
does this.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.