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

[oiskuu]

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).

<Reveal this spoiler or all in this thread>

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.