The Clear Table Saga

["Wim Couwenberg" <w.couwenberg@...>]

Wim Couwenberg wrote:
> On second (or third?) thought, I'd suggest a slightly
> altered version of the C implementation of zap_table:

Aaahhh...  That seemed like a good idea but it is in fact *terrible*!  A
simple test painfully confirmed what I suspected after thinking about it
some more: this "simpler" second version is S..L..O..W.  On my Celeron
400MHz machine it takes over 9 seconds to zap a table of about 10000
elements...!

The ADM inspired zap_table takes aboout 0.02 ~ 0.03 seconds for the same
task.  (Which by the way is still slow, considering that a dedicated zap
function would only need to free/alloc the table array...?)

[see the two zap_table examples below]

The reason for the huge difference is (IMHO) simple: since setting a field
to nil does not remove it from the table it will consequently take longer
and longer to find the first non-nil valued field if we start from scratch
each time!  (One would expect quadratic behaviour but the timings seemed a
bit erratic... maybe due to (processor) caching?)

In ADM's zap the next key will be located relative to the previous one,
which only takes constant time...


Such a simple question, so much to learn...  ;-)

Bye,
Wim

SLOW version:

> /* suppose that the table is at stack index "table" */
>
> void zap_table(lua_State *L, int table)
> {
>      while (lua_pushnil(L), lua_next(L, table))
>      {
>            lua_pop(L, 1);  /* pop value */
>            lua_pushnil(L);
>            lua_settable(L, table);  /* zap the key */
>      }
> }
>


"Fast" version:

> /* suppose that the table is at stack index "table" */
>
> void zap_table(lua_State *L, int table)
> {
>      lua_pushnil(L);
>
>      while (lua_next(L, table))
>      {
>            lua_pop(L, 1);  /* pop value */
>            lua_pushvalue(L, -1);  /* duplicate the key */
>            lua_pushnil(L);
>            lua_settable(L, table);  /* zap the key */
>      }
> }