5

我正在尝试在 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;
}

提前感谢我可以阅读的任何建议或资源。

4

3 回答 3

4

在 Linux 上？忘记register关键字，这只是对编译器的建议，根据我的经验gcc，这是浪费空间。gcc有能力自己解决这个问题。

我只是确保您使用疯狂的优化级别进行编译-O3，然后检查一下。我见过gcc在那个级别上生成代码，这让我花了几个小时才理解，真是鬼鬼祟祟。

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

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

与大多数优化一样，您通常可以用空间换取时间。请记住，对于小文件（小于 1M），您不会看到任何改进，因为无论缓冲区有多大，仍然只有一次读取。如果进程的加载需要更多时间来设置内存，您甚至可能会发现速度略有下降。

但是，由于这仅适用于小文件（无论如何性能都不是问题），所以这并不重要。性能是一个问题的大文件应该有望找到改进。

而且我知道我不需要告诉你这个（因为你表明你正在这样做），但我还是会为那些不知道的人提一下：测量，不要猜测！地上到处都是那些通过猜测优化的人的尸体:-)

于 2011-03-22T01:19:39.353 回答
3

您将无法加快 CRC 计算的实际运算速度，因此您可以查看的区域是 (a) 读取文件和 (b) 循环的开销。

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

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

您的代码也有一些您可能想要消除的冗余。

  • sizeof (unsigned char)为 1（根据 C 中的定义）；无需显式计算

  • c = &(buff[0])完全等同于c = buff

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

于 2011-03-22T01:08:21.380 回答
3

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

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

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

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

And the last optimization idea that crosses my mind is to fork(2) into 2, 3, or 4 processes (or use threading), each of which can compute the crc32 of a portion of the file, and then combine the end results after all processes have completed. crc32 may not be computationally intensive enough to actually benefit from trying to use multiple cores out of SMP or multicore computers, and figuring out how to combine partial computations of crc32 may not be feasible -- I haven't looked into it myself :) -- but it might repay the effort, and learning how to write multi-process or multi-threaded software is well worth the effort regardless.

于 2011-03-22T01:25:26.030 回答