Using bts assembly instruction with gcc compiler

Question

I want to use the bts and bt x86 assembly instructions to speed up bit operations in my C++ code on the Mac. On Windows, the _bittestandset and _bittest intrinsics work well, and provide significant performance gains. On the Mac, the gcc compiler doesn't seem to support those, so I'm trying to do it directly in assembler instead.

Here's my C++ code (note that 'bit' can be >= 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;
}

The following assembler code works, but is not optimal, as the compiler can't optimize register allocation:

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

Question: How do I get the compiler to fully optimize around the bts instruction? And how do I replace TestBit by a bt instruction?

Answer 1

BTS (and the other BT* insns) with a memory destination are slow. (>10 uops on Intel). You'll probably get faster code from doing the address math to find the right byte, and loading it into a register. Then you can do the BT / BTS with a register destination and store the result.

Or maybe shift a 1 to the right position and use OR with with a memory destination for SetBit, or AND with a memory source for TestBit. Of course, if you avoid inline asm, the compiler can inline TestBit and use TEST instead of AND, which is useful on some CPUs (since it can macro-fuse into a test-and-branch on more CPUs than AND).

This is in fact what gcc 5.2 generates from your C source (memory-dest OR or TEST). Looks optimal to me (fewer uops than a memory-dest bt). Actually, note that your code is broken because it assumes unsigned long is 32 bits, not CHAR_BIT * sizeof(unsigned_long). Using uint32_t, or char, would be a much better plan. Note the sign-extension of eax into rax with the cqde instruction, due to the badly-written C which uses 1 instead of 1UL.

Also note that inline asm can't return the flags as a result (except with a new-in-gcc v6 extension!), so using inline asm for TestBit would probably result in terrible code code like:

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

Modern compilers can and do use BT when appropriate (with a register destination). End result: your C probably compiles to faster code than what you're suggesting doing with inline asm. It would be even faster after being bugfixed to be correct and 64bit-clean. If you were optimizing for code size, and willing to pay a significant speed penalty, forcing use of bts could work, but bt probably still won't work well (because the result goes into the flags).

Answer 2

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

Answer 3

This version efficiently returns the carry flag (via the gcc-v6 extension mentioned by Peter in the top answer) for a subsequent test instruction. It only supports a register operand since use of a memory operand is very slow as he said:

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;
}

Use in code is then like so. The wasSet variable is optimized away and the produced assembly will have bts followed immediately by jb instruction checking the carry flag.

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

Although it seems a bit contrived, this does save me several instructions vs the "1ULL << bitToTest" version.

Answer 4

Another slightly indirect answer, GCC exposes a number of atomic operations starting with version 4.1.