有和没有辅助变量的可变交换 – 哪个更快?

我想你们都听说过“交换问题”; 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; } 

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

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

第二个更长,但我不太了解汇编代码,所以我不知道这是否意味着它更慢,所以我想听听有人对此有更多了解的意见。

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

看看一些优化的assembly。 从

 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看起来尽可能高效。

XOR交换技巧的问题在于它是严格顺序的。 它似乎看起来很快,但实际上并非如此。 有一个叫做XCHG的指令可以交换两个寄存器,但由于其primefaces性质,这也可能比简单地使用3个MOVs慢。 使用temp的常用技术是一个很好的选择;)

为了了解成本,可以想象每个命令都要执行成本,间接寻址也有其自身的成本。

 movl -12(%rbp), %ecx 

这行将需要类似于时间单位来访问ecx寄存器中的值,一个时间单位用于访问rbp,另一个用于应用偏移量(-12)和更多时间单位(让我们说任意3)用于移动值来自存储在ecx中的地址到-12(%rbp)指示的地址。

如果计算每一行和所有行中的所有操作,第二种方法肯定比第一种方法更昂贵。