[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: ltable.c table deletion
- From: Doug Currie <doug.currie@...>
- Date: Tue, 31 Jan 2012 21:47:39 -0500
On Jan 31, 2012, at 7:05 PM, Josh Haberman wrote:
> This is the key result that I realized but couldn't find
> published anywhere, which made me wonder whether this was previously
> known. All algorithms I could find published used the (much) more
> complicated and expensive removal algorithm.
… which saves a next pointer at every bucket. I.e., the cost of the simpler deletion algorithm is a next pointer at every bucket, a cost that many implementations go to great pains to avoid (because cutting the size of the hash table fits more of it in cache). [Lua's hash table is a great piece on engineering, and I'm not knocking it, just trying to point out why many other implementations make different choices.]
-- e