New HashTable structure / algorithm (Hash.c)
Motivation
While improving the performance of lookupIPE()
using a HashTable
(Hash.c
/ Hash.h
), @bgamari came up with the idea that the HashTable
itself could be improved. (!5724 (comment 352644))
There are some algorithms that are likely to perform better (regarding size and speed) than the traditional "the bucket is a linked list" approach.
E.g. Swiss Tables (used as Hash Brown in Rust) or Robin Hood Hash Maps.
Proposal
This proposal should communicate two facts:
- The insight that we may improve the performance of the RTS by changing
HashTable
. - This is being worked on. (Please get in touch if you want to collaborate - More people -> More fun
😉 )
My plan is to create a project outside of the GHC tree to develop a drop-in replacement (the API is described by Hash.h
) and benchmark it against the original implementation.
I'm planning to start with Swiss Tables/Hash Brown, but - as smart as our community is - please feel free to propose other algorithms (but please be realistic, I'm not eager to spend the next years developing all known Hash Table algorithms in C