Re: ltable.c table deletion
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: ltable.c table deletion
- From: Doug Currie <doug.currie@...>
- Date: 2012年1月31日 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