在 C++ 中针对变量的异或运算实现内联汇编程序的正确方法

Question

我最近看到一篇关于如何使用异或运算而不是使用临时变量来执行交换操作的文章。当我使用 int a ^= b; 编译代码时，结果不会简单地是（对于 at&t 语法）

xor b, a
etc.

相反，它会将原始值加载到寄存器中，对其进行异或并将其写回。为了优化这一点，我想在内联汇编中编写它，因此它只使用三个刻度来完成整个事情，而不是像通常那样使用 15 个刻度。

我尝试了多个关键字，例如：

asm(...);
asm("...");
asm{...};
asm{"..."};
asm ...
__asm ...

None 有效，要么给我语法错误，gcc 似乎不接受所有这些语法，要么说

main.cpp: Assembler messages:
main.cpp:12: Error: too many memory references for `xor'

基本上，我想在汇编程序块中使用我的 C++ 代码中定义的变量，使用三行代码对它们进行异或运算，然后让我的交换变量基本上像这样：

int main() {
    volatile int a = 5;
    volatile int b = 6;
    asm {
        xor a,b
        xor b,a
        xor a,b
    };
    //a should now be 6, b should be 5
}

澄清一下：我想避免使用编译器生成的 mov 操作，因为它们需要更多 cpu 周期，而不仅仅是执行三个 xor 操作，这需要三个周期。我怎样才能做到这一点？

Answer 1

要使用内联汇编，您应该使用 __asm__ volatile. However, this type of optimization may be premature. Just because there are more instructions does not mean the code is slower - some instructions can be really slow. For example, a floating point BCD store instruction (fbstp), while admittedly rare, takes over 200 cycles - compared to one cycle for a simple mov (Agner Fog's Optimization Guide 是适合这些时间的好资源）。

所以，我实现了一堆“交换”函数，一些用 C++，一些用汇编，并做了一些测量，运行每个函数连续 1 亿次。

测试用例

`std::swap`

std::swap 可能是这里的首选解决方案。它做你想做的事（交换两个变量的值），适用于大多数标准库类型而不仅仅是整数，清楚地传达你想要实现的目标，并且可以跨架构移植。

void std_swap(int *a, int *b) {
    std::swap(*a, *b);
}

这是生成的程序集：它将两个值加载到寄存器中，然后将它们写回到相反的内存位置。

movl    (%rdi), %eax
movl    (%rsi), %edx
movl    %edx, (%rdi)
movl    %eax, (%rsi)

异或交换

这就是您在 C++ 中尝试做的事情：

void xor_swap(int *a, int *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

这不会直接转化为仅 xor 指令，因为 x86 上没有允许您直接 xor 内存中两个位置的指令 - 您总是需要至少加载一个两者的一个寄存器：

movl    (%rdi), %eax
xorl    (%rsi), %eax
movl    %eax, (%rdi)
xorl    (%rsi), %eax
movl    %eax, (%rsi)
xorl    %eax, (%rdi)

您还会生成一堆额外的指令，因为这两个指针可能别名，即指向重叠的内存区域。然后，更改一个变量也会更改另一个变量，因此编译器需要不断地存储和重新加载这些值。 使用特定于编译器的 __restrict 关键字的实现将编译为与 std_swap 相同的代码（感谢 @Ped7g 在评论中指出了这个缺陷）。

用临时变量交换

这是带有临时变量的“标准”交换（编译器会立即优化为与 std::swap 相同的代码）：

void tmp_swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

`xchg`指令

xchg 可以 swap 一个内存值和一个寄存器值——一开始它看起来很适合你的用例。但是，当您使用它访问内存时，它真的很慢，稍后您会看到。

void xchg_asm_swap(int *a, int *b) {
    __asm__ volatile (
        "movl    (%0), %%eax\n\t"
        "xchgl   (%1), %%eax\n\t"
        "movl    %%eax, (%0)"
        : "+r" (a), "+r" (b)
        : /* No separate inputs */
        : "%eax"
    );
}

我们需要将两个值之一加载到寄存器中，因为两个内存位置没有xchg。

汇编中的 XOR 交换

我在 Assembly 中制作了两个版本的基于 XOR 的交换。第一个只加载寄存器中的一个值，第二个在交换它们并将它们写回之前加载两个值。

void xor_asm_swap(int *a, int *b) {
    __asm__ volatile (
        "movl   (%0), %%eax\n\t"
        "xorl   (%1), %%eax\n\t"
        "xorl   %%eax, (%1)\n\t"
        "xorl   (%1), %%eax\n\t"
        "movl   %%eax, (%0)"
        : "+r" (a), "+r" (b)
        : /* No separate inputs */
        : "%eax"
    );
}

void xor_asm_register_swap(int *a, int *b) {
    __asm__ volatile (
        "movl   (%0), %%eax\n\t"
        "movl   (%1), %%ecx\n\t"
        "xorl   %%ecx, %%eax\n\t"
        "xorl   %%eax, %%ecx\n\t"
        "xorl   %%ecx, %%eax\n\t"
        "movl   %%eax, (%0)\n\t"
        "movl   %%ecx, (%1)"
        : "+r" (a), "+r" (b)
        : /* No separate inputs */
        : "%eax", "%ecx"
    );
}

结果

您可以在 Godbolt.

上查看完整的编译结果以及生成的汇编代码

在我的机器上，时间（以微秒为单位）略有不同，但通常是可比的：

std_swap:              127371
xor_swap:              150152
tmp_swap:              125896
xchg_asm_swap:         699355
xor_asm_swap:          130586
xor_asm_register_swap: 124718

你可以看到 std_swap、tmp_swap、xor_asm_swap 和 xor_asm_register_swap 的速度通常非常相似——事实上，如果我移动 xor_asm_register_swap到前面，结果比std_swap稍微慢一点。另请注意 tmp_swap 与 std_swap 完全相同的汇编代码（尽管它通常测量速度更快，可能是因为排序）。

在 C++ 中实现的

xor_swap 稍微慢一些，因为由于别名，编译器会为每个指令生成额外的内存 load/store - 如上所述，如果我们将 xor_swap 修改为采用 int * __restrict a, int * __restrict b 代替（意味着 a 和 b 从不别名），编译器生成与 std_swap 和 tmp_swap.

相同的代码

xchg_swap，尽管使用了最少的指令，非常慢（比任何其他选项慢四倍以上），只是因为 xchg 如果涉及内存访问，则不是快速操作。

最终，您可以选择使用一些基于程序集的自定义版本（难以理解和维护）或仅使用 std::swap（这恰恰相反，并且还受益于任何优化标准库设计者可以想出的，例如在较大类型上使用矢量化）。由于这是超过 1 亿次迭代，因此应该清楚的是，在这里使用汇编代码的潜在改进非常小——如果你有任何改进（尚不清楚），你最多可以减少几微秒。

TL;DR：你不应该那样做，只需使用 std::swap(a, b)

附录：`asm volatile`

我认为此时稍微解释一下内联汇编代码可能有意义。 __asm__（在GNU模式下，asm就够了）引入一段汇编代码。 volatile 是为了确保编译器不会优化它 - 它喜欢只删除块，否则。

__asm__ volatile有两种形式。其中之一还处理 goto 标签；我不会在这里解决它。另一种形式最多接受四个参数，用冒号分隔 (:):

最简单的形式(__asm__ volatile ("rdtsc"))只是转储汇编代码，但并不真正与它周围的C++代码交互。特别是，你需要猜测变量是如何分配给寄存器的，这并不是很好。
注意汇编代码指令用"\n"分隔，因为这段汇编代码是逐字传递给GNU汇编器的(gas)。
第二个参数是输出操作数的列表。您可以指定它们具有的“类型”（特别是，=r 表示“任何寄存器操作数”，而 +r 表示“任何寄存器操作数，但它也用作输入”）。例如，: "+r" (a), "+r" (b) 告诉编译器用包含 a 的寄存器替换 %0（引用第一个操作数），用包含 [=43= 的寄存器替换 %1 ].
此表示法意味着您需要用 %%eax 替换 %eax（您通常会在 AT&T 汇编表示法中引用 eax）以转义百分号。
如果您愿意，也可以使用 ".intel_syntax\n" 切换到 Intel 的汇编语法。
第三个参数相同，但处理仅输入操作数。
第四个参数告诉编译器哪些寄存器和内存位置丢失了它们的值以启用围绕汇编代码的优化。例如，“clobbering”"memory" 可能会提示编译器插入完整的内存栅栏。可以看到我把我用来暂存的寄存器都加到这个列表里了

在 C++ 中针对变量的异或运算实现内联汇编程序的正确方法

Correct way to implement inline assembler in c++ for xor operations on variables

c++

assembly

inline

xor

测试用例

`std::swap`

异或交换

用临时变量交换

`xchg`指令

汇编中的 XOR 交换

结果

附录：`asm volatile`

在 C++ 中针对变量的异或运算实现内联汇编程序的正确方法

Correct way to implement inline assembler in c++ for xor operations on variables

c++

assembly

inline

xor

测试用例

std::swap

异或交换

用临时变量交换

xchg指令

汇编中的 XOR 交换

结果

附录：__asm__ volatile

`std::swap`

`xchg`指令

附录：`asm volatile`