How can I speed up crc32 calculation?

Question

I'm trying to write a crc32 implementation on linux that's as fast as possible, as an exercise in learning to optimise C. I've tried my best, but I haven't been able to find many good resources online. I'm not even sure if my buffer size is sensible; it was chosen by repeated experimentation.

#include <stdio.h>
#define BUFFSIZE 1048567

const unsigned long int lookupbase = 0xEDB88320;
unsigned long int crctable[256] = {
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
/* LONG LIST OF PRECALCULTED VALUES */
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D};

int main(int argc, char *argv[]){
    register unsigned long int x;
    int i;
    register unsigned char *c, *endbuff;
    unsigned char buff[BUFFSIZE];
    register FILE *thisfile=NULL;
    for (i = 1; i < argc; i++){
        thisfile = fopen(argv[i], "r");
        if (thisfile == NULL) {
            printf("Unable to open ");
        } else {
            x = 0xFFFFFFFF;
            c = &(buff[0]);
            endbuff = &(buff[fread(buff, (sizeof (unsigned char)), BUFFSIZE, thisfile)]);
            while (c != endbuff){
                while (c != endbuff){
                    x=(x>>8) ^ crctable[(x&0xFF)^*c];
                    c++;
                }
                c = &(buff[0]);
                endbuff = &(buff[fread(buff, (sizeof (unsigned char)), BUFFSIZE, thisfile)]);
            }
            fclose(thisfile);
            x = x ^ 0xFFFFFFFF;
            printf("%0.8X ", x);
        }
        printf("%s\n", argv[i]);
    }
    return 0;
}

Thanks in advance for any suggestions or resources I can read through.

Answer 1

On Linux? Forget about the register keyword, that's just a suggestion to the compiler and, from my experience with gcc, it's a waste of space. gcc is more than capable of figuring that out for itself.

I would just make sure you're compiling with the insane optimisation level, -O3, and check that. I've seen gcc produce code at that level which took me hours to understand, so sneaky that it was.

And, on the buffer size, make it as large as you possibly can. Even with buffering, the cost of calling fread is still a cost, so the less you do it, the better. You would see a huge improvement if you increased the buffer size from 1K to 1M, not so much if you up it from 1M to 2M, but even a small amount of increased performance is an increase. And, 2M isn't the upper bound of what you can use, I'd set it to one or more gigabytes if possible.

You may then want to put it at file level (rather than inside main). At some point, the stack won't be able to hold it.

As with most optimisations, you can usually trade space for time. Keep in mind that, for small files (less than 1M), you won't see any improvement since there is still only one read no matter how big you make the buffer. You may even find a slight slowdown if the loading of the process has to take more time to set up memory.

But, since this would only be for small files (where the performance isn't a problem anyway), it shouldn't really matter. Large files, where the performance is an issue, should hopefully find an improvement.

And I know I don't need to tell you this (since you indicate you are doing it), but I will mention it anyway for those who don't know: Measure, don't guess! The ground is littered with the corpses of those who optimised with guesswork :-)