Re: worst case time using hash-tables in Lua

[Robert Burke <sharpobject@...>]

On Fri, May 15, 2020 at 7:48 PM Philippe Verdy <verdyp@gmail.com> wrote:
>
> I spoke about null nodes meaning nodes whose key part is not set (so the associated-value part is also not set, both can be will be null/nil pointers or values): if you don't like it, I cabn speak about free nodes, unused nodes, empty nodes.
Do you have a preferred scheme for cleaning up nodes whose key part is
set and whose value part is not set when performing insertions of new
keys?

> This is independant of the fact these nodes (also called buckets) may also contain internal chaining pointer (I think there's no need at all for them and their usage in Lua is based on a broken assumption that it could generate shorter chains, while in fact it creates much longer chains and worst cases are in fact easier to reach).
>
> Using linear probes with a constant step (1 or a large prime) *warranties* there's a limit to the worst case for long chains.
Well, it does this only probabilistically, which the current code does as well.

Have you had a look at Malte Skarupke's blog posts about this topic?
He created a hash table that uses linear probing and has an actual
upper bound on chain length, but he found that nobody would use it
because it replaced DOS attacks that degrade performance with DOS
attacks that cause your program to crash by running out of memory.
Later he created another hash table that is fairly similar to Lua's
implementation, and one of his claimed benefits of the new one over
the old one is that is saves memory because it has short chains at
very high load factors. Here's the post about the new thing, which
links to the old thing:
https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/

> And finally Lua's hash table are in fact even slower than using a linear global scan of the full table !
This claim seems like it should be fairly easy to prove. What
operation is slower than a linear scan of an array under what
circumstances?
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org