使用gcc编译器和bts汇编指令

Question

我希望在Mac上使用bts和bt x86汇编指令来加速C++代码中的位操作。在Windows上，_bittestandset和_bittest内置函数表现良好，并提供了显著的性能提升。但是，在Mac上，gcc编译器似乎不支持这些函数，所以我尝试直接使用汇编语言来实现。

以下是我的C++代码（请注意，“bit”可以大于等于32）：

typedef unsigned long LongWord;
#define DivLongWord(w) ((unsigned)w >> 5)
#define ModLongWord(w) ((unsigned)w & (32-1))

inline void SetBit(LongWord array[], const int bit)
{
   array[DivLongWord(bit)] |= 1 << ModLongWord(bit);
}

inline bool TestBit(const LongWord array[], const int bit)
{
    return (array[DivLongWord(bit)] & (1 << ModLongWord(bit))) != 0;
}

以下汇编代码可以工作，但并不是最优的，因为编译器无法优化寄存器分配:

inline void SetBit(LongWord* array, const int bit)
{
   __asm {
      mov   eax, bit
      mov   ecx, array
      bts   [ecx], eax
   }
}

问题：我该如何让编译器在bts指令周围进行完全优化？我该如何用bt指令替换TestBit？

- smartgo

---

不是直接回答，而是一个指向<a href="http://www.cims.nyu.edu/cgi-systems/info2html?(gcc)Extended%2520Asm">GCC扩展汇编</a>文档的链接。 - Nikolai Fetissov

BT*带有内存操作数是慢的，因为CISC语义很疯狂。实际上，让编译器发出移位/OR（或TEST）指令序列比使用此代码更快。（至少针对这个已经修复漏洞并且64位清洁版本的代码而言）。 - Peter Cordes

有关BT*（和其他）指令的性能，请参见：https://www.agner.org/optimize/ - fviktor

Answer 1

BTS（以及其他 BT* 指令）的内存目标很慢。 （在 Intel 上>10 uops）。您可能会通过执行地址计算来查找正确的字节，并将其加载到寄存器中来获得更快的代码。然后，您可以使用寄存器目标进行 BT / BTS 并存储结果。

或者也可以将 1 向右移动到正确的位置，并使用内存目标的 OR 进行 SetBit，或者使用内存源的 AND 进行 TestBit。当然，如果避免使用内联汇编，编译器可以内联 TestBit 并使用 TEST 而不是 AND，这在某些 CPU 上非常有用（因为它可以在更多的 CPU 上实现测试和分支）。

实际上，这就是 gcc 5.2 从您的 C 源代码生成的内容（内存目标的 OR 或 TEST）。看起来对我来说是最优的（比内存目标的 bt 少了几个 uops）。实际上，请注意，您的代码存在问题，因为它假设 unsigned long 是 32 位而不是 CHAR_BIT * sizeof(unsigned_long)。使用 uint32_t 或 char 将是一个更好的计划。请注意，由于使用了1而不是 1UL，C 语言编写的不好，导致了将 eax 扩展为 rax 的符号扩展。

还请注意，除非使用gcc v6 中的新扩展！，否则内联汇编无法将标志作为结果返回。因此，对于 TestBit 使用内联汇编可能会导致像这样的可怕代码：

...  ; inline asm
bt   reg, reg
setc al       ; end of inline asm
test al, al   ; compiler-generated
jz bit_was_zero

现代编译器可以在适当的情况下（使用寄存器目标）使用BT。最终结果：你的C代码可能会编译成比你用内联汇编建议做的更快的代码。如果进行了修复以正确并具有64位清洁性，它将更快。如果你优化代码大小，并愿意承担显著的速度惩罚，则强制使用bts可能会起作用，但bt可能仍然不太好（因为结果进入标志）。

- Peter Cordes

---

实际上，从v6版本开始，gcc可以返回标志位。 - David Wohlferd

@DavidWohlferd：谢谢！他们终于包含了那个，真有趣。 - Peter Cordes

