[gclist] optimal heap expansion factor?

Fergus Henderson fjh@cs.mu.OZ.AU
Fri, 17 Oct 2003 20:21:36 +1000

I've been working on adding support for type-accurate garbage collection to
the Mercury implementation.  Currently I've got a very simple two-space
copying collector.  The size of the two spaces is fixed, and currently
it collects only when the current space fills up.

I'm in the process of rewriting it so that it instead initially uses
just a small fraction of the space before collecting.  Then after each
collection, it will recompute an appropriate size at which to do the
next collection, based on how much live data remained after collection.
This approach will hopefully improve locality and reduce working set
size for programs that don't have much live data.

Specifically, I was thinking of doing something like this:

	- at program initialization:
		size_at_which_to_GC = initial_GC_size;

	- at each allocation:
		if (heap_usage > size_at_which_to_GC)

	- after each GC:
		if (size_at_which_to_GC < heap_usage * heap_expansion_factor)
		    size_at_which_to_GC = heap_usage * heap_expansion_factor;

Firstly, does that seem like a reasonable algorithm?

Secondly, any suggestions on what might be reasonable values for
"initial_GC_size" and "heap_expansion_factor"? 

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