Re: GC Compaction

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

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.

Rici Lake:
> 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 :)

Nothing is mentioned in the Lua documentation about whether or not Lua
compacts or is particularly susceptible to fragmentation, so most people
won't think to obtain a decent malloc library.

Given Lua's heavy heap usage perhaps it should be distributed with a
suitably low-fragmenting library?


Peter Hill:
> 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.

Rici Lake:
> 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.

But on a satelite (or in a VCR, or on a palm top) you might have limited
memory and so the serialising option may be expensive (compaction can
usually be done using little extra memory). You could pre-allocate the
serialising memory... but how accurately can you estimate how much is
needed? And you need to serialise it all... closures (with their upvalues),
self-referencing tables, etc. No easy effort.


Rici Lake:
> 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 :)

It seems a part of Lua design to not make any requirements of common sense
with regard to memory allocation. The manual makes no commentary as to how
memory is managed (except for how the GC is triggered) and makes no
suggestions about avoiding fragmentation.

Moreover, it is quite reasonable to expect that the Lua scripts (as opposed
to the C core) be written by naive programmers... as Lua often seems to be
used to allow various extensions (eg, game AI for monsters) to be made by
different people at different times.

You can't *rely* on common sense in Lua as far as memory management goes...
and the manual doesn't ask us to.

*cheers*
Peter Hill.

Ki: Contractors... high-paid leeches stealing our work.
Fooker: If you think of them as disposable employees, you'll feel much
better...