是否可以检查2组3个整数中的任何一个是否等于少于9个比较？

Question

int eq3(int a, int b, int c, int d, int e, int f){
    return a == d || a == e || a == f 
        || b == d || b == e || b == f 
        || c == d || c == e || c == f;
}

此函数接收6个整数，如果前3个整数中的任何一个等于后3个整数中的任何一个，则返回true。有没有类似的比特黑客方法可以让它更快？

Answer 1

如果您想要按位版本，请查看异或。如果您异或两个相同的数字，答案将为0。否则，如果一个设置而另一个未设置，位将翻转。例如1000 xor 0100是1100。

您拥有的代码可能会导致至少1次管道刷新，但除此之外，它在性能方面还可以。

Answer 2

扩展dawg的SSE比较方法，可以使用向量或组合比较结果，并将比较结果的掩码移回整数，以测试0/非零。

此外，您可以更高效地将数据转换为向量（尽管当许多单独的整数位于寄存器中时，将其转换为向量仍然相当麻烦，而不是存储在内存中）。

你应该避免因为做三个小商店和一个大负载而导致的商店转发暂停。

///// UNTESTED ////////
#include <immintrin.h>
int eq3(int a, int b, int c, int d, int e, int f){

    // Use _mm_set to let the compiler worry about getting integers into vectors
    // Use -mtune=intel or gcc will make bad code, though :(
    __m128i abcc = _mm_set_epi32(0,c,b,a);  // args go from high to low position in the vector
    // masking off the high bits of the result-mask to avoid false positives
    // is cheaper than repeating c (to do the same compare twice)

    __m128i dddd = _mm_set1_epi32(d);
    __m128i eeee = _mm_set1_epi32(e);

    dddd = _mm_cmpeq_epi32(dddd, abcc);
    eeee = _mm_cmpeq_epi32(eeee, abcc);  // per element: 0(unequal) or -1(equal)
    __m128i combined = _mm_or_si128(dddd, eeee);

    __m128i ffff = _mm_set1_epi32(f);
    ffff = _mm_cmpeq_epi32(ffff, abcc);
    combined = _mm_or_si128(combined, ffff);

    // results of all the compares are ORed together.  All zero only if there were no hits
    unsigned equal_mask = _mm_movemask_epi8(combined);
    equal_mask &= 0x0fff;  // the high 32b element could have false positives
    return equal_mask;
    // return !!equal_mask if you want to force it to 0 or 1
    // the mask tells you whether it was a, b, or c that had a hit

    // movmskps would return a mask of just 4 bits, one for each 32b element, but might have a bypass delay on Nehalem.
    // actually, pmovmskb apparently runs in the float domain on Nehalem anyway, according to Agner Fog's table >.<
}

这编译成了非常好的asm，在clang和gcc之间非常相似，但是clang的fverbose asm在洗牌上有很好的注释。只有19条指令包括ret，从独立的依赖链中获得了相当多的并行性。使用msse4.1或mavx，它可以保存另一对指令。（但可能不会跑得更快）

随着叮当声，道格的版本大约是两倍的大小。使用gcc时，会发生一些糟糕的事情，这很可怕（超过80条指令。看起来像是gcc优化错误，因为它看起来比直接翻译源代码更糟糕）。即使是clang的版本也花费了很长时间将数据输入/输出向量正则表达式，因此只需无分支地进行比较和/或将真值结合在一起可能会更快。

这将编译成合适的代码：

// 8bit variable doesn't help gcc avoid partial-register stalls even with -mtune=core2 :/
int eq3_scalar(int a, int b, int c, int d, int e, int f){
    char retval = (a == d) | (a == e) | (a == f)
         | (b == d) | (b == e) | (b == f)
         | (c == d) | (c == e) | (c == f);
    return retval;
}

