[m-dev.] Idea for reducing cost of heap allocation

[Fergus Henderson]

On 01-May-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> Pete just gave a talk on structure reuse which prompted
> some discussion between Tyson, Pete and myself.
> 
> Pete's experiments showed that a very simple caching
> strategy for reusing dead cells significantly reduced the
> number of heap allocations performed in the ray tracer.
> 
> It occurred to us that we could extend the idea trivially
> to reduce the cost of all heap allocations by
> (a) always looking in the cache first for a cell of the
> right size (it's probably sensible to limit the cache to
> worrying about cells of, say, 1 - 4 words in size) and
> (b) if the cache does not contain a cell of the right size
> allocating N > 1 units of the required size, returning one, 
> and caching the remaining number.  With luck this should 
> reduce the cost of each genuine heap allocation by a factor
> approaching N.

That assumes that the cost of checking this cache is zero.
But it's not.  For a sufficiently efficient collector,
the cost of checking the cache will be similar to the
cost of doing a memory allocation (which is just checking
a free list).

A better bang-for-buck optimization IMHO would be to
specialize GC_malloc for different sized allocations,
e.g.

	// in Mercury runtime

	#include "gc_inline.h"

	GC_malloc_1_word() {
		return GC_MALLOC_WORDS(1); /* this is a macro */
					   /* it is the inline version of
					      GC_malloc */
	}

	GC_malloc_2_words() {
		return GC_MALLOC_WORDS(2);
	}

	etc. up to abuot 10

and then generate calls to GC_malloc_1_word(), etc.
This gets the benefit of --inline-alloc, with negligable space cost.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------