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: <sigh>
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.
