Code snippets, ideas and events from IT related projects

Intro

Często zachodzi potrzeba zamienienia między sobą wartości zmiennych, co zazwyczaj wykonuje się przy użyciu dodatkowej zmiennej, jednak są inne możliwości, np użycie XOR'a. Sprawdzimy, która z tych metod jest bardziej wydajna, oraz to, jak kompilator optymalizuje nasz kod w C. BTW to pierwszy post tutaj z asemblerem w tle =)

Rzecz dzieje się na poziomie procesora i jego instrukcji (mnemoników), stąd wykorzystamy kod w C i asemblerze. Przypomnijmy, że gdy kompilujemy przy użyciu gcc program podając flagę -S otrzymamy plik z kodem asemblera, który możemy przeanalizować/zmodyfikować i skompilować do kodu wynikowego. Flaga -pg pozwala analizować gprof'em czas wykonywania funkcji w programie. Więcej info o tym jest w tym poście (wiem.. ciągle go nie skończył).

W gcc poziom optymalizacji zmienia flaga -O, (O1 < O2 < O3). Spróbujmy dla poniższego kodu, dla kolejnych poziomów optymalizacji zobaczyć, jak wygląda kod asemblera wynikowy (z którego został skompilowany kod w C i który zostanie skompilowany do kodu wynikowego). Wydajność obu metod zbadamy gprof'em.

   1  #include <stdio.h>
   2  
   3  void swapByXOR(int *a, int *b){
   4      // we dont care if a is b
   5      *a = *a^*b;
   6      *b = *a^*b;
   7      *a = *a^*b;
   8  }
   9  
  10  int swapByBuffer(int *a, int *b){
  11      int c;
  12      c = *a;
  13      *a = *b;
  14      *b = c;
  15  }
  16  
  17  int main(){
  18      int a = 0x44, b = 0x67;
  19      int i, max = 400000000;
  20  
  21      for(i=0; i<max; i++)
  22          swapByBuffer(&a, &b);
  23      for(i=0; i<max; i++)
  24          swapByXOR(&a, &b);
  25  }
  26  

Bez optymalizacji:

rgawron@rgawron-laptop:~/testsub$ gcc -O0 -S merge.c
rgawron@rgawron-laptop:~/testsub$ cat merge.s

	.file	"merge.c"
	.text
.globl swapByXOR
	.type	swapByXOR, @function
swapByXOR:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	movl	(%eax), %edx
	movl	12(%ebp), %eax
	movl	(%eax), %eax
	xorl	%eax, %edx
	movl	8(%ebp), %eax
	movl	%edx, (%eax)
	movl	8(%ebp), %eax
	movl	(%eax), %edx
	movl	12(%ebp), %eax
	movl	(%eax), %eax
	xorl	%eax, %edx
	movl	12(%ebp), %eax
	movl	%edx, (%eax)
	movl	8(%ebp), %eax
	movl	(%eax), %edx
	movl	12(%ebp), %eax
	movl	(%eax), %eax
	xorl	%eax, %edx
	movl	8(%ebp), %eax
	movl	%edx, (%eax)
	popl	%ebp
	ret
	.size	swapByXOR, .-swapByXOR
.globl swapByBuffer
	.type	swapByBuffer, @function
swapByBuffer:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$16, %esp
	movl	8(%ebp), %eax
	movl	(%eax), %eax
	movl	%eax, -4(%ebp)
	movl	12(%ebp), %eax
	movl	(%eax), %edx
	movl	8(%ebp), %eax
	movl	%edx, (%eax)
	movl	12(%ebp), %edx
	movl	-4(%ebp), %eax
	movl	%eax, (%edx)
	leave
	ret
	.size	swapByBuffer, .-swapByBuffer
.globl main
	.type	main, @function
main:
	leal	4(%esp), %ecx
	andl	$-16, %esp
	pushl	-4(%ecx)
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ecx
	subl	$24, %esp
	movl	$68, -8(%ebp)
	movl	$103, -12(%ebp)
	movl	$400000000, -20(%ebp)
	movl	$0, -16(%ebp)
	jmp	.L6
.L7:
	leal	-12(%ebp), %eax
	movl	%eax, 4(%esp)
	leal	-8(%ebp), %eax
	movl	%eax, (%esp)
	call	swapByBuffer
	addl	$1, -16(%ebp)
.L6:
	movl	-16(%ebp), %eax
	cmpl	-20(%ebp), %eax
	jl	.L7
	movl	$0, -16(%ebp)
	jmp	.L9
.L10:
	leal	-12(%ebp), %eax
	movl	%eax, 4(%esp)
	leal	-8(%ebp), %eax
	movl	%eax, (%esp)
	call	swapByXOR
	addl	$1, -16(%ebp)
.L9:
	movl	-16(%ebp), %eax
	cmpl	-20(%ebp), %eax
	jl	.L10
	addl	$24, %esp
	popl	%ecx
	popl	%ebp
	leal	-4(%ecx), %esp
	ret
	.size	main, .-main
	.ident	"GCC: (GNU) 4.2.3 (Ubuntu 4.2.3-2ubuntu7)"
	.section	.note.GNU-stack,"",@progbits

Każdy mnemonik (pojedyńcza instrukcja) zużywa stalą (dla danego procka) ilość cykli, stąd im mniej instrukcji tym wydajniej działa dany fragment kodu. Również stosowanie instrukcji które zużywają mniej taktów zamiast tych bardziej kosztownych przyspiesza kod. Można by sie pokusić o przeliczenie ile taktów zużywa każda funkcja (z tego co pamiętam i xor i mov po jednym).