玩一下如何将来自调用者的数据转换为向量regs。如果三个组来自内存，那么可能。传递指针，以便向量加载可以从它们的原始位置获取它们是最好的。在通往向量的路上通过整数寄存器很糟糕（更高的延迟，更多的uops），但是如果您的数据已经存在于regs中，那么进行整数存储然后进行向量加载是一种损失。gcc很蠢，并且遵循AMD优化指南的建议在内存中反弹，尽管Agner Fog说他发现即使在AMD CPU上也不值得。英特尔的情况肯定更糟，AMD的情况显然更糟，所以这绝对是-mtune=通用的错误选择。无论如何...

第9个可以使用整数比较完成，并将其真值与向量结果进行ORed。在某些CPU（特别是AMD，可能还有Intel Haswell和更高版本）上，根本不将6个整数中的一个转移到向量regs可能是一种胜利。将三个整数无分支比较与向量随机/比较混合在一起会很好地交织它们。

这些向量比较可以通过对整数数据使用SHUFP来设置（因为它可以组合来自两个源寄存器的数据）。这在大多数CPU上都很好，但当使用内部函数而不是实际的asm时，需要很多恼人的转换。即使存在旁路延迟，与punpckldq和pshufd相比，这也是一个不错的权衡。

aabb    ccab
====    ====
dede    deff

c==f

使用asm，例如：

#### untested
# pretend a is in eax, and so on
movd     xmm0, eax
movd     xmm1, ebx
movd     xmm2, ecx

shl      rdx, 32
#mov     edi, edi     # zero the upper 32 of rdi if needed, or use shld instead of OR if you don't care about AMD CPUs
or       rdx, rdi     # de in an integer register.
movq     xmm3, rdx    # de, aka (d<<32)|e
# in 32bit code, use a vector shuffle of some sort to do this in a vector reg, or:
#pinsrd  xmm3, edi, 1  # SSE4.1, and 2 uops (same as movd+shuffle)
#movd    xmm4, edi    # e

movd     xmm5, esi    # f

shufps   xmm0, xmm1, 0            #  xmm0=aabb  (low dword = a; my notation is backwards from left/right vector-shift perspective)
shufps   xmm5, xmm3, 0b01000000   # xmm5 = ffde  
punpcklqdq xmm3, xmm3            # broadcast: xmm3=dede
pcmpeqd  xmm3, xmm0              # xmm3: aabb == dede

# spread these instructions out between vector instructions, if you aren't branching
xor      edx,edx
cmp      esi, ecx     # c == f
#je   .found_match    # if there's one of the 9 that's true more often, make it this one.  Branch mispredicts suck, though
sete     dl

shufps   xmm0, xmm2, 0b00001000  # xmm0 = abcc
pcmpeqd  xmm0, xmm5              # abcc == ffde

por      xmm0, xmm3
pmovmskb eax, xmm0    # will have bits set if cmpeq found any equal elements
or       eax, edx     # combine vector and scalar compares
jnz  .found_match
# or record the result instead of branching on it
setnz    dl

这也是19条指令（不包括最终的jcc/setcc），但其中一条是异零习惯用法，还有其他简单的整数指令。（较短的编码，有些可以在Haswell上的port6上运行，无法处理向量指令）。由于构建abcc的洗牌链，可能会有更长的dep链。

Answer 3

假设您预期的结果为高比率的假结果，您可以快速进行“预检查”以快速隔离此类病例：

如果在a中设置了未在d、e和f中设置的位，则a不能等于其中任何一个。

因此像这样的东西

int pre_eq3(int a, int b, int c, int d, int e, int f){
    int const mask = ~(d | e | f);
    if ((a & mask) && (b & mask) && (c & mask)) {
         return false;
    }
    return eq3(a, b, c, d, e, f);
}

可以加速它（8个操作，而不是9个操作，但如果结果实际上是真的，则成本要高得多）。如果掩码==0，那么这当然没有帮助。

如果高概率<代码>a，这可以进一步改善

int pre_eq3(int a, int b, int c, int d, int e, int f){
    int const mask = ~(d | e | f);
    if ((a & b & c) & mask) {
        return false;
    }
    if ((a & mask) && (b & mask) && (c & mask)) {
         return false;
    }
    return eq3(a, b, c, d, e, f);
}

现在，如果a，b和c都设置了位，而d，e和c都没有设置任何位，那么我们很快就会退出。