如何加速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;
}

非常感谢您提供的任何建议或资源，我可以仔细阅读。

- sockmeistr

---

你正在将I/O与CRC计算交错进行。这将使得衡量CRC代码性能上的小差异变得更加困难。 - Jim Lewis

我不仅对加速CRC感兴趣；如果您有任何关于加速Linux输入/输出的建议，我很乐意听取。 - sockmeistr

知道什么时候不要进行优化非常重要。这是一个很好的例子。毫无意义，文件I/O比crc计算慢多个数量级。加速它需要更昂贵的硬件，而不是代码。 - Hans Passant

@HansPassant - 在这种情况下，事实证明I/O的数量级与CRC计算相同 - 将行x =（x >> 8）^ crctable [(x＆0xFF）^ * c];更改为x ^ = * c可以将我的PC上的运行时间减半。 - sockmeistr

我对奇迹深信不疑，尽管持怀疑态度。请注意吉姆的评论。为了好玩，重新启动计算机并再次尝试。只有一次。 - Hans Passant

你必须指定你正在尝试优化代码的吞吐量（少量大输入）还是调用速度（许多小输入）。如果你的代码足够好，那么你的吞吐量将受到RAM或磁盘带宽的限制（与例如异或输入的速度进行比较），并且没有进一步优化的意义。对于小输入，程序启动或函数调用开销，即堆栈和缓存使用更为重要。无论如何，请记住使用远大于L3缓存的总输入大小进行测试。 - Dima Tisnek

Answer 1

在Linux上？忘掉register关键字，那只是对编译器的一个建议，而且根据我的经验，使用gcc时，这只会浪费空间。gcc可以自己找出最佳方案。

我只需要确保你使用了疯狂的优化级别-O3，并检查一下即可。我曾经看到gcc在这个级别上生成的代码让我花了几个小时才理解，它太狡猾了。

关于缓冲区大小，尽可能地将其设置得更大。即使使用缓冲区，调用fread的成本仍然存在，因此您做得越少，性能就越好。如果您将缓冲区大小从1K增加到1M，则会看到巨大的改进，但如果您将其从1M增加到2M，则不会有太大的改进，但即使是少量的性能提升也是一种提升。并且，2M并不是您可以使用的上限，如果可能，我会将其设置为一个或多个 gigabytes 。

然后，您可能希望将其放在文件级别（而不是在main内部）。在某些情况下，堆栈无法容纳它。

与大多数优化一样，您通常可以用空间来换时间。请记住，对于小文件（小于1M），即使您将缓冲区设置得很大，仍然只有一个读取，因此不会看到任何改进。如果加载过程需要更多时间来设置内存，则甚至可能会导致轻微的减速。

但是，由于这只适用于小文件（性能本来就不是问题的情况下），所以这并不重要。对于性能是问题的大文件，应该会发现一些改进。

我知道我不需要告诉你这个（因为你表示你正在做这件事），但是我还是想提一下，因为有些人不知道：测量，不要猜测！地面上堆满了那些通过猜测进行优化的尸体 :-)

- paxdiablo

---

最初我认为 register 不会有任何作用，但是当我尝试使用 time 进行实验时，加入它确实让我的程序加速了——尽管我不确定这是在我开始使用显式的 -O3 标志编译之前还是之后。 我通过增加缓冲区大小直到 time 不再显示任何速度提升来确定缓冲区大小，但你说得对；使数字更大并不会真正伤害到程序。 - sockmeistr

Answer 2

您无法加速CRC计算的实际算术运算，因此可以考虑的领域是(a)读取文件的开销和(b)循环的开销。

您正在使用相当大的缓冲区大小，这很好（但为什么是奇数？）。使用read(2)系统调用（假设您在类Unix系统上）而不是fread(3)标准库函数可能会节省一个copy操作（将数据从fread的内部缓冲区复制到您的缓冲区中）。

对于循环开销，请查看循环展开。

---

您的代码中还存在一些冗余，您可能希望消除它们。

• sizeof (unsigned char) 的值为1（在C语言中已定义），无需显式计算

• c = &(buff[0]) 与 c = buff 完全等效

这些更改都不会提高代码的性能（假设编译器良好），但它们会使其更清晰，并符合通常的C风格。

- David Gelhar

---

缓冲区大小为奇数的原因是我不小心打成了1048567而不是2^20的1048576。不知道这是怎么发生的 - 发现得好。 - sockmeistr

sizeof(unsigned char)不是计算出来的，它在编译时设置，对于c=buff和c=&(buff[0])也是一样的。 - Dima Tisnek

Answer 3

你要求将三个值存储在寄存器中，但标准的x86只有四个通用寄存器：这会给最后一个剩余的寄存器带来很大的负担，这也是我认为register只是防止你使用&foo找到变量地址的一个原因。我认为现代编译器甚至不再使用它作为提示了。可以随意删除所有三个用法并重新计时应用程序。

由于你自己读取文件的大块内容，你可能会直接使用open(2)和read(2)，并删除所有幕后的标准IO处理。另一种常见的方法是将文件open(2)和mmap(2)到内存中：让操作系统在需要时将其分页。这可以使未来的页面在你执行计算时被乐观地从磁盘读取：这是一种常见的访问模式，也是操作系统设计人员试图优化的一种方式。（一次映射整个文件的简单机制确实对你可以处理的文件大小有上限，可能在32位平台上约为2.5 GB，在64位平台上则非常巨大。将文件分块映射将允许你处理任意大小的文件，即使在32位平台上也是如此，但代价是像现在读取的循环一样的循环，但用于映射。）

正如David Gelhar所指出的，你正在使用一个奇数长度的缓冲区——这可能会使将文件读入内存的代码路径变得复杂。如果你想坚持从文件读入缓冲区，请使用8192的倍数（两个页面的内存），因为直到最后一个循环它都不会有特殊情况。

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

我想到的最后一个优化点是将fork(2)分成2、3或4个进程（或使用线程），每个进程可以计算文件的一部分的crc32，然后在所有进程完成后组合最终结果。crc32可能不足以从SMP或多核计算机中获得多核效益，并且确定如何组合crc32的部分计算可能是不可行的——我自己还没有研究过:) ——但这可能会回报努力，学习编写多进程或多线程软件无论如何都是值得的。

- sarnold

---

结果发现将约500MB的文件映射到内存中，然后循环遍历它们需要很长时间——大约比我之前的方法慢3倍。我是一次一个字节地循环遍历mmap的；我不确定Linux是否将此解释为我想要逐字节加载文件到内存中...转换为“打开”和“读取”在运行时没有明显变化；但是，我正在测试几个大文件的情况——也许对于许多小文件来说会有所不同。将块大小加倍是一个有趣的想法；我明天会好好看看。谢谢 - sockmeistr

BUFSIZE看起来像2 ** 20，最后两位数字被意外交换了。 :D - Jürgen A. Erhard