Hoán đổi biến có và không có biến phụ - nhanh hơn?

Question

Tôi đoán tất cả các bạn đã nghe về 'vấn đề trao đổi'; SO có đầy đủ các câu hỏi về nó. Phiên bản hoán đổi mà không sử dụng biến số thứ ba thường được coi là nhanh hơn vì, tốt, bạn có một biến ít hơn. Tôi muốn biết chuyện gì đang xảy ra đằng sau rèm cửa và viết hai chương trình sau:

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

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

    return 0; 
} 

và phiên bản mà không biến thứ ba:

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

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

    return 0; 
} 

tôi tạo ra mã assembly bằng kêu vang và nhận được điều này cho phiên bản đầu tiên (có sử dụng một biến thứ ba):

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

và điều này cho phiên bản thứ hai (mà không sử dụng một biến thứ ba):

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

Điều thứ hai dài hơn nhưng tôi không biết nhiều về mã lắp ráp nên tôi không biết điều đó có nghĩa là nó chậm hơn vì vậy tôi muốn nghe ý kiến ​​của ai đó có kiến ​​thức hơn về nó.

Phiên bản trên của trao đổi biến nhanh hơn và mất ít bộ nhớ hơn?

Answer 1

Nhìn vào một số cụm được tối ưu hóa. Từ

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 sản xuất

.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 

Đối với tôi, swap_temp vẻ như hiệu quả như có thể được.

Answer 2

Để có ý tưởng về chi phí, hãy tưởng tượng rằng mọi lệnh đều có chi phí để thực hiện và việc gửi địa chỉ gián tiếp có chi phí riêng.

movl -12(%rbp), %ecx 

Dòng này sẽ cần một cái gì đó giống như một đơn vị thời gian cho việc truy cập các giá trị trong ecx đăng ký, một đơn vị thời gian để truy cập vào RBP, một số khác cho việc áp dụng (-12) và nhiều đơn vị thời gian bù đắp (giả sử tùy ý 3) để di chuyển giá trị từ địa chỉ được lưu trữ trong ecx đến địa chỉ được chỉ ra từ -12 (% rbp).

Nếu bạn đếm tất cả các hoạt động trong mỗi dòng và tất cả các dòng, phương pháp thứ hai là chắc chắn tốn kém hơn so với đầu tiên.

Answer 3

Vấn đề với mẹo trao đổi XOR là nó hoàn toàn tuần tự. Nó có vẻ có vẻ nhanh chóng, nhưng thực tế, nó không phải. Có một lệnh gọi là XCHG hoán đổi hai thanh ghi, nhưng điều này cũng có thể chậm hơn so với việc sử dụng 3 MOVs, do tính chất nguyên tử của nó. Kỹ thuật chung với nhiệt độ là một lựa chọn tuyệt vời;)