lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

2017-02-27 19:12 GMT+08:00 Daurnimator <>:
> I read this today:
> 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

static const am_Entry *am_gettable(const am_Table *t, am_Symbol key) {
    const am_Entry *e;
    if (t->size == 0 || == 0) return NULL;
    e = am_mainposition(t, key);
    for (; e-> !=; 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 :-)

Xavier Wang.