| 1 |
CityHash, a family of hash functions for strings. |
| 2 |
|
| 3 |
|
| 4 |
Introduction |
| 5 |
============ |
| 6 |
|
| 7 |
CityHash provides hash functions for strings. The functions mix the |
| 8 |
input bits thoroughly but are not suitable for cryptography. See |
| 9 |
"Hash Quality," below, for details on how CityHash was tested and so on. |
| 10 |
|
| 11 |
We provide reference implementations in C++, with a friendly MIT license. |
| 12 |
|
| 13 |
CityHash32() returns a 32-bit hash. |
| 14 |
|
| 15 |
CityHash64() and similar return a 64-bit hash. |
| 16 |
|
| 17 |
CityHash128() and similar return a 128-bit hash and are tuned for |
| 18 |
strings of at least a few hundred bytes. Depending on your compiler |
| 19 |
and hardware, it's likely faster than CityHash64() on sufficiently long |
| 20 |
strings. It's slower than necessary on shorter strings, but we expect |
| 21 |
that case to be relatively unimportant. |
| 22 |
|
| 23 |
CityHashCrc128() and similar are variants of CityHash128() that depend |
| 24 |
on _mm_crc32_u64(), an intrinsic that compiles to a CRC32 instruction |
| 25 |
on some CPUs. However, none of the functions we provide are CRCs. |
| 26 |
|
| 27 |
CityHashCrc256() is a variant of CityHashCrc128() that also depends |
| 28 |
on _mm_crc32_u64(). It returns a 256-bit hash. |
| 29 |
|
| 30 |
All members of the CityHash family were designed with heavy reliance |
| 31 |
on previous work by Austin Appleby, Bob Jenkins, and others. |
| 32 |
For example, CityHash32 has many similarities with Murmur3a. |
| 33 |
|
| 34 |
Performance on long strings: 64-bit CPUs |
| 35 |
======================================== |
| 36 |
|
| 37 |
We are most excited by the performance of CityHash64() and its variants on |
| 38 |
short strings, but long strings are interesting as well. |
| 39 |
|
| 40 |
CityHash is intended to be fast, under the constraint that it hash very |
| 41 |
well. For CPUs with the CRC32 instruction, CRC is speedy, but CRC wasn't |
| 42 |
designed as a hash function and shouldn't be used as one. CityHashCrc128() |
| 43 |
is not a CRC, but it uses the CRC32 machinery. |
| 44 |
|
| 45 |
On a single core of a 2.67GHz Intel Xeon X5550, CityHashCrc256 peaks at about |
| 46 |
5 to 5.5 bytes/cycle. The other CityHashCrc functions are wrappers around |
| 47 |
CityHashCrc256 and should have similar performance on long strings. |
| 48 |
(CityHashCrc256 in v1.0.3 was even faster, but we decided it wasn't as thorough |
| 49 |
as it should be.) CityHash128 peaks at about 4.3 bytes/cycle. The fastest |
| 50 |
Murmur variant on that hardware, Murmur3F, peaks at about 2.4 bytes/cycle. |
| 51 |
We expect the peak speed of CityHash128 to dominate CityHash64, which is |
| 52 |
aimed more toward short strings or use in hash tables. |
| 53 |
|
| 54 |
For long strings, a new function by Bob Jenkins, SpookyHash, is just |
| 55 |
slightly slower than CityHash128 on Intel x86-64 CPUs, but noticeably |
| 56 |
faster on AMD x86-64 CPUs. For hashing long strings on AMD CPUs |
| 57 |
and/or CPUs without the CRC instruction, SpookyHash may be just as |
| 58 |
good or better than any of the CityHash variants. |
| 59 |
|
| 60 |
Performance on short strings: 64-bit CPUs |
| 61 |
========================================= |
| 62 |
|
| 63 |
For short strings, e.g., most hash table keys, CityHash64 is faster than |
| 64 |
CityHash128, and probably faster than all the aforementioned functions, |
| 65 |
depending on the mix of string lengths. Here are a few results from that |
| 66 |
same hardware, where we (unrealistically) tested a single string length over |
| 67 |
and over again: |
| 68 |
|
| 69 |
Hash Results |
| 70 |
------------------------------------------------------------------------------ |
| 71 |
CityHash64 v1.0.3 7ns for 1 byte, or 6ns for 8 bytes, or 9ns for 64 bytes |
| 72 |
Murmur2 (64-bit) 6ns for 1 byte, or 6ns for 8 bytes, or 15ns for 64 bytes |
| 73 |
Murmur3F 14ns for 1 byte, or 15ns for 8 bytes, or 23ns for 64 bytes |
| 74 |
|
| 75 |
We don't have CityHash64 benchmarks results for v1.1, but we expect the |
| 76 |
numbers to be similar. |
| 77 |
|
| 78 |
Performance: 32-bit CPUs |
| 79 |
======================== |
| 80 |
|
| 81 |
CityHash32 is the newest variant of CityHash. It is intended for |
| 82 |
32-bit hardware in general but has been mostly tested on x86. Our benchmarks |
| 83 |
suggest that Murmur3 is the nearest competitor to CityHash32 on x86. |
| 84 |
We don't know of anything faster that has comparable quality. The speed rankings |
| 85 |
in our testing: CityHash32 > Murmur3f > Murmur3a (for long strings), and |
| 86 |
CityHash32 > Murmur3a > Murmur3f (for short strings). |
| 87 |
|
| 88 |
Installation |
| 89 |
============ |
| 90 |
|
| 91 |
We provide reference implementations of several CityHash functions, written |
| 92 |
in C++. The build system is based on autoconf. It defaults the C++ |
| 93 |
compiler flags to "-g -O2", which is probably slower than -O3 if you are |
| 94 |
using gcc. YMMV. |
| 95 |
|
| 96 |
On systems with gcc, we generally recommend: |
| 97 |
|
| 98 |
./configure |
| 99 |
make all check CXXFLAGS="-g -O3" |
| 100 |
sudo make install |
| 101 |
|
| 102 |
Or, if your system has the CRC32 instruction, and you want to build everything: |
| 103 |
|
| 104 |
./configure --enable-sse4.2 |
| 105 |
make all check CXXFLAGS="-g -O3 -msse4.2" |
| 106 |
sudo make install |
| 107 |
|
| 108 |
Note that our build system doesn't try to determine the appropriate compiler |
| 109 |
flag for enabling SSE4.2. For gcc it is "-msse4.2". The --enable-sse4.2 |
| 110 |
flag to the configure script controls whether citycrc.h is installed when |
| 111 |
you "make install." In general, picking the right compiler flags can be |
| 112 |
tricky, and may depend on your compiler, your hardware, and even how you |
| 113 |
plan to use the library. |
| 114 |
|
| 115 |
For generic information about how to configure this software, please try: |
| 116 |
|
| 117 |
./configure --help |
| 118 |
|
| 119 |
Failing that, please work from city.cc and city*.h, as they contain all the |
| 120 |
necessary code. |
| 121 |
|
| 122 |
|
| 123 |
Usage |
| 124 |
===== |
| 125 |
|
| 126 |
The above installation instructions will produce a single library. It will |
| 127 |
contain CityHash32(), CityHash64(), and CityHash128(), and their variants, |
| 128 |
and possibly CityHashCrc128(), CityHashCrc128WithSeed(), and |
| 129 |
CityHashCrc256(). The functions with Crc in the name are declared in |
| 130 |
citycrc.h; the rest are declared in city.h. |
| 131 |
|
| 132 |
|
| 133 |
Limitations |
| 134 |
=========== |
| 135 |
|
| 136 |
1) CityHash32 is intended for little-endian 32-bit code, and everything else in |
| 137 |
the current version of CityHash is intended for little-endian 64-bit CPUs. |
| 138 |
|
| 139 |
All functions that don't use the CRC32 instruction should work in |
| 140 |
little-endian 32-bit or 64-bit code. CityHash should work on big-endian CPUs |
| 141 |
as well, but we haven't tested that very thoroughly yet. |
| 142 |
|
| 143 |
2) CityHash is fairly complex. As a result of its complexity, it may not |
| 144 |
perform as expected on some compilers. For example, preliminary reports |
| 145 |
suggest that some Microsoft compilers compile CityHash to assembly that's |
| 146 |
10-20% slower than it could be. |
| 147 |
|
| 148 |
|
| 149 |
Hash Quality |
| 150 |
============ |
| 151 |
|
| 152 |
We like to test hash functions with SMHasher, among other things. |
| 153 |
SMHasher isn't perfect, but it seems to find almost any significant flaw. |
| 154 |
SMHasher is available at http://code.google.com/p/smhasher/ |
| 155 |
|
| 156 |
SMHasher is designed to pass a 32-bit seed to the hash functions it tests. |
| 157 |
No CityHash function is designed to work that way, so we adapt as follows: |
| 158 |
For our functions that accept a seed, we use the given seed directly (padded |
| 159 |
with zeroes); for our functions that don't accept a seed, we hash the |
| 160 |
concatenation of the given seed and the input string. |
| 161 |
|
| 162 |
The CityHash functions have the following flaws according to SMHasher: |
| 163 |
|
| 164 |
(1) CityHash64: none |
| 165 |
|
| 166 |
(2) CityHash64WithSeed: none |
| 167 |
|
| 168 |
(3) CityHash64WithSeeds: did not test |
| 169 |
|
| 170 |
(4) CityHash128: none |
| 171 |
|
| 172 |
(5) CityHash128WithSeed: none |
| 173 |
|
| 174 |
(6) CityHashCrc128: none |
| 175 |
|
| 176 |
(7) CityHashCrc128WithSeed: none |
| 177 |
|
| 178 |
(8) CityHashCrc256: none |
| 179 |
|
| 180 |
(9) CityHash32: none |
| 181 |
|
| 182 |
Some minor flaws in 32-bit and 64-bit functions are harmless, as we |
| 183 |
expect the primary use of these functions will be in hash tables. We |
| 184 |
may have gone slightly overboard in trying to please SMHasher and other |
| 185 |
similar tests, but we don't want anyone to choose a different hash function |
| 186 |
because of some minor issue reported by a quality test. |
| 187 |
|
| 188 |
|
| 189 |
For more information |
| 190 |
==================== |
| 191 |
|
| 192 |
http://code.google.com/p/cityhash/ |
| 193 |
|
| 194 |
[email protected] |
| 195 |
|
| 196 |
Please feel free to send us comments, questions, bug reports, or patches. |