The CityHash project began at Google in 2010 when I realized that we should push engineers to use faster and better hash functions for strings. While researching exactly what to recommend, we developed our own family of hash functions that are excellent for hash tables.
The primary goal of CityHash is performance on short strings, but CityHash is also excellent for long strings. Compared to high-quality alternatives, CityHash generally achieves higher instruction-level parallelism or requires fewer instructions per input byte. We didn't develop CityHash for cryptography, so the level of quality to seek was initially nebulous. Over time, we developed our own quality tests, and also sought to perform well on Austin Appleby's SMHasher test suite.
I will discuss the design and implementation of CityHash, and explain why we prefer CityHash to various alternatives.
This is joint work with Jyrki Alakuijala.
Slides:
Download the slides for this presentation in PDF format.
About the speaker:
Geoff Pike is a Staff Software Engineer at Google. Geoff's Ph.D. work at UC Berkeley focused on loop optimizations for scientific computation. More recently, his interests have included control-flow integrity, high-performance elementary algorithms and data structures, ChromeOS, web search, memory allocators, and dynamic binary translation.
Contact information:
Geoff Pike
Google, Inc.
1950 Charleston Rd
Mountain View, CA 94043
4153052688