使用进位标志进行高效的128位加法

Question

我在我的C++代码的内部循环中使用了128位整数计数器.(不相关背景:实际应用是评估规则网格上的有限差分方程,其中涉及重复递增大整数,甚至64位也不够精确,因为小的舍入累积足以影响答案.)

我将整数表示为两个64位无符号长整数.我现在需要将这些值递增128位常数.这并不难,但你必须手动捕捉低字到高字的进位.

我有这样的工作代码:

inline void increment128(unsigned long &hiWord, unsigned long &loWord)
  {
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    loWord += loAdd;
    if (loWord < loAdd) ++hiWord; // test_and_add_carry
    hiWord += hiAdd;
  }

这是一个紧凑而简单的代码.有用.

不幸的是,这大约是我运行时的20%.这条杀手线就是低价测试.如果我删除它,我显然得到了错误的答案,但运行时开销从20%下降到4%!因此携带测试特别昂贵!

我的问题:C++是否公开了硬件进位标志,即使是作为GCC的扩展？如果实际编译的指令使用最后一个进位指令进行添加,似乎可以在没有上面的测试和添加进位线的情况下完成添加.有没有办法重写test-and-add-carry行以使编译器使用内部操作码？

Answer 1

实际上,如果你仔细编写代码,gcc会自动使用进位...

我编译了这段代码gcc -O2 -Wall -Werror -S:

void increment128_1(unsigned long &hiWord, unsigned long &loWord)
{
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    loWord += loAdd;
    if (loWord < loAdd) ++hiWord; // test_and_add_carry                                                                                                             
    hiWord += hiAdd;
}

void increment128_2(unsigned long &hiWord, unsigned long &loWord)
{
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    loWord += loAdd;
    hiWord += hiAdd;
    hiWord += (loWord < loAdd); // test_and_add_carry                                                                                                               
}

这是increment128_1的程序集:

.cfi_startproc
        movabsq     $-8801131483544218438, %rax
        addq        (%rsi), %rax
        movabsq     $-8801131483544218439, %rdx
        cmpq        %rdx, %rax
        movq        %rax, (%rsi)
        ja  .L5
        movq        (%rdi), %rax
        addq        $1, %rax
.L3:
        movabsq     $6794178679361, %rdx
        addq        %rdx, %rax
        movq        %rax, (%rdi)
        ret

...这是increment128_2的程序集:

        movabsq     $-8801131483544218438, %rax
        addq        %rax, (%rsi)
        movabsq     $6794178679361, %rax
        addq        (%rdi), %rax
        movabsq     $-8801131483544218439, %rdx
        movq        %rax, (%rdi)
        cmpq        %rdx, (%rsi)
        setbe       %dl
        movzbl      %dl, %edx
        leaq        (%rdx,%rax), %rax
        movq        %rax, (%rdi)
        ret

请注意第二个版本中缺少条件分支.

[编辑]

此外,引用通常不利于性能,因为GCC必须担心别名...通常更好的方法是按值传递事物.考虑:

struct my_uint128_t {
    unsigned long hi;
    unsigned long lo;
};

my_uint128_t increment128_3(my_uint128_t x)
{
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    x.lo += loAdd;
    x.hi += hiAdd + (x.lo < loAdd);
    return x;
}

部件:

        .cfi_startproc
        movabsq     $-8801131483544218438, %rdx
        movabsq     $-8801131483544218439, %rax
        movabsq     $6794178679362, %rcx
        addq        %rsi, %rdx
        cmpq        %rdx, %rax
        sbbq        %rax, %rax
        addq        %rcx, %rax
        addq        %rdi, %rax
        ret

这实际上是三者中最严密的代码.

...好吧所以他们都没有自动使用随身携带:-).但他们确实避免了条件分支,我敢打赌它是缓慢的部分(因为分支预测逻辑会在一半时间内将其错误).

[编辑2]

还有一个,我偶然发现了一点点.你知道GCC内置了对128位整数的支持吗？

typedef unsigned long my_uint128_t __attribute__ ((mode(TI)));

my_uint128_t increment128_4(my_uint128_t x)
{
    const my_uint128_t hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    return x + (hiAdd << 64) + loAdd;
}

这个组件的组装大致和它一样好:

        .cfi_startproc
        movabsq     $-8801131483544218438, %rax
        movabsq     $6794178679361, %rdx
        pushq       %rbx
        .cfi_def_cfa_offset 16
        addq        %rdi, %rax
        adcq        %rsi, %rdx
        popq        %rbx
        .cfi_offset 3, -16
        .cfi_def_cfa_offset 8
        ret

(不确定推/弹ebx来自何处,但这仍然不错.)

顺便说一句,所有这些都与GCC 4.5.2一致.

Answer 2

当然,最好的答案是使用内置__int128_t支持.

或者,使用内联asm.我更喜欢使用命名参数形式:

__asm("add %[src_lo], %[dst_lo]\n"
      "adc %[src_hi], %[dst_hi]"
      : [dst_lo] "+&r" (loWord), [dst_hi] "+r" (hiWord)
      : [src_lo] "erm" (loAdd), [src_hi] "erm" (hiAdd)
      : );

loWord被标记为早期的clobber操作数,因为它是在读取其他一些操作数之前编写的.这避免了错误的代码hiAdd = loWord,因为它会阻止gcc使用相同的寄存器来保存两者.它确实阻止了编译器对loAdd = loWord案例使用相同的寄存器,但它是安全的.

正如早期的问题所指出的那样,内联asm很容易出错(以难以调试的方式,只有在对内联代码进行一些更改后才会引起麻烦).

假设x86和x86-64内联asm破坏了标志,因此不需要显式的"cc"clobber.