CMP*_*G8B 4 c sorting performance compare sorting-network
给定以下结构:
struct four_points {
uint32_t a, b, c, d;
}
比较两个这样的结构并返回匹配的变量数(在任何位置)的绝对最快方法是什么？
例如:
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上,有时应用蛮力是可行的方法.诀窍是编写不受指令延迟限制的代码,只是吞吐量.
重复是否常见？如果它们非常罕见或具有模式,则使用分支来处理它们会使常见情况更快.如果它们真的不可预测,最好做一些无分支的事情.我正在考虑使用一个分支来检查它们之间罕见的位置之间的重复,并为更常见的地方进行无分支.
基准测试是棘手的,因为具有分支的版本在使用相同数据测试一百万次时会发光,但实际使用中会有很多分支误预测.
我还没有对任何基准测试,但是我已经提出了一个版本,它通过使用OR而不是添加来组合找到的匹配来跳过重复项.它编译为漂亮的x86 asm,gcc完全展开.(没有条件分支,甚至没有循环).
这是在godbolt上.(g ++是哑的,并且在x86的输出上使用32位操作setcc,它只设置低8位.这种部分寄存器访问会产生减速.而且我甚至不确定它是否会将高24位归零...无论如何,gcc 4.9.2中的代码看起来不错,在godbolt上也是如此
// 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.
在具有128个向量的计算机上,可以使用4个打包的32位整数(例如x86与SSE2),您可以将每个元素广播s1到其自己的向量,重复数据删除,然后执行4个打包比较.icc做了类似的事情来自动调整我的match4_ordups函数(在godbolt上查看.)
使用movemask将比较结果存储回整数寄存器,以获得比较相等元素的位图.Popcount这些位图,并添加结果.
这让我有了一个更好的想法:通过元素旋转只进行3次shuffle来完成所有比较:
{ 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组合,我们需要合并重复项,然后才能有效地计算它们.打包比较基于该位置中的两个元素之间的比较,输出具有每个元素= 0或-1(所有位设置)的向量.它旨在为AND或XOR创建一个有用的操作数来屏蔽一些向量元素,例如使v1 + = v2&mask以每个元素为基础进行条件化.它也只是一个布尔值真值.
通过将一个矢量旋转两个,将另一个矢量旋转一个,然后在四个移位和未移位矢量之间进行比较,可以进行所有16个比较,只有2个混洗.如果我们不需要消除重复,这将是很好的,但是既然我们这样做,那么结果在哪里就很重要.我们不只是添加所有16个比较结果.
或者将打包比较结果一起降低到一个向量.将根据s2中的元素是否在s1中具有任何匹配来设置每个元素. int _mm_movemask_ps (__m128 a)将矢量转换为位图,然后弹出位图.(pophant需要Nehalem或更新的CPU,否则会回退到具有4位查找表的版本.)
垂直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的网站.如果调用代码已经在寄存器中有许多8个值,则标量版本可能是一个胜利,即使对于仅从内存中读取结构的微基准测试来说它也会更慢.
由于重复处理尚未完成,我对此进行循环计数很懒惰.IACA表示Haswell可以每4.05个时钟周期运行一次迭代,延迟时间为17个周期(不确定是否包括负载的内存延迟.有很多指令级并行可用,并且所有指令都有单周期延迟,movmsk(2)和popcnt(3)除外).没有AVX,它会稍微慢一些,因为gcc会选择更糟糕的指令排序,并且仍会浪费movdqa复制矢量寄存器的指令.
使用AVX2,这可以match4在256b向量中并行执行两个操作.AVX2通常用作两个128b通道,而不是完整的256b向量.设置代码以便能够并行利用2或4(AVX-512)match4操作,可以在编译这些CPU时获得收益.它对于s1s和s2s连续存储都不是必需的,因此单个32B负载可以获得两个结构.AVX2具有相当快的负载128b到寄存器的上部通道.
s2也许比较s2到一个转移而不是自己的旋转版本.
#### 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窗口命名为使用 - 从两个对齐的负载模拟未对齐负载的情况.所以你有一个该元素的常量向量.)
更新:我想到了一个避免需要身份元素的好技巧.我们实际上可以通过两次矢量比较来获得所有6个必要的s2与s2比较,然后将结果组合起来.
在两个向量中的相同位置进行相同的比较,可以将两个结果一起进行OR,而不必在OR之前进行掩码.(围绕缺乏哨兵价值工作).
对比较的输出进行混洗而不是额外的随机播放和S2的比较.这意味着我们可以d==a在其他比较旁边完成.
请注意,我们不仅限于改变整个元素.按字节顺序将不同比较结果中的字节转换为单个向量元素,并将其与零进行比较.(这比我希望的节省更多,见下文).
检查重复项是一个很大的减速(特别是吞吐量,而不是延迟).所以你最好还是在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;
}
这需要SSSE3 pshufb.它和a 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上产生额外的延迟,因为它在FP域中运行. PBLENDW是SSE4.1. popcnt可以在AMD K10上使用,但PBLENDW不是(某些巴塞罗那核心的PhenomII CPU可能仍在使用中).实际上,K10也没有PSHUFB,所以只需要SSE4.1和POPCNT,并使用PBLENDW.(或者使用PSHUFB版本,除非它会缓存错过很多次.)
避免从内存加载向量常量的另一个选项是movemask s2bc,并使用整数而不是向量操作.但是,它看起来会慢一些,因为额外的movemask不是免费的,并且整数ANDN不可用.BMI1直到Haswell才出现,甚至Skylake Celerons和Pentiums都没有.(非常讨厌,IMO.这意味着编译器无法再开始使用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(从两个源寄存器的任何元素中挑选字节)将允许byte-shuffle替换合并s2b和s2c的OR.
嗯,pshufb并没有像我想象的那样拯救我,因为它需要一个寄存器pcmpeqd和一个pxor零寄存器.它还从内存中的常量加载其shuffle掩码,这可能会在D-cache中丢失.不过,这是我提出的最快的版本.
如果内联到循环中,则可以使用相同的归零寄存器,从而保存一条指令.但是,OR和AND可以在port0(Intel CPU)上运行,它不能运行shuffle或比较指令.但是PXOR,不使用任何执行端口(在Intel SnB系列微体系结构上).
我没有运行任何这些的真正基准,只有IACA.
PBLENDW和PSHUFB版本具有相同的延迟(22个周期,针对非AVX编译),但PSHUFB版本具有更好的吞吐量(每7.1c一个,而每7.4c一个,因为PBLENDW需要shuffle端口,并且已经有很多争论.)IACA表示,使用PANDN而不是PBLENDW的版本也是每7.4c的吞吐量,令人失望.Port0没有饱和,所以IDK为什么它和PBLENDW一样慢.
离开它们是为了让人们在寻找相关事物的向量时尝试的东西.
使用向量进行重复检查s2比检查s2对比s1更有效,因为如果使用向量进行一次比较,则与4进行比较一样昂贵.比较后需要的改组或屏蔽,如果没有哨兵值则消除误报,这很烦人.
目前为止的想法:
s2由元素切换,并将其与自身进行比较.屏蔽误差从0移位.垂直或这些在一起,并使用它来ANDN s1 vs 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个可以运行向量指令,因此混合中的一些标量代码可以填充port6.AMD在向量和整数执行资源之间有更多的分离.
洗牌s2以某种方式完成所有必要的比较,然后改变输出.也许使用movemask - > 4位查找表的东西？
| 归档时间： |
|
| 查看次数： |
195 次 |
| 最近记录： |