有无辅助变量的变量交换-哪个更快? [英] Variable swap with and without auxiliary variable - which is faster?

问题描述

我想你们都听说过交换问题"； SO充满了关于它的问题. 不使用第三个变量的交换版本通常被认为是更快的，因为您的变量变少了.我想知道幕后发生了什么，并编写了以下两个程序:

I guess you all heard of the 'swap problem'; SO is full of questions about it. The version of the swap without use of a third variable is often considered to be faster since, well, you have one variable less. I wanted to know what was going on behind the curtains and wrote the following two programs:

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

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

    return 0;
}

以及没有第三个变量的版本:

and the version without third variable:

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

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

    return 0;
}

我使用clang生成了汇编代码，并将其用于第一个版本(使用第三个变量):

I generated the assembly code using clang and got this for the first version (that uses a third variable):

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

，这是第二个版本(不使用第三个变量):

and this for the second version (that does not use a third variable):

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

第二个比较长，但是我对汇编代码不了解很多，所以我不知道这是否意味着它比较慢，所以我想听听其他人对它的了解.

The second one is longer but I don't know much about assembly code so I have no idea if that means that it is slower so I'd like to hear the opinion of someone more knowledgable about it.

以上哪个版本的变量交换速度更快且占用的内存更少?

推荐答案

查看一些优化的程序集.来自

Look at some optimised assembly. From

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看起来效率最高.

To me, swap_temp looks as efficient as can be.

这篇关于有无辅助变量的变量交换-哪个更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！