tar*_*342 3 c++ bit-manipulation intrinsics micro-optimization
有没有办法使用内在函数来优化以下代码？它获取 16 位整数中的所有奇数索引位，并将它们尽可能向右移动。
我在想也许可以使用 Fortran 中 IHFTC 的 C++ 等效项（是否有与此等效的 C++ 版本？）。但我觉得还有更有效的方法。
int x = some16bitInt;
x = x&0x5555;
int y = 0;
for (int i = 0; i < 8; i++)
y = y | ((x >> i) & (0x01 << i));
'''
x86：pext如果可用，请使用 BMI2，Zen2 或更早版本的 AMD 除外。
否则：@jorgbrown 建议对我的 bithack 进行一个很好的改进。
或者，如果您在没有 fast 的循环中执行大量此类操作，那么在按某种pext顺序将所需的所有位打包到低 8 中之后，值得考虑 Jorg 的表查找想法，因此该表只有 256 x 1 字节条目。
FortranISHFTC只是一个旋转。C 不直接具有此功能，但您可以可移植且安全地编写一个函数，该函数使编译器具有模式识别功能并编译为单个循环指令。 C++ 中循环移位（旋转）操作的最佳实践
我不确定这是一个有用的构建块，但它是可用的。
在具有 BMI2 指令集扩展的 x86 上，有一个pext位提取指令，您可以将其与0x5555控制输入一起使用。请参阅英特尔的文档以了解_pext_u32和_u64
它在 Intel Haswell 及更高版本上非常快（1 uop、3 个周期延迟、1/时钟吞吐量），但在 Zen 3 之前的 AMD 上
相当慢（Zen1/2：7 uop、18 个周期延迟/吞吐量）。 https://agner.org/optimize/和https://uops.info/。我认为这比我使用纯 C 提出的移位/掩码内容更糟糕，特别是如果延迟很重要或在循环中执行此操作（不仅仅是前端吞吐量）。
#include <immintrin.h>
// Good on Intel, and AMD Zen3 and later.
unsigned extract_even_bits_bmi2(unsigned a) {
return _pext_u32(a, 0x5555);
}
使用 GCC / clang，您必须使用-mbmi2（或更好，-march=haswell）进行编译才能使用 BMI2 内在函数。
我认为通常的乘法技巧（将多个输入字节移位并添加到结果的最高字节中）在这里不起作用；你有太多的位，而且它们距离太近。请参阅如何计算 32 位整数中设置的位数？对于用例：
((n & 0x0F0F0F0F) * 0x01010101) >> 24水平添加 中的所有字节n。
您可以想象在输入上使用类似的东西来以* 0x08040201不同的方式对齐不同字节的位。但这仍然留下了重大未解决的问题。也许 SIMD 与 8 位元素相乘以使位对一起移位？
但这并不比通过屏蔽、移位以及对移动的位与不移动的位进行“或”或“加”来移动位更好。 通过大约 log2(n_bits) 个步骤，我们可以获得所有连续的位。
有多种方法可以做到这一点，请参阅Godbolt。这方面还有改进的空间，例如进行调整以更好地为一种 ISA 编译而不是另一种 ISA。例如帮助一些ARM编译器看到这0b0000011000000110只是另一个常量右移，所以它可以and r0, r1, r2, lsr #4或其他什么。
或者将位向右移动而不是向左移动，因为 ISA 无法对左侧执行任何特殊操作。
unsigned pack_even_bits16_v2(unsigned x)
{
// ARM / ARM64: repeat these bit-patterns to fill 32 bits,
// so they fit in an immediate for AND.
// but that's worse for other RISCs like PowerPC
x &= 0x5555; // 0a0b0c0d0e0f0g0h
x += x<<1; // aabbccddeeffgghh // x86 LEA eax, [rdi + rdi*2]
unsigned move = x & 0b0000011000000110; // bits to move
unsigned keep = x & 0b0110000001100000; // bits to keep
x = keep + (move << 2); // 0abcd000 0efgh000
// 0abcd000 0efgh000 // with byte boundary shown
unsigned tmp = x >> 7; // high group into place, shifting out the low bits
x &= 0xFF; // grab the whole low byte ; possibly with a zero-latency movzx
x = (x>>3) | tmp;
return x;
}
我向左移动低位而不是向右移动高位，因为 x86 可以使用一条指令 LEA 进行左移和加法。在其他 ISA 上，它可能会在最后保存一个移位以将位向右移动。
这对于 AArch64 和 PowerPC64 以及 x86 来说编译得非常好。Clang 看透了 PowerPC 的位操作，并使用强大的rlwinm（旋转左字立即与掩码）和rlwimi（...掩码插入）指令:)至少它做到了。不幸的是，当前的 clang trunk 现在mulli在 rlwinm + 3x rlwimi 之前执行两个乘法指令；下面的汇编来自这个答案是新的。
# clang trunk -O3 for PowerPC64.
# Compiling the x += x & 0x1111; version, not the x += x<<1 version where we get a multiply
andi. 4, 3, 21845 # x & 0x5555
andi. 3, 3, 4369 # x & 0x1111
add 4, 4, 3 #
rlwinm 3, 4, 31, 30, 31 # isolate the low 2 bits. PPC counts bits from MSB=0 LSB=31 for 32-bit registers
rlwimi 3, 4, 29, 28, 29 # insert the next 2-bit bitfield
rlwimi 3, 4, 27, 26, 27 # ...
rlwimi 3, 4, 25, 24, 25
blr
最好是成对组合而不是形成一个大链条。
掩码保留一些位，然后将其添加到原始位，将清除原始位置并产生左进位一位。假设下一个更高的空间已经被清零，这会移动这些位，同时保留其他位。
这还使用内联asm来解决 GCC/clang 错过的优化，它们不仅仅movzx在 x86 上使用零扩展字节。似乎重新安排了一些周围的逻辑，最终花费了更多的指令。
unsigned pack_even_bits16_jorg(unsigned x) {
// x = ?a?b?c?d ?e?f?g?h
x &= 0b01010101'01010101;
// x = 0a0b0c0d 0e0f0g0h
x += (x & 0b00010001'00010001); // move bits left by adding to themselves
// x = 0ab00cd0 0ef00gh0
x += x << 2;
// x = 0abcdcde fefghgh0
x >>= 3;
// x = 0000abcd cdefefgh
x &= 0b00001111'00001111;
// x = 0000abcd 0000efgh
unsigned out;
#if 0 || !defined(__GNUC__) || !( defined(__x86__)||defined(__x86_64__) )
out = (unsigned char)x; // MSVC correctly uses MOVZX here.
#else // Work around gcc/clang missed optimization. TODO: __builtin_constant_p(x) to use pure C for constprop.
asm("movzb {%b1, %0 | %0, %b1}" : "=r"(out) : "r"(x)); // AT&T | Intel dialect alternatives so it compiles ok with -masm=intel
// alternatively shl $4, %ah ; or %ah, %al avoids a movzx if you only need the low byte. But that writes AH, renaming it separately on Intel.
#endif
out += x >> 4;
return out;
}
在 Godbolt 上查看它和测试代码。它对于 ARM64 的编译效果同样好，对于 PowerPC 的编译效果更好，对于 x86 / x86-64 的编译效果更好。如果您将 AND 常量模式调整为重复到 32 位，那么对于 ARM64 可能会更好，这样 GCC 就可以将它们用作立即数。
移动位的另一种方法是使用 XOR 将所选位归零，然后通过移位和加法将它们移位并存放到其他位置。
unsigned tmp = x & mask;
x += tmp; // left shift those bits
x += tmp<<1; // left shift them again. (x86 can do this with LEA eax, [rax + rdx*2])
或者
unsigned tmp = x & 0b0000011000000110; // bits to move
x ^= tmp; // clear those bits
x += tmp << 2; // LEA eax, [eax + edx*4] 1 fast instruction on x86
当仅移动 2 个位置时，add + shift-and-add 与 xor + shift-and-add 的依赖链长度基本相同。
但是有条件地清除旧位而不是使用相反的掩码可能更糟。至少如果相反的掩码适合立即数，或者 ISA 有 ANDNOT 指令。或者对于 ARM，移位掩码。旧的方法有两种x可以并行运行，而tmp = x & mask; x ^= tmp如果按照编写的方式进行编译，则可以使用数据依赖性序列化执行。（事实并非如此；gcc 和 clang 足够聪明，知道 XOR 的作用并无条件清除这些位。）
| 归档时间： |
|
| 查看次数： |
991 次 |
| 最近记录： |