6 ms·

CityHash, a family of hash functions for strings.

23 points by atdt 14y ago

shin_lao 14y ago
The code looks pretty big, I'm afraid this will affect negatively the instruction cache.
- unwind 14y ago
  The announcement claims: On a single core of a 2.67GHz Intel Xeon X5550, CityHashCrc256 peaks at about 5 to 5.5 bytes/cycle. That is pretty impressive, I don't think there's room for a lot of cache missing in that performance envelope.
  - kevingadd 14y ago
    You have to understand that you can't measure the impact of an algorithm on the icache by just benchmarking it in a loop. If the algorithm being benchmarked fits into icache, it'll perform great in that loop, but when you drop it into your application it could blow everything out of the icache each time you call it and degrade the performance of the rest of your application. It'll also perform worse in your application since it's not remaining in icache either.
- ComputerGuru 14y ago
  Actually, it's rather ironic in that past a certain point, in order to optimize for cache size your lines of code will grow to a huge amount. Case in point: Judy arrays [0] [1]. That is some of the most heavily-optimized code I have ever seen, optimized through-and-through for each and every possible CPU-related factor including the various cache levels, instruction pipeline optimizations, and more. Yet the codebase is positively gargantuan compared to any other implementation of a dynamic array or hash table, mainly as a result of these optimizations. Don't be so quick to judge by LoC. 0: http://judy.sourceforge.net/ http://judy.sourceforge.net/ 1: http://linux.die.net/man/3/judy http://linux.die.net/man/3/judy
ComputerGuru 14y ago
Previously on HN with some good discussions: http://news.ycombinator.com/item?id=3521551 http://news.ycombinator.com/item?id=3521551 http://news.ycombinator.com/item?id=2434547 http://news.ycombinator.com/item?id=2434547 Lots of comparison to MurmurHash3, which is my preferred hashing function for generic (read: non-string data). I have since switched to CityHash for string hashing.
steeve 14y ago
You know, everytime I see articles about CityHash/MurmurHash I always wonder why more people don't know about xxHash, which is 3 times faster than MurmurHash. http://code.google.com/p/xxhash/ http://code.google.com/p/xxhash/ http://fastcompression.blogspot.fr/2012/04/selecting-checksum-algorithm.html http://fastcompression.blogspot.fr/2012/04/selecting-checksu... On a side note, same goes with LZ4 being twice as fast as Speedy (from the same author). http://code.google.com/p/lz4/ http://code.google.com/p/lz4/
- tryp 14y ago
  I did a quick skim of the source for xxHash and CityHash. They appear to rely heavily on 32- and 64-bit multiply operations, and are likely "fast" to the extent that these operations are vectorized. The benchmarks I noticed are all run on recent x86_64 processors with big vector units and caches. It would be interesting to see how they stack up on other platforms like ARM with and without NEON, PPC with and without Altivec, and MIPS. Without that data, the algorithms look pretty tailored for SSE3, and so I'd hesitate to build them into any application or protocol that needs to be portable or implemented in embedded devices.

23 points by atdt 14y ago

shin_lao 14y ago

The code looks pretty big, I'm afraid this will affect negatively the instruction cache.

unwind 14y ago
The announcement claims: On a single core of a 2.67GHz Intel Xeon X5550, CityHashCrc256 peaks at about 5 to 5.5 bytes/cycle. That is pretty impressive, I don't think there's room for a lot of cache missing in that performance envelope.
- kevingadd 14y ago
  You have to understand that you can't measure the impact of an algorithm on the icache by just benchmarking it in a loop. If the algorithm being benchmarked fits into icache, it'll perform great in that loop, but when you drop it into your application it could blow everything out of the icache each time you call it and degrade the performance of the rest of your application. It'll also perform worse in your application since it's not remaining in icache either.
ComputerGuru 14y ago
Actually, it's rather ironic in that past a certain point, in order to optimize for cache size your lines of code will grow to a huge amount. Case in point: Judy arrays [0] [1]. That is some of the most heavily-optimized code I have ever seen, optimized through-and-through for each and every possible CPU-related factor including the various cache levels, instruction pipeline optimizations, and more. Yet the codebase is positively gargantuan compared to any other implementation of a dynamic array or hash table, mainly as a result of these optimizations. Don't be so quick to judge by LoC. 0: http://judy.sourceforge.net/ http://judy.sourceforge.net/ 1: http://linux.die.net/man/3/judy http://linux.die.net/man/3/judy

ComputerGuru 14y ago

Previously on HN with some good discussions: http://news.ycombinator.com/item?id=3521551 http://news.ycombinator.com/item?id=3521551 http://news.ycombinator.com/item?id=2434547 http://news.ycombinator.com/item?id=2434547 Lots of comparison to MurmurHash3, which is my preferred hashing function for generic (read: non-string data). I have since switched to CityHash for string hashing.

steeve 14y ago

You know, everytime I see articles about CityHash/MurmurHash I always wonder why more people don't know about xxHash, which is 3 times faster than MurmurHash. http://code.google.com/p/xxhash/ http://code.google.com/p/xxhash/ http://fastcompression.blogspot.fr/2012/04/selecting-checksum-algorithm.html http://fastcompression.blogspot.fr/2012/04/selecting-checksu... On a side note, same goes with LZ4 being twice as fast as Speedy (from the same author). http://code.google.com/p/lz4/ http://code.google.com/p/lz4/

tryp 14y ago
I did a quick skim of the source for xxHash and CityHash. They appear to rely heavily on 32- and 64-bit multiply operations, and are likely "fast" to the extent that these operations are vectorized. The benchmarks I noticed are all run on recent x86_64 processors with big vector units and caches. It would be interesting to see how they stack up on other platforms like ARM with and without NEON, PPC with and without Altivec, and MIPS. Without that data, the algorithms look pretty tailored for SSE3, and so I'd hesitate to build them into any application or protocol that needs to be portable or implemented in embedded devices.