Re: A fast array implementation

[Edgar Toernig <froese@...>]

Joshua Jensen wrote:
> 
> I did look at the table implementation in Lua.  lua_rawgeti() calls
> luaH_getnum().  luaH_getnum() sure looks like it accesses a hash table to
> me, complete with a hash on the index being requested and a run of the
> bucket's linked list checking for a number type and then checking if the key
> matches...

Just look a little bit closer.  If the table only holds integer valued keys
from a to b (without missing elements) there are _no_ collisions.  So the
loop in luaH_getnum is never taken.  The hash has become an array.  Over-
writing already present keys is similar fast.  The only slower case is
growing the table (rehash log2(n) times).  But similar work would be necessary
for dynamic arrays too.

IMHO the _only_ benefit of arrays would be that there's no need to store the
keys.  They would take only half the memory...

Ciao, ET.