Zmienna zamiana zi bez zmiennej pomocniczej - która jest szybsza?

Question

Chyba wszyscy słyszeliście o "problemie z zamianą"; SO jest pełne pytań na ten temat. Wersja wymiany bez użycia trzeciej zmiennej jest często uważana za szybszą, ponieważ, cóż, masz jedną zmienną mniej. Chciałem wiedzieć, co dzieje się za kurtyną i napisał dwie następujące programy:

int main() { 
    int a = 9; 
    int b = 5; 
    int swap; 

    swap = a; 
    a = b; 
    b = swap; 

    return 0; 
} 

i wersję bez zmiennej trzecie:

int main() { 
    int a = 9; 
    int b = 5; 

    a ^= b; 
    b ^= a; 
    a ^= b; 

    return 0; 
} 

I wygenerowany kod montaż przy użyciu szczęk i dostał to dla pierwsza wersja (która wykorzystuje trzeciej zmiennej):

... 
Ltmp0: 
    movq %rsp, %rbp 
Ltmp1: 
    movl $0, %eax 
    movl $0, -4(%rbp) 
    movl $9, -8(%rbp) 
    movl $5, -12(%rbp) 
    movl -8(%rbp), %ecx 
    movl %ecx, -16(%rbp) 
    movl -12(%rbp), %ecx 
    movl %ecx, -8(%rbp) 
    movl -16(%rbp), %ecx 
    movl %ecx, -12(%rbp) 
    popq %rbp 
    ret 
Leh_func_end0: 
... 

a to dla drugiej wersji (które nie korzysta z trzeciej zmiennej):

... 
Ltmp0: 
    movq %rsp, %rbp 
Ltmp1: 
    movl $0, %eax 
    movl $0, -4(%rbp) 
    movl $9, -8(%rbp) 
    movl $5, -12(%rbp) 
    movl -12(%rbp), %ecx 
    movl -8(%rbp), %edx 
    xorl %ecx, %edx 
    movl %edx, -8(%rbp) 
    movl -8(%rbp), %ecx 
    movl -12(%rbp), %edx 
    xorl %ecx, %edx 
    movl %edx, -12(%rbp) 
    movl -12(%rbp), %ecx 
    movl -8(%rbp), %edx 
    xorl %ecx, %edx 
    movl %edx, -8(%rbp) 
    popq %rbp 
    ret 
Leh_func_end0: 
... 

Druga jest dłuższa, ale nie wiem zbyt wiele na temat kodu zespołu, więc nie mam pojęcia, czy to oznacza, że ​​jest wolniejsza, więc chciałbym usłyszeć opinię kogoś bardziej kompetentnego na ten temat.

Która z powyższych wersji zmiennej swap jest szybsza i zajmuje mniej pamięci?

Answer 1

Obejrzyj zoptymalizowany zespół. Od

void swap_temp(int *restrict a, int *restrict b){ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 

void swap_xor(int *restrict a, int *restrict b){ 
    *a ^= *b; 
    *b ^= *a; 
    *a ^= *b; 
} 

gcc -O3 -std=c99 -S -o swapping.s swapping.c produkowane

.file "swapping.c" 
.text 
.p2align 4,,15 
.globl swap_temp 
.type swap_temp, @function 
swap_temp: 
.LFB0: 
.cfi_startproc 
movl (%rdi), %eax 
movl (%rsi), %edx 
movl %edx, (%rdi) 
movl %eax, (%rsi) 
ret 
.cfi_endproc 
.LFE0: 
.size swap_temp, .-swap_temp 
.p2align 4,,15 
.globl swap_xor 
.type swap_xor, @function 
swap_xor: 
.LFB1: 
.cfi_startproc 
movl (%rsi), %edx 
movl (%rdi), %eax 
xorl %edx, %eax 
xorl %eax, %edx 
xorl %edx, %eax 
movl %edx, (%rsi) 
movl %eax, (%rdi) 
ret 
.cfi_endproc 
.LFE1: 
.size swap_xor, .-swap_xor 
.ident "GCC: (SUSE Linux) 4.5.1 20101208 [gcc-4_5-branch revision 167585]" 
.section .comment.SUSE.OPTs,"MS",@progbits,1 
.string "Ospwg" 
.section .note.GNU-stack,"",@progbits 

Dla mnie swap_temp wygląda tak wydajna, jak może być.

Answer 2

Aby zorientować się w kosztach, należy wyobrazić sobie, że każde polecenie ma koszt do wykonania, a także adresowanie pośrednie ma swój własny koszt.

movl -12(%rbp), %ecx 

Linia ta będzie musiała coś w jednostce czasu dostępu wartość w rejestrze ECX, jedną jednostkę czasu dostępu RBP, inny dla stosowania przesunięcia (-12) i więcej czasu jednostek (powiedzmy dowolnie 3) za przeniesienie wartości z adresu zapisanego w ecx na adres wskazany z -12 (% rbp).

Jeśli zliczysz wszystkie operacje w każdym wierszu i całej linii, druga metoda jest z pewnością droższa niż pierwsza.

Answer 3

Problem z sztuczką XOR Swap polega na tym, że jest ściśle sekwencyjny. Może wydawać się zwodniczo szybki, ale w rzeczywistości tak nie jest. Istnieje instrukcja o nazwie XCHG, która zamienia dwa rejestry, ale może być wolniejsza niż po prostu użycie 3 MOVs, ze względu na jej atomową naturę. Wspólna technika z tempem jest doskonałym wyborem;)