RE: Heap usage and variable argument C functions

["Cory Bloyd" <cory.bloyd@...>]

-----Original Message-----
> From: Asko Kauppi [mailto:asko.kauppi@sci.fi] 
>
>> always constructed incrementally.  Therefore the collector could
>> possibly be triggered during a table construction because of the
>> fragmentation they induce.
>
>Hmm.. (again).  I'm not a Lua internals expert, but what would be gc'ed

>if things are only added to the table?  Fragmantation - what do you 
>mean by that?

I'm worried about the malloc/free operations that happen as the internal
representation of the table changes.  If the malloc fails, does Lua try
calling the garbage collector or does it just blow up?  We will be
always running Lua in as-tight-as-possible memory pools so we will be
seeing allocation failures as a regular occurrence in the development
process.

I don't have a textbook definition handy, but "memory fragmentation"
refers to a problem that occurs in heap-style memory systems with
certain allocation/deallocation usage patterns.  The idea is that you
start with a nice, open, linear memory space.
|---------------|

If you wanted to, you could do 4 mallocs that each grab 25%
A = allocate(25%); B = allocate(25%); C = allocate(25%); D =
allocate(25%);
|AAA|BBB|CCC|DDD|

You would think that if you freed two of these that you could do a new
malloc that grabs the newly open 50%, but it often doesn't work out that
way.
free(B); free(D);
|AAA|---|CCC|---|
E = allocate(50%);
Error.  There is no linear chunk of memory big enough.

On most major systems you don't have to worry about this because memory
virtualization can shuffle the memory space and make it work out for
you.  But on some embedded systems this is a major issue.  If growing a
table involves calls to free() then it will probably fragment memory.

There are three clear usage patterns I see for growing a table.
1) Grow the table as an array indexed by sequential integers to take
advantage of the array optimization.  Eventually there will be too many
items to fit in the currently allocated array.  The system will need to
allocate a new array, copy the old values and then delete the old array.
Memory is fragmented.

2) Grow the table as a hash that does not take advantage of the array
optimization.  In theory, the system could allocate the items one at a
time and never free() anything in the process, but I doubt that is how
it works.

3) Grow the table as either a hash or an array, but then switch styles.
Either way, some the old representation will need to be freed after
allocating the new one.

I realize I am being very picky about a problem that most people don't
have.  If I absolutely must have 100% memory safety I should just use a
less dynamic language.  Fortunately, my requirements are not 100%.  So
what I am trying to do is learn how to use Lua as well as possible so
that I can at least know what the rules are when I bend/break them.