Re: garbage collection thoughts... again?!

[Roberto Ierusalimschy <roberto@...>]

My personal thoughts...


* I disagree with Thatcher (and Linus).  Mark-and-Sweep is a trivial
algorithm, and (as far as I know) the only GC technique that is
completely modular (it does not need any modification in other parts of
the interpreter). It has a quite acceptable overall performance. Its
main (only?) drawback is the long pauses. Reference counting (RC) is
a nightmare to implement right, can have a big performance impact
without careful optimizations (which make the implementation even more
difficult), and does not collect cycles. For those that think that RC
is conceptually simple, it is worth remembering that it took several
years after its creation for people to realize that it does not collect
cycles.


* The fact that Perl and Python use reference counting (RC) and are
very sucessful is not a very good argument.  Perl programs are not
exactly famous for not leaking memory and Python does not use "pure"
RC. Moreover, Lua has very different requirements than Perl and Python,
and has also very different characteristics.

Particularly, I believe that cycles are much more common in Lua than in
those other languages. As an example, something as simple as the
next line creates a cycle in Lua:

  function f() return 1 end

(Notice that getfenv(f).f == f ;-)

If you delete "f" you break the cycle. But if you delete the environment,
RC will not collect it.


* "make simple things simple, complex things possible". Currently it is
not possible to run a Lua program without eventual long pauses. Ending
these pauses is a complex requirement, for specialized uses. It should
be possible to do that.  But we should not sacrifice simple things (to
program without worring about cycles) to achieve that. I consider any GC
algorithm that does not collect cycles unacceptable for Lua.


* I think that any implementation that imposes an overhead on stack
manipulation in Lua would ruin its performance. (It is not by chance
that Lua is much faster than Perl and Python regarding function calls,
parameter passing, and other basic language facilities.)


* After all those "requirements", I must say that reference counting
is still an option ;) Regarding the stack, we could use a deferred
reference counting algorithm, which runs a "mark-and-sweep" only over
the stack(s) to complete a collection. (Of course, that spoils the
immediateness of reference counting, but such short stack marks can
be run much more frequently than a full mark-and-sweep.) Regarding
cycles, Rafael Lins recently published a paper called "Lazy Cyclic
Reference Counting", that seems a much improved version of his previous
algorithms.  We still have to study its impact on a "typical" Lua
program (whatever that means...).


* Whatever the final algorithm, it should be clear that it will
need some cooperation from a programmer to achieve soft real-time
performance. There will be short pauses to traverse the stack(s), to
clean weak tables, etc. (Cooperation here means things like to avoid the
use of too many weak tables or other similar rules.) There is no chance
to achieve hard real-time performance. I doubt this is possible with
any scripting language. This is difficult even for hard languages doing
dynamic memory allocation. (First you need a "malloc" that never returns
NULL...)

-- Roberto