寻找最快的Hamming距离C实现方法

Question

寻找最快的Hamming距离C实现方法

cperformanceassemblyoptimizationhamming-distance

4

我希望找到两个等长字符串中有多少不同的字符。我发现异或算法被认为是最快的，但它们返回以位为单位表示的距离。我希望结果以字符表示。假设 "pet" 和 "pit" 的距离为 1，但 'e' 和 'i' 可能有两个不同的位，因此异或返回 2。

我写的函数是：

// na = length of both strings
unsigned int HammingDistance(const char* a, unsigned int na, const char* b) {

    unsigned int num_mismatches = 0;
    while (na) {
        if (*a != *b)
            ++num_mismatches;

        --na;
        ++a;
        ++b;
    }

    return num_mismatches;
}

能不能让它变得更快一些呢？也许可以使用一些底层命令或实现不同的算法？

系统信息：Intel Xeon X5650上的Gcc 4.7.2

谢谢。

- pdrak

4

你的表现有没有问题，需要优化吗？ - Andrey

对于单个字符进行异或可能有效，因为您想检测两个字符之间是否存在差异，您可以将它们异或并检查结果是否不等于0。但是，如果可以设计出更短的无分支指令序列，则可能不是最优的 - 查找无分支条件或无分支代码。 - didierc

1

@Andrey 2 这是一个非常密集的过程中至关重要的一部分。它在我的一个程序中运行了50亿次。 - pdrak

4个回答

1

代替

if (*a != *b)
    ++num_mismatches;

这种方法在某些架构上（使用8位字节）会更快，因为它避免了分支:

int bits = *a ^ *b;
bits |= bits >> 4;
bits |= bits >> 2;
bits |= bits >> 1;
num_mismatches += bits & 1;

- Jim Balter

我刚刚在英特尔 Xeon 上尝试了一下，运行速度比原来慢。不过还是谢谢你的帮助。 - pdrak

1

在 x86 系统上，“num_mismatches += *a != *b” 这个操作可以被编译成不包含分支的代码，例如“test %areg,%breg; setnz %al; movzbl %al,%eax; add %eax,%mismatches_reg;”。 - fuz

1

如何展开循环：

while (na >= 8){
  num_mismatches += (a[0] != b[0]);
  num_mismatches += (a[1] != b[1]);
  num_mismatches += (a[2] != b[2]);
  num_mismatches += (a[3] != b[3]);
  num_mismatches += (a[4] != b[4]);
  num_mismatches += (a[5] != b[5]);
  num_mismatches += (a[6] != b[6]);
  num_mismatches += (a[7] != b[7]);
  a += 8; b += 8; na -= 8;
}
if (na >= 4){
  num_mismatches += (a[0] != b[0]);
  num_mismatches += (a[1] != b[1]);
  num_mismatches += (a[2] != b[2]);
  num_mismatches += (a[3] != b[3]);
  a += 4; b += 4; na -= 4;
}
if (na >= 2){
  num_mismatches += (a[0] != b[0]);
  num_mismatches += (a[1] != b[1]);
  a += 2; b += 2; na -= 2;
}
if (na >= 1){
  num_mismatches += (a[0] != b[0]);
  a += 1; b += 1; na -= 1;
}

此外，如果您知道有长段相等的字符，您可以将指针转换为long*并每次比较4个字符，仅当不相等时才查看单个字符。

此代码基于memset和memcpy快速执行。它将字符串复制到long数组中，以消除对齐问题并将字符串填充为整数long数目。在比较每对long时，如果它们不相等，则将指针转换为char*并计算不相等的字符数。主循环也可以展开，类似于上面的方法。

