new hash table #24
Description
The old hash table uses:
- linked lists for its collisions, with slow out-of-cache pointer chasing and data overhead.
- unsorted flags at the end, while some flags are needed for compare.
- has questionable security measures to slow down all cases. seed ok, randomize iter maybe, but randomize the collisions and slow hash funcs is stupid. the security should be fixed with proper implementations, not by pseudo-security theatre.
either use:
- rurban/hash-sortbuckets: a sorted static list of collisions (up to 8, maybe start with 3, then 8) as in knuth sorted hash table,
- khash: use open addressing as everyone else. faster, less space.
- ✓ PERTURB_KEYS_TOP move-to-front with a linked list is the only sane strategy for simple chained bucket lists.
- ✓ HV_FILL_RATE: try lower fill rates than 100%. 100% is pretty insane, esp. with our bad hash funcs. make it fast with builtin_ctz.
- ✓ use __builtin_ctz for faster division in DO_HSPLIT. Allow -DHV_FILL_RATE=90 definition. (Tested to be the best with FNV1A)
- HE_ARRAY: According to http://goanna.cs.rmit.edu.au/~jz/fulltext/spire05.pdf
the best for chained hashing is currently a cache-friendly array:
cache-friendly continuous buffer of HE's w/ inlined HEK (char_) + SV_ val, but no hash, no next ptr. Also for shared he's: PL_strtab. - ✓ array_he: inline parts of the HE into the array. array_he vs ll_he. (linked list, see also the he-array branch). array_he (
HvARRAY = AHE[]) can contain{ hent_he, hent_hash }. this way the hash catches 99% of all comparisons already, and we don't have to chase the external hek ptr, when the hash check fails. every HE entry will then be 2 words (128), instead of one word (64), called AHE. The linked list still contains the oldHE*, with{ hent_next, hent_hek, hent_val }. - one-word-AHE: As possible improvement on that on 64bit use 48bits for the HE ptr, and 16bits of the hash to be compared first. See https://www.semanticscholar.org/paper/Fast-Dynamically-Sized-Concurrent-Hash-Table-Barnat-Rockai/ab7dd007587f411cf99bfe056639e055eff22e0c/pdf
- use robin-hood as this is currently the best worse-case strategy (being super defensive, but not so stupid to use SipHash, which adds no benefit). with better threading support (shared hashes) eventually use leapfrog.
- compact ordered hash. use an array of short indices into a compacted array of hash/key/val entries as in PyPy and now python: "compact ordered dict". This saves a lot of space and only add's one indirect lookup into cache-friendly array. See global unified freelist methane/cpython#1 https://mail.python.org/pipermail/python-dev/2016-September/146327.html
This also iterates over the hash in insertion order, which effectively hides any attempt to get the seed over the iterators. For attacks you need to get collision and robin-hood reordering timings.
maybe use the glibc htable (hsearch, hcreate), just add random seeds and flood detection (collision counts). (or khash, which is basically the same). coucal looks good also. https://github.com/xroche/coucal
but best is probably preshing's http://preshing.com/20160314/leapfrog-probing/, which even can be made concurrent easily.
open addressing is cache friendly and much faster, but table growth is slow.
potion uses khash, first double open, then quadratic open.
either way, first I need to abstract away the collision search in MACROS
and reduce the needed comparisons from 4 to 1. (edit: after my critic, they improved that part to one ptr cmp)
maybe we can normalize all keys to utf8 for faster checks. (probably not)
utf8 is a HEK flag. See http://cpansearch.perl.org/src/RURBAN/illguts-0.49/index.html#hek
The current implementation is just insanity and it only got worse over the years.
The last attempt was here: https://github.com/rurban/perl/commits/rurban/hash-sortbuckets
See the featurex/gh24-*hash* branches.
See also GH #102
plan
- ✓ -Dhash_func, add and test many more funcs
- ✓ PERTURB_KEYS_TOP
- ✓ HV_FILL_RATE
- ✓ d_builtin_ctz
- ✓ seperate hv_common_magic
- ✓ security: warn and protect against hash flood
- ✓ fix NODEFAULT_SHAREKEYS (fix NODEFAULT_SHAREKEYS #201)
- ✓ hash_loop: abstract loops and array_he
- ✓ array_he: seperate HvARRAY from collisions entries, add hent_hash
- 80% new_hash_table: merge HE fields for faster loop, usehekbitfield, d_little_endian.
- one-word-AHE (hash+he on 64bit)
- 40% open_hash, compact_ordered: various strategies with the new abstractions