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

[Ralph Becket]

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.  This could be a real win with the 
conservative GC.

On a related note, the structure reuse optimization does
take advantage of di/uo mode annotations; once we get ui
and unique nested modes working it will be sensible to
extend the library with more accurate modes.

-- Ralph
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------