rgawron@rgawron-laptop:~/testsub$ gcc -O0 -pg merge.c
rgawron@rgawron-laptop:~/testsub$ ./a.out 
rgawron@rgawron-laptop:~/testsub$ gprof -b ./a.out 
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 43.00      5.50     5.50 400000000    13.75    13.75  swapByXOR
 32.21      9.62     4.12                             main
 24.78     12.79     3.17 400000000     7.92     7.92  swapByBuffer

Optymalizacja 02:

	.file	"merge.c"
	.text
	.p2align 4,,15
.globl swapByXOR
	.type	swapByXOR, @function
swapByXOR:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %ecx
	movl	12(%ebp), %edx
	movl	(%ecx), %eax
	xorl	(%edx), %eax
	movl	%eax, (%ecx)
	xorl	(%edx), %eax
	movl	%eax, (%edx)
	xorl	%eax, (%ecx)
	popl	%ebp
	ret
	.size	swapByXOR, .-swapByXOR
	.p2align 4,,15
.globl swapByBuffer
	.type	swapByBuffer, @function
swapByBuffer:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %edx
	movl	12(%ebp), %ecx
	pushl	%ebx
	movl	(%edx), %ebx
	movl	(%ecx), %eax
	movl	%eax, (%edx)
	movl	%ebx, (%ecx)
	popl	%ebx
	popl	%ebp
	ret
	.size	swapByBuffer, .-swapByBuffer
	.p2align 4,,15
.globl main
	.type	main, @function
main:
	leal	4(%esp), %ecx
	andl	$-16, %esp
	pushl	-4(%ecx)
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%edi
	pushl	%esi
	pushl	%ebx
	movl	$1, %ebx
	pushl	%ecx
	subl	$24, %esp
	leal	-24(%ebp), %edi
	leal	-20(%ebp), %esi
	movl	$68, -20(%ebp)
	movl	$103, -24(%ebp)
	movl	%edi, 4(%esp)
	movl	%esi, (%esp)
	call	swapByBuffer
	.p2align 4,,7
.L6:
	movl	%edi, 4(%esp)
	addl	$1, %ebx
	movl	%esi, (%esp)
	call	swapByBuffer
	cmpl	$400000000, %ebx
	jne	.L6
	movl	%edi, 4(%esp)
	movl	$1, %ebx
	movl	%esi, (%esp)
	call	swapByXOR
	.p2align 4,,7
.L8:
	movl	%edi, 4(%esp)
	addl	$1, %ebx
	movl	%esi, (%esp)
	call	swapByXOR
	cmpl	$400000000, %ebx
	jne	.L8
	addl	$24, %esp
	popl	%ecx
	popl	%ebx
	popl	%esi
	popl	%edi
	popl	%ebp
	leal	-4(%ecx), %esp
	ret
	.size	main, .-main
	.ident	"GCC: (GNU) 4.2.3 (Ubuntu 4.2.3-2ubuntu7)"
	.section	.note.GNU-stack,"",@progbits

Kompilator nie tworzy dodatkowej zmiennej, zamiast tego odkłada obie na stos a nastepnie pobiera je w odwrotnej koljeności.

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 43.65      2.44     2.44 400000000     6.10     6.10  swapByXOR
 30.77      4.16     1.72 400000000     4.30     4.30  swapByBuffer
 25.58      5.59     1.43                             main

Optymalizacja O3:

	.file	"merge.c"
	.text
	.p2align 4,,15
.globl swapByXOR
	.type	swapByXOR, @function
swapByXOR:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %ecx
	movl	12(%ebp), %edx
	movl	(%ecx), %eax
	xorl	(%edx), %eax
	movl	%eax, (%ecx)
	xorl	(%edx), %eax
	movl	%eax, (%edx)
	xorl	%eax, (%ecx)
	popl	%ebp
	ret
	.size	swapByXOR, .-swapByXOR
	.p2align 4,,15
.globl swapByBuffer
	.type	swapByBuffer, @function
swapByBuffer:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %edx
	movl	12(%ebp), %ecx
	pushl	%ebx
	movl	(%edx), %ebx
	movl	(%ecx), %eax
	movl	%eax, (%edx)
	movl	%ebx, (%ecx)
	popl	%ebx
	popl	%ebp
	ret
	.size	swapByBuffer, .-swapByBuffer
	.p2align 4,,15
.globl main
	.type	main, @function
main:
	leal	4(%esp), %ecx
	andl	$-16, %esp
	pushl	-4(%ecx)
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ecx
	popl	%ecx
	popl	%ebp
	leal	-4(%ecx), %esp
	ret
	.size	main, .-main
	.ident	"GCC: (GNU) 4.2.3 (Ubuntu 4.2.3-2ubuntu7)"
	.section	.note.GNU-stack,"",@progbits

Tu jest najmilej :) Kompilator zauważył, iż kod zmieniający wartość zmiennych i nigdzie tego nie wykorzystujący jest zbędny i usunął jego wywołanie w main'ie. Nie ma co odpalać gprof'a, bo nasze funkcje nie zostaną wywołane.

Wnioski?

Metoda z XOR'em jest tylko ciekawostką. Angielska Wikipedia podaje, iż przydaje się ona w sytuacjach gdy ilość miejsca jest ograniczona, np. w systemach wbudowanych.

Linki, sznurki i pętelki

• Arrtykuł o tym samym temacie, trochę z innej perspektywy. Właściwie jakbym znalazł go wcześniej to nie wgłębiał bym się w to sam. Ehh google nie gryzie =)
• Wikipedia o zamienianiu przez XOR
• Optymalizacja w gcc - rozpiska, jak działają poszczególne opcje
• W ramach dygresji wstawki asemblera w C oraz krótki opis gcc