Re: Lua's memory management was RE: Lua's GC

[RLake@...]

Paul escribió:

>> The obvious solution to this problem is to make sure that all internal
>> references are indirect (i.e. a table identifier is NOT just a memory
>> address) so that compaction can be done trivially.  Is this what Lua
>> does right now, or am I completely confused on this subject?

> I believe Lua has more to care about in GC besides object
> references, string, udata, closure and functions are all handled
> differently. And yes, they are all direct memory pointers.

> There are good memory allocators that just replace malloc &
> free, but they may not provide specific functionalities like
> what you have mentioned though.

The reason it's hard for extendable languages like Lua to compact memory
is that C routines like to iterate over strings using pointers. If a
string got relocated in the middle of such an iteration, chaos would
ensue.

While compacting garbage collectors have an intuitive appeal to them,
in practice they do not necessarily turn out to be better:

1) With a good memory allocator, fragmentation is suprisingly low in
most real life programs. The key is "with a good memory allocator".
I'd recommend Doug Lea's.

2) Compacting garbage collectors tend to use up an awful lot of
(virtual) memory; the classic copying algorithm involves copying the
entire heap, which means that you need effectively two heap spaces.
Compacting in place is possible but you have to store forwarding
pointers somewhere, which can get tricky.

3) Copying a large object is a lot of overhead.

4) Copying/compacting garbage collectors interact badly with
virtual memory systems; they can create an awful lot of paging.
There are possible ways to avoid this but they require specific
OS features, making even a semi-portable solution impossible.

5) There is some evidence that copying garbage collectors
decrease locality of reference, increasing paging activity.

References: Richard Jones and Rafael Lins: Garbage Collection, Algorithms
for Automatic Dynamic
Memory Management. (see
<http://www.cs.ukc.ac.uk/people/staff/rej/gcbook/gcbook.html>)
This is mandatory reading for anyone interested in the subject.

Mark S. Johnstone, Paul R. Wilson. 1998. The Memory Fragmentation Problem:
Solved?. ACM. ISMM'98 pp.26-36
(I thought this paper was available online somewhere but I can't find a URL
just now.) Here's the
abstract:
"We show that for 8 real and varied C and C++ programs, several
conventional dynamic storage allocators provide near-zero fragmentation,
once overheads due to implementation details (headers, alignment, etc.) are
properly accounted for. This substantially strengthens our previous results
showing that the memory fragmentation problem has generally been
misunderstood, and that good allocator policies can provide good memory
usage for most programs. The new results indicate that for most programs,
excellent allocator policies are readily available, and efficiency of
implementation is the major challenge. While we believe that our
experimental results are state-of-the-art and our methodology is superior
to most previous work, more work should be done to identify and study
unusual problematic program behaviors not represented in our sample."