Re: GC Compaction

["Peter Hill" <corwin@...>]

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:

Thank you for the reference... that was very interesting!

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.


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.

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.

The comments above are not to say that Lua isn't used for single-run
programs but I have high hopes of it being useful for a whole lot more.


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.


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?


o Some systems (eg Palm OS) inherently support compaction, and when porting
Lua to such a system it would be poor to not be able to take advantage of
that feature.

*more food for thought*
Peter Hill.