如何加快 crc32 计算？

Question

我正在尝试在 linux 上尽可能快地编写 crc32 实现，作为学习优化 C 的练习。我已经尽力了，但我一直无法在网上找到很多好的资源。我什至不确定我的缓冲区大小是否合理；它是通过反复实验选择出来的。

#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;
}

在此先感谢您提供我可以通读的任何建议或资源。

Answer 1

您要求将三个值存储在寄存器中，但标准 x86 只有四个通用寄存器：这对最后一个剩余寄存器来说是一个巨大的负担，这就是为什么我期望实际上register只会阻止您的原因之一用于&foo查找变量的地址。我认为现在没有任何现代编译器使用它作为提示。请随意删除所有三种用途并重新安排您的应用程序。

由于您自己正在读取大量文件，因此您不妨直接使用open(2)andread(2)并删除幕后的所有标准 IO 处理。另一种常见的方法是将open(2)文件mmap(2)放入内存：让操作系统根据需要将其分页。这可能允许您在进行计算时乐观地从磁盘读取未来的页面：这是一种常见的访问模式，操作系统设计者已尝试优化一种模式。（一次映射整个文件的简单机制确实对您可以处理的文件大小设置了上限，在 32 位平台上可能约为 2.5 GB，在 64 位平台上绝对巨大。以块的形式映射文件将即使在 32 位平台上，您也可以处理任意大小的文件，但代价是像现在用于读取和映射的循环一样。）

正如 David Gelhar 指出的那样，您使用的是奇数长度的缓冲区——这可能会使将文件读入内存的代码路径变得复杂。如果您想坚持从文件读取到缓冲区，我建议使用多个8192（两页内存），因为在最后一个循环之前不会出现特殊情况。

如果您真的想追求最后一点速度，并且不介意大幅增加预计算表的大小，则可以以 16 位块的形式查看文件，而不仅仅是 8 位块。通常，沿着 16 位对齐访问内存比沿着 8 位对齐访问内存要快，并且您可以将循环的迭代次数减少一半，这通常会带来巨大的速度提升。当然，缺点是增加了内存压力（65k 条目，每个 8 字节，而不是每个 4 字节 256 个条目），而且更大的表不太可能完全放入 CPU 缓存中。

我想到的最后一个优化想法是fork(2)分成 2、3 或 4 个进程（或使用线程），每个进程都可以计算文件一部分的 crc32 ，然后在所有进程完成后合并最终结果。crc32 的计算强度可能不足以真正受益于尝试使用 SMP 或多核计算机中的多个内核，并且弄清楚如何组合 crc32 的部分计算可能不可行 - 我自己还没有研究过:) - - 但它可能会得到回报，并且学习如何编写多进程或多线程软件无论如何都是值得的。