Re: Interesting article on hash table performance

[Xavier Wang <weasley.wx@...>]

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.