Thread: swapping pointers

yes,and although i dont know much about code optimisation, but i have heard that there are more chances, the compiler would recognise that the user is trying to swap(and use XCHG) by use of a temp variable that by the XOR method or any of their variations. isnt that right?

Originally Posted by creeping death

yes,and although i dont know much about code optimisation, but i have heard that there are more chances, the compiler would recognise that the user is trying to swap(and use XCHG) by use of a temp variable that by the XOR method or any of their variations. isnt that right?

It is MUCH easier for a compiler to realize that

Code:

temp = a;
a = b;
b = temp;

is a swap than it is to detect the xor pattern is a swap - but sure, the optimizer could be written to recognize both/either one.

--
Mats

Originally Posted by matsp

It is MUCH easier for a compiler to realize that

Code:

temp = a;
a = b;
b = temp;

is a swap than it is to detect the xor pattern is a swap - but sure, the optimizer could be written to recognize both/either one.

--
Mats

source code

Code:

#include<stdio.h>

void swap(int x,int y)
{
    int temp;
    temp=x;
    x=y;
    y=temp;
}

void swap2(int x,int y)
{
    x=x^y;
    y=x^y;
    x=x^y;
}

int main()
{
    int x=3,y=4;
    swap(x,y);
    swap2(x,y);
    printf("x=%d,y=%d",x,y);
}

assembly instruction by gcc inline assembler

Code:

swap:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$16, %esp
	movl	8(%ebp), %eax
	movl	%eax, -4(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, 8(%ebp)
	movl	-4(%ebp), %eax
	movl	%eax, 12(%ebp)
	leave
	ret
	.size	swap, .-swap
.globl swap2
	.type	swap2, @function
swap2:
	pushl	%ebp
	movl	%esp, %ebp
	movl	12(%ebp), %eax
	xorl	%eax, 8(%ebp)
	movl	8(%ebp), %eax
	xorl	%eax, 12(%ebp)
	movl	12(%ebp), %eax
	xorl	%eax, 8(%ebp)
	popl	%ebp
	ret
	.size	swap2, .-swap2
	.section	.rodata

optimised (O3)

Code:

swap:
	pushl	%ebp
	movl	%esp, %ebp
	popl	%ebp
	ret
	.size	swap, .-swap
.globl swap2
	.type	swap2, @function
swap2:
	pushl	%ebp
	movl	%esp, %ebp
	popl	%ebp
	ret
	.size	swap2, .-swap2
	.section	.rodata.str1.1,"aMS",@progbits,1

xchg is not called after all(making compiler call xchg/swp isnt easy after all)...and when optimised, both are exactly the same.

Actually, the compiler optimized away ALL of the swap function, since all it does is change the local copies of x and y. You didn't actually test your code, did you?

I will be back with proper code.

I do not expect the compiler to generate the xchg instruction tho'.

Code:

_swap:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %edx
	pushl	%ebx
	movl	12(%ebp), %ecx
	movl	(%edx), %ebx
	movl	(%ecx), %eax
	movl	%eax, (%edx)
	movl	%ebx, (%ecx)
	popl	%ebx
	popl	%ebp
	ret
	.p2align 4,,15
.globl _swap2
	.def	_swap2;	.scl	2;	.type	32;	.endef
_swap2:
	pushl	%ebp
	movl	%esp, %ebp
	movl	12(%ebp), %edx
	movl	8(%ebp), %ecx
	movl	(%edx), %eax
	xorl	(%ecx), %eax
	movl	%eax, (%ecx)
	xorl	(%edx), %eax
	movl	%eax, (%edx)
	xorl	%eax, (%ecx)
	popl	%ebp
	ret
...
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	subl	$24, %esp
	andl	$-16, %esp
	call	__alloca
	call	___main
	movl	$LC0, (%esp)
	movl	$4, %ecx
	movl	$3, %eax
	movl	%ecx, 4(%esp)
	movl	%eax, 8(%esp)
	call	_printf
	movl	$LC0, (%esp)
	movl	$4, %edx
	movl	$3, %eax
	movl	%edx, 8(%esp)
	movl	%eax, 4(%esp)
	call	_printf
	leave
	xorl	%eax, %eax
	ret

Note that it actualy inlines the entire swap and does it without even calling swap in this case. I'll see if I can come up with a more complex case where it does call swap.

--
Mats

Originally Posted by matsp

Actually, the compiler optimized away ALL of the swap function, since all it does is change the local copies of x and y. You didn't actually test your code, did you?

I will be back with proper code.

I do not expect the compiler to generate the xchg instruction tho'.

--
Mats

i see..and no

Further to my edit above:
1. It seems like (at least in trivial cases) the compiler at least understands that the point of the XOR swap is to swap elements [or at least that this is the effect of it].
2. It's pretty hard to get gcc -O3 to actually CALL the function swap - it just swaps the variables inline.

--
Mats