我想你们都听说过“交换问题”; 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)指示的地址。
如果计算每一行和所有行中的所有操作,第二种方法肯定比第一种方法更昂贵。
以上就是c/c++开发分享有和没有辅助变量的可变交换 – 哪个更快?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/560109.html