6
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You are correct about the inline assembly subroutine drawback. As soon as a add a ret to the code, it slows down to 6,67 cycles. There is problem with using the parity flag. It only tests the LSB for parity. As such it will fail when bits 2 and 9 will be swapped. Clever as update2 it is broken, because the parity flag is broken :-< This also makes update 1 broken. \$\endgroup\$ – Johan Sep 14 '17 at 10:03
  • 1
    \$\begingroup\$ Well, nuts. I really liked that solution. I had test code, but clearly not enough. I've got an alternate (no JPE) that gets me down to 2.29, but I'll want to look at it again. \$\endgroup\$ – David Wohlferd Sep 14 '17 at 10:19
  • \$\begingroup\$ @Johan Is using BMI acceptable? \$\endgroup\$ – David Wohlferd Sep 14 '17 at 11:15
  • \$\begingroup\$ Not like it matters. I've got 2 solutions (one with BMI, one w/o) that both clock in at 2.86. \$\endgroup\$ – David Wohlferd Sep 14 '17 at 11:41
  • \$\begingroup\$ I see one option that works (your top solution that runs in 4.3 and the BMI2 below that clocks at 3.0. The two other listings don't work. Where do you see the 2.86 ? \$\endgroup\$ – Johan Sep 14 '17 at 13:48
4
\$\begingroup\$

My other answer gives improved latency using instructions available on all x86_64 processors.

However you didn't specify a target CPU. If I can assume that the CPU supports BMI2, I can do even better (note the use of shlx):

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
shlx eax, eax, ecx  ; shift to ecx position (no flags)

btr r9d, ecx            ; read and clear the ecx bit
setc r10b               ; convert cf to bit
shlx r10d, r10d, edx    ; shift to edx position (no flags)

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

mov [r8], r9d

Using the same version of iaca as above (v2.2), this gives me:

Block Throughput: 3.10 Cycles
Throughput Bottleneck: FrontEnd, Port0, Port6

Upgrading to the new version of iaca (v2.3) which defaults to Architecture - SKL instead of Architecture - BDW, I get:

Block Throughput: 3.00 Cycles
Throughput Bottleneck: FrontEnd

3 cycles is getting pretty small. I'm not sure I can beat that.

\$\endgroup\$
  • \$\begingroup\$ BMI1/2 sure is cool unfortunately it's out for me because of portability issues. \$\endgroup\$ – Johan Sep 14 '17 at 13:49
0
\$\begingroup\$

You might want to look into delta swaps. They may not apply for your purposes, I'm not sure as I'm not exactly a pro at assembly, but it can certainly do a fast swap of 2 bits, or more provided the distance between the bits that need to be swapped is the same distance apart.

example

  //rdi = input
  //rsi = bit0
  //rdx = bit1
  mov eax, 1
  shlx rax, rax, rsi
  shrx rcx, rdi, rdx
  xor rcx, rdi
  and rcx, rax
  xor rdi, rcx
  shlx rax, rcx, rdx
  xor rax, rdi         //output in rax
  ret

At the very least it's a very versatile tool to have.

\$\endgroup\$
  • \$\begingroup\$ I'm quite sure it's relevant, though of course I could be mistaken, and as for the lag of a quote, ya I suppose it is sort of bad style, but I'm simply not adept enough at assembly to know exactly what part is relevant to the OP. Implementation after all matters. \$\endgroup\$ – Zacariaz Dec 5 '17 at 21:53
  • \$\begingroup\$ Sorry - I was trimming down an auto-response. Good work! \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Dec 5 '17 at 21:55
  • \$\begingroup\$ No need to be sorry, it was in no way an inappropriate response, but appreciated just the same. \$\endgroup\$ – Zacariaz Dec 5 '17 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.