[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: A fast array implementation
- From: "Joshua Jensen" <jjensen@...>
- Date: Thu, 19 Apr 2001 23:30:21 -0600
From: "Edgar Toernig" <firstname.lastname@example.org>
> 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
> > 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
> > matches...
> Just look a little bit closer. If the table only holds integer valued
> 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
> for dynamic arrays too.
> IMHO the _only_ benefit of arrays would be that there's no need to store
> 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
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.
Author, Workspace Whiz! - A Visual Studio Add-in