计算两个 _m128i SIMD 向量之间的匹配字节数
Count number of matching bytes between two _m128i SIMD vectors
我正在开发一个生物信息学工具，我正在尝试使用 SIMD 来提高它的速度。
给定两个长度为 16 的字符数组，我需要快速计算字符串匹配的索引数。例如，以下两个字符串“TTTTTTTTTTTTTTTTT”和“AAAAGGGGTTTTCCCC”匹配第 9 到第 12 个位置（“TTTT”），因此输出应为 4.
如下函数foo所示（运行正常但速度较慢），我将seq1和seq2中的每个字符打包到__m128i变量s1和s2中，并使用_mm_cmpeq_epi8比较每个位置同时。然后，使用 popcnt128（来自 Marat Dukhan 的Fast counting the number of set bits in __m128i register）将匹配位数相加。
float foo(char* seq1, char* seq2) {
__m128i s1, s2, ceq;
int match;
s1 = _mm_load_si128((__m128i*)(seq1));
s2 = _mm_load_si128((__m128i*)(seq2));
ceq = _mm_cmpeq_epi8(s1, s2);
match = (popcnt128(ceq)/8);
return match;
}
尽管 Marat Dukhan 的 popcnt128 比天真地将 __m128i 中的每一位相加要快得多，但 __popcnt128() 是函数中最慢的瓶颈，约占计算量的 80%速度。所以，我想想出一个 popcnt128 的替代方案。
我试图将 __m128i ceq 解释为一个字符串，并将其用作预先计算的查找 table 的键，该查找将字符串映射到总位数。如果 char 数组是可散列的，我可以做类似
union{__m128i ceq; char c_arr[16];}
match = table[c_arr] // table = unordered map
如果我尝试对字符串执行类似的操作（即 union{__m128i ceq; string s;};），我会收到以下错误消息“::()”被隐式删除，因为默认定义的格式不正确”。当我尝试其他事情时，我 运行 陷入分段错误。
有什么方法可以告诉编译器将 __m128i 读取为字符串，以便我可以直接使用 __m128i 作为 unordered_map 的键？我不明白为什么它不起作用，因为字符串是一个连续的字符数组，可以自然地用 __m128i 表示。但是我无法让它工作，也无法在线找到任何解决方案。
您可能正在为更长的序列、多个 SIMD 数据向量执行此操作。在这种情况下，您可以在向量 中累加计数 ，只在最后求和。 单独对每个向量进行 popcount 效率要低得多。
请参阅 How to count character occurrences using SIMD - 而不是 _mm256_set1_epi8(c); 来搜索特定字符，从其他字符串加载。其他一切都一样，包括
counts = _mm_sub_epi8(counts, _mm_cmpeq_epi8(s1, s2));
在内部循环中，循环展开。 （比较结果是整数 0 / -1，因此减去它会将 0 或 1 添加到另一个向量。）这在 256 次迭代后有溢出的风险，因此最多 255 次。该链接问题使用 AVX2，但 __m128i 这些内部函数的版本只需要 SSE2。 （当然，AVX2 会让你在每条向量指令上完成两倍的工作。）
使用_mm_sad_epu8(v, _mm_setzero_si128());对外循环中的字节计数器进行水平求和，然后累加到另一个计数向量中。 同样，这都在链接的问答中的代码中，所以只需 copy/paste 然后将另一个字符串的负载添加到内部循环中， 而不是使用广播常量.
Can counting byte matches between two strings be optimized using SIMD? 显示了 128 位向量的基本相同内容，包括底部的版本，它仅在内部循环后执行 SAD hsums。它已经为两个输入指针编写，而不是 char 和 string。
对于单个向量：
您不需要计算 所有 __m128i 中的位；通过将每个元素的 1 位提取为标量整数，利用每个字节中的所有 8 位都相同的事实。 （与其他一些 SIMD ISA 不同，x86 SIMD 可以高效地做到这一点）
count = __builtin_popcnt(_mm_movemask_epi8(cmp_result));
另一个可能的选项是psadbw反对0（比较结果的字节hsum），但这需要一个最后的hsum步骤，将qword减半，所以这样就可以了比 HW popcnt 还差。但是，如果您不能使用 -mpopcnt 进行编译，那么如果您需要仅使用 SSE2 的基线 x86-64，则值得考虑。 （你还需要在 psadbw 之前取反，或者将总和缩小 1/255...）
（请注意，psadbw 策略基本上是我在答案的第一部分中描述的，但仅适用于单个向量，没有利用将多个计数廉价地添加到一个向量累加器中的能力。）
如果您确实需要 float 作为结果，那么 psadbw 策略就没那么糟糕了：您可以使用 _mm_cvtepi32_ps 始终将值保留在 SIMD 向量中对水平和结果进行打包转换（甚至比 cvtsi2ss int->float 标量转换更便宜）。 _mm_cvtps_f32是免费的；标量浮点数只是 XMM 寄存器的低位元素。
但是说真的，你真的需要一个整数作为 float 现在吗？ 你至少不能等到你得到所有向量的总和，还是保持整数？
-mpopcnt 由 gcc -msse4.2 或 -march=native 暗示任何小于 10 年的事物。 Core 2 缺少硬件 popcnt，但 Nehalem 为英特尔提供了它。
我正在开发一个生物信息学工具，我正在尝试使用 SIMD 来提高它的速度。
给定两个长度为 16 的字符数组，我需要快速计算字符串匹配的索引数。例如，以下两个字符串“TTTTTTTTTTTTTTTTT”和“AAAAGGGGTTTTCCCC”匹配第 9 到第 12 个位置（“TTTT”），因此输出应为 4.
如下函数foo所示（运行正常但速度较慢），我将seq1和seq2中的每个字符打包到__m128i变量s1和s2中，并使用_mm_cmpeq_epi8比较每个位置同时。然后，使用 popcnt128（来自 Marat Dukhan 的Fast counting the number of set bits in __m128i register）将匹配位数相加。
float foo(char* seq1, char* seq2) {
__m128i s1, s2, ceq;
int match;
s1 = _mm_load_si128((__m128i*)(seq1));
s2 = _mm_load_si128((__m128i*)(seq2));
ceq = _mm_cmpeq_epi8(s1, s2);
match = (popcnt128(ceq)/8);
return match;
}
尽管 Marat Dukhan 的 popcnt128 比天真地将 __m128i 中的每一位相加要快得多，但 __popcnt128() 是函数中最慢的瓶颈，约占计算量的 80%速度。所以，我想想出一个 popcnt128 的替代方案。
我试图将 __m128i ceq 解释为一个字符串，并将其用作预先计算的查找 table 的键，该查找将字符串映射到总位数。如果 char 数组是可散列的，我可以做类似
union{__m128i ceq; char c_arr[16];}
match = table[c_arr] // table = unordered map
如果我尝试对字符串执行类似的操作（即 union{__m128i ceq; string s;};），我会收到以下错误消息“::()”被隐式删除，因为默认定义的格式不正确”。当我尝试其他事情时，我 运行 陷入分段错误。
有什么方法可以告诉编译器将 __m128i 读取为字符串，以便我可以直接使用 __m128i 作为 unordered_map 的键？我不明白为什么它不起作用，因为字符串是一个连续的字符数组，可以自然地用 __m128i 表示。但是我无法让它工作，也无法在线找到任何解决方案。
您可能正在为更长的序列、多个 SIMD 数据向量执行此操作。在这种情况下，您可以在向量 中累加计数 ，只在最后求和。 单独对每个向量进行 popcount 效率要低得多。
请参阅 How to count character occurrences using SIMD - 而不是 _mm256_set1_epi8(c); 来搜索特定字符，从其他字符串加载。其他一切都一样，包括
counts = _mm_sub_epi8(counts, _mm_cmpeq_epi8(s1, s2));
在内部循环中，循环展开。 （比较结果是整数 0 / -1，因此减去它会将 0 或 1 添加到另一个向量。）这在 256 次迭代后有溢出的风险，因此最多 255 次。该链接问题使用 AVX2，但 __m128i 这些内部函数的版本只需要 SSE2。 （当然，AVX2 会让你在每条向量指令上完成两倍的工作。）
使用_mm_sad_epu8(v, _mm_setzero_si128());对外循环中的字节计数器进行水平求和，然后累加到另一个计数向量中。 同样，这都在链接的问答中的代码中，所以只需 copy/paste 然后将另一个字符串的负载添加到内部循环中， 而不是使用广播常量.
Can counting byte matches between two strings be optimized using SIMD? 显示了 128 位向量的基本相同内容，包括底部的版本，它仅在内部循环后执行 SAD hsums。它已经为两个输入指针编写，而不是 char 和 string。
对于单个向量：
您不需要计算 所有 __m128i 中的位；通过将每个元素的 1 位提取为标量整数，利用每个字节中的所有 8 位都相同的事实。 （与其他一些 SIMD ISA 不同，x86 SIMD 可以高效地做到这一点）
count = __builtin_popcnt(_mm_movemask_epi8(cmp_result));
另一个可能的选项是psadbw反对0（比较结果的字节hsum），但这需要一个最后的hsum步骤，将qword减半，所以这样就可以了比 HW popcnt 还差。但是，如果您不能使用 -mpopcnt 进行编译，那么如果您需要仅使用 SSE2 的基线 x86-64，则值得考虑。 （你还需要在 psadbw 之前取反，或者将总和缩小 1/255...）
（请注意，psadbw 策略基本上是我在答案的第一部分中描述的，但仅适用于单个向量，没有利用将多个计数廉价地添加到一个向量累加器中的能力。）
如果您确实需要 float 作为结果，那么 psadbw 策略就没那么糟糕了：您可以使用 _mm_cvtepi32_ps 始终将值保留在 SIMD 向量中对水平和结果进行打包转换（甚至比 cvtsi2ss int->float 标量转换更便宜）。 _mm_cvtps_f32是免费的；标量浮点数只是 XMM 寄存器的低位元素。
但是说真的，你真的需要一个整数作为 float 现在吗？ 你至少不能等到你得到所有向量的总和，还是保持整数？
-mpopcnt 由 gcc -msse4.2 或 -march=native 暗示任何小于 10 年的事物。 Core 2 缺少硬件 popcnt，但 Nehalem 为英特尔提供了它。