比较两对 4 个变量并返回匹配数？
Comparing two pairs of 4 variables and returning the number of matches?
给定以下结构：
struct four_points {
uint32_t a, b, c, d;
}
比较两个这样的结构和return匹配（在任何位置）的变量数量的绝对最快的方法是什么？
例如：
four_points s1 = {0, 1, 2, 3};
four_points s2 = {1, 2, 3, 4};
我会寻找结果 3，因为三个数字在两个结构之间匹配。但是，鉴于以下情况：
four_points s1 = {1, 0, 2, 0};
four_points s2 = {0, 1, 9, 7};
然后我希望结果只有 2，因为两个结构之间只有两个变量匹配（尽管第一个有两个零）。
我已经找到了一些用于执行比较的基本系统，但这是将在短时间内被调用几百万次的东西，需要相对较快。我目前最好的尝试是使用排序网络对任一输入的所有四个值进行排序，然后循环排序后的值并保留相等值的计数，相应地推进任一输入的当前索引。
是否有任何一种技术可以比排序和迭代执行得更好？
在现代 CPU 年代，有时正确应用蛮力是可行的方法。诀窍是编写不受指令延迟限制的代码，只受吞吐量限制。
重复是否常见？如果它们非常罕见，或者有一个模式，使用分支来处理它们可以使常见情况更快。如果他们真的是不可预测的table，最好做一些无分支的事情。我正在考虑使用分支来检查罕见位置之间的重复项，并在更常见的位置使用无分支。
基准测试很棘手，因为带有分支的版本在使用相同数据进行一百万次测试时会大放异彩，但在实际使用中会有很多分支预测错误。
我还没有对任何东西进行基准测试，但我想出了一个版本，通过使用 OR 而不是加法 来组合找到的匹配项来跳过重复项。它编译成 gcc 完全展开的漂亮的 x86 asm。 （没有条件分支，甚至没有循环）。
Here it is on godbolt。 （g++ 是愚蠢的，在 x86 setcc 的输出上使用 32 位操作，它只设置低 8 位。这种部分寄存器访问会产生减速。而且我什至不确定它是否会将高 24 位归零所有...无论如何，gcc 4.9.2 的代码看起来不错，godbolt 上的 clang 也不错）
// 8-bit types used because x86's setcc instruction only sets the low 8 of a register
// leaving the other bits unmodified.
// Doing a 32bit add from that creates a partial register slowdown on Intel P6 and Sandybridge CPU families
// Also, compilers like to insert movzx (zero-extend) instructions
// because I guess they don't realize the previous high bits are all zero.
// (Or they're tuning for pre-sandybridge Intel, where the stall is worse than SnB inserting the extra uop itself).
// The return type is 8bit because otherwise clang decides it should generate
// things as 32bit in the first place, and does zero-extension -> 32bit adds.
int8_t match4_ordups(const four_points *s1struct, const four_points *s2struct)
{
const int32_t *s1 = &s1struct->a; // TODO: check if this breaks aliasing rules
const int32_t *s2 = &s2struct->a;
// ignore duplicates by combining with OR instead of addition
int8_t matches = 0;
for (int j=0 ; j<4 ; j++) {
matches |= (s1[0] == s2[j]);
}
for (int i=1; i<4; i++) { // i=0 iteration is broken out above
uint32_t s1i = s1[i];
int8_t notdup = 1; // is s1[i] a duplicate of s1[0.. i-1]?
for (int j=0 ; j<i ; j++) {
notdup &= (uint8_t) (s1i != s1[j]); // like dup |= (s1i == s1[j]); but saves a NOT
}
int8_t mi = // match this iteration?
(s1i == s2[0]) |
(s1i == s2[1]) |
(s1i == s2[2]) |
(s1i == s2[3]);
// gcc and clang insist on doing 3 dependent OR insns regardless of parens, not that it matters
matches += mi & notdup;
}
return matches;
}
// see the godbolt link for a main() simple test harness.
在具有 128b 向量且可以处理 4 个打包的 32 位整数的机器上（例如 x86 和 SSE2），您可以将 s1 的每个元素广播到它自己的向量，去重，然后执行 4 个打包-比较。 icc 做了类似这样的事情来自动向量化我的 match4_ordups 函数（在 godbolt 上查看。）
使用movemask将比较结果存储回整数寄存器，以获得比较相等的元素的位图。 Popcount 那些位图，并添加结果。
这让我想到了一个更好的主意：只用 3 次元素轮换洗牌就完成了所有比较：
{ 1d 1c 1b 1a }
== == == == packed-compare with
{ 2d 2c 2b 2a }
{ 1a 1d 1c 1b }
== == == == packed-compare with
{ 2d 2c 2b 2a }
{ 1b 1a 1d 1c } # if dups didn't matter: do this shuffle on s2
== == == == packed-compare with
{ 2d 2c 2b 2a }
{ 1c 1b 1a 1d } # if dups didn't matter: this result from { 1a ... }
== == == == packed-compare with
{ 2d 2c 2b 2a } { 2b ...
这只是 3 次随机播放，并且仍然进行了所有 16 次比较。诀窍是将它们与我们需要合并重复项的 OR 结合起来，然后能够有效地计算它们。打包比较根据该位置的两个元素之间的比较输出一个向量，每个元素 = 零或 -1（所有位设置）。它旨在为 AND 或 XOR 提供有用的操作数，以屏蔽某些向量元素，例如使 v1 += v2 & 掩码在每个元素的基础上成为条件。它也只是一个布尔真值。
通过将一个向量旋转 2，将另一个向量旋转 1，然后比较四个移位和未移位的向量，可以进行全部 16 次比较，仅进行 2 次混洗。如果我们不需要消除重复项，那就太好了，但既然我们这样做了，那么结果在哪里就很重要了。我们不只是将所有 16 个比较结果相加。
或将打包比较结果合并为一个向量。将根据 s2 的该元素是否在 s1 中有任何匹配来设置每个元素。 int _mm_movemask_ps (__m128 a) 将矢量转换为位图，然后对位图进行 popcount。 （Nehalem or newer CPU required for popcnt，否则退回到具有 4 位查找的版本 table。）
垂直 OR 处理 s1 中的重复项，但 s2 中的重复项是一个不太明显的扩展，需要更多的工作。我最终确实想到了一种不到两倍慢的方法（见下文）。
#include <stdint.h>
#include <immintrin.h>
typedef struct four_points {
int32_t a, b, c, d;
} four_points;
//typedef uint32_t four_points[4];
// small enough to inline, only 62B of x86 instructions (gcc 4.9.2)
static inline int match4_sse_noS2dup(const four_points *s1pointer, const four_points *s2pointer)
{
__m128i s1 = _mm_loadu_si128((__m128i*)s1pointer);
__m128i s2 = _mm_loadu_si128((__m128i*)s2pointer);
__m128i s1b= _mm_shuffle_epi32(s1, _MM_SHUFFLE(0, 3, 2, 1));
// no shuffle needed for first compare
__m128i match = _mm_cmpeq_epi32(s1 , s2); //{s1.d==s2.d?-1:0, 1c==2c, 1b==2b, 1a==2a }
__m128i s1c= _mm_shuffle_epi32(s1, _MM_SHUFFLE(1, 0, 3, 2));
s1b = _mm_cmpeq_epi32(s1b, s2);
match = _mm_or_si128(match, s1b); // merge dups by ORing instead of adding
// note that we shuffle the original vector every time
// multiple short dependency chains are better than one long one.
__m128i s1d= _mm_shuffle_epi32(s1, _MM_SHUFFLE(2, 1, 0, 3));
s1c = _mm_cmpeq_epi32(s1c, s2);
match = _mm_or_si128(match, s1c);
s1d = _mm_cmpeq_epi32(s1d, s2);
match = _mm_or_si128(match, s1d); // match = { s2.a in s1?, s2.b in s1?, etc. }
// turn the the high bit of each 32bit element into a bitmap of s2 elements that have matches anywhere in s1
// use float movemask because integer movemask does 8bit elements.
int matchmask = _mm_movemask_ps (_mm_castsi128_ps(match));
return _mm_popcnt_u32(matchmask); // or use a 4b lookup table for CPUs with SSE2 but not popcnt
}
查看删除 s2 中重复项的版本，以更易读的顺序排列相同的代码。我尝试安排指令，以防 CPU 只是在执行之前勉强解码指令，但 gcc 将指令置于相同的顺序，而不管你将内在函数放入的顺序如何。
这非常快，如果 128b 负载中没有存储转发停顿。如果您只是编写了具有四个 32 位存储的结构，运行 在接下来的几个时钟周期内启用此函数将在它尝试使用 128b 负载加载整个结构时产生停顿。参见 Agner Fog's site。如果调用代码在寄存器中已经有 8 个值中的许多值，那么标量版本可能是一个胜利，即使对于只从内存中读取结构的微基准测试来说它会更慢。
由于重复处理尚未完成，因此我懒得进行循环计数。 IACA 表示 Haswell 可以 运行 它具有每 4.05 个时钟周期一次迭代的吞吐量和 17 个周期的延迟（不确定这是否包括加载的内存延迟。有很多指令级并行可用，并且除了 movmsk(2) 和 popcnt(3))，所有指令都有单周期延迟。没有 AVX 会稍微慢一些，因为 gcc 选择了一个更差的指令顺序，并且仍然浪费 movdqa 指令复制向量寄存器。
使用 AVX2，这可以在 256b 向量中并行执行两个 match4 操作。 AVX2 通常用作两个 128b 通道，而不是完整的 256b 向量。将您的代码设置为能够并行利用 2 或 4 个 (AVX-512) match4 操作，当您可以针对这些 CPU 进行编译时，您将获得收益。 s1 或 s2s 都不必连续存储，因此单个 32B 负载可以获得两个结构。 AVX2 可以相当快地将 128b 加载到寄存器的上通道。
处理 s2
中的重复项
也许将 s2 与 shifted 而不是自身的旋转版本进行比较。
#### comparing S2 with itself to mask off duplicates
{ 0 2d 2c 2b }
{ 2d 2c 2b 2a } == == ==
{ 0 0 2d 2c }
{ 2d 2c 2b 2a } == ==
{ 0 0 0 2d }
{ 2d 2c 2b 2a } ==
嗯，如果零可以作为常规元素出现，我们可能还需要在比较之后进行字节移位，以将潜在的误报变成零。 如果在s1中有一个标记值不能出现，你可以移入它的元素，而不是0。（SSE有PALIGNR，它给你任何连续的 16B window 你想要附加的两个寄存器的内容。命名为从两个对齐负载模拟未对齐负载的用例。所以你有一个该元素的常数向量。）
更新：我想到了一个很好的技巧，可以避免使用标识元素。实际上，我们只需进行两次向量比较就可以获得所有 6 次必要的 s2 与 s2 比较，然后合并结果。
在两个向量的相同位置进行相同的比较可以让您对两个结果进行“或”运算，而无需在“或”运算之前进行屏蔽。 （解决缺少标记值的问题）。
洗牌比较的输出，而不是 S2 的额外洗牌和比较。这意味着我们可以在其他比较之后完成 d==a。
请注意，我们并不局限于随机排列整个元素。按字节顺序混洗以将来自不同比较结果的字节放入单个向量元素中，并将 that 与零进行比较。 （这比我希望的要少，见下文）。
检查重复项会大大降低速度（尤其是吞吐量，而不是延迟）。所以你仍然最好在 s2 中安排一个标记值，它永远不会匹配任何 s1 元素，你说这是可能的。我只提出这个，因为我认为它很有趣。 （并为您提供一个选项，以防您有时需要不需要哨兵的版本。）
static inline
int match4_sse(const four_points *s1pointer, const four_points *s2pointer)
{
// IACA_START
__m128i s1 = _mm_loadu_si128((__m128i*)s1pointer);
__m128i s2 = _mm_loadu_si128((__m128i*)s2pointer);
// s1a = unshuffled = s1.a in the low element
__m128i s1b= _mm_shuffle_epi32(s1, _MM_SHUFFLE(0, 3, 2, 1));
__m128i s1c= _mm_shuffle_epi32(s1, _MM_SHUFFLE(1, 0, 3, 2));
__m128i s1d= _mm_shuffle_epi32(s1, _MM_SHUFFLE(2, 1, 0, 3));
__m128i match = _mm_cmpeq_epi32(s1 , s2); //{s1.d==s2.d?-1:0, 1c==2c, 1b==2b, 1a==2a }
s1b = _mm_cmpeq_epi32(s1b, s2);
match = _mm_or_si128(match, s1b); // merge dups by ORing instead of adding
s1c = _mm_cmpeq_epi32(s1c, s2);
match = _mm_or_si128(match, s1c);
s1d = _mm_cmpeq_epi32(s1d, s2);
match = _mm_or_si128(match, s1d);
// match = { s2.a in s1?, s2.b in s1?, etc. }
// s1 vs s2 all done, now prepare a mask for it based on s2 dups
/*
* d==b c==a b==a d==a #s2b
* d==c c==b b==a d==a #s2c
* OR together -> s2bc
* d==abc c==ba b==a 0 pshufb(s2bc) (packed as zero or non-zero bytes within the each element)
* !(d==abc) !(c==ba) !(b==a) !0 pcmpeq setzero -> AND mask for s1_vs_s2 match
*/
__m128i s2b = _mm_shuffle_epi32(s2, _MM_SHUFFLE(1, 0, 0, 3));
__m128i s2c = _mm_shuffle_epi32(s2, _MM_SHUFFLE(2, 1, 0, 3));
s2b = _mm_cmpeq_epi32(s2b, s2);
s2c = _mm_cmpeq_epi32(s2c, s2);
__m128i s2bc= _mm_or_si128(s2b, s2c);
s2bc = _mm_shuffle_epi8(s2bc, _mm_set_epi8(-1,-1,0,12, -1,-1,-1,8, -1,-1,-1,4, -1,-1,-1,-1));
__m128i dupmask = _mm_cmpeq_epi32(s2bc, _mm_setzero_si128());
// see below for alternate insn sequences that can go here.
match = _mm_and_si128(match, dupmask);
// turn the the high bit of each 32bit element into a bitmap of s2 matches
// use float movemask because integer movemask does 8bit elements.
int matchmask = _mm_movemask_ps (_mm_castsi128_ps(match));
int ret = _mm_popcnt_u32(matchmask); // or use a 4b lookup table for CPUs with SSE2 but not popcnt
// IACA_END
return ret;
}
pshufb 这需要 SSSE3。它和一个 pcmpeq（和一个 pxor 来生成一个常量）正在替换一个 shuffle (bslli(s2bc, 12))、一个 OR 和一个 AND。
d==bc c==ab b==a a==d = s2b|s2c
d==a 0 0 0 = byte-shift-left(s2b) = s2d0
d==abc c==ab b==a a==d = s2abc
d==abc c==ab b==a 0 = mask(s2abc). Maybe use PBLENDW or MOVSS from s2d0 (which we know has zeros) to save loading a 16B mask.
__m128i s2abcd = _mm_or_si128(s2b, s2c);
//s2bc = _mm_shuffle_epi8(s2bc, _mm_set_epi8(-1,-1,0,12, -1,-1,-1,8, -1,-1,-1,4, -1,-1,-1,-1));
//__m128i dupmask = _mm_cmpeq_epi32(s2bc, _mm_setzero_si128());
__m128i s2d0 = _mm_bslli_si128(s2b, 12); // d==a 0 0 0
s2abcd = _mm_or_si128(s2abcd, s2d0);
__m128i dupmask = _mm_blend_epi16(s2abcd, s2d0, 0 | (2 | 1));
//__m128i dupmask = _mm_and_si128(s2abcd, _mm_set_epi32(-1, -1, -1, 0));
match = _mm_andnot_si128(dupmask, match); // ~dupmask & match; first arg is the one that's inverted
我不推荐MOVSS；它会在 AMD 上产生额外的延迟，因为它 运行s 在 FP 域中。 PBLENDW 是 SSE4.1。 popcnt 在 AMD K10 上可用，但 PBLENDW 不可用（某些 Barcelona-core PhenomII CPU 可能仍在使用）。其实K10也没有PSHUFB，所以只需要SSE4.1和POPCNT，用PBLENDW就可以了。 （或者使用 PSHUFB 版本，除非它会经常缓存未命中。）
另一个避免从内存中加载向量常量的选项是移动掩码 s2bc，并使用整数而不是向量操作。然而，它看起来会更慢，因为额外的 movemask 不是免费的，并且整数 ANDN 不可用。 BMI1直到Haswell才出现，连Skylake Celerons和Pentiums都不会有。 （Very annoying, IMO. It means compilers can't start using BMI 甚至更长。）
unsigned int dupmask = _mm_movemask_ps(cast(s2bc));
dupmask |= dupmask << 3; // bit3 = d==abc. garbage in bits 4-6, careful if using AVX2 to do two structs at once
// only 2 instructions. compiler can use lea r2, [r1*8] to copy and scale
dupmask &= ~1; // clear the low bit
unsigned int matchmask = _mm_movemask_ps(cast(match));
matchmask &= ~dupmask; // ANDN is in BMI1 (Haswell), so this will take 2 instructions
return _mm_popcnt_u32(matchmask);
AMD XOP 的 VPPERM（从两个源寄存器的任何元素中挑选字节）将让字节洗牌取代合并 s2b 和 s2c 的 OR。
嗯，pshufb 并没有像我想的那样拯救我，因为它需要一个 pcmpeqd 和一个 pxor 来将寄存器归零。它还从内存中的常量加载其洗牌掩码，这可能会在 D 缓存中丢失。不过，这是我想出的最快的版本。
如果内联到一个循环中，可以使用相同的归零寄存器，从而节省一条指令。但是，OR 和 AND 可以 运行 on port0 (Intel CPUs)，它不能 运行 洗牌或比较指令。但是，PXOR 不使用任何执行端口（在 Intel SnB 系列微体系结构上）。
我没有运行任何这些的真正基准，只有 IACA。
PBLENDW 和 PSHUFB 版本具有相同的延迟（22 个周期，为非 AVX 编译），但 PSHUFB 版本具有更好的吞吐量（每 7.1c 一个，而每 7.4c 一个，因为 PBLENDW 需要随机播放端口，并且已经有很多争论。） IACA 说使用 PANDN 和常数而不是 PBLENDW 的版本也是每 7.4c 吞吐量一个，令人失望。端口 0 未饱和，所以 IDK 为什么它和 PBLENDW 一样慢。
没有成功的旧想法。
保留它们是为了方便人们在将向量用于相关事物时寻找可以尝试的事物。
使用向量对 s2 进行重复检查比检查 s2 与 s1 的工作量更大，因为如果使用向量，一次比较的开销相当于 4 次。在比较 之后 需要进行改组或屏蔽，如果没有哨兵值则删除误报，这很烦人。
目前的想法：
将 s2 移动一个元素，并将其与自身进行比较。屏蔽移入 0 的误报。垂直或将它们放在一起，并将其用于 ANDN s1 与 s2 向量。
标量代码，用于执行较少数量的 s2 与自身比较，构建要在 popcnt 之前使用的位掩码。
广播s2.d并对照s2（所有位置）进行检查。但这会将结果水平放置在一个向量中，而不是垂直放置在 3 个向量中。要使用它，也许 PTEST / SETCC 为位图制作一个掩码（在 popcount 之前应用）。 （PTEST 掩码 _mm_setr_epi32(0, -1, -1, -1)，只测试 c,b,a，而不是 d==d）。使用标量代码执行 (c==a | c==b) 和 b==a，并将其组合成掩码。 Intel Haswell 和更高版本有 4 个 ALU 执行端口，但其中只有 3 个可以 运行 矢量指令，因此混合中的一些标量代码可以填充端口 6。 AMD 在向量和整数执行资源之间有更多的分离。
随机播放 s2 以某种方式完成所有必要的比较，然后随机播放输出。也许使用 movemask -> 4 位查找 table？
给定以下结构：
struct four_points {
uint32_t a, b, c, d;
}
比较两个这样的结构和return匹配（在任何位置）的变量数量的绝对最快的方法是什么？
例如：
four_points s1 = {0, 1, 2, 3};
four_points s2 = {1, 2, 3, 4};
我会寻找结果 3，因为三个数字在两个结构之间匹配。但是，鉴于以下情况：
four_points s1 = {1, 0, 2, 0};
four_points s2 = {0, 1, 9, 7};
然后我希望结果只有 2，因为两个结构之间只有两个变量匹配（尽管第一个有两个零）。
我已经找到了一些用于执行比较的基本系统，但这是将在短时间内被调用几百万次的东西，需要相对较快。我目前最好的尝试是使用排序网络对任一输入的所有四个值进行排序，然后循环排序后的值并保留相等值的计数，相应地推进任一输入的当前索引。
是否有任何一种技术可以比排序和迭代执行得更好？
在现代 CPU 年代，有时正确应用蛮力是可行的方法。诀窍是编写不受指令延迟限制的代码，只受吞吐量限制。
重复是否常见？如果它们非常罕见，或者有一个模式，使用分支来处理它们可以使常见情况更快。如果他们真的是不可预测的table，最好做一些无分支的事情。我正在考虑使用分支来检查罕见位置之间的重复项，并在更常见的位置使用无分支。
基准测试很棘手，因为带有分支的版本在使用相同数据进行一百万次测试时会大放异彩，但在实际使用中会有很多分支预测错误。
我还没有对任何东西进行基准测试，但我想出了一个版本，通过使用 OR 而不是加法 来组合找到的匹配项来跳过重复项。它编译成 gcc 完全展开的漂亮的 x86 asm。 （没有条件分支，甚至没有循环）。
Here it is on godbolt。 （g++ 是愚蠢的，在 x86 setcc 的输出上使用 32 位操作，它只设置低 8 位。这种部分寄存器访问会产生减速。而且我什至不确定它是否会将高 24 位归零所有...无论如何，gcc 4.9.2 的代码看起来不错，godbolt 上的 clang 也不错）
// 8-bit types used because x86's setcc instruction only sets the low 8 of a register
// leaving the other bits unmodified.
// Doing a 32bit add from that creates a partial register slowdown on Intel P6 and Sandybridge CPU families
// Also, compilers like to insert movzx (zero-extend) instructions
// because I guess they don't realize the previous high bits are all zero.
// (Or they're tuning for pre-sandybridge Intel, where the stall is worse than SnB inserting the extra uop itself).
// The return type is 8bit because otherwise clang decides it should generate
// things as 32bit in the first place, and does zero-extension -> 32bit adds.
int8_t match4_ordups(const four_points *s1struct, const four_points *s2struct)
{
const int32_t *s1 = &s1struct->a; // TODO: check if this breaks aliasing rules
const int32_t *s2 = &s2struct->a;
// ignore duplicates by combining with OR instead of addition
int8_t matches = 0;
for (int j=0 ; j<4 ; j++) {
matches |= (s1[0] == s2[j]);
}
for (int i=1; i<4; i++) { // i=0 iteration is broken out above
uint32_t s1i = s1[i];
int8_t notdup = 1; // is s1[i] a duplicate of s1[0.. i-1]?
for (int j=0 ; j<i ; j++) {
notdup &= (uint8_t) (s1i != s1[j]); // like dup |= (s1i == s1[j]); but saves a NOT
}
int8_t mi = // match this iteration?
(s1i == s2[0]) |
(s1i == s2[1]) |
(s1i == s2[2]) |
(s1i == s2[3]);
// gcc and clang insist on doing 3 dependent OR insns regardless of parens, not that it matters
matches += mi & notdup;
}
return matches;
}
// see the godbolt link for a main() simple test harness.
在具有 128b 向量且可以处理 4 个打包的 32 位整数的机器上（例如 x86 和 SSE2），您可以将 s1 的每个元素广播到它自己的向量，去重，然后执行 4 个打包-比较。 icc 做了类似这样的事情来自动向量化我的 match4_ordups 函数（在 godbolt 上查看。）
使用movemask将比较结果存储回整数寄存器，以获得比较相等的元素的位图。 Popcount 那些位图，并添加结果。
这让我想到了一个更好的主意：只用 3 次元素轮换洗牌就完成了所有比较：
{ 1d 1c 1b 1a }
== == == == packed-compare with
{ 2d 2c 2b 2a }
{ 1a 1d 1c 1b }
== == == == packed-compare with
{ 2d 2c 2b 2a }
{ 1b 1a 1d 1c } # if dups didn't matter: do this shuffle on s2
== == == == packed-compare with
{ 2d 2c 2b 2a }
{ 1c 1b 1a 1d } # if dups didn't matter: this result from { 1a ... }
== == == == packed-compare with
{ 2d 2c 2b 2a } { 2b ...
这只是 3 次随机播放，并且仍然进行了所有 16 次比较。诀窍是将它们与我们需要合并重复项的 OR 结合起来，然后能够有效地计算它们。打包比较根据该位置的两个元素之间的比较输出一个向量，每个元素 = 零或 -1（所有位设置）。它旨在为 AND 或 XOR 提供有用的操作数，以屏蔽某些向量元素，例如使 v1 += v2 & 掩码在每个元素的基础上成为条件。它也只是一个布尔真值。
通过将一个向量旋转 2，将另一个向量旋转 1，然后比较四个移位和未移位的向量，可以进行全部 16 次比较，仅进行 2 次混洗。如果我们不需要消除重复项，那就太好了，但既然我们这样做了，那么结果在哪里就很重要了。我们不只是将所有 16 个比较结果相加。
或将打包比较结果合并为一个向量。将根据 s2 的该元素是否在 s1 中有任何匹配来设置每个元素。 int _mm_movemask_ps (__m128 a) 将矢量转换为位图，然后对位图进行 popcount。 （Nehalem or newer CPU required for popcnt，否则退回到具有 4 位查找的版本 table。）
垂直 OR 处理 s1 中的重复项，但 s2 中的重复项是一个不太明显的扩展，需要更多的工作。我最终确实想到了一种不到两倍慢的方法（见下文）。
#include <stdint.h>
#include <immintrin.h>
typedef struct four_points {
int32_t a, b, c, d;
} four_points;
//typedef uint32_t four_points[4];
// small enough to inline, only 62B of x86 instructions (gcc 4.9.2)
static inline int match4_sse_noS2dup(const four_points *s1pointer, const four_points *s2pointer)
{
__m128i s1 = _mm_loadu_si128((__m128i*)s1pointer);
__m128i s2 = _mm_loadu_si128((__m128i*)s2pointer);
__m128i s1b= _mm_shuffle_epi32(s1, _MM_SHUFFLE(0, 3, 2, 1));
// no shuffle needed for first compare
__m128i match = _mm_cmpeq_epi32(s1 , s2); //{s1.d==s2.d?-1:0, 1c==2c, 1b==2b, 1a==2a }
__m128i s1c= _mm_shuffle_epi32(s1, _MM_SHUFFLE(1, 0, 3, 2));
s1b = _mm_cmpeq_epi32(s1b, s2);
match = _mm_or_si128(match, s1b); // merge dups by ORing instead of adding
// note that we shuffle the original vector every time
// multiple short dependency chains are better than one long one.
__m128i s1d= _mm_shuffle_epi32(s1, _MM_SHUFFLE(2, 1, 0, 3));
s1c = _mm_cmpeq_epi32(s1c, s2);
match = _mm_or_si128(match, s1c);
s1d = _mm_cmpeq_epi32(s1d, s2);
match = _mm_or_si128(match, s1d); // match = { s2.a in s1?, s2.b in s1?, etc. }
// turn the the high bit of each 32bit element into a bitmap of s2 elements that have matches anywhere in s1
// use float movemask because integer movemask does 8bit elements.
int matchmask = _mm_movemask_ps (_mm_castsi128_ps(match));
return _mm_popcnt_u32(matchmask); // or use a 4b lookup table for CPUs with SSE2 but not popcnt
}
查看删除 s2 中重复项的版本，以更易读的顺序排列相同的代码。我尝试安排指令，以防 CPU 只是在执行之前勉强解码指令，但 gcc 将指令置于相同的顺序，而不管你将内在函数放入的顺序如何。
这非常快，如果 128b 负载中没有存储转发停顿。如果您只是编写了具有四个 32 位存储的结构，运行 在接下来的几个时钟周期内启用此函数将在它尝试使用 128b 负载加载整个结构时产生停顿。参见 Agner Fog's site。如果调用代码在寄存器中已经有 8 个值中的许多值，那么标量版本可能是一个胜利，即使对于只从内存中读取结构的微基准测试来说它会更慢。
由于重复处理尚未完成，因此我懒得进行循环计数。 IACA 表示 Haswell 可以 运行 它具有每 4.05 个时钟周期一次迭代的吞吐量和 17 个周期的延迟（不确定这是否包括加载的内存延迟。有很多指令级并行可用，并且除了 movmsk(2) 和 popcnt(3))，所有指令都有单周期延迟。没有 AVX 会稍微慢一些，因为 gcc 选择了一个更差的指令顺序，并且仍然浪费 movdqa 指令复制向量寄存器。
使用 AVX2，这可以在 256b 向量中并行执行两个 match4 操作。 AVX2 通常用作两个 128b 通道，而不是完整的 256b 向量。将您的代码设置为能够并行利用 2 或 4 个 (AVX-512) match4 操作，当您可以针对这些 CPU 进行编译时，您将获得收益。 s1 或 s2s 都不必连续存储，因此单个 32B 负载可以获得两个结构。 AVX2 可以相当快地将 128b 加载到寄存器的上通道。
处理 s2
中的重复项
也许将 s2 与 shifted 而不是自身的旋转版本进行比较。
#### comparing S2 with itself to mask off duplicates
{ 0 2d 2c 2b }
{ 2d 2c 2b 2a } == == ==
{ 0 0 2d 2c }
{ 2d 2c 2b 2a } == ==
{ 0 0 0 2d }
{ 2d 2c 2b 2a } ==
嗯，如果零可以作为常规元素出现，我们可能还需要在比较之后进行字节移位，以将潜在的误报变成零。 如果在s1中有一个标记值不能出现，你可以移入它的元素，而不是0。（SSE有PALIGNR，它给你任何连续的 16B window 你想要附加的两个寄存器的内容。命名为从两个对齐负载模拟未对齐负载的用例。所以你有一个该元素的常数向量。）
更新：我想到了一个很好的技巧，可以避免使用标识元素。实际上，我们只需进行两次向量比较就可以获得所有 6 次必要的 s2 与 s2 比较，然后合并结果。
在两个向量的相同位置进行相同的比较可以让您对两个结果进行“或”运算，而无需在“或”运算之前进行屏蔽。 （解决缺少标记值的问题）。
洗牌比较的输出，而不是 S2 的额外洗牌和比较。这意味着我们可以在其他比较之后完成
d==a。请注意，我们并不局限于随机排列整个元素。按字节顺序混洗以将来自不同比较结果的字节放入单个向量元素中，并将 that 与零进行比较。 （这比我希望的要少，见下文）。
检查重复项会大大降低速度（尤其是吞吐量，而不是延迟）。所以你仍然最好在 s2 中安排一个标记值，它永远不会匹配任何 s1 元素，你说这是可能的。我只提出这个，因为我认为它很有趣。 （并为您提供一个选项，以防您有时需要不需要哨兵的版本。）
static inline
int match4_sse(const four_points *s1pointer, const four_points *s2pointer)
{
// IACA_START
__m128i s1 = _mm_loadu_si128((__m128i*)s1pointer);
__m128i s2 = _mm_loadu_si128((__m128i*)s2pointer);
// s1a = unshuffled = s1.a in the low element
__m128i s1b= _mm_shuffle_epi32(s1, _MM_SHUFFLE(0, 3, 2, 1));
__m128i s1c= _mm_shuffle_epi32(s1, _MM_SHUFFLE(1, 0, 3, 2));
__m128i s1d= _mm_shuffle_epi32(s1, _MM_SHUFFLE(2, 1, 0, 3));
__m128i match = _mm_cmpeq_epi32(s1 , s2); //{s1.d==s2.d?-1:0, 1c==2c, 1b==2b, 1a==2a }
s1b = _mm_cmpeq_epi32(s1b, s2);
match = _mm_or_si128(match, s1b); // merge dups by ORing instead of adding
s1c = _mm_cmpeq_epi32(s1c, s2);
match = _mm_or_si128(match, s1c);
s1d = _mm_cmpeq_epi32(s1d, s2);
match = _mm_or_si128(match, s1d);
// match = { s2.a in s1?, s2.b in s1?, etc. }
// s1 vs s2 all done, now prepare a mask for it based on s2 dups
/*
* d==b c==a b==a d==a #s2b
* d==c c==b b==a d==a #s2c
* OR together -> s2bc
* d==abc c==ba b==a 0 pshufb(s2bc) (packed as zero or non-zero bytes within the each element)
* !(d==abc) !(c==ba) !(b==a) !0 pcmpeq setzero -> AND mask for s1_vs_s2 match
*/
__m128i s2b = _mm_shuffle_epi32(s2, _MM_SHUFFLE(1, 0, 0, 3));
__m128i s2c = _mm_shuffle_epi32(s2, _MM_SHUFFLE(2, 1, 0, 3));
s2b = _mm_cmpeq_epi32(s2b, s2);
s2c = _mm_cmpeq_epi32(s2c, s2);
__m128i s2bc= _mm_or_si128(s2b, s2c);
s2bc = _mm_shuffle_epi8(s2bc, _mm_set_epi8(-1,-1,0,12, -1,-1,-1,8, -1,-1,-1,4, -1,-1,-1,-1));
__m128i dupmask = _mm_cmpeq_epi32(s2bc, _mm_setzero_si128());
// see below for alternate insn sequences that can go here.
match = _mm_and_si128(match, dupmask);
// turn the the high bit of each 32bit element into a bitmap of s2 matches
// use float movemask because integer movemask does 8bit elements.
int matchmask = _mm_movemask_ps (_mm_castsi128_ps(match));
int ret = _mm_popcnt_u32(matchmask); // or use a 4b lookup table for CPUs with SSE2 but not popcnt
// IACA_END
return ret;
}
pshufb 这需要 SSSE3。它和一个 pcmpeq（和一个 pxor 来生成一个常量）正在替换一个 shuffle (bslli(s2bc, 12))、一个 OR 和一个 AND。
d==bc c==ab b==a a==d = s2b|s2c
d==a 0 0 0 = byte-shift-left(s2b) = s2d0
d==abc c==ab b==a a==d = s2abc
d==abc c==ab b==a 0 = mask(s2abc). Maybe use PBLENDW or MOVSS from s2d0 (which we know has zeros) to save loading a 16B mask.
__m128i s2abcd = _mm_or_si128(s2b, s2c);
//s2bc = _mm_shuffle_epi8(s2bc, _mm_set_epi8(-1,-1,0,12, -1,-1,-1,8, -1,-1,-1,4, -1,-1,-1,-1));
//__m128i dupmask = _mm_cmpeq_epi32(s2bc, _mm_setzero_si128());
__m128i s2d0 = _mm_bslli_si128(s2b, 12); // d==a 0 0 0
s2abcd = _mm_or_si128(s2abcd, s2d0);
__m128i dupmask = _mm_blend_epi16(s2abcd, s2d0, 0 | (2 | 1));
//__m128i dupmask = _mm_and_si128(s2abcd, _mm_set_epi32(-1, -1, -1, 0));
match = _mm_andnot_si128(dupmask, match); // ~dupmask & match; first arg is the one that's inverted
我不推荐MOVSS；它会在 AMD 上产生额外的延迟，因为它 运行s 在 FP 域中。 PBLENDW 是 SSE4.1。 popcnt 在 AMD K10 上可用，但 PBLENDW 不可用（某些 Barcelona-core PhenomII CPU 可能仍在使用）。其实K10也没有PSHUFB，所以只需要SSE4.1和POPCNT，用PBLENDW就可以了。 （或者使用 PSHUFB 版本，除非它会经常缓存未命中。）
另一个避免从内存中加载向量常量的选项是移动掩码 s2bc，并使用整数而不是向量操作。然而，它看起来会更慢，因为额外的 movemask 不是免费的，并且整数 ANDN 不可用。 BMI1直到Haswell才出现，连Skylake Celerons和Pentiums都不会有。 （Very annoying, IMO. It means compilers can't start using BMI 甚至更长。）
unsigned int dupmask = _mm_movemask_ps(cast(s2bc));
dupmask |= dupmask << 3; // bit3 = d==abc. garbage in bits 4-6, careful if using AVX2 to do two structs at once
// only 2 instructions. compiler can use lea r2, [r1*8] to copy and scale
dupmask &= ~1; // clear the low bit
unsigned int matchmask = _mm_movemask_ps(cast(match));
matchmask &= ~dupmask; // ANDN is in BMI1 (Haswell), so this will take 2 instructions
return _mm_popcnt_u32(matchmask);
AMD XOP 的 VPPERM（从两个源寄存器的任何元素中挑选字节）将让字节洗牌取代合并 s2b 和 s2c 的 OR。
嗯，pshufb 并没有像我想的那样拯救我，因为它需要一个 pcmpeqd 和一个 pxor 来将寄存器归零。它还从内存中的常量加载其洗牌掩码，这可能会在 D 缓存中丢失。不过，这是我想出的最快的版本。
如果内联到一个循环中，可以使用相同的归零寄存器，从而节省一条指令。但是，OR 和 AND 可以 运行 on port0 (Intel CPUs)，它不能 运行 洗牌或比较指令。但是，PXOR 不使用任何执行端口（在 Intel SnB 系列微体系结构上）。
我没有运行任何这些的真正基准，只有 IACA。
PBLENDW 和 PSHUFB 版本具有相同的延迟（22 个周期，为非 AVX 编译），但 PSHUFB 版本具有更好的吞吐量（每 7.1c 一个，而每 7.4c 一个，因为 PBLENDW 需要随机播放端口，并且已经有很多争论。） IACA 说使用 PANDN 和常数而不是 PBLENDW 的版本也是每 7.4c 吞吐量一个，令人失望。端口 0 未饱和，所以 IDK 为什么它和 PBLENDW 一样慢。
没有成功的旧想法。
保留它们是为了方便人们在将向量用于相关事物时寻找可以尝试的事物。
使用向量对 s2 进行重复检查比检查 s2 与 s1 的工作量更大，因为如果使用向量，一次比较的开销相当于 4 次。在比较 之后 需要进行改组或屏蔽，如果没有哨兵值则删除误报，这很烦人。
目前的想法：
将
s2移动一个元素，并将其与自身进行比较。屏蔽移入 0 的误报。垂直或将它们放在一起，并将其用于 ANDN s1 与 s2 向量。标量代码，用于执行较少数量的 s2 与自身比较，构建要在 popcnt 之前使用的位掩码。
广播
s2.d并对照s2（所有位置）进行检查。但这会将结果水平放置在一个向量中，而不是垂直放置在 3 个向量中。要使用它，也许PTEST / SETCC为位图制作一个掩码（在 popcount 之前应用）。 （PTEST掩码_mm_setr_epi32(0, -1, -1, -1)，只测试c,b,a，而不是d==d）。使用标量代码执行 (c==a | c==b) 和 b==a，并将其组合成掩码。 Intel Haswell 和更高版本有 4 个 ALU 执行端口，但其中只有 3 个可以 运行 矢量指令，因此混合中的一些标量代码可以填充端口 6。 AMD 在向量和整数执行资源之间有更多的分离。随机播放
s2以某种方式完成所有必要的比较，然后随机播放输出。也许使用 movemask -> 4 位查找 table？