Fast bitswap in assembly Can the following code to swap two bits be optimized?

  //ecx = bita, the index of the first bit to be swapped
  //edx = bitb, the index of the second bit to be swapped.
  //r8 = data, the int32 who's bits are to be swapped
  //code        ;latency //comments
  mov eax,1     ;1   
  shl eax,cl    ;1     // Set bitA
  mov ecx,[r8]  ;3     // ecx = input
  bts eax,edx   ;0     // Set bitB
  mov edx,eax   ;1     // save the mask for later
  and eax,ecx   ;0     // Let's see if bitA = BitB, if so we don't need to swap
  popcnt eax,eax ;1    // if the bits are not the same, popcount will be 1
  xor edx,ecx    ;0    // Invert the bits in the input, just in case
  sub eax,1      ;1    // is eax odd?, i.e. are the bits different?
  cmovnz ecx,edx ;2    // Bits are different, result is swapped, if not result = input
  mov [r8],ecx   ;3    // write the result


Total latency: 13 cycles.
The code exploits the fact that bit xor 1 inverts and only bits that are different need to be swapped. Still it's a lot of instructions just to swap two bits.
I'm still a bit fuzzy on how to compute latency, but using iaca v2.2, it reports your code as:

Block Throughput: 10.65 Cycles
Throughput Bottleneck: Dependency chains


I'm calling that "the number to beat."

A brief fiddle with your code gives me:

xor eax, eax
xor r10d, r10d

mov r9d, [r8]   ; read the value
btr r9d, edx    ; read and clear the edx bit

setc al         ; convert cf to bit
shl eax, cl     ; shift bit to ecx position

btr r9d, ecx    ; read and clear the ecx bit

mov ecx, edx    ; need edx in ecx for shift
setc r10b       ; convert cf to bit
shl r10d, cl    ; shift bit to edx position

or r9d, eax     ; copy in old edx bit
or r9d, r10d    ; copy in old ecx bit

mov [r8], r9d   ; store result


Which iaca describes as:

Block Throughput: 4.30 Cycles
Throughput Bottleneck: FrontEnd


That's the best I can do for the moment.



Update: Actually, I can do a bit (haha) better:

xor eax, eax        ; build a mask using both bits
bts eax, ecx
bts eax, edx

mov r9d, [r8]       ; read the value
mov r10d, r9d       ; copy the value

and r10d, eax       ; and out the 2 bits we are looking for
jpe done            ; if neither or both bits are set, we're done

xor r9d, eax        ; swap the bits
mov [r8], r9d       ; store the result

done:


jpe is a relatively uncommon instruction which means 'jump parity even.'  Parity is set by the and to indicate the parity of the result.  Parity 'even' means that an even number of bits are set (0 is even).  If an even number of bits are set, then either both bits were zero, or both bits were 1.  In either case, swapping will have no effect since the bits are the same.

iaca v2.3 rates this as:

Block Throughput: 2.00 Cycles
Throughput Bottleneck: FrontEnd


FYI: If you change this api such that the parameter is a mask containing the 2 bits to swap instead of 2 discrete parameters, the time drops to 1.24.  Not knowing the details of the caller, I'm not sure how practical that is.  If you are really working with 2 different computed values for your bit positions, moving this work up to the caller doesn't buy you anything (in fact it probably makes things worse).  But it's something to think about.

So, we started with 10.64 (OP's code).  First cut dropped that to 4.3.  Using BMI2 instructions, I dropped it to 3.  Now using common instructions again, we're down to 2.00 (with a chance at 1.24).

I'm pretty sure I'm done now.  Pretty sure.



Update 2: &lt;sigh&gt;

xor eax, eax        ; build a mask using both bits
bts eax, ecx
bts eax, edx

test [r8], eax      ; compute parity
jpe done            ; if neither or both bits are set, we're done

xor [r8], eax       ; swap the bits

done:


While I might think that loading r8 into a register, testing it, modifying it and then writing it back would be faster, iaca doesn't see it that way.  I'd probably have to test it to be sure.  I'll leave that as an exercise for the student.  Still, this gives us:

Block Throughput: 1.50 Cycles
Throughput Bottleneck: FrontEnd


If this thing gets any faster, it's going to start giving cycles back...



As OP has pointed out, the JPE that I used above only works for bits in the first byte.  Oops.

So, this is my next best:

xor r9d, r9d    ; build mask
bts r9d, ecx
bts r9d, edx

mov r10d, r9d   ; duplicate mask

and r9d, [r8]   ; Load the bits
jz done         ; neither bit set

cmp r9d, r10d   ; Both bits set?
je done

xor [r8], r10d  ; Swap the bits

done:


It's not the 1.5 I was getting above, but it's a respectable 2.00.  Still a pretty good improvement from the 10.65 we started with.

There are some things that might be worth trying when you roll this back into your original code.  While iaca is useful for counting latency, nothing beats real life tests.


I was a little bit iffy about the two jumps, but iaca doesn't much care for replacing them with cmovxx.
Seems like loading the value into a register instead of anding directly from memory, then using that register instead of xoring back into memory should have been a win.
And as I've mentioned below, writing this in C instead of asm might also be a win (nb: MSVC's _bittestandset doesn't optimize well, so creativity may be required).  However since this post was about asm, that's what I'm limiting myself to.




One last point:

Since this code has now gone from 'small' to 'trivial,' I'd suggest re-visiting the decision to write it in assembler.  While I doubt that a C compiler will end up using the jpe instruction, it seems likely it could do a credible job of producing code using basically this approach.

And let's not forget that there are costs associated with calling assembly code from C:


7 very valuable and scarce registers (rax, rcx, rdx, r8-r11) are assumed changed by the code (even if the asm never actually uses them).  Avoiding/spilling these has performance implications for the code making the call.
The stack must be set up/torn down (even though this code never uses the stack, by spec room must always be allocated for the first 4 parameters).
The actual call and ret statements must be executed, while an optimizer might well inline a C routine.
There is no chance that the C optimizer can interleave instructions from the surrounding code to take advantage of available ports/microfusing, or can improve the code based on compile time constant values.


Given all this, I'd expect that writing this in C using intrinsics (ie _bittestandset) would turn out to be a net win despite the fact that it might use a (slightly) less optimal set of instructions (assuming it doesn't figure out a way to do it even better).

I'm struggling with myself to NOT do this here, since it is clearly a separate question.  No wonder I can't rack up any karma.