The search for a faster CRC32 • Hacker News Board

Re: The search for a faster CRC32

#51

Post by toolslive » Fri, Dec 04, 2015, 6:52 PM UTC

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.

That's why you have to tag the value with an identifier of the algorithm, so you can change your mind later. The problems they currently face are a direct consequence of an architectural mistake a few years ago.

Re: The search for a faster CRC32

#52

Post by jfb » Fri, Dec 04, 2015, 7:16 PM UTC

toolslive wrote: post #51

jfb wrote: post #22

Earlier quoted context omitted.

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.

That's why you have to tag the value with an identifier of the algorithm, so you can change your mind later. The problems they currently face are a direct consequence of an architectural mistake a few years ago.

Maybe; maybe not. Regardless, they aren't in a position to alter their software to the degree required at this time.

Re: The search for a faster CRC32

#53

Post by robn_fastmail » Fri, Dec 04, 2015, 10:18 PM UTC

jfb wrote: post #52

toolslive wrote: post #51

Earlier quoted context omitted.

That's why you have to tag the value with an identifier of the algorithm, so you can change your mind later. The problems they currently face are a direct consequence of an architectural mistake a few years ago.

Maybe; maybe not. Regardless, they aren't in a position to alter their software to the degree required at this time .

Indeed. As I note in the post, this wasn't something we _needed_ to do at that time, we were just curious.

Replacing a function with a faster implementation is trivial; its just another deployment and we do several of those each week. Changing data format adds operational complexity - two codepaths need to be run and maintained and we increase system load and lower response times for the duration. (The data format is versioned, so that's easy - no architectural problem there).

Its totally worth doing if you need to, and we're not afraid of that, but you don't do it on a whim - it takes proper planning and testing and needs multiple people involved.