[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: ltable.c table deletion
- From: Josh Haberman <jhaberman@...>
- Date: Wed, 1 Feb 2012 14:12:37 -0800
On Wed, Feb 1, 2012 at 2:19 AM, Mike Pall <firstname.lastname@example.org> wrote:
Josh Haberman wrote:1. To allow deletion of values during a table traversal.
> Is there a reason for this?
If the key was removed, too, the traversal would lose its
anchor. This is because traversals in Lua are incremental,
based on the previous key, and don't need extra context
(e.g. a hash table position).
[LuaJIT tries to use a hidden context to speed up traversals.]
2. To preserve the key slot in the table.
Fields that toggle from non-nil to nil and back do not need to
create a new key in the table every time. Creating a new key is
substantially more expensive than re-using an existing key slot.
These make sense.
3. To save work.
Removing individual keys is expensive, because you'll need to
traverse the whole chain for each key.
Just wanted to clarify that by "each" key you mean "the chain
of the key you are removing." You *don't* have to traverse all
chains in the hash table to perform a single deletion if you avoid
coalescing (that's the result I discovered but couldn't find published).
Also I wanted to point out that the average length of each chain
for a good hash function is very short (even at 100% load), so
deletions would be O(1) on average but O(n) worst-case (ie.
just like insertions).
But clearly the other two reasons outweigh any potential benefits
of performing actual table deletions.