@PeterCordes 你曾经看过编译器生成'bts'的情况吗？我可以至少让clang和icc为"test bit"类型函数生成bt，但尝试使用bts则没有成功，尽管相对于使用'shl'或'shlx'和'or'以及一些额外的操作来加载常量'1'等，这似乎非常有用于"set bit"类型函数。 - BeeOnRope

@BeeOnRope：我忘了。你描述的听起来很熟悉：使用bt测试位，但未使用bts设置位。我相信至少在Intel CPU上，对于像foo |= 1<<n这样的东西是有优势的，其中n不是编译时常量，而foo已经在寄存器中了。是的，我刚刚测试了一下，没有运气：https://godbolt.org/g/9s6i9D - Peter Cordes

是的，那正是我在godbolt链接中测试的习语。我确实找到了一种只能在icc上生成bts的方法，特别是在编译时位索引的情况下。在那里，gcc和clang都不使用bts，而且如果位置是可变的话，icc也不使用它（在这种情况下，它甚至更有用，因为变量移位的非bts代码通常比常量情况下慢得多，尤其是在SHLX之前）。 - BeeOnRope

Answer 2

inline void SetBit(*array, bit) {
    asm("bts %1,%0" : "+m" (*array) : "r" (bit));
}

- ephemient

---

太好了，谢谢。这帮助我解决了我的第二个问题：内联函数 bool TestBit(const LongWord array[], const int bit) { bool flag; asm("bt %2,%1; setb %0" : "=q" (flag) : "m" (*array), "r" (bit)); return flag; } - smartgo

@ephemient：您能否请在您的回答中添加解释。 - arunmoezhi

如果 bit 可能超出 0..31 范围，你的内存操作数应该是整个数组，而不仅仅是它的第一个元素。（记住 bts 的疯狂 CISC 位串语义，带有内存操作数。）此外，你应该让源操作数为 "ri"，因为它适用于立即操作数（并且这样速度要快得多）。但实际上，在现代 x86 上根本不应该使用这个。带有内存操作数的 bts 是慢的（请参见我的答案）。 - Peter Cordes

这条指令会破坏C标志，但汇编代码中并没有说明。 - Maxim Egorushkin

@MaximEgorushkin：对于x86和x86-64的GNU C内联汇编，"cc"清除器是隐含的。虽然有些人认为手动指定它是一种好的风格，但这并不是一个错误。 - Peter Cordes

Answer 3

此版本通过Peter在顶部回答中提到的gcc-v6扩展高效地返回进位标志，以供后续测试指令使用。它仅支持寄存器操作数，因为使用内存操作数非常缓慢，如他所说：

int variable_test_and_set_bit64(unsigned long long &n, const unsigned long long bit) {
    int oldbit;
    asm("bts %2,%0"
        : "+r" (n), "=@ccc" (oldbit)
        : "r" (bit));
    return oldbit;
}

在代码中使用的方式就像这样。wasSet变量被优化掉了，生成的汇编代码将有bts指令紧随其后，然后是检查进位标志的jb指令。

unsigned long long flags = *(memoryaddress);
unsigned long long bitToTest = someOtherVariable;
int wasSet = variable_test_and_set_bit64(flags, bitToTest);
if(!wasSet) {
  *(memoryaddress) = flags;
}

虽然看起来有点牵强，但这比“1ULL << bitToTest”版本节省了我几条指令。

- muusbolla

---

很好，感谢您写下这篇文章。理想情况下，GCC在优化纯C时应该自己使用bts reg,reg，在一些情况下它确实这样做了（比如非指针），但是对于mem[pos/32] |= 1<<(pos%32)却没有（https://godbolt.org/z/an6W1nqTq）。它已经存在这个未优化的bug多年了；clang也是如此。相关：https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80813，关于使用`bt`来只读检查位数组。 - Peter Cordes

Answer 4

另一个稍微间接的答案是，GCC 从4.1版本开始公开了一些原子操作。

- D.Shawley