[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: The Clear Table Saga
- From: "Wim Couwenberg" <w.couwenberg@...>
- Date: Sun, 18 May 2003 17:06:19 +0200
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 */
> }
> }