有效地收集单个字节，以 4 的字节步长分隔
Efficiently gather individual bytes, separated by a byte-stride of 4
我正在尝试优化一种算法，该算法将处理大量数据集，这些数据集可能会从 AVX SIMD 指令中受益匪浅。不幸的是，输入内存布局对于所需的计算来说并不是最优的。必须重新排序信息，方法是从恰好相隔 4 个字节的各个字节组装 __m256i 个值：
开始编辑
我的目标 CPU 不支持 AVX2 指令，所以就像@Elalfer 和@PeterCordes 指出的那样，我不能使用 __m256i 值，代码必须转换为使用 __m128i 值相反）
编辑结束
内存中的数据集布局
Byte 0 | Byte 1 | Byte 2 | Byte 3
Byte 4 | Byte 5 | Byte 6 | Byte 7
...
Byte 120 | Byte 121 | Byte 122 | Byte 123
Byte 124 | Byte 125 | Byte 126 | Byte 127
__m256i 变量中的所需值：
| Byte 0 | Byte 4 | Byte 8 | ... | Byte 120 | Byte 124 |
除了这个简单的代码之外，还有更有效的方法来收集和重新排列跨步数据吗？
union { __m256i reg; uint8_t bytes[32]; } aux;
...
for( int i = 0; i < 32; i++ )
aux.bytes[i] = data[i * 4];
编辑：
我要优化的步骤是位列转置；换句话说，某一列的位（在我的数据排列中有 32 个可能的位列）应该成为单个 uint32_t 值，而其余位将被忽略。
我通过重新排列数据来执行转置，执行左移以将所需的位列作为每个子字节中的最高有效位，最后提取并 assemble 这些位到通过 _mm256_movemask_epi8() 内在的单个 uint32_t 值。
您可以尝试展开该循环，这至少应该去掉循环体中的一次比较 (i<32)、一次递增 (i++) 和一次乘法 (i*4)。常量数组偏移量也可能比变量稍微快一些。但请注意，您的编译器无论如何都可能会生成类似（或更好）的代码，并启用适当的编译选项。
union { __m256i reg; uint8_t bytes[32]; } aux;
...
aux.bytes[0] = data[0];
aux.bytes[1] = data[3];
...
aux.bytes[31] = data[124];
其中一种方法是 - 用 _mm256_shuffle_epi8 打包字节，混合所有 _mm256_blend_epi32 结果向量（你需要做 4 次这样的加载+随机播放），然后做一个 32 位排列 _mm256_permutevar8x32_epi32.
这是一个伪代码（希望你能想出shuffle masks）：
L1 = load32byte(buf)
L2 = load32byte(buf+32)
L3 = load32byte(buf+64)
L4 = load32byte(buf+96)
// Pack 4 bytes in the corresponding 32bit DWORD in each lane and zero-out other bytes
L1 = shuffle(L1, mask_for_L1)
L2 = shuffle(L2, mask_for_L2)
L3 = shuffle(L3, mask_for_L3)
L4 = shuffle(L4, mask_for_L4)
// Vec = blend(blend(L1,L2),blend(L3,L4))
Vec = or(or(or(L1,L2),L3),L4)
Vec = permute(Vec) // fix DWORD order in the vector
更新：忘了我说的原因 "zero-out other bytes" - 这样你就可以用 or
替换 blend
更新：根据彼得在下面的评论重新安排 or 操作，减少了一个周期的延迟。
PS。我还建议您在进行位操作时查看 BMI 指令集。
我刚刚注意到编辑，其中有一个特殊情况的答案。
如果你需要对同一个数据做很多不同的位位置，那么你现在的方案很好。
如果您只需要 128B 内存中的一位位置（尤其是最高位位置），则可以使用 _mm256_movemask_ps 从每个 32b 元素中获取高位。然后在 GP 寄存器中组合四个 8bit 掩码。
一个好的编译器应该将其优化为：
vmovdqu ymm0, [buf + 0]
; to select a different bit:
; vpslld ymm0, ymm0, count ; count can be imm8 or the low byte of an xmm register
vmovmskps eax, ymm0
vmovdqu ymm0, [buf + 32]
vmovmskps ebx, ymm0
... ecx and edx
mov ah, bl
mov ch, dl
shl ecx, 16
or eax, ecx
只有在测试高位时这才好（因此您不需要在 vmovmsk 之前移动每个向量）。即便如此，这可能比其他解决方案更多的指令（和代码大小）。
原题答案：
与 Elalfer 的想法类似，但对 pack 指令使用洗牌单元而不是 pshufb。此外，所有的 AND 都是独立的，因此它们可以并行执行。 Intel CPU 可以一次执行 3 个 AND，但只能执行一次 shuffle。 （或者在 pre-Haswell 上同时洗牌两次。）
// without AVX2: you won't really be able to
// do anything with a __m256i, only __m128i
// just convert everything to regular _mm_..., and leave out the final permute
mask = _mm256_set1_epi32(0x000000ff);
// same mask for all, and the load can fold into the AND
// You can write the load separately if you like, it'll still fold
L1 = and(mask, (buf)) // load and zero the bytes we don't want
L2 = and(mask, (buf+32))
L3 = and(mask, (buf+64))
L4 = and(mask, (buf+96))
// squish dwords from 2 concatenated regs down to words in 1 reg
pack12 = _mm256_packus_epi32(L1, L2);
pack34 = _mm256_packus_epi32(L3, L4);
packed = _mm256_packus_epi16(pack12, pack34); // note the different width: zero-padded-16 -> 8
Vec = permute(packed) // fix DWORD order in the vector (only needed for 256b version)
Vec = shift(Vec, bit_wanted)
bitvec = movemask(Vec)
// shift:
// I guess word or dword granularity is fine, since byte granularity isn't available.
// You only care about the high bit, so it doesn't matter than you're not shifting zeroes into the bottom of each byte.
// _mm_slli_epi32(Vec, imm8): 1 uop, 1c latency if your count is a compile-time constant.
// _mm_sll_epi32 (Vec, _mm_cvtsi32_si128(count)): 2uop 2c latency if it's variable.
// *not* _mm_sllv_epi32(): slower: different shift count for each element.
如果您只使用 AVX（如您所说）执行此操作，那么您将没有可用的 256b 整数指令。只需构建 128b 个向量，并在 mask 数据时得到 16b。最后不需要最终排列。
使用整数指令合并掩码：(m2<<16) | m1。如果需要，通过组合两个 32b 掩码，甚至可以达到 64b 掩码数据。
性能：这避免了使用 AVX 单独加载指令的需要，因为 vpand 可以 micro-fuse a memory operand if used with a one-register addressing mode。
- 周期 1：3
vpand 条指令。 （或者只有 2 个，如果我们在等待地址，因为只有 2 个加载端口。）
- 周期2：最后一两个
vpand，一个pack（L1，L2）
- 周期 3：下一个
pack（L3、L4）
- 第 4 周期：决赛
pack
- // 256b AVX2：置换
- 周期 5：带 imm8 计数的打包移位：1 uop，1c 延迟。
- 周期 6：移动掩码（3 个周期延迟）
延迟 = 8（SnB 及更高版本）
吞吐量：3 次随机播放 (p5)、4 次逻辑运算 (p015)、1 次移位 (p0)、1 次 pmovmsk (p0)。 4 个负载。
- SnB/IvB：9 个 ALU 微指令 -> 3c。 4 次内存读取：2c.
因此，根据您对掩码的处理方式，需要 3 个累加器来保持执行端口饱和。 (ceil(8/3) = 3.).
变量中的移位计数无法通过编译器内联/展开解析为编译时常量：延迟 = 9。移位为 p1/p5.[=25= 产生另一个 uop ]
对于 Haswell 及更高版本的 AVX2，vpermd.
还有 3 个额外的延迟
我正在尝试优化一种算法，该算法将处理大量数据集，这些数据集可能会从 AVX SIMD 指令中受益匪浅。不幸的是，输入内存布局对于所需的计算来说并不是最优的。必须重新排序信息，方法是从恰好相隔 4 个字节的各个字节组装 __m256i 个值：
开始编辑
我的目标 CPU 不支持 AVX2 指令，所以就像@Elalfer 和@PeterCordes 指出的那样，我不能使用 __m256i 值，代码必须转换为使用 __m128i 值相反）
编辑结束
内存中的数据集布局
Byte 0 | Byte 1 | Byte 2 | Byte 3
Byte 4 | Byte 5 | Byte 6 | Byte 7
...
Byte 120 | Byte 121 | Byte 122 | Byte 123
Byte 124 | Byte 125 | Byte 126 | Byte 127
__m256i 变量中的所需值：
| Byte 0 | Byte 4 | Byte 8 | ... | Byte 120 | Byte 124 |
除了这个简单的代码之外，还有更有效的方法来收集和重新排列跨步数据吗？
union { __m256i reg; uint8_t bytes[32]; } aux;
...
for( int i = 0; i < 32; i++ )
aux.bytes[i] = data[i * 4];
编辑：
我要优化的步骤是位列转置；换句话说，某一列的位（在我的数据排列中有 32 个可能的位列）应该成为单个 uint32_t 值，而其余位将被忽略。
我通过重新排列数据来执行转置，执行左移以将所需的位列作为每个子字节中的最高有效位，最后提取并 assemble 这些位到通过 _mm256_movemask_epi8() 内在的单个 uint32_t 值。
您可以尝试展开该循环，这至少应该去掉循环体中的一次比较 (i<32)、一次递增 (i++) 和一次乘法 (i*4)。常量数组偏移量也可能比变量稍微快一些。但请注意，您的编译器无论如何都可能会生成类似（或更好）的代码，并启用适当的编译选项。
union { __m256i reg; uint8_t bytes[32]; } aux;
...
aux.bytes[0] = data[0];
aux.bytes[1] = data[3];
...
aux.bytes[31] = data[124];
其中一种方法是 - 用 _mm256_shuffle_epi8 打包字节，混合所有 _mm256_blend_epi32 结果向量（你需要做 4 次这样的加载+随机播放），然后做一个 32 位排列 _mm256_permutevar8x32_epi32.
这是一个伪代码（希望你能想出shuffle masks）：
L1 = load32byte(buf)
L2 = load32byte(buf+32)
L3 = load32byte(buf+64)
L4 = load32byte(buf+96)
// Pack 4 bytes in the corresponding 32bit DWORD in each lane and zero-out other bytes
L1 = shuffle(L1, mask_for_L1)
L2 = shuffle(L2, mask_for_L2)
L3 = shuffle(L3, mask_for_L3)
L4 = shuffle(L4, mask_for_L4)
// Vec = blend(blend(L1,L2),blend(L3,L4))
Vec = or(or(or(L1,L2),L3),L4)
Vec = permute(Vec) // fix DWORD order in the vector
更新：忘了我说的原因 "zero-out other bytes" - 这样你就可以用 or
blend
更新：根据彼得在下面的评论重新安排 or 操作，减少了一个周期的延迟。
PS。我还建议您在进行位操作时查看 BMI 指令集。
我刚刚注意到编辑，其中有一个特殊情况的答案。
如果你需要对同一个数据做很多不同的位位置，那么你现在的方案很好。
如果您只需要 128B 内存中的一位位置（尤其是最高位位置），则可以使用 _mm256_movemask_ps 从每个 32b 元素中获取高位。然后在 GP 寄存器中组合四个 8bit 掩码。
一个好的编译器应该将其优化为：
vmovdqu ymm0, [buf + 0]
; to select a different bit:
; vpslld ymm0, ymm0, count ; count can be imm8 or the low byte of an xmm register
vmovmskps eax, ymm0
vmovdqu ymm0, [buf + 32]
vmovmskps ebx, ymm0
... ecx and edx
mov ah, bl
mov ch, dl
shl ecx, 16
or eax, ecx
只有在测试高位时这才好（因此您不需要在 vmovmsk 之前移动每个向量）。即便如此，这可能比其他解决方案更多的指令（和代码大小）。
原题答案：
与 Elalfer 的想法类似，但对 pack 指令使用洗牌单元而不是 pshufb。此外，所有的 AND 都是独立的，因此它们可以并行执行。 Intel CPU 可以一次执行 3 个 AND，但只能执行一次 shuffle。 （或者在 pre-Haswell 上同时洗牌两次。）
// without AVX2: you won't really be able to
// do anything with a __m256i, only __m128i
// just convert everything to regular _mm_..., and leave out the final permute
mask = _mm256_set1_epi32(0x000000ff);
// same mask for all, and the load can fold into the AND
// You can write the load separately if you like, it'll still fold
L1 = and(mask, (buf)) // load and zero the bytes we don't want
L2 = and(mask, (buf+32))
L3 = and(mask, (buf+64))
L4 = and(mask, (buf+96))
// squish dwords from 2 concatenated regs down to words in 1 reg
pack12 = _mm256_packus_epi32(L1, L2);
pack34 = _mm256_packus_epi32(L3, L4);
packed = _mm256_packus_epi16(pack12, pack34); // note the different width: zero-padded-16 -> 8
Vec = permute(packed) // fix DWORD order in the vector (only needed for 256b version)
Vec = shift(Vec, bit_wanted)
bitvec = movemask(Vec)
// shift:
// I guess word or dword granularity is fine, since byte granularity isn't available.
// You only care about the high bit, so it doesn't matter than you're not shifting zeroes into the bottom of each byte.
// _mm_slli_epi32(Vec, imm8): 1 uop, 1c latency if your count is a compile-time constant.
// _mm_sll_epi32 (Vec, _mm_cvtsi32_si128(count)): 2uop 2c latency if it's variable.
// *not* _mm_sllv_epi32(): slower: different shift count for each element.
如果您只使用 AVX（如您所说）执行此操作，那么您将没有可用的 256b 整数指令。只需构建 128b 个向量，并在 mask 数据时得到 16b。最后不需要最终排列。
使用整数指令合并掩码：(m2<<16) | m1。如果需要，通过组合两个 32b 掩码，甚至可以达到 64b 掩码数据。
性能：这避免了使用 AVX 单独加载指令的需要，因为 vpand 可以 micro-fuse a memory operand if used with a one-register addressing mode。
- 周期 1：3
vpand条指令。 （或者只有 2 个，如果我们在等待地址，因为只有 2 个加载端口。） - 周期2：最后一两个
vpand，一个pack（L1，L2） - 周期 3：下一个
pack（L3、L4） - 第 4 周期：决赛
pack - // 256b AVX2：置换
- 周期 5：带 imm8 计数的打包移位：1 uop，1c 延迟。
- 周期 6：移动掩码（3 个周期延迟）
延迟 = 8（SnB 及更高版本）
吞吐量：3 次随机播放 (p5)、4 次逻辑运算 (p015)、1 次移位 (p0)、1 次 pmovmsk (p0)。 4 个负载。
- SnB/IvB：9 个 ALU 微指令 -> 3c。 4 次内存读取：2c.
因此，根据您对掩码的处理方式，需要 3 个累加器来保持执行端口饱和。 (ceil(8/3) = 3.).
变量中的移位计数无法通过编译器内联/展开解析为编译时常量：延迟 = 9。移位为 p1/p5.[=25= 产生另一个 uop ]
对于 Haswell 及更高版本的 AVX2，vpermd.