Why is this CRC32 implementation in C# so slow?

Question

I'm using the following function to compute the CRC32 of a file in a VS2008, .NET 3.5 project:

public UInt32 ComputeHash(System.IO.Stream stream)
{
    unchecked
    {
        const int BUFFER_SIZE = 1024;

        UInt32 crc32Result = 0xFFFFFFFF;
        byte[] buffer = new byte[BUFFER_SIZE];
        int count = stream.Read(buffer, 0, BUFFER_SIZE);

        while (count > 0)
        {
            for (int i = 0; i < count; i++)
            {
                crc32Result = ((crc32Result) >> 8) ^ _crc32Table[(buffer[i]) ^ (crc32Result) & _LOOKUP_TABLE_MAX_INDEX];
            }
            count = stream.Read(buffer, 0, BUFFER_SIZE);
        }

        return ~crc32Result;
    }
}

For the sake of brevity, I have left out the function that builds the lookup table (_crc32Table). The table is an array of UInt32, is built when the class is instantiated, and contains 256 values (256 is also the value of _LOOKUP_TABLE_MAX_INDEX + 1).

I have run some benchmarks comparing this to the MD5CryptoServiceProvider and SHA1CryptoServiceProvider ComputeHash functions and they are much faster. The MD5 function is over twice as fast and the SHA1 hash is about 35% faster. I was told CRC32 is fast, but that's not what I'm seeing.

Am I mistaken in my assumptions? Is this to be expected or is there a flaw in this algorithm?

Answer 1

You are comparing your code to built in functions and asking why they are faster. What you need to do is find the source for the built in functions. How do they work? See what's different.

Betcha the built in functions call out to a native library and cheat by not having to run inside the managed memory framework.

Answer 2

Profiling may help determine how much time is taken by the IO call (Read) versus the CRC calculation. Code is often IO-bound. However, as someone who's implemented a pretty fast CRC function in C#, I can give some pointers as to why it would be slower than MD5.

• You're reading memory one byte at a time. Implement slicing-by-four so you can read four bytes at a time, or perhaps slicing-by-eight so you can read eight bytes at a time (but only if the code actually runs in 64-bit mode - you should fall back to slicing-by-four in 32-bit mode, which you should test using if(sizeof(IntPtr) < 8) or similar).
• You're processing one byte per loop iteration, and thus paying the loop overhead for every byte. Implement slicing-by-N or else consider loop unrolling. (Doing both may be unnecessary.)
• You're incurring two array bounds-checks per byte. You can use 'unsafe' code to avoid bounds checks. With unsafe code you should also ensure that you align your read pointers, although since you're only accessing .NET arrays you can probably assume they're already aligned to the machine word size. Note that unsafe code is unsafe, so be careful!
• MD5 was designed to be a very fast algorithm and doesn't have the problems listed above. It reads multiple bytes at a time and processes them in parallel, and is implemented in unmanaged code.
• This is minor, but your loop construct isn't optimal. Since you know count != 0, a do/while loop that pre-decrements count (i.e. --count) and compares to zero is better than a for loop that compares two variables. With your code, this would save a couple instructions and perhaps a memory read per byte.

If you implement slicing-by-N, pack all the lookup tables into a single large table so they can all be accessed through the same pointer. You can also use the same table for slicing-by-4 and slicing-by-8. Also be aware that a typical slicing-by-N implementation assumes a particular machine endianness, so you may need a separate version for big-endian machines, which you can check for using BitConverter.IsLittleEndian.

Answer 3

maybe: Are you counting the computation of the lookup table in your observation of the CRC throughput? Normally the lookup table is computed once and cached. If you don't cache it you will be computing it every time you calculate a CRC. Also if you only measure one CRC, then you may have included the table computation cost in the CRC computation cost. Best to measure many iterations of each hash.

---

Addendum: When I measured, I saw a factor of 2.6x, comparing your CRC32 to the MD5 hash, when the app was compiled with /debug+ and /optimize-. Using /debug- and /optimize+, I saw a factor of 1.6x. The absolute MD5 performance did not vary when I changed the compile flags. With no debug, CRC was still slower, but it was much closer.

Answer 4

I'm not too familiar with the optimizations that are automatically being performed when this code executes but you have a couple of options if profiling isn't working for you.

I can suggest trying out unsafe code and using pointer arithmetic for the buffer[i] and _crc32Table lookups in case it isn't already being optimized.

The only other place I can see you running into performance issues is with the Stream.Read calls. Have you experimented with different BUFFER_SIZE values?

Using a larger byte buffer and possibly doing some manual loop unrolling could help you out too if they aren't being optimized automatically.