Re: Interesting article on hash table performance

[Russell Haley <russ.haley@...>]

On Mon, Feb 27, 2017 at 4:41 AM, Xavier Wang <weasley.wx@gmail.com> wrote:
> 2017-02-27 19:12 GMT+08:00 Daurnimator <quae@daurnimator.com>:
>> I read this today:
>> https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
>> I thought it might be interesting reading for many of you.
>>
>> I'm eager to see how lua's algorithm compares, and what lessons might be learnt.
>>
>
> I feel Lua's implement is much faster than this. it use a limited
> linear search, but Lua's use a linked list into open address. with a
> linked list, Lua's get a free node is much easier than author's.
>
> when insert, Lua also move the colliding node into it's main position.
> in my amoeba library[1], in a 1000+ elements hash table, the most link
> has only 3 elements. and the lookup loop looks even more compact than
> author's:
>
> static const am_Entry *am_gettable(const am_Table *t, am_Symbol key) {
>     const am_Entry *e;
>     if (t->size == 0 || key.id == 0) return NULL;
>     e = am_mainposition(t, key);
>     for (; e->key.id != key.id; e = am_index(e, e->next))
>         if (e->next == 0) return NULL;
>     return e;
> }
>
> the most inspired thing is the limited linear search, in Lua it means
> limited search in lastfree, it's not easy to add this change to my
> hashtable, and I will do some research for this change. but in current
> test, the worst case for max loop for lastfree is the whole list
> length. so maybe it will have a big improve.
>
> it's really a very impressive thing, TIL :-)
>
> --
> regards,
> Xavier Wang.
>
Did you mean to add this link as reference [1]:
https://github.com/starwing/amoeba?

Very slick. Some months back I found a round robin database for
applicative monitoring here: https://github.com/shmul/mule. I didn't
drill in too far but I wonder out loud if your library could be
applied for relative logic in things like object tracking?

I'll keep your library in mind when I am creating my
killer-artificially-intelligent-robot in lua.

Russ