變量交換有和沒有輔助變量 - 哪個更快？

Question

我想你們都聽說過「交換問題」; SO充滿了關於它的問題。 不使用第三個變量的交換版本通常被認爲是更快的，因爲，你有一個變量更少。我想知道發生了什麼事情的窗簾後面，並寫了下面的兩個方案：

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

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

    return 0; 
} 

和版本，而第三個變量：

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

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

    return 0; 
} 

我生成使用鐺的彙編代碼，並得到了本作第一版本（即使用第三變量）：

... 
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: 
... 

並且這對於所述第二版本（即不使用第三可變）：

... 
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: 
... 

第二個更長，但我不太瞭解彙編代碼，所以我不知道這是否意味着它更慢，所以我希望聽到更多人對此有所瞭解的意見。

以上哪個版本的變量swap速度更快，佔用的內存更少？

Answer 1

看看一些優化的程序集。從

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生產

.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 

對我來說，看起來swap_temp同樣有效即可。

Answer 2

想要了解成本，想象一下，每個命令都需要執行成本，而間接尋址也有自己的成本。

movl -12(%rbp), %ecx 

這條線將需要像一個時間單位訪問在ECX寄存器中的值， 一個時間單位訪問RBP，另一個用於施加偏置（-12），並有更多的時間 單位（假設任意3）用於將值從存儲在ecx中的地址移動到由-12（％rbp）指示的地址 。

如果您計算每行和所有行的所有操作，第二種方法肯定比第一種方法昂貴。

Answer 3

XOR交換技巧的問題在於它嚴格是順序的。它看起來似乎很快，但事實上並非如此。有一條叫做XCHG的指令可以交換兩個寄存器，但由於它的原子性質，這個指令也可能比簡單地使用3 MOVs慢。常見的技術與溫度是一個很好的選擇;）