# Interesting article on hash table performance

5 messages
Open this post in threaded view
|

## Interesting article on hash table performance

 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.
Open this post in threaded view
|

## Re: Interesting article on hash table performance

 2017-02-27 19:12 GMT+08:00 Daurnimator <[hidden email]>: > 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.
Open this post in threaded view
|

## Re: Interesting article on hash table performance

 In reply to this post by Daurnimator On 2/27/2017 3:12 AM, Daurnimator wrote: > 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'm not familiar with Lua's algorithm for hash tables, but removing the bounds check for the array in the inner loop by having allocating a slightly larger array reminds me of removing the bounds check in insertion sort by placing the smallest/largest element at the beginning/end, respectively, based on which way you search the array. That's a really awesome insight.