c-在4元素短数组中找到16位匹配的最快方法

Question

我可以使用纳米台进行确认。今天我觉得自己不聪明，想不出一个简单的方法

我有一个数组，short arr[]={0x1234, 0x5432, 0x9090, 0xFEED};。我知道我可以使用SIMD一次比较所有元素，使用movemask+tzcnt来找到匹配的索引。然而，由于它只有64位，我想知道是否有更快的方法？

首先，我想也许我可以通过写target|(target<<16)|(target<<32)|(target<<48)来构建一个64位int，但后来我意识到AND和SUB与比较不同，因为低16可以影响高16。然后我想我可以写index=tzcnt((target==arr[0]?1:0)... | target==arr[3]?8:0，而不是简单的循环

有人能想出更聪明的办法吗？我怀疑使用三元方法会给我最好的结果，因为它是无分支的？

Answer 1

对于SWAR compare For equality，您想要的运算是XOR，它与SUB一样，在相等的输入上产生全零，但与SUB不同，它不会横向传播进位。

但是，您需要检测一个连续的16个0位。与pcmpeqw不同，其他元素中会有一些零位。

所以它可能与https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord，但具有更宽的掩码模式，可以在16位而不是8位块上操作。

还有一种更快的方法——使用hasless(v，1)，定义如下；它在4个操作中工作，不需要后续验证。它简化为

#define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)

每当v中的相应字节为零或大于0x80时，子表达式(v - 0x01010101UL)计算为任何字节中设置的高位。子表达式~v & 0x80808080UL计算为以字节为单位设置的高位，其中v的字节没有设置其高位(因此字节小于0x80)。最后，通过对这两个子表达式进行"与"运算，结果是其中v中的字节为零的高位集，因为在第一个子表达式中由于大于0x80的值而设置的高位被第二子表达式屏蔽。

这个bithack最初是由Alan Mycroft在1987年发起的。

所以它可能看起来像这样(未经测试)：

#include <stdint.h>
#include <string.h>
// returns 0 / non-zero status.
uint64_t hasmatch_16in64(uint16_t needle, const uint16_t haystack[4])
{
uint64_t vneedle = 0x0001000100010001ULL * needle;  // broadcast
uint64_t vbuf;
memcpy(&vbuf, haystack, sizeof(vbuf));  // aliasing-safe unaligned load
//static_assert(sizeof(vbuf) == 4*sizeof(haystack[0]));
uint64_t match = vbuf ^ vneedle;
uint64_t any_zeros = (match - 0x0001000100010001ULL) & ~match & 0x8000800080008000ULL;
return any_zeros;
// unsigned matchpos = _tzcnt_u32(any_zeros) >> 4;  // I think.
}

Godbolt带有GCC和clang，还包括SIMD内部版本。

# gcc12.2 -O3 -march=x86-64-v3 -mtune=znver1
# x86-64-v3 is the Haswell/Zen1 baseline: AVX2+FMA+BMI2, but with tune=generic
# without tune=haswell or whatever, GCC uses shl/add /shl/add instead of imul, despite still needing the same constant
hasmatch_16in64:
movabs  rax, 281479271743489       #    0x1000100010001
movzx   edi, di                    # zero-extend to 64-bit
imul    rdi, rax                   # vneedle
xor     rdi, QWORD PTR [rsi]       # match
# then the bithack
mov     rdx, rdi
sub     rdx, rax
andn    rax, rdi, rdx              # BMI1
movabs  rdx, -9223231297218904064  # 0x8000800080008000
and     rax, rdx
ret

不幸的是，Clang添加了0xFFFEFFFEFFFEFFFF，而不是重用乘数常数，因此它有三个64位立即数常数。

AArch64可以将这样的重复模式常数作为逐位操作的即时操作，并且没有那么方便的SIMDmovemask，因此这可能更为成功，尤其是如果您可以保证短裤阵列的对齐。

---

匹配位置

如果您需要知道匹配的位置，我认为bithack在每个零字节或u16的高位都有一个1，而不是其他位置。(最低的先验/最后运算是涉及0x80008000...的逐位AND)。

所以也许tzcnt(any_zeros) >> 4从位索引到u16索引，向下取整。例如，如果第二个为零，则tzcnt结果将为31。CCD_ 15＝1。

---

如果这不起作用，那么是的，AVX2或AVX-512vpbroadcastw xmm0, edi/vmovq/vpcmeqw/vpmovmskb/tzcnt也会很好地工作，代码大小更小，uop更少，但延迟可能更高。或者更少(要获得字节偏移量，如果需要哪个short的索引，请右移。)

实际上，只有SSE2pshuflw可以向XMM寄存器的低qword广播一个字。MMX也是如此，它实际上允许内存源pcmpeqw mm0, [rsi]，因为它没有对齐要求，并且只有64位，而不是128位。

如果你能使用SIMD内部函数，特别是如果你有来自AVX2的高效单词广播，一定要看看它

#include <immintrin.h>
// note the unsigned function arg, not uint16_t;
// we only use the low 16, but GCC doesn't realize that and wastes an instruction in the non-AVX2 version
int hasmatch_SIMD(unsigned needle, const uint16_t haystack[4])
{
#ifdef __AVX2__   // or higher
__m128i vneedle = _mm_set1_epi16(needle);
#else
__m128i vneedle =  _mm_cvtsi32_si128(needle);  // movd
vneedle = _mm_shufflelo_epi16(vneedle, 0);     // broadcast to low half
#endif
__m128i vbuf = _mm_loadl_epi64((void*)haystack);    // alignment and aliasing safe
unsigned mask = _mm_movemask_epi8(_mm_cmpeq_epi16(vneedle, vbuf));
//return _tzcnt_u32(mask) >> 1;
return mask;
}

# clang expects narrow integer args to already be zero- or sign-extended to 32
hasmatch_SIMD:
movd    xmm0, edi
pshuflw xmm0, xmm0, 0                   # xmm0 = xmm0[0,0,0,0,4,5,6,7]
movq    xmm1, qword ptr [rsi]           # xmm1 = mem[0],zero
pcmpeqw xmm1, xmm0
pmovmskb        eax, xmm1
ret

AXV-512为我们提供了vpbroadcastw xmm0, edi，取代了vmovd+vpbroadcastw xmm,xmm或movd + pshuflw，节省了一个shuffle uop。

对于AVX2，这是5条单uop指令，而SWAR比特破解是7条(或9条计算常数)。或者6或8不计算"0"的零扩展；针"；。因此SIMD更适合前端吞吐量。(https://agner.org/optimize//https://uops.info/)

这些指令中的一些可以在哪些端口上运行是有限制的(而bithack指令大多是任何整数ALU端口)，但据推测，您并不是在许多这样的4元素数组上循环执行这一操作。否则SIMD就是一个明显的胜利；同时检查CCD_ 28的低半部和高半部中的两个4元素阵列。因此，我们可能确实需要考虑设置这些常量的前端成本。

我没有把迟到的时间加起来；即使在通常在整数和SIMD单元之间具有良好延迟的英特尔CPU上，它也可能更高。

不幸的是，如果在没有AVX2的情况下编译，GCC未能从SIMD版本中优化movzx edi, di；只有clang实现了CCD_ 30的上16被后面的shuffle丢弃。也许最好将函数arg设为unsigned，而不是显式地设置为窄的16位类型。

Answer 2

Clang with-O2或-O3以及GCC with-O3将一个简单的搜索循环编译为无分支指令：

int indexOf(short target, short* arr) {
int index = -1;
for (int i = 0; i < 4; ++i) {
if (target == arr[i]) {
index = i;
}
}
return index;
}

演示

我怀疑没有SIMD你能做得更好。换句话说，编写简单易懂的代码来帮助编译器生成高效的代码。

附带说明：出于某种原因，Clang和GCC都没有在这个非常相似的代码上使用条件移动：

int indexOf(short target, short* arr) {
for (int i = 0; i < 4; ++i) {
if (target == arr[i]) {
return i;
}
}
return -1;
}