I wonder if some other hash might be faster (e.g. fletcher 16).
Fletcher has poor properties as a hash according to SMHasher, if I recall correctly.
xxHash is one of the best in terms of speed and quality.
The search for a faster CRC32
41–50 of 53 posts
Re: The search for a faster CRC32
#42Earlier quoted context omitted.
Last time I needed really fast hashing I used FNV. How does it compare to xxhash?
There are hash functions that are as fast or faster than FNV and stastically stronger (and faster) than xxhash. There are multiple hash function families that should be used before either of the above in modern applications unless you need backward compatibility (like the CRC case in the article). This is an active research area and both of the above, while adequate for many casual use cases, should not be used for c…
Comparing xxHash with FNV is a strawman, it's apples and oranges in terms of quality.
You are discounting xxHash considerably. xxHash is one of the best, if not the best, all factors considered.
SMHasher:
xxHash, speed=5.4 GB/s, quality=10
MurmurHash 3a, speed=2.7 GB/s, quality=10
SBox, speed=1.4 GB/s, quality=9
Lookup3, speed=1.2 GB/s, quality=9
CityHash64, speed=1.05 GB/s, quality=10
FNV, speed=0.55 GB/s, quality=5
CRC32, speed=0.43 GB/s, quality=9
MD5-32, speed=0.33 GB/s, quality=10
SHA1-32, speed=0.28 GB/s, quality=10Re: The search for a faster CRC32
#43Earlier quoted context omitted.
There are hash functions that are as fast or faster than FNV and stastically stronger (and faster) than xxhash. There are multiple hash function families that should be used before either of the above in modern applications unless you need backward compatibility (like the CRC case in the article). This is an active research area and both of the above, while adequate for many casual use cases, should not be used for c…
Comparing xxHash with FNV is a strawman, it's apples and oranges in terms of quality. You are discounting xxHash considerably. xxHash is one of the best, if not the best, all factors considered. SMHasher: xxHash, speed=5.4 GB/s, quality=10 MurmurHash 3a, speed=2.7 GB/s, quality=10 SBox, speed=1.4 GB/s, quality=9 Lookup3, speed=1.2 GB/s, quality=9 CityHash64, speed=1.05 GB/s, quality=10 FNV, speed=0.55 GB/s, quality=5…
With all due respect, xxHash is a decent hash function but you are comparing it against some relatively weak or slow hash functions. As was pointed out last time this came up, the Metro64 hash example I offered is simultaneously faster and higher quality than xxHash. There are hash functions that are faster than xxHash and stronger than some of the cryptographic hashes, and xxHash definitely has much more bias than even MD5.
Getting a perfect score with SMHasher is table stakes. The default settings on SMHasher are much too loose for current research; I know it well, I have hacked it extensively. A state-of-the-art non-cryptographic hash function today generally has the following properties:
- statistical quality greater than or equal to MD5, a cryptographic hash. xxHash is not close to MD5 in quality.
- faster than xxHash on large keys, and for really good hashes, memory bandwidth bound. (Metro64 is, again, faster than xxHash, though not memory bandwidth bound.)
- faster than xxHash on small keys (Metro64, to use that example, is almost 2x faster)
There are a lot of good hash functions being developed by researchers. But empirically, xxHash is nowhere near the state-of-the-art any way you slice it. It is a decent hash function but there are many functions produced by many researchers that are both faster and higher quality. It isn't personal, people can measure it for themselves.
Re: The search for a faster CRC32
#44Earlier quoted context omitted.
Comparing xxHash with FNV is a strawman, it's apples and oranges in terms of quality. You are discounting xxHash considerably. xxHash is one of the best, if not the best, all factors considered. SMHasher: xxHash, speed=5.4 GB/s, quality=10 MurmurHash 3a, speed=2.7 GB/s, quality=10 SBox, speed=1.4 GB/s, quality=9 Lookup3, speed=1.2 GB/s, quality=9 CityHash64, speed=1.05 GB/s, quality=10 FNV, speed=0.55 GB/s, quality=5…
With all due respect, xxHash is a decent hash function but you are comparing it against some relatively weak or slow hash functions. As was pointed out last time this came up, the Metro64 hash example I offered is simultaneously faster and higher quality than xxHash. There are hash functions that are faster than xxHash and stronger than some of the cryptographic hashes, and xxHash definitely has much more bias than e…
Yes, I remember reading your post on Metro64 at the time:
http://www.jandrewrogers.com/2015/05/27/metrohash/
Interesting that you based your results there on SMHasher. Are there better benchmarks available?
Re: The search for a faster CRC32
#45Earlier quoted context omitted.
That's a misunderstanding. If you need a hash or checksum for very long data (megabytes, gigabytes), use xxhash. It's not the best for hash tables.
Good to know. I was using FNV to hash spam signatures which are typically small. Glad I chose well.
If your spam signatures are small (around 32 bytes) and fixed size, you might also want to look into a pure XOR tabulation hash. It's excellent for generating fixed-size keys for hash tables:
http://www2.imm.dtu.dk/projects/thrash-workshop/slides/thoru...
https://en.wikipedia.org/wiki/Tabulation_hashing
I use it all the time when I need a hash table index. It's simple to understand, safe and fast. Even though it can generate more assembly than other hashes, it's actually often faster because it has no multiply operation, only XOR. If the tables are small enough to fit into cache (i.e. small keys), it's brilliant. It has properties suitable for triangular probing, where other hashes sometimes don't have enough independence. And if you need a rolling hash, i.e. for Rabin Karp, it's also perfect.
Re: The search for a faster CRC32
#46Earlier quoted context omitted.
According to the Stephan Brumme website you linked to, the slice-by-8 lookup table is 8K and the slice-by-16 table is 16K, so your combo version of crc32 needs 24K of L1 cache to run at full speed. Modern server class CPUs typically have 32K of L1 dcache so that doesn't leave much room for the rest of your work. Maybe that's reasonable (I don't really know what Cyrus does), but I thought it was worth thinking about.
Most of the time we're iterating through a cyrus.index, where there's 104 bytes per record, and we're doing a CRC32 over 100 of them, or we're reading through a twoskip database where we're CRCing the header (24+bytes, average 32) and then doing a couple of mmap lookup and memcmp operations before jumping to the next header, which is normally only within a hundred bytes forwards on a bit and mostly sorted database. T…
I'm fairly sure E5520 has 32 kB L1 data cache, not 128 kB. L1 caches are core local, not shared like L3.
Re: The search for a faster CRC32
#47Earlier quoted context omitted.
Most of the time we're iterating through a cyrus.index, where there's 104 bytes per record, and we're doing a CRC32 over 100 of them, or we're reading through a twoskip database where we're CRCing the header (24+bytes, average 32) and then doing a couple of mmap lookup and memcmp operations before jumping to the next header, which is normally only within a hundred bytes forwards on a bit and mostly sorted database. T…
I'm fairly sure E5520 has 32 kB L1 data cache, not 128 kB. L1 caches are core local, not shared like L3.
This is what the datasheet says [1]:
- Instruction Cache = 32kB, per core
- Data Cache = 32kB, per core
- 256kB Mid-Level cache, per core
- 8MB shared among cores (up to 4)
[1] http://www.intel.com/content/www/us/en/processors/xeon/xeon-...
Re: The search for a faster CRC32
#48I love how the linked Twoskip PDF presentation [1] lists as one of the features:
"Easy to rewrite in other languages (e.g. Perl!)"
[1] http://opera.brong.fastmail.fm.user.fm/talks/twoskip/twoskip...
Re: The search for a faster CRC32
#49I wonder if some other hash might be faster (e.g. fletcher 16).
No, if you have a HW supported crc32 builtin nothing will be faster than this.
You can safely skip the PCLMULQDQ optimization, which only works on newer CPU's, but crc32 should be almost everywhere nowadays.
Re: The search for a faster CRC32
#50> kernel, oh, how I wanted to like this. Every CRC32 operation consists of a write to and read from a socket...
Why didn't they extract the CRC32 code from the kernel and try it directly?
https://github.com/torvalds/linux/blob/master/lib/crc32.c https://github.com/torvalds/linux/blob/master/include/linux/...