我有一个看似简单的问题。将一个字符串加载到__m128i寄存器中(使用_mm_loadu_si128),然后找到字符串的长度(使用_mm_cmpistri)。现在,假设长度小于16,我想在字符串末尾的零后面只有零。实现这个目标的一种方法是将'len'个字节复制到另一个寄存器中,或者将原始寄存器与一个长度为8 * len的1s掩码进行AND运算。但是很难找到一个简单的方式来创建这样的掩码,使它仅取决于刚刚计算的长度。
// Load 16 bytes and propagate the first zero towards the end of the register
inline __m128i loadNullTerminated( const char* pointer )
{
// Load 16 bytes
const __m128i chars = _mm_loadu_si128( ( const __m128i* )pointer );
const __m128i zero = _mm_setzero_si128();
// 0xFF for bytes that were '\0', 0 otherwise
__m128i zeroBytes = _mm_cmpeq_epi8( chars, zero );
// If you have long strings and expect most calls to not have any zeros, uncomment the line below.
// You can return a flag to the caller, to know when to stop.
// if( _mm_testz_si128( zeroBytes, zeroBytes ) ) return chars;
// Propagate the first "0xFF" byte towards the end of the register.
// Following 8 instructions are fast, 1 cycle latency/each.
// Pretty sure _mm_movemask_epi8 / _BitScanForward / _mm_loadu_si128 is slightly slower even when the mask is in L1D
zeroBytes = _mm_or_si128( zeroBytes, _mm_slli_si128( zeroBytes, 1 ) );
zeroBytes = _mm_or_si128( zeroBytes, _mm_slli_si128( zeroBytes, 2 ) );
zeroBytes = _mm_or_si128( zeroBytes, _mm_slli_si128( zeroBytes, 4 ) );
zeroBytes = _mm_or_si128( zeroBytes, _mm_slli_si128( zeroBytes, 8 ) );
// Now apply that mask
return _mm_andnot_si128( zeroBytes, chars );
}
更新:这里还有另一种版本,使用了Noah有关那个int64 -1
指令的想法。可能稍微快一些。反汇编。
__m128i loadNullTerminated_v2( const char* pointer )
{
// Load 16 bytes
const __m128i chars = _mm_loadu_si128( ( const __m128i* )pointer );
const __m128i zero = _mm_setzero_si128();
// 0xFF for bytes that were '\0', 0 otherwise
const __m128i zeroBytes = _mm_cmpeq_epi8( chars, zero );
// If you have long strings and expect most calls to not have any zeros, uncomment the line below.
// You can return a flag to the caller, to know when to stop.
// if( _mm_testz_si128( eq_zero, eq_zero ) ) return chars;
// Using the fact that v-1 == v+(-1), and -1 has all bits set
const __m128i ones = _mm_cmpeq_epi8( zero, zero );
__m128i mask = _mm_add_epi64( zeroBytes, ones );
// This instruction makes a mask filled with lowest valid bytes in each 64-bit lane
mask = _mm_andnot_si128( zeroBytes, mask );
// Now need to propagate across 64-bit lanes
// ULLONG_MAX if there were no zeros in the corresponding 8-byte long pieces of the string
__m128i crossLaneMask = _mm_cmpeq_epi64( zeroBytes, zero );
// Move the lower 64-bit lanes of noZeroes64 into higher position
crossLaneMask = _mm_unpacklo_epi64( mask, crossLaneMask );
// Update the mask.
// Lower 8 bytes will not change because _mm_unpacklo_epi64 copied that part from the mask.
// However, upper lane may become zeroed out.
// Happens when _mm_cmpeq_epi64 detected at least 1 '\0' in any of the first 8 characters.
mask = _mm_and_si128( mask, crossLaneMask );
// Apply that mask
return _mm_and_si128( mask, chars );
}
pslldq/por
依赖链的周期可能比pmovmskb / bsf / load低1或2个周期的延迟。但是这些操作需要8个uops,如果您没有AVX进行非破坏性复制和移位,则需要另外4个movdqa uops。(您可以使用_mm_shuffle_epi32
来进行4字节和8字节粒度的复制和移位,以避免这种情况,因为将低4或8字节保持不变而不是移入零以提供OR是可以的) - Peter Cordes(SRC-1) XOR (SRC)
(如blsmsk)可以设置qword中最低位以下的所有位,如果我们使用psubq
(或带有-1的paddq
)。 如果我们可以从两个8字节半扩展到16字节向量,我们只需与其进行AND运算即可。 - Peter Cordespcmpeqd
/ psrlq
按63便宜地生成1,1
,并从中获得0,1
,但编译器将constprop&load。 - Peter Cordes4a,61,63,65,6b,00,00,00,63,65,6b,20,00,00,00,00
- Jacek Ambroziakstatic const __m128i ZERO =
_MM_SETR_EPI32(0u, 0u, 0u, 0u);
static const __m128i INDEXES =
_MM_SETR_EPI8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
static const __m128i ONES = _MM_SETR_EPI32(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF);
_Alignas(32) static unsigned char MASK_SOURCE[32] =
{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF};
static __m128i mask_string1(__m128i input, uint32_t *const plen) {
const __m128i zeros = _mm_cmpeq_epi8(input, ZERO);
if (_mm_testz_si128(zeros, zeros)) {
*plen = 16;
return input;
} else {
const uint32_t length = _tzcnt_u32(_mm_movemask_epi8(zeros));
*plen = length;
return
length < 15 ?
_mm_and_si128(input, _mm_loadu_si128((__m128i_u *) (MASK_SOURCE + (16 - length)))) :
input;
}
}
static __m128i mask_string2(__m128i input, uint32_t *const plen) {
__m128i zeros = _mm_cmpeq_epi8(input, ZERO);
if (_mm_testz_si128(zeros, zeros)) {
*plen = 16;
return input;
} else {
const uint32_t length = _tzcnt_u32(_mm_movemask_epi8(zeros));
*plen = length;
if (length < 15) {
zeros = _mm_or_si128(zeros, _mm_slli_si128(zeros, 1));
zeros = _mm_or_si128(zeros, _mm_slli_si128(zeros, 2));
zeros = _mm_or_si128(zeros, _mm_slli_si128(zeros, 4));
zeros = _mm_or_si128(zeros, _mm_slli_si128(zeros, 8));
// Now apply that mask
return _mm_andnot_si128(zeros, input);
} else {
return input;
}
}
}
static __m128i mask_string3(__m128i input, uint32_t *const plen) {
const __m128i zeros = _mm_cmpeq_epi8(input, ZERO);
if (_mm_testz_si128(zeros, zeros)) {
*plen = 16;
return input;
} else {
const uint32_t length = _tzcnt_u32(_mm_movemask_epi8(zeros));
*plen = length;
return
length < 15 ?
_mm_andnot_si128(_mm_cmpgt_epi8(INDEXES, _mm_set1_epi8(length)), input) :
input;
}
}
__m128i set_zeros_3(__m128i v, uint32_t *plen) {
// cmp zeros
__m128i eq_zero = _mm_cmpeq_epi8(ZERO, v);
if (_mm_testz_si128(eq_zero, eq_zero)) {
*plen = 16;
return v;
} else {
*plen = _tzcnt_u32(_mm_movemask_epi8(eq_zero));
#ifdef COND
if (_mm_testz_si128(eq_zero, eq_zero)) {
return;
}
#endif
__m128i eq_zero64 = _mm_cmpeq_epi64(eq_zero, ZERO);
__m128i mask64_1 = _mm_unpacklo_epi64(ONES, eq_zero64);
// add(-1) / sub(1)
__m128i partial_mask = _mm_add_epi64(eq_zero, ONES);
#if defined __AVX512F__ && defined __AVX512VL__
__m128i result =
_mm_ternarylogic_epi64(partial_mask, mask64_1, v, (1 << 7));
#else
__m128i mask = _mm_and_si128(mask64_1, partial_mask);
__m128i result = _mm_and_si128(mask, v);
#endif
return result;
}
}
_mm_movemask_epi8
的输出分配给一个变量,并在该变量上测试0。_mm_testz_si128
的延迟为3个uops,与_mm_movemask_epi8
+testl; jz
相同。_mm_movemask_epi8
位于port0上,因此它占用了一个执行单元,否则该单元将用于关键路径依赖链。 - Noah
pcmpeqb
/pmovmskb
/tzcnt
会给你一个位置,然后你可以使用它来索引一个滑动窗口到一个缓冲区中的0xff, ..., 0 ...
或类似的内容,以获取一个 AND 掩码。例如:Vectorizing with unaligned buffers: using VMASKMOVPS: generating a mask from a misalignment count? Or not using that insn at all。 - Peter Cordesalignas(32)
),在Nehalem及更高版本的Intel CPU以及最近的AMD上,未对齐访问将不会有任何惩罚。如何在x86_64上准确基准测试未对齐访问速度。 - Peter Cordespcmpistri
),但实现了你所说的目标。如果您知道__m128i
包含零,那么如果有一个技巧可以仅使用SIMD指令创建__m128i not_zero
掩码,它可能也可以得到改进。 - Noah