时间戳

首页 > 解决方案 > 使用内部函数提取和移位奇数/偶数位

c++ - 使用内部函数提取和移位奇数/偶数位

问题描述

有没有办法使用内在函数优化以下代码？它采用 16 位整数中的所有奇数索引位，并将它们尽可能向右移动。

我在想也许可以使用 Fortran 的 ISHFTC 的 c++ 等价物（甚至有一个 c++ 等价物吗？）。但我觉得有一种更有效的方法。

int x = some16bitInt;
x = x&0x5555;
int y = 0;
for (int i = 0; i < 8; i++)
    y = y | ((x >> i) & (0x01 << i));
'''

标签： c++bit-manipulationintrinsicsmicro-optimization

解决方案

  • x86：使用 BMI2（pext如果可用），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 内在函数。

可移植的 ISO C++

我认为通常的乘法技巧（将多个输入字节移位并添加到结果的顶部字节中）在这里不起作用；你有太多的位，他们太靠近了。请参阅如何计算 32 位整数中设置的位数？对于用例：
((n & 0x0F0F0F0F) * 0x01010101) >> 24水平添加n.

你可以想象在你的输入上使用类似的东西来* 0x08040201以不同的方式对齐来自不同字节的位。但这仍然留下了重大的未解决问题。也许 SIMD 与 8 位元素相乘以使成对的位移到一起？

但这并不比通过屏蔽、移位和 ORing 或将移动的位与不移动的位相加来移动位更好。 通过大约 log2(n_bits) 步，我们可以让所有位连续。

有多种方法可以做到这一点，请参阅Godbolt。这方面还有改进的余地，比如调整以更好地为一个 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(Rotate Left Word Immediate AND Mask) 和rlwimi(... Mask Insert) 指令:) 至少它做到了。mulli不幸的是，在 rlwinm + 3x rlwimi 之前，当前的 clang 主干现在正在执行两个乘法指令；下面的 asm 来自这个答案是新的。

# 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

组合成对而不是形成一个大链会更好。

Jorg 的改进版本：通过添加自身来移动位

屏蔽以保留一些位，然后将其添加到原始位置，将清除原始位置并产生一个左进位。假设下一个更高的空间已经归零，这会移动这些位，同时将其他位留在原处。

这也使用内联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 做了什么并无条件地清除这些位。）

推荐阅读