比较一个字节数组与其他字节数组的最快方法？

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)我所有的查找数组,并使用内置PCMPGT在如何比较两个以上号码在平行下？.我知道这里有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/256的需要.然后,您可以只比较那些所谓的'哈希'匹配的那些.有众所周知的类似哈希的东西,如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个阵列(我猜不是!)这显然是一个胜利.