Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The search for a faster CRC32

blog.fastmail.com

Post reply on HN
Print view View original

31–40 of 53 posts

Re: The search for a faster CRC32

#31

Post by mcbain »

amluto wrote: post #30
revelation wrote: post #23

If they have CRC accounting for 10% of CPU, they must be using these checksums a lot. At some point I'd imagine the false error rate simply due to bit flips and other random errors on the path from database through CRC function will outlast whatever value you are getting from the constant rechecks. Also, literature suggests a throughput of ∼2.67 bytes per cycle for the CRC32 instruction, a three fold improvement over…

Is the CRC32 instruction much faster than an optimized implementation using PCLMULQDQ? It's available on a wider range of CPUs, but I thought I remembered that PCLMULQDQ worked very quickly.

I think when I looked single instr crc32 was ~5 times faster than the pclmulqdq version.

As an aside, if they have a server in production that doesn't support CLMUL, they should junk that machine - it appeared in Westmere and Bulldozer - everything earlier is EOLed. Crc32 was in sse4.2, so Nehalem.

The crc32 instruction is hard to beat, has been around for years, and I would guess the different poly could be phased in on their systems like you would for changing a password algorithm, or just try the new poly since it is quick, and if it fails use the old poly.

Re: The search for a faster CRC32

#32

Post by illumen »

amluto wrote: post #30
revelation wrote: post #23

If they have CRC accounting for 10% of CPU, they must be using these checksums a lot. At some point I'd imagine the false error rate simply due to bit flips and other random errors on the path from database through CRC function will outlast whatever value you are getting from the constant rechecks. Also, literature suggests a throughput of ∼2.67 bytes per cycle for the CRC32 instruction, a three fold improvement over…

Is the CRC32 instruction much faster than an optimized implementation using PCLMULQDQ? It's available on a wider range of CPUs, but I thought I remembered that PCLMULQDQ worked very quickly.

A parallel PCLMULQDQ version is faster than a serial CRC32. Because CRC32 has a latency of 3 cycles.

A parallel CRC32 can be slightly faster with more data segment used, and more code size.

Also PCLMULQDQ can use an polynomial I think. So they could make a compatible version.

The lookup table version they used has to have used lots more CPU cache. Also, I would suggest they look at reducing the amount of times they call the function. Since there are two ways to speed up functions that are called a lot. One is to stop calling it so many times.

Or since IO is limiting, they could consider compressing/decompressing the data as well. Using something fast like LZ4 compression. This will give them faster IO and a checksum at the same time. Something like Blosc can be faster than memcpy. Especially since the data is replicated over the network as well, and they would save space on their storage.

Modern CPU performance optimization is very often about memory IO. If the data is in L2/L3 then you can do a LOT of computation on it, almost for free, compared to the time it takes to get it into L2/L3.

During that time waiting for memory/disk/network IO, they might consider other things. Like indexing, better checksums (like SHA1) or even encryption. Especially if the data is already in L2/L3.

Re: The search for a faster CRC32

#34

Post by stelund »

jfb wrote: post #22
melted wrote: post #20

Modern Intel CPUs have an instruction specifically to compute CRC. This instruction is easily consumed through a C++ intrinsic, literally in one line of code. You can't do any better than that, no matter what you use.

In this particular case, however: [Intel's CRC32 CPU instructions] uses different inputs to the CRC32 algorithm (known as the polynomial) which is apparently more robust, and is used in networks, filesystems, that sort of thing. It gives different results to the "standard" polynomial, typically used in compression. They would have to go back and recompute all their existing stored checksums.

But they can create new with the new polynomial and try to check against that first. If it fails then fall back to regular polynomial.

Re: The search for a faster CRC32

#35

Post by dalke »

aidenn0 wrote: post #33

I wonder if some other hash might be faster (e.g. fletcher 16).

If they were going to use a different hash function then they would more likely uses the built-in CRC32 instruction, which computes CRC-32C. That would certainly be faster.

Re: The search for a faster CRC32

#36

Post by brongondwana »

minimax wrote: post #17
robn_fastmail wrote: post #14

Earlier quoted context omitted.

I think that mostly, your benchmarks have to match your workloads. Most of the CRC32 benchmarks I've seen are looking at larger buffers. The xxhash function mentioned elsewhere in this thread was claimed to be "an order of magnitude" faster, but again, large buffers - the gain over CRC32 on the same tests were rather more modest (though not at all insignificant). In this case, I think (but am curious, will investigat…

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. The mmap lookahead will also have been in that close-by range.

Also, our oldest CPU on production servers seems to be the E5520 right now, which has 128kb of L1 data cache.

Re: The search for a faster CRC32

#37

Post by jandrewrogers »

baudehlo wrote: post #24
jszymborski wrote: post #2

why not rip out CRC32 and put in xxhash?

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 checksums for the same reason CRC32 should not be used for checksums in large systems.

As an example from one of my hash function research projects, MetroHash64 will outperform xxhash both for speed and stastical robustness (which is quasi-cryptographic). If you only need 32 bits, truncate larger hashes; if they have very strong stastical properties, that works well.

Lots of people working on this stuff.

Re: The search for a faster CRC32

#38

Post by mockery »

> cloudflare is amazing until the input buffer gets under 80 bytes. That's the point where it stops using the optimised implementation and falls back to the regular zlib implementation (slice-by-4). I'm not sure why (no explanatory comments I could find), but it's a showstopper for our uses.

Why on earth is this a showstopper?

Re: The search for a faster CRC32

#39

Post by awalton »

jszymborski wrote: post #2

why not rip out CRC32 and put in xxhash?

If you were going to rewrite your data, why wouldn't you go with something that's been standardized by every hardware implementers as the next generation CRC algorithm, CRC32c (the one the article explicitly throws out at the beginning, because the author did not want to rewrite the data)? Even ARM chips and network- and storage-focused microcontrollers have hardware acceleration for it these days...

Re: The search for a faster CRC32

#40

Post by krallja »

mockery wrote: post #38

> cloudflare is amazing until the input buffer gets under 80 bytes. That's the point where it stops using the optimised implementation and falls back to the regular zlib implementation (slice-by-4). I'm not sure why (no explanatory comments I could find), but it's a showstopper for our uses. Why on earth is this a showstopper?

> The buffers we checksum are small, the minimum being 24 bytes (a twoskip header), average perhaps 32 bytes. This is our target case.
Post reply on HN