Optimizing Lua memory access/usage...

["Joshua Jensen" <jjensen@...>]

I've spent some time lately adding optimizations to Lua to decrease the
amount of memory fragmentation produced over time.  The nature of Lua's
growing of its internal arrays lends itself to fragmentation levels that
aren't acceptable in a tight memory environment (such as a game console
or embedded device).  In its current form, it is very nearly impossible
to optimize Lua's memory usage when new script data is loaded into the
Lua state as a result of some action performed by the user of the
software (such as progressing to a new menu).

For my project, I am able to monitor the state of the heap, because the
memory manager I am using tracks a great deal of debug data (including
named allocations).  I have littered throughout the Lua code, in macro
form, a new define called luaM_setname() that sets the active name for
the memory allocation.  I am basing all my optimizations on heap dumps
after various operations.

I intend to post the code to all the optimizations I have been working
on as soon as I am sure they all work.  Thus far, I have:

* Added the ability to set a minimum size for the string table stored in
the global state.  Just during a lua_newthread() call, the string table
resizes itself several times.  By setting a default minimum size to
NUM_RESERVED + NUM_TAGS, there are no resizes of the string table during
the lua_newthread() call.  In addition, the garbage collector takes into
account the minimum string size (it is stored in global_State) and won't
size the string table lower than the amount specified.
* Added the ability to set a minimum size for the tag method data.  It
is the same idea as the string table.  The tag method table also resizes
itself several times during the lua_newthread() call.  Note that I have
not figured out how to maintain the minimum size in the garbage
collector (if it is necessary).
* luaH_new() provides the ability the set the default size of the hash
table.  I've added a new function called lua_newtablesize() that allows
the default number of elements to be passed in for a newly created
array.

When a table is defined in an incoming Lua file, the parser is able to
determine the size to create the table at, when the table is in the
form:

Table =
{
	Index1 = 5,
	Index2 = 10,
	Index3 = 15,
}

However, the parser can't determine the size of a table that looks like:

Table = {}
Table.Index1 = 5
Table.Index2 = 10
Table.Index3 = 15

The difference in allocation patterns is significant.  In the first case
above, all memory for the hash is allocated, since the size is known.
In the second case, the parser can't determine the size.

Even though the parser can't determine the size, I, as the programmer,
can.  For optimization purposes, I need to be able to pass in a hash
size for the table's creation.

There are different approaches to this problem.  The simplest is using a
C callback function to create the table.  I could use the
lua_newtablesize() function to create the table and pass it back on the
stack.  I'm not fond of the callback approach, because it is
significantly slower than just executing the OP_NEWTABLE instruction in
the virtual machine.

Table = createtable(3)

My preferred approach is to change the parser somewhat to allow the
definition of a table to look like (optional, of course):

Table = {}&3  -- Or some other equally ugly character.
-- preferable, I'd like:
Table = &3{}  -- Because then the size is at the TOP of the table
definition instead of the bottom.

The above table definition makes a NEWTABLE 0 3 instruction (instead of
a NEWTABLE 0 0).  At the cost of making the table definition look
uglier, memory fragmentation completely disappears (no reallocated
hashes), the table construction is run at full speed, and table writes
are run much faster, since there is no need to resize the hash.

I have not figured out how to do this in the parser yet.  I thought I'd
throw it out for general consumption, and see if my logic is flawed.  If
anybody knows how to easily add this to the parser, I'd be grateful.

Thanks,
Joshua Jensen