Skip to content

Instantly share code, notes, and snippets.

@DrFrankenstein

DrFrankenstein/swaps.c

Created October 27, 2011 00:54
Show Gist options
  • Save DrFrankenstein/1318483 to your computer and use it in GitHub Desktop.
Save DrFrankenstein/1318483 to your computer and use it in GitHub Desktop.
Download ZIP
Comparing the performances of various value swapping techniques
Raw
swaps.c
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#include <stdio.h>
/* Optimizations enabled EXCEPT for function inlining. */
extern void xchg_swap(int*, int*);
extern void xchg_swap_loop(int);
void in_place_swap(int* x, int* y)
{
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
void buffered_swap(int* x, int* y)
{
int z = *x;
*x = *y;
*y = z;
}
int main(void)
{
const int NUM_SWAP = INT_MAX;
int x = 1234, y = 5678, i;
long int elapsed = clock();
for(i = 0; i < NUM_SWAP; i++)
{
in_place_swap(&x, &y);
}
printf("%d called in-place XOR swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
elapsed = clock();
for(i = 0; i < NUM_SWAP; i++)
{
buffered_swap(&x, &y);
}
printf("%d called buffered swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
elapsed = clock();
for(i = 0; i < NUM_SWAP; i++)
{
xchg_swap(&x, &y);
}
printf("%d called swaps using XCHG instruction took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
elapsed = clock();
for(i = 0; i < NUM_SWAP; i++)
{
x ^= y;
y ^= x;
x ^= y;
}
printf("%d inline in-place XOR swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
elapsed = clock();
for(i = 0; i < NUM_SWAP; i++)
{
int z = x;
x = y;
y = z;
}
printf("%d inline buffered swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
elapsed = clock();
xchg_swap_loop(NUM_SWAP);
printf("%d inline swaps using XCHG instruction took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
return EXIT_SUCCESS;
}
Raw
swaps.list.asm
; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.40219.01
TITLE C:\Users\Carl Tessier\Documents\Visual Studio 2008\Projects\ctest\ctest\swaps.c
.686P
.XMM
include listing.inc
.model flat
INCLUDELIB OLDNAMES
PUBLIC ??_C@_0CP@KPPIDIDF@?$CFd?5called?5in?9place?5XOR?5swaps?5too@ ; `string'
PUBLIC ??_C@_0CL@FBOPGFHL@?$CFd?5called?5buffered?5swaps?5took?5?$CFl@ ; `string'
PUBLIC ??_C@_0DJ@PLIACGIK@?$CFd?5called?5swaps?5using?5XCHG?5instr@ ; `string'
PUBLIC ??_C@_0CP@MKHDBCGC@?$CFd?5inline?5in?9place?5XOR?5swaps?5too@ ; `string'
PUBLIC ??_C@_0CL@LAAMDJGG@?$CFd?5inline?5buffered?5swaps?5took?5?$CFl@ ; `string'
PUBLIC ??_C@_0DJ@GAEIEJEI@?$CFd?5inline?5swaps?5using?5XCHG?5instr@ ; `string'
EXTRN @__security_check_cookie@4:PROC
EXTRN __imp__clock:PROC
EXTRN __imp__printf:PROC
EXTRN _xchg_swap:PROC
EXTRN _xchg_swap_loop:PROC
; COMDAT ??_C@_0DJ@GAEIEJEI@?$CFd?5inline?5swaps?5using?5XCHG?5instr@
CONST SEGMENT
??_C@_0DJ@GAEIEJEI@?$CFd?5inline?5swaps?5using?5XCHG?5instr@ DB '%d inlin'
DB 'e swaps using XCHG instruction took %ld clocks.', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0CL@LAAMDJGG@?$CFd?5inline?5buffered?5swaps?5took?5?$CFl@
CONST SEGMENT
??_C@_0CL@LAAMDJGG@?$CFd?5inline?5buffered?5swaps?5took?5?$CFl@ DB '%d in'
DB 'line buffered swaps took %ld clocks.', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0CP@MKHDBCGC@?$CFd?5inline?5in?9place?5XOR?5swaps?5too@
CONST SEGMENT
??_C@_0CP@MKHDBCGC@?$CFd?5inline?5in?9place?5XOR?5swaps?5too@ DB '%d inli'
DB 'ne in-place XOR swaps took %ld clocks.', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0DJ@PLIACGIK@?$CFd?5called?5swaps?5using?5XCHG?5instr@
CONST SEGMENT
??_C@_0DJ@PLIACGIK@?$CFd?5called?5swaps?5using?5XCHG?5instr@ DB '%d calle'
DB 'd swaps using XCHG instruction took %ld clocks.', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0CL@FBOPGFHL@?$CFd?5called?5buffered?5swaps?5took?5?$CFl@
CONST SEGMENT
??_C@_0CL@FBOPGFHL@?$CFd?5called?5buffered?5swaps?5took?5?$CFl@ DB '%d ca'
DB 'lled buffered swaps took %ld clocks.', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0CP@KPPIDIDF@?$CFd?5called?5in?9place?5XOR?5swaps?5too@
CONST SEGMENT
??_C@_0CP@KPPIDIDF@?$CFd?5called?5in?9place?5XOR?5swaps?5too@ DB '%d call'
DB 'ed in-place XOR swaps took %ld clocks.', 0aH, 00H ; `string'
CONST ENDS
PUBLIC _buffered_swap
; Function compile flags: /Ogtp
; File c:\users\carl tessier\documents\visual studio 2008\projects\ctest\ctest\swaps.c
; COMDAT _buffered_swap
_TEXT SEGMENT
_buffered_swap PROC ; COMDAT
; _x$ = ecx
; _y$ = eax
; 19 : int z = *x;
mov edx, DWORD PTR [ecx]
push esi
; 20 : *x = *y;
mov esi, DWORD PTR [eax]
mov DWORD PTR [ecx], esi
; 21 : *y = z;
mov DWORD PTR [eax], edx
pop esi
; 22 : }
ret 0
_buffered_swap ENDP
_TEXT ENDS
PUBLIC _in_place_swap
; Function compile flags: /Ogtp
; COMDAT _in_place_swap
_TEXT SEGMENT
_in_place_swap PROC ; COMDAT
; _x$ = eax
; _y$ = ecx
; 12 : *x ^= *y;
mov edx, DWORD PTR [ecx]
xor DWORD PTR [eax], edx
mov edx, DWORD PTR [eax]
; 13 : *y ^= *x;
xor DWORD PTR [ecx], edx
mov ecx, DWORD PTR [ecx]
; 14 : *x ^= *y;
xor DWORD PTR [eax], ecx
; 15 : }
ret 0
_in_place_swap ENDP
_TEXT ENDS
PUBLIC _main
; Function compile flags: /Ogtp
; COMDAT _main
_TEXT SEGMENT
_elapsed$ = -12 ; size = 4
_x$ = -8 ; size = 4
_y$ = -4 ; size = 4
_main PROC ; COMDAT
; 25 : {
push ebp
mov ebp, esp
sub esp, 12 ; 0000000cH
push ebx
push esi
; 26 : const int NUM_SWAP = INT_MAX;
; 27 : int x = 1234, y = 5678, i;
; 28 : long int elapsed = clock();
mov esi, DWORD PTR __imp__clock
push edi
mov DWORD PTR _x$[ebp], 1234 ; 000004d2H
mov DWORD PTR _y$[ebp], 5678 ; 0000162eH
call esi
mov ebx, eax
mov edi, 2147483647 ; 7fffffffH
npad 10
$LL15@main:
; 29 :
; 30 : for(i = 0; i < NUM_SWAP; i++)
; 31 : {
; 32 : in_place_swap(&x, &y);
lea ecx, DWORD PTR _y$[ebp]
lea eax, DWORD PTR _x$[ebp]
call _in_place_swap
dec edi
jne SHORT $LL15@main
; 33 : }
; 34 :
; 35 : printf("%d called in-place XOR swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
call esi
mov edi, DWORD PTR __imp__printf
sub eax, ebx
push eax
push 2147483647 ; 7fffffffH
push OFFSET ??_C@_0CP@KPPIDIDF@?$CFd?5called?5in?9place?5XOR?5swaps?5too@
call edi
add esp, 12 ; 0000000cH
; 36 : elapsed = clock();
call esi
mov DWORD PTR _elapsed$[ebp], eax
mov ebx, 2147483647 ; 7fffffffH
$LL12@main:
; 37 :
; 38 : for(i = 0; i < NUM_SWAP; i++)
; 39 : {
; 40 : buffered_swap(&x, &y);
lea eax, DWORD PTR _y$[ebp]
lea ecx, DWORD PTR _x$[ebp]
call _buffered_swap
dec ebx
jne SHORT $LL12@main
; 41 : }
; 42 :
; 43 : printf("%d called buffered swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
call esi
sub eax, DWORD PTR _elapsed$[ebp]
push eax
push 2147483647 ; 7fffffffH
push OFFSET ??_C@_0CL@FBOPGFHL@?$CFd?5called?5buffered?5swaps?5took?5?$CFl@
call edi
add esp, 12 ; 0000000cH
; 44 : elapsed = clock();
call esi
mov DWORD PTR _elapsed$[ebp], eax
mov ebx, 2147483647 ; 7fffffffH
npad 1
$LL9@main:
; 45 :
; 46 : for(i = 0; i < NUM_SWAP; i++)
; 47 : {
; 48 : xchg_swap(&x, &y);
lea eax, DWORD PTR _y$[ebp]
push eax
lea ecx, DWORD PTR _x$[ebp]
push ecx
call _xchg_swap
add esp, 8
dec ebx
jne SHORT $LL9@main
; 49 : }
; 50 :
; 51 : printf("%d called swaps using XCHG instruction took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
call esi
sub eax, DWORD PTR _elapsed$[ebp]
push eax
push 2147483647 ; 7fffffffH
push OFFSET ??_C@_0DJ@PLIACGIK@?$CFd?5called?5swaps?5using?5XCHG?5instr@
call edi
add esp, 12 ; 0000000cH
; 52 : elapsed = clock();
call esi
mov ecx, DWORD PTR _y$[ebp]
mov ebx, eax
mov eax, DWORD PTR _x$[ebp]
mov edx, 2147483647 ; 7fffffffH
$LL6@main:
; 53 :
; 54 : for(i = 0; i < NUM_SWAP; i++)
; 55 : {
; 56 : x ^= y;
xor eax, ecx
; 57 : y ^= x;
xor ecx, eax
; 58 : x ^= y;
xor eax, ecx
dec edx
jne SHORT $LL6@main
mov DWORD PTR _x$[ebp], eax
mov DWORD PTR _y$[ebp], ecx
; 59 : }
; 60 :
; 61 : printf("%d inline in-place XOR swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
call esi
sub eax, ebx
push eax
push 2147483647 ; 7fffffffH
push OFFSET ??_C@_0CP@MKHDBCGC@?$CFd?5inline?5in?9place?5XOR?5swaps?5too@
call edi
add esp, 12 ; 0000000cH
; 62 : elapsed = clock();
call esi
mov ecx, DWORD PTR _x$[ebp]
mov edx, DWORD PTR _y$[ebp]
mov DWORD PTR _elapsed$[ebp], eax
mov ebx, 2147483647 ; 7fffffffH
npad 6
$LL3@main:
; 63 :
; 64 : for(i = 0; i < NUM_SWAP; i++)
dec ebx
; 65 : {
; 66 : int z = x;
mov eax, ecx
; 67 : x = y;
mov ecx, edx
; 68 : y = z;
mov edx, eax
jne SHORT $LL3@main
mov DWORD PTR _y$[ebp], edx
mov DWORD PTR _x$[ebp], ecx
; 69 : }
; 70 :
; 71 : printf("%d inline buffered swaps took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
call esi
sub eax, DWORD PTR _elapsed$[ebp]
push eax
push 2147483647 ; 7fffffffH
push OFFSET ??_C@_0CL@LAAMDJGG@?$CFd?5inline?5buffered?5swaps?5took?5?$CFl@
call edi
; 72 : elapsed = clock();
call esi
; 73 :
; 74 : xchg_swap_loop(NUM_SWAP);
push 2147483647 ; 7fffffffH
mov ebx, eax
call _xchg_swap_loop
; 75 :
; 76 : printf("%d inline swaps using XCHG instruction took %ld clocks.\n", NUM_SWAP, clock() - elapsed);
call esi
sub eax, ebx
push eax
push 2147483647 ; 7fffffffH
push OFFSET ??_C@_0DJ@GAEIEJEI@?$CFd?5inline?5swaps?5using?5XCHG?5instr@
call edi
add esp, 28 ; 0000001cH
pop edi
pop esi
; 77 :
; 78 : return EXIT_SUCCESS;
xor eax, eax
pop ebx
; 79 : }
mov esp, ebp
pop ebp
ret 0
_main ENDP
_TEXT ENDS
END
Raw
swaps.out
2147483647 called in-place XOR swaps took 37867 clocks.
2147483647 called buffered swaps took 12163 clocks.
2147483647 called swaps using XCHG instruction took 71621 clocks.
2147483647 inline in-place XOR swaps took 6900 clocks.
2147483647 inline buffered swaps took 4276 clocks.
2147483647 inline swaps using XCHG instruction took 11637 clocks.
Raw
xchg_swap.asm
.model flat, C
code segment
public xchg_swap
xchg_swap proc _x: dword, _y: dword
mov eax,[_x]
xchg eax,[_y]
mov [_x],eax
ret
xchg_swap endp
public xchg_swap_loop
xchg_swap_loop proc _count: dword
mov eax,1234
mov edx,5678
mov ecx,_count
_next: xchg eax,edx
loop _next
ret
xchg_swap_loop endp
code ends
end
Raw
xchg_swap.list.asm
Microsoft (R) Macro Assembler Version 10.00.40219.01 10/26/11 21:41:47
xchg_swap.asm Page 1 - 1
.model flat, C
00000000 code segment
public xchg_swap
00000000 xchg_swap proc _x: dword, _y: dword
00000000 55 * push ebp
00000001 8B EC * mov ebp, esp
00000003 8B 45 08 mov eax,[_x]
00000006 87 45 0C xchg eax,[_y]
00000009 89 45 08 mov [_x],eax
ret
0000000C C9 * leave
0000000D C3 * ret 00000h
0000000E xchg_swap endp
public xchg_swap_loop
0000000E xchg_swap_loop proc _count: dword
0000000E 55 * push ebp
0000000F 8B EC * mov ebp, esp
00000011 B8 000004D2 mov eax,1234
00000016 BA 0000162E mov edx,5678
0000001B 8B 4D 08 mov ecx,_count
0000001E 92 _next: xchg eax,edx
0000001F E2 FD loop _next
ret
00000021 C9 * leave
00000022 C3 * ret 00000h
00000023 xchg_swap_loop endp
00000023 code ends
end
Microsoft (R) Macro Assembler Version 10.00.40219.01 10/26/11 21:41:47
xchg_swap.asm Symbols 2 - 1
Segments and Groups:
N a m e Size Length Align Combine Class
FLAT . . . . . . . . . . . . . . GROUP
_DATA . . . . . . . . . . . . . 32 Bit 00000000 Para Public 'DATA'
_TEXT . . . . . . . . . . . . . 32 Bit 00000000 Para Public 'CODE'
code . . . . . . . . . . . . . . 32 Bit 00000023 Private
Procedures, parameters, and locals:
N a m e Type Value Attr
xchg_swap_loop . . . . . . . . . P Near 0000000E code Length= 00000015 Public C
_count . . . . . . . . . . . . DWord bp + 00000008
_next . . . . . . . . . . . . L Near 0000001E code
xchg_swap . . . . . . . . . . . P Near 00000000 code Length= 0000000E Public C
_x . . . . . . . . . . . . . . DWord bp + 00000008
_y . . . . . . . . . . . . . . DWord bp + 0000000C
Symbols:
N a m e Type Value Attr
@CodeSize . . . . . . . . . . . Number 00000000h
@DataSize . . . . . . . . . . . Number 00000000h
@Interface . . . . . . . . . . . Number 00000001h
@Model . . . . . . . . . . . . . Number 00000007h
@code . . . . . . . . . . . . . Text _TEXT
@data . . . . . . . . . . . . . Text FLAT
@fardata? . . . . . . . . . . . Text FLAT
@fardata . . . . . . . . . . . . Text FLAT
@stack . . . . . . . . . . . . . Text FLAT
0 Warnings
0 Errors
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment