5

我正在使用以下函数来计算 VS2008、.NET 3.5 项目中文件的 CRC32：

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

为简洁起见，我省略了构建查找表 (_crc32Table) 的函数。该表是一个 UInt32 的数组，在类实例化时构建，包含 256 个值（256 也是 _LOOKUP_TABLE_MAX_INDEX + 1 的值）。

我已经运行了一些基准测试，将其与 MD5CryptoServiceProvider 和 SHA1CryptoServiceProvider ComputeHash 函数进行比较，它们的速度要快得多。MD5 函数的速度是原来的两倍多，而 SHA1 哈希则快了大约 35%。有人告诉我 CRC32 很快，但这不是我所看到的。

我的假设有误吗？这是意料之中的还是这个算法有缺陷？

4

4 回答 4

6

您正在将您的代码与内置函数进行比较，并询问为什么它们更快。您需要做的是找到内置函数的来源。它们是如何工作的？看看有什么不同。

Betcha 内置函数调用本机库并通过不必在托管内存框架内运行来作弊。

于 2009-06-03T16:51:32.140 回答
3

分析可能有助于确定 IO 调用（读取）与 CRC 计算所花费的时间。代码通常受 IO 限制。然而，作为一个在 C# 中实现了一个非常快的 CRC 函数的人，我可以给出一些关于为什么它会比 MD5 慢的指针。

  • 您一次读取一个字节的内存。实现slicing-by-4，这样你一次可以读取 4 个字节，或者可能是 slicing-by-8，这样你就可以一次读取 8 个字节（但前提是代码实际上在 64 位模式下运行 - 你应该回退在 32 位模式下切成四倍，您应该使用 if(sizeof(IntPtr) < 8) 或类似方法进行测试。
  • 您每次循环迭代处理一个字节，因此为每个字节支付循环开销。实施 N 切片，否则考虑展开循环。（两者都做可能是不必要的。）
  • 每个字节都会发生两次数组边界检查。您可以使用“不安全”代码来避免边界检查。对于不安全的代码，您还应该确保对齐读取指针，尽管由于您只访问 .NET 数组，您可能会假设它们已经与机器字长对齐。请注意，不安全的代码是不安全的，所以要小心！
  • MD5 被设计为一种非常快速的算法，没有上面列出的问题。它一次读取多个字节并并行处理它们，并在非托管代码中实现。
  • 这是次要的，但您的循环构造不是最佳的。既然您知道 count != 0，那么预先递减计数（即 --count）并与零进行比较的 do/while 循环比比较两个变量的 for 循环要好。使用您的代码，这将节省一些指令，并且可能会节省每字节读取的内存。

如果您实现按 N 切片，请将所有查找表打包到一个大表中，以便可以通过同一个指针访问它们。您还可以使用同一个表进行 4 切片和 8 切片。另请注意，典型的 N 切片实现假定特定的机器字节序，因此您可能需要一个单独的版本用于大字节序机器，您可以使用 BitConverter.IsLittleEndian 检查它。

于 2016-05-08T17:12:08.673 回答
0

也许：您在观察 CRC 吞吐量时是否计算了查找表的计算？通常，查找表计算一次并缓存。如果您不缓存它，您将在每次计算 CRC 时计算它。此外，如果您只测量一个 CRC，那么您可能已将表计算成本包含在 CRC 计算成本中。最好测量每个哈希的多次迭代。

附录：当我测量时，当应用程序使用 /debug+ 和 /optimize- 编译时，我看到了 2.6 倍的系数，将您的 CRC32 与 MD5 哈希值进行比较。使用 /debug- 和 /optimize+，我看到了 1.6 倍。当我更改编译标志时，绝对 MD5 性能没有变化。没有调试，CRC 仍然较慢，但更接近。

于 2009-06-03T16:41:41.780 回答
0

我不太熟悉此代码执行时自动执行的优化，但如果分析不适用于您，您有几个选择。

我可以建议尝试不安全的代码并使用指针算法进行缓冲区 [i] 和 _crc32Table 查找，以防它尚未被优化。

我可以看到您遇到性能问题的唯一其他地方是 Stream.Read 调用。您是否尝试过不同的 BUFFER_SIZE 值？

如果它们没有被自动优化，使用更大的字节缓冲区并可能进行一些手动循环展开也可以帮助您。

于 2009-06-03T17:11:06.110 回答