c++ - 对于大小为 4096 的缓冲区，最快的校验和算法是什么？

Question

我正在寻找一种尽可能快的散列/校验和算法，同时仍然能够检测到 4096 字节内存页的更改。因为大小是固定的，所以我希望应该有可能为此目的获得一个优化的算法，因为大小保证不会改变。

我正在做的是对一些内存页面进行校验和，执行操作，然后再次对页面进行校验和以查看它们是否已更改。由于空间原因，简单地按字节与旧字节的拷贝进行比较是不可行的。我不需要知道更改发生在页面中的什么位置，只要更改发生了即可，因此比较校验和就足够了。

我已经在硬件和 xxHash 中尝试了 CRC32，两者都取得了不错的效果。尽管如此，据我所知，它们并不是为固定大小的缓冲区量身定制的。

编辑:这是我在硬件中用于 CRC32 的代码。由于某些原因，它比 xxHash 慢。

// Warning! Not padding, so don't use if length isn't dividable by sizeof(uint32_t).
uint32_t sse42_crc32_32bit(const uint32_t* buffer, const uint32_t length)
{
    uint32_t crc = 0;
    const uint32_t numRounds = length / sizeof(uint32_t);

    for (uint32_t i = 0; i < numRounds; ++i)
    {
        crc = _mm_crc32_u32(crc, buffer[i]);
    }

    return crc;
}

Answer 1

有farmHash128 ，比 xxHash64 更快。不过，我不确定它的质量。

如果你用xxHash64，我觉得你展开一点点(比如展开8次)，会快一点。如果页面不在缓存中，预取可能会有所帮助。

但是请注意，这

"If I miss one bit of change it's game over."

是一个冒险的游戏。 xxHash64 的 64 位输出肯定是不够的的。您肯定会遇到哈希冲突。我会说您至少需要为此目的使用 256 位哈希。它不会 100% 检测到变化，但会关闭。通常的智慧是使用碰撞概率低于系统故障概率的哈希大小(乘以 10^-X，其中 X 是一个“较小”的正数，如 5)。