是否可以检查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;
}

如果3个第一个int中的任何一个等于3个最后一个int中的任何一个,则此函数接收6个int并返回true.是否有任何类似的方式使其更快？

Answer 1

假设您期望获得高比率的false结果,您可以快速"预先检查"以快速隔离此类情况:

如果在一个位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次 17次,但如果实际结果会更加昂贵true).如果mask == 0那时当然这没有帮助.

如果高概率a & b & c设置了一些位,则可以进一步改进:

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都没有设置任何位,那么我们的速度非常快.

Answer 2

扩展 dawg 的 SSE 比较方法，您可以使用向量 OR 组合比较结果，并将比较结果的掩码移回整数以测试 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对 shuffles 提出了很好的注释。只有 19 条指令ret，包括来自单独依赖链的相当数量的并行性。使用-msse4.1、 或-mavx，它可以节省另外几条指令。（但可能不会跑得更快）

有了 clang，dawg 的版本大约是原来的两倍大小。使用 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;
}

尝试如何将调用者的数据获取到向量寄存器中。如果三人一组来自记忆，那么概率。最好传递指针，以便矢量加载可以将它们从原始位置获取。在通往向量的过程中通过整数寄存器很糟糕（更高的延迟，更多的微指令），但是如果你的数据已经存在于寄存器中，那么进行整数存储然后向量加载是一种损失。gcc 很愚蠢，并且遵循 AMD 优化指南的建议来通过内存进行反弹，尽管 Agner Fog 表示他发现即使在 AMD CPU 上这也不值得。对于英特尔来说，这肯定更糟糕，而对于 AMD 来说，这显然是一次洗礼，或者可能更糟糕，所以这绝对是错误的选择-mtune=generic。反正...

还可以仅用两次打包向量比较来完成 9 次比较中的 8 次。

第 9 个可以通过整数比较来完成，并将其真值与向量结果进行或运算。在某些 CPU（尤其是 AMD，也许还有 Intel Haswell 及更高版本）上，根本不将 6 个整数之一传输到向量寄存器可能是一种胜利。将三个整数无分支比较与向量洗牌/比较混合可以很好地交错它们。

shufps这些向量比较可以通过使用整数数据来设置（因为它可以组合来自两个源寄存器的数据）。这在大多数 CPU 上都很好，但在使用内在函数而不是实际的汇编时需要大量烦人的转换。即使存在旁路延迟，与 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 链。