Re: GC Compaction

[RLake@...]

Peter Hill:
> I know that Lua does garbage collection of unused objects... but does it
> also compact the free memory or does the memory pool become fragmented?

Roberto Ierusalimschy:
> Have you read "The Memory Fragmentation Problem: Solved?"
> From http://lua-users.org/lists/lua-l/2002-11/msg00288.html:

Peter Hill:
> I suspect that what they assert... that people tend to have an
exaggerated
> fear of fragmentation (exacerbated by poorly designed allocation schemes)
is
> most likely true.

> However there are a few points with regard to Lua...

> o The 1% fragmentation estimate was for good malloc strategies... a poor
one
> could have 50% fragmentation or more. Lua5 seems to just use the standard
> 'realloc / free' routines as far as I can tell so, depending on your
> development platform, things might turn out rather badly.

It is certainly true that Lua depends on the malloc library and some are
really not very good. On the other hand, it is easy to configure Lua to
use other malloc libraries. So choose a good one :)

> o The programs tested all ran for a specific limited data run... from gcc
> compiling a single source file to Perl running a script to fiddle with
> dictionary entries.

> An embedded language like Lua, however, is quite likely to find itself in
> long-running applications. For example, using Lua to handle the AI for
> monsters in some Quake-like game (which could run for hours at a session)
or
> even a permanently online game like Everquest. In such cases memory
> fragmentation *might* not escalate but, unless that is provable (rather
than
> just statistically common) it may prohibit the use of Lua.

It is probably not possible to prove anything about fragmentation. But it
is quite possibly the case that fragmentation is even less of an issue in
long-running applications than limited data runs (because there is more
opportunity to reuse memory holes).

> Ditto when you are running a satelite! The program author can control the
> memory management style of their C code but they can't prevent Lua from
> fragmenting. I agree that no program should be *forced* to use compaction
> but it would be nice if the option was available when needed.

There is a reasonably simple strategy for controlling fragmentation on
long-running applications, if you have the luxury to stop the world for
a bit very once in a while: simply serialise the whole application, reset
the world, and read the application back in. That's the strategy I would
use on a satellite, for example.

> o The programs used in the experiment were all written in C / C++. As
such
> they had a tendency to use a small set of fixed-size data types (structs
or
> classes) which strongly aids against fragmentation.

> Now Lua is, of course, also written in C so that most of its internal
> structures are fixed size 'struct' types... but it also handles
potentially
> a *lot* of Lua table allocations. Now these hash tables need to store
> varying quantities of data... and I'm not sure whether this is achieved
> using a small number of pre-set sizes or whether the sizes continuously
> vary. If they do vary a lot, though, then that will make Lua an
> 'exceptional' application as far as fragmentation goes, aggravatting the
> problem significantly.

That's not at all clear.

First of all, Lua itself uses a very limited set of memory sizes (I have
memory traces somewhere to demonstrate this) because hash tables always
have a power of two number of elements (in Lua 5, hash tables also have
an integer vector which can theoretically be of any size, but the
reallocation strategy tends to construct vectors of a limited set of
sizes.)

Strings (and user datas) are allocated to the size needed. However, most
strings are short.

Also, most allocators deliberately reduce the number of sizes of objects
allocated, although this may or may not be a good strategy. Having lots of
different sizes increases the number of fragments, but does not necessarily
increase the amount of memory that those fragments represent. A little
allocation simulator I wrote to test some malloc strategies showed an
amazing accumulation of 8-byte holes ("shrapnel"). However, since each
one was only eight bytes, they didn't actually accumulate much space.

However, it is relatively easy to fragment memory, both with Lua and
with C. Here is a classic example in Lua, but it is actually a simplified
version of actual code I found in a C library (unnamed to protect the
guilty):

a = {}
temp = {}
for i = 1, 1000000 do
  a[i] = get_next_word()
  temp[i] = string.upper(a[i])
end
-- ... a little bit of processing.
temp = {}

The allocations (of strings) in the for loop are interlaced, so when temp
disappears (in the C original it was free'd), each allocation in a is
still separated by the hole used by the allocation of the string (of the
same size) in temp.

While the above example would benefit from a compacting garbage collector,
it would also benefit from a bit of common sense :) Of course, it was only
an issue because the table turned out to be a lot bigger than the author
was probably originally thinking it would be.

I suspect that this sort of thing happens even more often in C++ code, by
the way, because of typical programming style with constructors.

> o There are a lot of Lua programs & systems out there. So *HAS* anyone
> modified the code to add a "fragmentation analysis" feature to the memory
> module so we can see what the situation really is for various programms?

If you use a malloc which can do memory traces, you can easily do the
analysis yourself. (FreeBSD comes with such an allocator, for example).
I'll try to dig up the Lua code I wrote a couple of years ago to analyse
these traces, but no promises. It was an afternoon's work, though... it
is not at all difficult. (The FreeBSD allocator is not great, though.)

I was interested to discover the number of non-gc allocs and frees that
go on in typical Lua code; these have to do with the standard C library
and other libraries which I was using.