How do you pre-size an array in Lua?

Question

I've got a Lua program that seems to be slower than it ought to be. I suspect the issue is that I'm adding values to an associative array one at a time and the table has to allocate new memory each time.

There did seem to be a table.setn function, but it fails under Lua 5.1.3:

stdin:1: 'setn' is obsolete
stack traceback:
        [C]: in function 'setn'
        stdin:1: in main chunk
        [C]: ?

I gather from the Google searching I've done that this function was depreciated in Lua 5.1, but I can't find what (if anything) replaced the functionality.

Do you know how to pre-size a table in Lua?

Alternatively, is there some other way to avoid memory allocation when you add an object to a table?

Answer 1

I don't think you can - it's not an array, it's an associative array, like a perl hash or an awk array.

http://www.lua.org/manual/5.1/manual.html#2.5.5

I don't think you can preset its size meaningfully from the Lua side.

If you're allocating the array on the C side, though, the

void lua_createtable (lua_State *L, int narr, int nrec);

may be what you need.

Creates a new empty table and pushes it onto the stack. The new table has space pre-allocated for narr array elements and nrec non-array elements. This pre-allocation is useful when you know exactly how many elements the table will have. Otherwise you can use the function lua_newtable.

Answer 2

There is still an internal luaL_setn and you can compile Lua so that it is exposed as table.setn. But it looks like that it won't help because the code doesn't seem to do any pre-extending.

(Also the setn as commented above the setn is related to the array part of a Lua table, and you said that your are using the table as an associative array)

The good part is that even if you add the elements one by one, Lua does not increase the array that way. Instead it uses a more reasonable strategy. You still get multiple allocations for a larger array but the performance is better than getting a new allocation each time.

Answer 3

static int new_sized_table( lua_State *L )
{
    int asize = lua_tointeger( L, 1 );
    int hsize = lua_tointeger( L, 2 );
    lua_creatatable( L, asize, hsize );
    return( 1 );
}

...

lua_pushcfunction( L, new_sized_table );
lua_setglobal( L, "sized_table" );

Then, in Lua,

array = function(size) return sized_table(size,0) end

a = array(10)

Answer 4

Let me focus more on your question:

adding values to an associative array one at a time

Tables in Lua are associative, but using them in an array form (1..N) is optimized. They have double faces, internally.

So.. If you indeed are adding values associatively, follow the rules above.

If you are using indices 1..N, you can force a one-time size readjust by setting t[100000]= something. This should work until the limit of optimized array size, specified within Lua sources (2^26 = 67108864). After that, everything is associative.

p.s. The old 'setn' method handled the array part only, so it's no use for associative usage (ignore those answers).

p.p.s. Have you studied general tips for keeping Lua performance high? i.e. know table creation and rather reuse a table than create a new one, use of 'local print=print' and such to avoid global accesses.

Answer 5

Although this doesn't answer your main question, it answers your second question:

Alternatively, is there some other way to avoid memory allocation when you add an object to a table?

If your running Lua in a custom application, as I can guess since your doing C coding, I suggest you replace the allocator with Loki's small value allocator, it reduced my memory allocations 100+ fold. This improved performance by avoiding round trips to the Kernel, and made me a much happier programmer :)

Anyways I tried other allocators, but they were more general, and provide guarantee's that don't benefit Lua applications (such as thread safety, and large object allocation, etc...), also writing your own small-object allocator can be a good week of programming and debugging to get just right, and after searching for an available solution Loki's allocator wasthe easiest and fastest I found for this problem.

Answer 6

If you declare your table in code with a specific amount of items, like so:

local tab = { 0, 1, 2, 3, 4, 5, ... , n }

then Lua will create the table with memory already allocated for at least n items.

However, Lua uses the 2x incremental memory allocation technique, so adding an item to a table should rarely force a reallocation.