c - 将一个字节数组与许多其他字节数组进行比较的最快方法？

Question

我有一个具有以下结构的循环:

• 计算长度为 k 的字节数组(有些慢)
• 查找计算出的字节数组是否与我拥有的 N 字节数组列表中的任何一个相匹配。
• 重复

我的循环要调用很多次(它是我程序的主循环)，我希望第二步尽可能快。

第二步的简单实现是使用memcmp:

char* calc;
char** list;
int k, n, i;
for(i = 0; i < n; i++) {
  if (!memcmp(calc, list[i], k)) {
    printf("Matches array %d", i);
  }
}

你能想出更快的方法吗？一些事情:

• 我的列表在我的程序开始时是固定的，任何预先计算都可以。
• 假设 k 较小 (<= 64)，N 适中(大约 100-1000)。
• 性能是这里的目标，可移植性不是问题。内在/内联汇编很好，只要它更快。

以下是我的一些想法:

• 给定 k<64 并且我在 x86_64 上，我可以将我的查找数组排序为长数组，然后对其进行二进制搜索。 O(日志(n))。即使 k 很大，我也可以对查找数组进行排序并使用 memcmp 进行二分查找。
• 再一次，鉴于 k 很小，我可以计算所有查找数组的 8/16/32 位校验和(最简单的方法是使用 xor 将我的数组自身折叠起来)并使用内置的-in PCMPGT 如 How to compare more than two numbers in parallel? .我知道 SSE4.2 在此处可用。

您认为在这里进行矢量化/sse 是个好主意吗？如果是，您认为最好的方法是什么。我想说这不是早期优化，但性能在这里至关重要，我需要外循环尽可能快。谢谢

EDIT1:它看起来像 http://schani.wordpress.com/tag/c-optimization-linear-binary-search-sse2-simd/提供了一些有趣的想法。在 long 列表上进行二进制搜索似乎是可行的方法..

Answer 1

最佳解决方案将取决于要匹配的数组数量、数组的大小以及它们更改的频率。我会考虑完全避免进行比较。

假设要与之比较的数组列表不会经常更改，并且您有很多这样的数组，我会为每个数组创建一个散列，然后当您进行比较时，散列您正在测试的东西。然后你只需要比较哈希值。使用像 SHA256 这样的哈希，您可以将其作为正指标和负指标(即哈希匹配足以说明数组匹配，而哈希不匹配足以说明数组不同)。如果您有(比方说)1,000,000 个数组进行比较，而这些数组几乎没有变化，那么这会非常有效，因为计算散列比 1,000,000 个数组比较要快。

如果您的数组数量较少，您可以考虑使用更快的非加密散列。例如，简单地将数组模块 256 中的字节相加的“散列”(这是一个糟糕的散列，您可以做得更好)将消除比较(比方说)目标数组空间的 255/256ths 的需要。然后，您可以只比较所谓的“哈希”匹配的那些。有众所周知的类似哈希的东西，例如 CRC-32，可以快速计算。

在任何一种情况下，您都可以通过散列(对 X 取模)进行查找以确定实际比较哪些数组。

您建议 k 较小，N 适中(即大约 1000)。我猜速度将围绕内存缓存。此处不访问 1,000 个小型阵列将非常有帮助。

如果数组以与比较相似的频率变化，以上所有内容都将无用。

加法(假设您正在查看 64 字节或类似字节)。我会研究一个非常快速的非加密散列函数。例如看:https://code.google.com/p/smhasher/wiki/MurmurHash3

看起来每个 32 位字需要 3-4 条指令来生成散列。然后，您可以将结果截断为(比方说)12 位的 4096 条目哈希表，冲突很少(每个桶都链接到目标数组)。这意味着您将查看大约 30 条指令来计算哈希值，然后是每个存储桶条目(预期值 1)一条指令来查找列表项，然后是针对每个预期命中(介于 0 和 1 之间)进行一次手动比较。因此，与其比较 1000 个数组，不如比较 0 和 1 个数组，并生成一个散列。如果您无法在 30 条指令中比较 999 个数组(我猜不会!)，这显然是一个胜利。