long la[BIG_ENOUGH];
long lb[BIG_ENOUGH];
memset(la, 0, sizeof(la));
memset(lb, 0, sizeof(lb));
memcpy(la, a, na);
memcpy(lb, b, nb);
int nla = (na + 3) & ~3; // assuming sizeof(long) = 4
long *pa = la, *pb = lb;
while(nla >= 1){
  if (pa[0] != pb[0]){
    num_mismatches += (((char*)pa[0])[0] != ((char*)pb[0])[0])
                    + (((char*)pa[0])[1] != ((char*)pb[0])[1])
                    + (((char*)pa[0])[2] != ((char*)pb[0])[2])
                    + (((char*)pa[0])[3] != ((char*)pb[0])[3])
                    ;
  }
  pa += 1;pb += 1; nla -= 1;
}

- Mike Dunlavey

我刚试了一下你的循环展开。在Intel Xeon上比原来的慢。我在实现你的第二个解决方案时遇到了麻烦。无论如何，感谢你的帮助。 - pdrak

@Petros：嗯...第一个展开的解决方案不应该比基本的字符循环慢，除非na通常相当短。 - Mike Dunlavey

2

较新的英特尔处理器并不总是喜欢展开循环。由于循环无法适应循环缓冲区，因此循环开销通常比指令重新解码时间小。 - harold

@harold：也许就是这样。我猜这真的取决于处理器。 - Mike Dunlavey

@Petros：我忘了问：这些字符串有多经常不同？如果它们几乎总是相等的，那么一个简单的memcmp(a, b, na)==0将很难被超越，只有当它们不相等时才调用您的函数。 - Mike Dunlavey

显示剩余3条评论

1

您可以通过对本机整数大小进行按位运算来使比较一次比较更多字节。

在您的代码中，您正在逐个比较字节的相等性，但是您的CPU可以在单个周期内比较至少一个字和8个字节（如果是x86-64）。当然，确切的性能能力取决于CPU架构。

但是，如果您使用大小为8的步幅推进两个指针，它可能在某些情况下更快。当必须从主存中读取字符串时，内存加载时间实际上将支配性能。但是，如果字符串在CPU高速缓存中，则可以进行异或运算，并通过测试64位值中位更改的位置来解释结果。

计算不为0的桶可以使用从0x33333333而不是0x55555555开始的SWAR算法的变体来完成。

该算法将更难处理，因为它需要使用具有适当内存对齐的uint64_t指针。您需要一个序言和后记来覆盖剩余的字节。也许您应该阅读编译器输出的汇编代码，看看它是否在尝试更复杂的代码之前做了更聪明的事情。

- vipw

我考虑了一下。虽然它在最好的情况下（字符串相等）有更好的情况，但平均值不会显著降低。特别是考虑到这种实现将会更加复杂（尤其是对齐）。 - Andrey

@Andrey 是的，我不能说我会建议尝试它。 - vipw

我因为复杂性和涉及的字符串相对较小的大小而没有尝试这个。不管怎样，还是谢谢你。 - pdrak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

如果字符串始终用零填充为32个字节，它们的地址是16对齐的，你可以像这样做：（代码未经测试或剖析）

movdqa xmm0, [a]
movdqa xmm1, [a + 16]
pcmpeqb xmm0, [b]
pcmpeqb xmm1, [b + 16]
pxor xmm2, xmm2
psadbw xmm0, xmm2
psadbw xmm1, xmm2
pextrw ax, xmm0, 0
pextrw dx, xmm1, 0
add ax, dx
movsx eax, ax
neg eax

但如果字符串通常很小，则会做很多不必要的工作，并且可能不会更快。如果字符串通常（几乎）为32个字节，则应该更快。

编辑：在看到您的更新评论之前，我就写了这个答案 - 如果字符串通常很小，则可能不是很好。16字节版本可能有用（也许）（有条件地运行第二次迭代，这个分支应该可以很好地预测，因为它很少被使用）。但对于如此短的字符串，正常代码很难被超越。

movdqa xmm0, [a]
pxor xmm1, xmm1
pcmpeqb xmm0, [b]
psadbw xmm0, xmm1
pextrw ax, xmm0, 0
movsx eax, ax
neg eax