Message: 7
Date: Thu, 30 Dec 2010 11:22:27 +0100
From: David Kastrup <dak@gnu.org>
Subject: Re: hpairs?
To: lua-l@lists.lua.org
Message-ID: <8762ublfvg.fsf@lola.goethe.zz>
Content-Type: text/plain
Tomas Lundell <tomas.lundell@gmail.com> writes:
> Please, do not refer to the "array part" or the "hash part" of a
> table,
> unless you are discussing the implementation of tables. They are
> completely invisible (except for performance).
>
> -- Roberto
>
>
>
> I have personally replaced the Lua table implementation with an
> single-mechanism array-based hash table to reduce branching and memory
> consumption. Apart from serving as a hash table, when a table is used
> only as an array, the data structure will look like one automatically
> (a tight array of ordered numbers). Naturally, from the outside the
> language appears unchanged.
If I understand correctly, basically numbers hash to themselves in that
scheme. The problem I see is that you lose efficiency for sequential
access when hashing more than just numbers, since the numbers then
compete with the non-numbers for hash buckets.
--
David Kastrup
Yep, they hash to themselves (less one because of a one-based indexing assumption).
The other detail is that the growing policy has to guess whether it's a pure array or not. Normal hash tables need to be <~ 75% loaded, otherwise you get too many collisions during insertion which hurts lookup performance. Pure arrays don't have collisions, so we can try to keep the size of the array close to the expected number of items.
If you mix numbers and other values, the table basically reverts back to being a hash table. I would guess that this a rare use case, especially performance wise.
/ Tom
