swap() on x86 platforms.

[Pal-Kristian Engstad]

Testing on a Pentium revealed that using xchgl for swapping numbers is
not the best way! The reason is that it does not pair very well with
other instructions. On a pentium, if there is a register available,
you should always use:

	movl	reg1, reg3	; t = a;
	movl	reg2, reg1	; a = b;
	movl	reg3, reg2	; b = t;

If a register is not available, it might be faster using the stack:

	pushl	reg1
	pushl	reg2
	popl	reg1
	popl	reg2

The down-side is of course that you have to use the stack.

Results: (Don't count on them!)

 Normal   = ~5.5 secs (+/- 0.1)
 XOR      = ~8.5 secs (+/- 0.1)
 XCHG     = ~6.0 secs (+/- 0.1)
 PUSH/POP = ~5.5 secs (+/- 0.1)

Code:

#include <stdlib.h>

#define FAST_SWAP 1

inline void 
swap1 (int & a, int & b)
{
    int tmp = a; a = b; b = tmp;
}

inline void 
swap2 (int & a, int & b)
{
    if (&a != &b) { a ^= b; b ^= a; a ^= b; }
}

inline void
swap3 (int & a, int & b)
{
    __asm ( "xchgl %0, %1" : "=r" (a), "=r" (b) : "0" (a), "1" (b) );
}

inline void
swap4 (int & a, int & b)
{
    __asm ( "pushl %0; pushl %1; popl %0; popl %1" : "=r" (a), "=r" (b) : "0" (a), "1" (b) );
}

int 
main (int argc, char** argv)
{
    int data [10240];

    for (int i=0; i < 10240; i++)
        data[i] = rand();
    
    for (int j=0; j < 10240; j++)
        for (int i=0; i < 10239; i++)
        {
#if FAST_SWAP == 1
            swap1 (data[i], data[i+1]);
#elif FAST_SWAP == 2
            swap2 (data[i], data[i+1]);
#elif FAST_SWAP == 3
            swap3 (data[i], data[i+1]);
#else
            swap4 (data[i], data[i+1]);
#endif
        }
}

PKE.