lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 

Am 12.03.2014 10:56 schröbte Richter, Jörg:

Hi,


Hi!



[Lua 5.2.2]

While trying to reduce the memory allocations of our application  I came
across a function that always allocates a table, sets some members, calls another
function with this table as argument.  Both the caller and the callee don't reference
the table thereafter.  I thought this would be a good candidate to always use the
same table.

But when using our custom memory allocator, I still see a lot of allocations at this
point that I dont expect anymore.

You can see the behaviour with the following program.  I would expect that the loop
reaches a state, where no more memory allocations are neccesary.  But like 2 times
out of 3 the following output happens:

   loop
   ptr=(nil) osize=0 nsize=0 res=(nil)


I don't know about this one, but ...


   ptr=(nil) osize=0 nsize=80 res=0x937da40


... this one allocates 4 hash table slots ...


   ptr=0x937d9e8 osize=80 nsize=0 res=(nil)


... and this one frees the 4 hash table slots previously used.


   loop
   ptr=(nil) osize=0 nsize=0 res=(nil)
   ptr=(nil) osize=0 nsize=80 res=0x937d9e8
   ptr=0x937da40 osize=80 nsize=0 res=(nil)
   [repeated...]

As you can see, one loop always frees the block allocated in the previous loop, and
a new block of the same size will be allocated.  This seems unnecessary.
I suspect that hash-collisions are somehow responsible for this behaviour.  Because it
does not happen every time.
Is this to be expected?
Lua allocates hash table slots in powers of 2, so you get 2 slots for 2 keys, 4 slots for 3 or 4 keys, 8 slots for 5 to 8 keys, etc. In your case you have 2 non-nil key-value pairs in the table. When you add another key-value pair (which is nil, but Lua doesn't check at that point) Lua allocates 4 slots. For the 5th `lua_setfield` Lua thinks it has to resize the hash part again, but when counting the existing key-value pairs, it realizes that it only needs 3 slots (2 existing non-nil, plus one new), so it allocates 4 slots again. And this happens on every loop iteration.
It doesn't happen, if the 4th key hashes to the same slot as the 3rd key (which contains nil), because then Lua will reuse that slot and not attempt a rehash at the 5th `lua_setfield`.
Sometimes there seems to be 2 rehashes to 4 hash slots in a single loop iteration -- I haven't figured that one out yet ...
You should be able to avoid those reallocations if you make the hash part big enough in the first place (either using `lua_createtable` or setting all keys to non-nil values at least once). 




    Jörg


Philipp






#include <lua.h>
#include <stdlib.h>
#include <stdio.h>

void* realalloc( void* ptr, size_t osize, size_t nsize )
{
   if( nsize == 0 )
   {
     free( ptr );
     return NULL;
   }
   return realloc( ptr, nsize );
}

void* alloc( void* ud, void* ptr, size_t osize, size_t nsize )
{
   void* res = realalloc( ptr, osize, nsize );
   printf( "ptr=%p osize=%d nsize=%d res=%p\n", ptr, (int)osize, (int)nsize, res );
   return res;
}

int main()
{
   int i;
   lua_State* L = lua_newstate( alloc, 0 );
   lua_pushstring( L, "xyz" );
   lua_pushstring( L, "valid" );
   lua_pushstring( L, "value" );
   lua_pushstring( L, "linepos" );
   lua_pushstring( L, "linecol" );
   lua_pushstring( L, "fashion" );
   lua_newtable( L );
   for( i = 0; i < 1000; ++i )
   {
     printf( "loop\n" );
     lua_pushinteger( L, 4 );
     lua_setfield( L, -2, "valid" );
     lua_pushstring( L, "xyz" );
     lua_setfield( L, -2, "value" );
     lua_pushnil( L );
     lua_setfield( L, -2, "linepos" );
     lua_pushnil( L );
     lua_setfield( L, -2, "fashion" );
     lua_pushnil( L );
     lua_setfield( L, -2, "linecol" );
   }
}