使用进位标志进行高效 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%！所以那个携带测试特别贵！

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

Answer 1

其实如果你仔细写代码的话，gcc会自动使用进位...

目前的GCC可以将 hiWord += (loWord < loAdd); 优化为 add/adc（x86 的 add-with-carry）。 此优化是在 GCC5.3 中引入的。

• 在 64 位模式下使用单独的 uint64_t 块：https://godbolt.org/z/S2kGRz。
• 在 32 位模式下使用 uint32_t 块也是如此：https://godbolt。 org/z/9FC9vc

（编者注：当然，困难的部分是编写一个带有进位和执行的正确全加器；这在 C 语言中很难， GCC 不知道如何优化我所见过的任何内容。）

还相关： https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html 可以为您提供来自无符号或有符号溢出检测的进位。

---

较旧的 GCC，如 GCC4.5，将在 add 的进位上进行分支或 setc，而不是使用 adc，并且仅使用 adc > (add-with-carry) 如果您使用了 __int128，则在 add 的标志结果上。 （或 32 位目标上的 uint64_t）。请参阅 gcc 中是否有 128 位整数？ - 仅在 64 位目标上，自 GCC4.1 起受支持。

我用 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("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 被标记为 early clobber 操作数，因为它是在读取其他一些操作数之前写入的。这可以避免 hiAdd = loWord 的错误代码，因为它将阻止 gcc 使用相同的寄存器来保存两者。不过，它确实会阻止编译器在 loAdd = loWord 情况下使用相同的寄存器，但这是安全的。

正如那个早期问题所指出的那样，内联汇编确实很容易出错（以难以调试的方式，只会在对其内联的代码进行一些更改后才会导致问题）。

假定 x86 和 x86-64 内联 asm 会破坏标志，因此不需要显式的“cc”破坏。