问题
是否有任何计算可行的方法，一组使用的x86 SIMD指令整数的内部寄存器的重复数据删除？
例
我们有一个4元组寄存器R1 = {3,9，2,9}，并且希望获得寄存器R2 = {3,9，2，NULL}。
限制
Stablility。 输入顺序的保护也是没有意义的。
输出 。 然而，任何数值去除/空值必须是在开始和/或寄存器的端：
这显然是一个奖金，如果它是已知会产生一个特定的输出格式。 此外，假设NULL有效均值为0（零）。
共性 。 必须能够容忍不存在重复的，在这种情况下产生一个输出等效于输入寄存器。
指令集 。 我正在寻找任何或所有的解决方案：SSE2，SSSE3; SSE4.x; AVX，AVX2
提出的解决方案总是把所有的独特的元素到输出的下部，首先出现次数排序。 较高的部分被归零。 这是很容易改变通过修改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两个处理器：酷睿2 E4700（艾伦代尔，2.6千兆赫）和酷睿i7-3770（Ivy Bridge的，3.4GHz的）。 这里有2 ^ 29秒的通话定时：
// 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)
请注意，结果必须由两种类型的元素：
然而，必要的洗牌面具在运行时确定，并在一个非常复杂的方式。 所有SSE指令可以立即只处理（即编译时间常数）洗牌口罩，除了一个。 这是_mm_shuffle_epi8从SSSE3内在。 为了获得洗牌面具很快，所有的面具都存储在一个查找表，一些位掩码或哈希索引。
以获得对于给定的输入向量混洗面具，有必要收集关于它等于元件的足够信息。 请注意，这是完全足够的知道哪些元素对都是为了决定如何去复制他们平等。 如果我们要另外进行排序，那么我们就需要知道不同的元素还怎么互相比较，这增加了信息量，并随后查找表。 这就是为什么我会告诉重复数据删除不排序在这里。
因此，我们必须在XMM寄存器4个32位元素。 他们撰写6双的总额。 因为我们只能比较在同一时间四个要素，我们至少需要两个比较。 事实上，这是很容易做到在两个XMM比较，让每一对元素的比较得到至少一次。 之后，我们可以通过使用提取的比较16位位掩码_mm_movemask_epi8 ，并将它们连接成一个单一的32位整数。 请注意，每个4位块将包含相同比特是肯定的，而最后两个4位的块不是必需的（它们对应于过度比较）。
理想情况下，我们需要从这个位掩码提取位于编译时已知位置正好6位。 它可以很方便地实现_pext_u32从BMI2指令集的内在。 其结果是，我们在范围[0..63]含有6个比特的整数，每个位表示相应的一对元件是否等于。 然后，我们从加载预计算的64项查找表洗牌面具，用我们的洗牌输入向量_mm_shuffle_epi8 。
不幸的是，BMI指令是很新（Haswell的和更高版本），我没有他们=）为了摆脱它，我们可以尝试创建一个非常简单和快速完善哈希函数的所有64有效位掩码（召回该位掩码是32位）。 对于类的哈希函数f(x) = (a * x) >> (32-b)通常是可以构建一个相当小的完美散列，用2x或3x内存开销。 由于我们的情况下是特别的，有可能构建一个最小完美散列函数，以便查找表具有最小的64个条目（即，大小= 1 KB）。
相同的算法不是8个元素（在XMM寄存器例如，16位整数）是可行的，因为有28个元素对，这意味着查寻表必须包含至少2 ^ 28的条目。
在一个YMM寄存器使用这种方法对64位元素也存在问题。 _mm256_shuffle_epi8内在没有帮助，因为它只是执行两个独立的128位洗牌（横跨车道从未洗牌）。 _mm256_permutevar8x32_epi32固有执行的32位的块的任意洗牌，但是它不能插入零。 为了使用它，你必须存储在LUT的独特元素的人数太多。 然后，你必须手动置零到您的注册较高的部分。
我已经意识到，使用BMI2对位提取或完善哈希函数是没有必要的，我们可以简单地使用_mm_movemask_ps提取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)
天真的解决方案
基于所述最大（）操作粗伪代码。 注释跟踪对于第一次迭代中的数据。
A = RIN //{3, 9, 2, 9}
For i = 0 .. 3:
B = Rotate(A, 1) //{9, 2, 9, 3}
C = Rotate(A, 2) //{2, 9, 3, 9}
D = Rotate(A, 3) //{9, 3, 9, 2}
RMAX = Max(A,B) //{9, 9, 9, 9}
RMAX = Max(RMAX, C) //{9, 9, 9, 9}
RMAX = Max(RMAX, D) //{9, 9, 9, 9}
ROUT[i] = RMAX[0] //ROUT = {9, null, null, null}
TMP = A
MASK = Equality(RMAX, TMP) //MASK = {0, 1, 0, 1}
MASK = Invert(MASK) //MASK = {1, 0, 1, 0}
Clear(A)
A = MoveMasked(TMP, MASK) //A = {3, null, 2, null}
一些想法：
A = RIN //{3, 9, 2, 9}
B = Rotate(A, 1) //{9, 2, 9, 3}
C = Rotate(A, 2) //{2, 9, 3, 9}
D = Rotate(A, 3) //{9, 3, 9, 2}
maskA = cmpeq(A,B) //{0, 0, 0, 0}
maskB = cmpeq(A,C) //{0, -1, 0, -1}
maskC = cmpeq(A,D) //{0, 0, 0, 0}
indexA = horSum( { 1,2,4,8 } * maskA ) // 0
indexB = horSum( { 1,2,4,8 } * maskB ) // 10
indexC = horSum( { 1,2,4,8 } * maskC ) // 0
// The problem is this function here
// Of the 4096 possible indexABC only a subset will occur
// Based on an enumeration of all possible indexes a pattern
// for an lookup table could possibly be found
shuffleConst = lookupShuffle( indexA, indexB, indexC )
shuffle(A, shuffleConst)
