Solution
推荐的解决方案总是将所有独有元素置于产出的下端, 由先发制人排序。 上端为零 。 通过修改 LUT 很容易改变定位策略: 将元素置于上方, 或将其顺序颠倒 。
static __m128i *const lookup_hash = (__m128i*) &lookup_hash_chars[0][0];
static inline __m128i deduplicate4_ssse3(__m128i abcd) {
__m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
__m128i cdab = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(1, 0, 3, 2));
uint32_t mask1 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, bcda));
uint32_t mask2 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, cdab));
uint32_t maskFull = (mask2 << 16U) + mask1;
//Note: minimal perfect hash function here
uint32_t lutIndex = (maskFull * 0X0044CCCEU) >> 26U;
__m128i shuf = lookup_hash[lutIndex];
return _mm_shuffle_epi8(abcd, shuf);
}
有完整的代码(通过测试) 这里。
我还实施了简单的天平解决方案,分选了5个参照国的网络,然后对连续元素进行序列比较。 我对两个处理器使用MSVC2013, 它们是:Core 2 E4700(Allendale,2.6 Ghz)和Core i7-3770(Ivy Bridge,3.4 Ghz)。以下是229通话的几秒钟时间:
// Allendale
SSE: time = 3.340 // ~16.2 cycles (per call)
Scalar: time = 17.218 // ~83.4 cycles (per call)
// Ivy Bridge
SSE: time = 1.203 // ~ 7.6 cycles (per call)
Scalar: time = 11.673 // ~73.9 cycles (per call)
Discussion
请注意,结果必须包括两类要素:
- elements from the input vector,
- zeros.
然而,必要的洗牌面罩是在运行时以非常复杂的方式确定的。所有 SSE 指令只能处理即时(即编译-时间常数)洗牌面罩,只有一个除外。这是SSSE3 所固有的。为了快速洗牌面罩,所有面罩都储存在一张外观表格中,由一些bitmaks或hases编制索引。
为获取给定输入矢量的折叠遮罩, 有必要收集足够的关于其中平等元素的信息 。 请注意, 要知道哪些对元素是相等的, 足以确定如何将其变现 。 如果我们想要另外对它们进行分类, 那么我们还需要知道不同元素是如何相互比较的, 这会增加信息量, 然后再查看表格 。 这就是为什么我在这里会显示不同元素的重复 < 坚固 > 而不 < / 坚固 > 排序 。
因此,我们在 XMM 登记册中有四个32位位元元素。 它们共组成六对元素。 由于我们只能一次比较四个元素, 我们需要至少两个比较。 事实上, 很容易进行两个 XMM 比较, 这样每对元素至少要比较一次。 在此之后, 我们可以通过使用 < code'mm_movemask_ epi8 < /code > 来提取16位位位位元的比较, 并将其组合成一个单32位整数。 请注意, 每个 4位元块将包含相同的位元, 而最后两个 4位元块是不必要的( 它们与过度比较相对 ) 。
理想情况下, 我们需要从这个位图中提取精确的 6 位位元, 位置位于汇编时已知的位置中。 使用 BMI2 指令设置的 code_ pext_ u32 , 很容易实现。 因此, 我们有一个包含 6 位元的整数 : < em> [0. 63] , 每个位数显示对应的元素配对是否相等 。 然后我们用 < code\ mm_ shuffle_ epi8 来装入一个从64 输入时的查看表上打乱的遮罩, 然后用 < code\ mm_ shuffle_ epi8 来打乱我们的输入矢量 。
不幸的是,BMI指令非常新(Haswell and later),而我没有这样的指令 =) 为了摆脱它,我们可以尝试创建一个非常简单和快速的 href="https://en.wikipedia.org/wiki/Perfect_hash_formation" rel="nreferrer">perfect hash 函数 ,所有64个有效比特(提醒比特是32-bit)。对于类中的散列函数 f(x) = (a* x) & gt; & gt; (32-b) 通常可以建立一个相当小的完美散列, 包含 2x 或 3x 的内存管理。由于我们的情况特殊, 有可能建立一个最小的完美散列功能, 因此外表只有64个条目(例如大小= 1 KB)。
8个元素(如XMM登记簿中的16位整数)使用同样的算法是不可行的,因为有28对元素,这意味着查看表必须至少包含228个条目。
在 YMM 注册的 64 位元元素使用此方法也有问题。 < code\ mm256_ shuffle_ epi8 < /code > 的内在功能没有帮助, 因为它只执行两个单独的 128 位元的洗牌( 绝对不横跨车道洗牌) 。 的内在功能可以任意打乱32 位元块, 但无法插入零 。 要使用它, 您也需要在 LUT 中存储独有的元素数量 。 然后您必须手工将零放入您的注册的较高部分 。
UPDATE: hash/BMI removed
我意识到使用 BMI2 来提取比特提取或完全散列函数是不必要的, 我们可以简单地使用 < code\ mm_ movemask_ps < / code > 来提取 32 位面罩。 这种方法可能存在轻微的潜伏问题, 因为我们混合了INT 和 FP 计算, 但实际上效果更快 。
static __m128i *const lookup_direct_offset = lookup_direct - 0xC0U;
static inline __m128i deduplicate4_ssse3_direct(__m128i abcd) {
__m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
__m128i cdcd = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(3, 2, 3, 2));
uint32_t mask1 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, bcda)));
uint32_t mask2 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, cdcd)));
uint32_t maskFull = 16U * mask2 + mask1;
//Note: use index directly
uint32_t lutIndex = maskFull;
__m128i shuf = lookup_direct_offset[lutIndex];
return _mm_shuffle_epi8(abcd, shuf);
}
全代码 也更新。
// Ivy Bridge
new: Time = 1.038 (782827520) // ~ 6.6 cycles (per call)
old: Time = 1.169 (782827520) // ~ 7.4 cycles (per call)
