Re: A fast array implementation

["Joshua Jensen" <jjensen@...>]

From: "Edgar Toernig" <froese@gmx.de>
> 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...

I strongly disagree here.  While I can't fully confirm your "no collisions"
response, I can confirm there are no collisions for small arrays.  And even
so, a straight retrieval of a value at a certain index still requires
multiple function calls, comparisons, etc.  An insertion is even more
costly.

By providing an array type, Lua can preallocate an array of TObjects (or
whatever they are) based on the size specified by the user.  To insert an
object into that array is as simple as array[index] = TObject.  Retrieval is
equally as simple.  Lua will run far quicker when using indexed access and
make it perform even better in the benchmarks.

Thanks,
Josh
Author, Workspace Whiz! - A Visual Studio Add-in
http://workspacewhiz.com/