Improving the efficiency of next

[Reuben Thomas <rrt@...>]

As witness

http://lua-users.org/lists/lua-l/2003-11/msg00052.html

there seems to be some confusion about the efficiency of lua_next. This
became of more interest to me when recently I started adapting ltable.c to
make general-purpose hash table routines.

The relevant functions are lua_next (in lapi.c) and luaH_index and
luaH_next (in ltable.c).

luaH_next is called each time lua_next is called, and it in turn calls
luaH_index. If luaH_next is called with key pointing to an item in the
array part of the hash table, it will loop through the array until it
finds the next non-nil item. If on the other hand key is in the hash part
of the table, then it will similarly loop through the hash part of the
table. So this is linear in the size of the table.

The same is true for ipairs, which is implemented entirely inside
luaB_ipairs, and doesn't use lua_next.

Timings confirm this:

> n = 1000000
> t = {}; for i = 1, n do t[i] = i; end
> s = os.clock (); for i = 1, n do t[i] = nil; end; print (os.clock() - s)
0.44
> n = 4000000
> t = {}; for i = 1, n do t[i] = i; end
> s = os.clock (); for i = 1, n do t[i] = nil; end; print (os.clock() - s)
1.74
> n = 8000000
> t = {}; for i = 1, n do t[i] = i; end
> s = os.clock (); for i = 1, n do t[i] = nil; end; print (os.clock() - s)
3.46

Finally, I note that luaH_index (which is called for every iteration of a
table traversal) does perform a key hash on every call. Since you're not
allowed to change a table during a traversal, it would seem
straightforward to make luaH_next record the actual position in the table,
so that luaH_index could be removed. This would require that all
traversals were "complete", because it would make part of the return value
of next a light userdata, or some such, that could not be faked in order
to start a traversal half-way through; perhaps that's just ugly.

-- 
http://www.mupsych.org/~rrt/ | What you don't know controls you