When I shortened the stored hash codes to 16 bits, I neglected to realize that I was also using this array code to store item counts in the hashtable, which of course led to integer overflow immediately. Should fix #24.
…ixes #8. (In theory)
…or using clang. Fixes #21.
…tch C implementations. This fixes #13.
Before, in the basic and cuckoo hash tables, we were storing full machine-word-sized hash codes in the table so that we could quickly search a whole cache line for a key (or a combination of keys) without branching. It turns out that a full machine word is not really necessary for this application; switching to a 16-bit key will very slightly increase the number of hash collisions within buckets (meaning that we'll compare more keys), but will pay big dividends in terms of: * reduced wastage of RAM * searching more keys at once, allowing buckets to grow bigger * more cache hits on the hash codes array. Preliminary results suggest a reduction in table overhead of about four bytes per key-value pair (on 64-bit) and speed increases around the 15% range, although I need to re-run these results and probably do some tuning afterwards.
…sibly resizing more often than before)