Re: Incremental garbage collection coming to Lua soon?

[David Jones <drj@...>]

In message <20030731000634.A9821@mozart>, David Jeske writes:
> 
> Thanks for this pointer. Here are a few other datapoints for your
> ref-counting is good list:

As it happens I have just got back from a client's site where I
have been assisting in the deployment of a mostly moving,
generational, incremental, page-protection based, garbage collector.

Whilst this is not at all like the collector that the lua team are
planning on implementing it does provide data and evidence that weaken
your points.

The collector is used in a interactive 3D design application.
Typical heap sizes range from 20MB to 500MB, pauses are essentially
unnoticeable.  Often a collection can take place entirely incrementally
as the user is moving the mouse from one part of the window (say 3d view
window) to another (say the object selector tool).  The only way to tell
that collections are happening is to use the inspection tools.

As deployed the collector is a mostly copying read barrier collector:
the Dijkstra tricolor invariant is maintained by turning grey objects
black whenever the mutator attempts to read a grey object.  The
Virtual Memory page protection system is used to implement the read
barrier meaning that the mutator has no extra code to implement the
read barrier.

> 1) Refcounting work is proportional to mutator changes, not heap
>    size. Every copying or sweeping collector I've used breaks down as
>    the heap gets even moderately big.

Our collector works fine up to 500MB and beyond, it has a scalable
architecture and is designed to work well at any size, including in 64
bit address spaces.

Your statement swings both ways of course, imagine the number of
reference count changes that sorting an array of strings involves.

> 2) The most popular automatic memory management systems use reference
>    counting including: Visual Basic, COM, Perl, and Python.

Since Java is in most mobile telephones these days I suspect it has a
deployment base way beyond any of the above.  However, this is an "appeal
to numbers" argument; unfortunately just because something is popular,
that doesn't make it right.

> 3) Pausing collectors are a constant nusance holding back the
>    capabilities of languages with garbage collection.

There are incremental collectors with bounded pause times.

Moreover a naive reference counting scheme does not have bounded
pause times either.  Imagine creating a list with a million elements
(or more plausibly in lua a table with a million unique strings)
and then letting go of the list, suddenly a million things need
their reference count decrementing and then consequently freeing.
Obviously this naive scheme can be improved, but so can a naive
garbage collector.

> 4) The most popularly used sweeping/copying collectors exist for Java,
>    which is notorious for it's pauses in interactive apps. 

Yes, there are bad implementations of garbage collection out there.
There are even bad implementations of good garbage collection
algorithms.

> 5) One of the most commonly used techniques for tracking liveliness of
>    shared datastructures in C/C++ programs is manual reference
>    counting.

This argument is the same as your point 2).

> 6) Reference counting cycle finders are basically mark-and-sweep
>    collectors. In systems with large heaps and/or large allocation
>    throughput, making incremental collectors perform is a
>    challenge. Reference counting reduces pressure on the garbage
>    collector by making many objects collectable without sweeping. It
>    also allows the mark-sweep algorithm to ignore objects which can't
>    hold references to other objects. 

Neither large heaps nor large allocation rate is a barrier to making a
good incremental garbage collector.

You say that reference counting allows the mark-sweep algorithm to
ignore objects which can't hold references to other objects, but it
isn't reference counting that allows, but merely being bothered to
implement it.  Or are you suggesting a scheme in which every object has
an additional field to record whether a reference has ever been written
into it and that this is used to direct the scanning of the collector?
As far as I know no such scheme has ever been implemented.

> 7) In an incremental mark-sweep collector based on coloring, the
>    mutator-marking scheme is doing work which is sufficiently like
>    reference counting anyhow.

This is simply not true.  In the usual write-barrier scheme black
objects are turned grey if the mutator writes into them; in the usual
read-barrier scheme grey objects are scanned are turned black if the
mutator reads them.  Neither of these is very much like reference
counting, most obviously because different sets of objects are affected,
and the garbage collector only maintains a bounded amount of state (a
colour: white, grey, or black) for each object.

> 8) Copying/compacting collectors optimize something which isn't
>    generally a problem for most programs (allocation time and
>    fragmentation) and create side-effects which are unacceptable for
>    many programs (uncontrolled pauses).

Uncontrolled pauses are not a necessary side effect of copying
collectors.

The compaction issue is much tougher call.  Compaction allows faster
allocation (_much_ faster in some applications) and it does reduce
fragmentation.  It also increases cache efficiency.  It's also a lot
easier to get a moving collector to recycle unused VM pages to the OS so
that some other application or some other component in the same
application can use them.  With the right API such pages can freed and
reused without keeping them in the cache which can be highly efficient.

> 9) Copying/compacting collectors which use handles to facilitate
>    object movement increase the overhead of using all pointers due to
>    the the handle-indirection cost. For most programs this is worse
>    than the increased mutator cost of reference counting.

Quite possibly so, but noone has suggested that yet.

In conclusion:

There is no reason why garbage collection cannot be used in an
application where pause times and efficiency is important.  Indeed
I've been involved in cases where a garbage collector was used
precisely because pause times and efficiency were important.

I've spoken with Roberto about this, and I'm confident that the lua team
are careful enough to come up with a good efficient solution.

Cheers,
 drj