在c ++中为变量的xor操作实现内联汇编程序的正确方法

Question

我最近看过一篇关于如何使用xor'ing而不是使用临时变量来执行交换操作的文章.当我使用int a ^= b;结果编译代码时,不会简单地(对于at&t语法)

xor b, a
etc.

相反,它会将原始值加载到寄存器中,然后将其写回寄存器.为了优化这个,我想在内联汇编中写这个,所以它只使用三个滴答来完成整个事情,而不是像正常情况那样.

我尝试了多个关键字:

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

这些都没有用,要么给我一个语法错误,gcc似乎不接受所有的语法或者说

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

基本上,我想使用我在汇编程序块中使用的c ++代码中定义的变量,使用三行来对它们进行xor,然后让我的交换变量基本上像这样:

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.但是,这种类型的优化可能为时过早.仅仅因为有更多的指令并不意味着代码更慢 - 一些指令可能非常慢.例如,浮点BCD存储指令(fbstp),而诚然少见,接管200次-相比,一个循环的简单mov(昂纳雾的优化指南是这些时序一个很好的资源).

所以,我实现了一堆"交换"函数,一些是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)

XOR交换

这是你在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可以使用寄存器值交换内存值 - 这对您的用例来说似乎很完美.但是,当您使用它来访问内存时,它确实很慢,您将在后面看到.

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(尽管它经常以更快的速度测量,可能是因为排序).

xor_swap用C++实现稍慢因为编译器生成每个的,因为混叠的指令的附加存储器的加载/存储-如上面提到的,如果我们修改xor_swap采取int * __restrict a, int * __restrict b代替(意味着a和b从不别名),编译器生成的相同的代码作为为std_swap和tmp_swap.

xchg_swap尽管使用最少的指令数,但速度非常慢(比任何其他选项慢四倍),因为xchg如果它涉及内存访问,则不是快速操作.

最终,你必须使用一些自定义组件为基础的版本之间的选择(是很难理解和维护),或只使用std::swap(这几乎是相反的,也不同于标准库的设计者能拿出任何优化的好处,例如,在较大类型上使用矢量化).由于这是超过一亿次迭代,应该明确的是这里使用汇编代码的潜在的改进是非常小的-如果你在所有的改进(这是不明确),你会刮掉一个几微秒之最多.

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

附录: __asm__ volatile

我认为在这一点上解释内联汇编代码可能是有意义的.__asm__(在GNU模式下,asm就足够了)引入了一个汇编代码块.这volatile是为了确保编译器不会优化它 - 它喜欢只删除块.

有两种形式__asm__ volatile.其中一个也处理goto标签; 我不会在这里解决它.另一种形式最多需要四个参数,用冒号(:)分隔:

• 最简单的form(__asm__ volatile ("rdtsc"))只是转储汇编代码,但并不真正与它周围的C++代码交互.特别是,您需要猜测变量如何分配给寄存器,这不是很好.
• 请注意,汇编代码指令是用"\n",因为这个汇编代码是逐字传递给GNU汇编程序(gas).
• 第二个参数是输出操作数列表.您可以指定它们具有的"类型"(特别是,=r表示"任何寄存器操作数",并且+r表示"任何寄存器操作数,但它也用作输入").例如,: "+r" (a), "+r" (b)告诉编译%0器用包含寄存器的寄存器替换(引用第一个操作数)a,并%1使用包含的寄存器b.
• 这种表示法意味着你需要更换%eax(正如你通常eax在AT&T组装表示法中引用的那样)%%eax以逃避百分号.
• ".intel_syntax\n"如果您愿意,还可以使用切换到Intel的汇编语法.
• 第三个参数是相同的,但处理仅输入操作数.
• 第四个参数告诉编译器哪些寄存器和内存位置丢失其值以启用汇编代码周围的优化.例如,"clobbering" "memory"可能会提示编译器插入完整的内存栅栏.您可以看到我将用于临时存储的所有寄存器添加到此列表中.