使用辅助变量和不使用辅助变量的变量交换 - 哪个更快？

Question

使用辅助变量和不使用辅助变量的变量交换 - 哪个更快？

6

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

第二个版本的代码更长，但我不太了解汇编代码，所以不知道这是否意味着它更慢，因此我想听听更了解此方面的人的意见。

上述两个变量交换的版本中，哪一个更快且占用更少的内存？

- shutefan

4

为了找出哪个更快，为什么不进行基准测试呢？ - Dan Fego

我不知道如何测量内存使用情况，而且我也对其背后的原因感兴趣。 - shutefan

4

看起来你没有开启优化进行编译。汇编代码中有很多冗余内容。 - Drew Dormann

1

XOR技巧在很久以前可能会更快，但在现代CPU上不再如此。只需使用临时变量并启用编译器优化即可。 - Blastfurnace

尝试评估编译器生成的未经过优化处理的代码速度是没有意义的。 - Gunther Piez

3个回答

3

XOR交换技巧的问题在于它是严格顺序的。它可能看起来速度很快，但实际上并非如此。有一条指令叫做XCHG可以交换两个寄存器，但由于其原子性，这可能比仅使用3个MOVs更慢。使用临时变量的常见技巧是一个很好的选择；）

- ScarletAmaranth

-1 xchg reg1, reg2 指令没有同步问题。同步问题只会在使用内存操作数的 xchg 指令中出现。 - Johan

@Johan 哇，好的，知道了，谢谢！ :) （我修正了答案） - ScarletAmaranth

你修改了答案，但仍然不正确。XCHG reg, reg没有原子性问题，因此它不比3个MOV慢。根据处理器的不同，XCHG可能会（或可能不会）分解成多个微操作。只有XCHG reg，[reg]（交换寄存器和内存位置）是慢的，因为它附加了一个隐式的LOCK前缀。正是LOCK前缀使其变慢。 - Johan

0

为了了解成本，可以想象每个命令都有执行成本，而间接寻址也有自己的成本。

movl   -12(%rbp), %ecx

这行代码需要一个时间单位来访问ecx寄存器中的值，另一个时间单位来访问rbp，再加上一个时间单位来应用偏移量（-12），以及更多的时间单位（任意设定为3个）来将存储在ecx中地址的值移动到-12（%rbp）所指示的地址。

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

- Angelos Kapsimanis

1

这在这种情况下是正确的，但并不普遍，因为它忽略了流水线操作的机会。 - gnometorule

同意，但是你必须知道如何优化你的代码以实现最佳流水线和最小化分支。我认为对于我们的朋友来说，从减少不必要的引用和过多的命令开始，然后再转向更高级的技术会更容易些。 - Angelos Kapsimanis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

看一下一些优化的汇编代码。来自

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 的效率似乎已经达到了极致。