GC and Mercury

[Fergus Henderson]

On 15-Mar-1998, Darius Blasband <darius at phidani.be> wrote:
> >... 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.
> 
> If I understand this properly, this means that any scheme that would
> allow the heap to be reset in a previous state at a cheap price would
> do the job.

That's correct.

> It might be worth considering such a scheme for a m&s collector...
> You might consider an optimistic scheme that would
> provide good performance for well-behaved systems (depth, complexity,
> granularity, depending on the approach), relying on common M&s 
> if you are outside the optimistic hypothesis.

Such as ...?

We've considered keeping a linked list of all allocations, so that at
reset time we can just traverse the list, deallocating objects as we
go.  However, even using an intrusive linked list (i.e. making the
first work of every allocated object the link), this still has a high
overhead -- one word per object.  As noted, the average size of each
object is small (2 words being the most common), so this overhead would
be quite significant.  And the cost of each reset would be at least
proportional to the number of objects allocated, not constant time.

It would still be worthwhile trying this out,
since for programs that backtrack a lot it might improve the
performance of the current M&S conservative collector quite a bit.
We just haven't gotten around to trying it yet...

> >> - 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.
> 
> What are the Mercury applications that are so real-time oriented
> that incremental GC must be considered ?

Well, we have an OpenGL interface... ;-)
In his spare time, I think Thomas Conway has been writing some
games using this interface.

Mercury aims to be a general-purpose programming language.
Real-time applications are not a speciality, but we don't
want to preclude them.

> >The Boehm (at al) conservative GC that we are currently using
> >does this.
> 
> Does it uses one or more pools ? 

Yes, it keeps a bunch of pools specifically for small objects.

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