Hope they contribute the change back to Cyrus.
Same day, in fact: https://git.cyrus.foundation/diffusion/I/browse/master/lib/c...
The search for a faster CRC32
11–20 of 53 posts
Re: The search for a faster CRC32
#12I read more about the slice-by-N algorithms because they sounded really interesting. The way they work is by using a set of lookup tables that are 4k to 16k in size (larger lookup table for larger N). The reason they are fast is because the lookup tables fit within the L1 cache on modern CPUs. So when you do 100M rounds of CRC32 it is super fast because the table is always cache hot, but I don't think this result is informative if you just want to occasionally do a CRC in between doing other types of work (especially for small buffer sizes). You will have to wait as the lookup tables are brought up through the cache heirarchy _and_ you are potentially evicting other useful data from the cache at the same time. Presumably PCLMULQDQ does not have this drawback.
Re: The search for a faster CRC32
#13I read more about the slice-by-N algorithms because they sounded really interesting. The way they work is by using a set of lookup tables that are 4k to 16k in size (larger lookup table for larger N). The reason they are fast is because the lookup tables fit within the L1 cache on modern CPUs. So when you do 100M rounds of CRC32 it is super fast because the table is always cache hot, but I don't think this result is…
This is a great point and a huge mental problem I have when looking at (and writing) benchmarks. If anyone knows more about this (i.e. if they can show why it isn't true) please speak up.
Re: The search for a faster CRC32
#14I read more about the slice-by-N algorithms because they sounded really interesting. The way they work is by using a set of lookup tables that are 4k to 16k in size (larger lookup table for larger N). The reason they are fast is because the lookup tables fit within the L1 cache on modern CPUs. So when you do 100M rounds of CRC32 it is super fast because the table is always cache hot, but I don't think this result is…
This is a great point and a huge mental problem I have when looking at (and writing) benchmarks. If anyone knows more about this (i.e. if they can show why it isn't true) please speak up.
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 investigate further at some point) our Cyrus servers are doing enough checksumming work to keep any tables hot in the cache. So the tests are hopefully a useful indicator of where improvements can be made.
Re: The search for a faster CRC32
#15> Next, we have to get our optimisation settings right. We compile Cyrus with no optimisations and full debugging because it makes it really easy to work with crash dumps.
Wait, so are these results without letting the compiler optimize?
Re: The search for a faster CRC32
#16> Next, we have to get our optimisation settings right. We compile Cyrus with no optimisations and full debugging because it makes it really easy to work with crash dumps. Wait, so are these results without letting the compiler optimize?
The results in the tests are all with optimisations (-O3 -march=sandybridge -mtune=intel), as mentioned in the post.
The exception is the Debian packaged version of zlib, because we don't control that. That's the reason I include stock zlib in the tests - if it had been wildly different from the system zlib, I would have looked into recompiling the Debian package with more optimisations. There were no major differences and indeed, inspecting the package further shows that it is compiled with optimisations.
On the Cyrus side, we used to link to the Debian zlib, so we get those optimisations. For the new code bundled in Cyrus itself, we have to enable optimisations ourselves.
Re: The search for a faster CRC32
#17Earlier quoted context omitted.
This is a great point and a huge mental problem I have when looking at (and writing) benchmarks. If anyone knows more about this (i.e. if they can show why it isn't true) please speak up.
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.
Re: The search for a faster CRC32
#18why not rip out CRC32 and put in xxhash?
More about xxhash here, it's by Yann Collet, the author of LZ4: http://fastcompression.blogspot.fr/2012/04/selecting-checksu...
And (perhaps more interestingly) Finite State Entropy coding:
http://fastcompression.blogspot.com/2013/12/finite-state-ent...
Re: The search for a faster CRC32
#19> Next, we have to get our optimisation settings right. We compile Cyrus with no optimisations and full debugging because it makes it really easy to work with crash dumps. Wait, so are these results without letting the compiler optimize?
The results in the tests are all with optimisations (-O3 -march=sandybridge -mtune=intel), as mentioned in the post. The exception is the Debian packaged version of zlib, because we don't control that. That's the reason I include stock zlib in the tests - if it had been wildly different from the system zlib, I would have looked into recompiling the Debian package with more optimisations. There were no major differenc…
Did you guys every try splashing out for a small intel compiler licence and bootstrapping a test system?
Re: The search for a faster CRC32
#20Modern 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.