Re^2: Bidirectional lookup algorithm? (try perfect hashing)

Ok. Here's a crude demo in case someone is interested in doing benchmarking comparisons or whatever. The program is pure C, tested on linux 64-bit. Give two arguments: Nkeys and Filename. File should contain sym-value pairs, both unique in their domains. (Space-separated, one pair per line).

Update. Some additional notes regarding the program.

Portability is easily improved upon:

Replace mmap/mremap with malloc/realloc. This is trivial.
The test for direct vs indirect entries (ss offset) might be written as !(s->o >> 56), avoiding issues with endianness.

There are at least two bugs to fix:

Verify sym to val loop has no test for NULL; this will fault on a missing key.
The fetch_by_key should not proceed with a memcmp in case keylen > 8, but the slot is direct (ie <= 8).

Many further optimizations to consider:

Try to allocate ss strings so that cache-line boundaries aren't crossed.
Terminate strings with a high-bit: more compact, plus faster than using memchr.
Specific inlined implementations for 8-byte memcmp, etc.
Inplace reorder looks up every key twice. Place an (un)processed flag to halve this.
Choose a faster hash function for string keys, FNV perhaps.
A primitive hash function for values. Just a mul by constant?

There's also a wishlist for the CMPH library, but enough for now.

Comment on Re^2: Bidirectional lookup algorithm? (try perfect hashing) Select or Download Code


We don't bite newbies here... much
	PerlMonks