RE: Incremental garbage collection coming to Lua soon?

["Nick Trout" <nick@...>]

> From: David Jeske [mailto:jeske@chat.net]
> Thanks for this pointer. Here are a few other datapoints for your
> ref-counting is good list:

I'm not sure that I agree all these points should be added to the
ref-counting-is-good list. If a hybrid mark and sweep/reference counting
system is the most efficient then so be it, but I fail to see how a lot
of your points are relevant.


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

Are you are making the assumption that Lua uses a copying and sweeping,
compacting GC? Lua uses non-moving mark and sweep. I don't see a
justification for RC here.


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

I think Python's GC implementation was an afterthought and the cycle
reference collection looks like a hack to me, i.e. you have to specify
how containers work. I wouldn't call any of the examples given high
performance scripting languages. Shouldn't we be looking for scripting
languages or systems which are deemed to have efficient memory usage,
not their popularity. We don't want to turn Lua into a run of the mill
common language implementation - I, and a lot of people on this list,
want a small, fast, efficient language.


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

Hence an incremental one is planned.


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

I believe Java is very inefficient in its use of memory. I think the
size of the pauses is related to its inefficient use of memory. I agree
they are unacceptable. [I don't know if I've used a Java VM that has
incremental collection or not; does the PC Sun or MS one have it?].
There is no talk of going to a copying collector.


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

This doesn't mean it should be added to the ref-counting-is-good list
though does it, where is the justification?


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

I am willing to believe reference counting would relieve pressure on the
M&S algorithm, but we are talking about a generational optimisation for
Lua so this should become less of a problem. I think the issue here is
whether the write barrier implementation for the generational
incremental GC is a bigger overhead than just using RC.


> 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 doesn't justify reference counting is good. You've made an analogy
only.


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

Which is probably why Lua doesn't use it.


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

I don't think anyone is suggesting this.

Regards,
Nick