TrieHash - A perfect hash function generator
Speaker: Julian Andres Klode
Track: Packaging, policy, and Debian infrastructure
Type: Short talk (20 minutes)
Time: Jul 25 (Thu), 11:00
TrieHash is a perfect hash function generator written for APT (and dpkg is in progress). It generates C code from a given list of words, that code performs substantially faster than competing perfect hash functions.
I’ll be discussing the basics of tries, compiler optimizations, and tricks for multi-byte access and case-insensitive comparisons in (GNU) C, and how these techniques were used to build TrieHash.