0

I've been reading about swapping the content of variables without using a temporary variable and besides the famous xor algorithm I've found out about the XCHG instruction from assembly on x86. So I wrote this code:

void swap(int *left, int *right){
__asm__ __volatile__(
        "movl %0, %%eax;"
        "movl %1, %%ebx;"
        :
        : "r" (*left), "r" (*right)
    );
__asm__ __volatile__(
        "xchg %eax, %ebx;"
            );
__asm__ __volatile__(
        "movl %%eax, %0;"
        "movl %%ebx, %1;"
        : "=r" (*left), "=r" (*right)
    );}

It does work but then I realized the XCHG instruction is not necessary at all.

void swap(int *left, int *right){
__asm__ __volatile__(
        "movl %0, %%eax;"
        "movl %1, %%ebx;"
        :
        : "r" (*left), "r" (*right)
    );
__asm__ __volatile__(
        "movl %%ebx, %0;"
        "movl %%eax, %1;"
        : "=r" (*left), "=r" (*right)
    );}

The second function works too but nobody seems to mention swapping variables using registers so is this code considered wrong and in reality it's not really working properly? Am I missing something?

I realize this will work only for x86 but since most people have a intel x86 processor could this code be be used in any real world programming? I realize that this probably won't be any faster than a regular swap with a temporary variable but i'm asking from a theoretical point of view. If during a test or an interview someone asks me to write a function in C to swap values for a x86 machine without using a temporary variable would this code be valid or it's complete crap? Thanks you.

azertyuiopml
  • 11
  • 2
  • It's - as you suggested - crap. You're effectively using _two_ temps: the registers. If an interviewer asks you this question, I'd run away from that company. – Gene Sep 14 '14 at 21:42
  • 1
    You should be more concerned with writing clean and maintainable code. Let the compiler do it's job and if performance _does_ become an issue profile and optimize as _necessary_. If someone presented this type of code to me in an interview they would be directed to the nearest exit. – Captain Obvlious Sep 14 '14 at 21:42
  • Well, the registers are temporary variables. – Rémi Sep 14 '14 at 21:42
  • But aren't the registers used during swapping with a temp variable too? When I say no temporary variable I mean no new variable on the stack. But I guess you are right. It does look like crap and probably isn't any faster at all :) Well i'm just beginning learning C so I'm a noob :) – azertyuiopml Sep 14 '14 at 21:46
  • If an interviewer asks you for a C function then I would stick to C code unless they explicitly tell you to use assembly. – Galik Sep 14 '14 at 21:50
  • @azertyuiopml `xchg` could _only_ ever be useful if the values to be swapped were _already_ in registers, but because modern-day compilers are darn well capable of SSA-based analysis, if they need to use as operand a value in a particular register well... they'll just tell the instruction to read from that register! Also `xchg` with a memory operand implicitly locks the bus and is consequently hideously slow. – Iwillnotexist Idonotexist Sep 14 '14 at 21:52
  • @azertyuiopml It's also somewhat unconventional to split up the inline assembler into three parts like that, besides being possibly incorrect. The compiler could choose to put something in-between that uses those registers. You should make one inline assembler block contain all your swapping code, and declare that your code _clobbers_ `eax` and `ebx`. Right now you're clobbering `ebx`, which IIRC is a callee-save register, without making the compiler save and restore its old value. – Iwillnotexist Idonotexist Sep 14 '14 at 22:00

3 Answers3

5

Valid, yes. By my criteria, you are a no-hire.

Why? Cost.

std::swap will do the job fine, and is probably fast enough. Your code will have a higher maintenance cost.

There certainly are times for dropping down into assembler for performance reasons.
This is not one of them.

EvilTeach
  • 28,120
  • 21
  • 85
  • 141
  • Well I guess you're right :) Thank you for your answer. – azertyuiopml Sep 14 '14 at 21:50
  • You are welcome. I approve of your interest. Understanding assembly makes it far easier to visualize the behavior of the machine. It makes you understand and appreicate why C and C++ are the right answers for most problems. Keep studying. – EvilTeach Sep 14 '14 at 22:51
  • `std::swap` will actually be faster than this. The OP's code is slower than what a compiler would emit, as well as broken. (It clobbers EAX and EBX without telling the compiler, will easily fail especially if compiled with optimization enabled, but unsafe even without optimization.) Even if you did it with inline asm with zero asm statements and just opposite input/output constraints, you still destroy constant-propagation and range analysis, defeating optimization. Asm can only be a performance win if you do something the compiler can't already do better than you personally can. – Peter Cordes Oct 29 '18 at 03:53
1

First, your inline assembly is broken in many ways:

  • abuse of volatile, it does not mean what you wanted.
  • you don't tell the compiler you clobbered registers. (this can be fixed)
  • compiler is free to insert code in between your inline assembly block

Inline assembly is very difficult to get it right, for both programmer and compiler.

Also, inline assembly might be optimized with very careful hack, however it affect the compiler in ways that impair the optimizer's ability (register allocation, re-ordering, etc), which usually results in overall performance drop. I'm not against inline assembly (or compiler intrinsics), but it require very careful handling that make it not justify in most circumstances.

Non-maskable Interrupt
  • 3,841
  • 1
  • 19
  • 26
0

std::swap will compile to more efficient asm than this.

That code is slower than what a compiler would emit, as well as broken.

It clobbers EAX and EBX without telling the compiler, and will easily fail especially if compiled with optimization enabled, but unsafe even without optimization.

See How to write a short block of inline gnu extended assembly to swap the values of two integer variables? for an example of correct asm around xchg, and a better version that just uses constraints to swap C variable with zero asm instructions, leaving up to the compiler to figure out which registers it wants which C variable in. asm("" : "=r" (a), "=r" (b) : "1" (a), "0" (b));

Even if you did it with inline asm with zero asm statements and just opposite input/output constraints, you still destroy constant-propagation and range analysis, defeating optimization. https://gcc.gnu.org/wiki/DontUseInlineAsm. My edit to that answer I linked earlier includes a pure C swap, showing that constant-propagation works there but not with either inline-asm swap.

So even a correctly-written version of this is still useless for any real-world use, other than as an exercise / example in using input/output constraints for GNU C inline asm to avoid mov at the start/end of real asm blocks, and leave as much as possible up to the compiler.

Asm can only be a performance win if you do something the compiler can't already do better than you personally can. (C++ code for testing the Collatz conjecture faster than hand-written assembly - why?)

Look at the compiler's asm output for a normal function (How to remove "noise" from GCC/clang assembly output?), and see

to understand more about what makes for efficient asm.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847