使用进位标志进行高效的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％。致命的问题在于loWord测试。如果我将其删除，显然会得到错误的答案，但运行时开销将从20％降至4％！因此，该进位测试特别昂贵！

我的问题是：C++是否公开硬件进位标志，即使是作为GCC的扩展？似乎可以通过使用add using last carry指令进行hiWord加法来进行添加，而无需上面的test-and-add-carry行。有没有一种重新编写test-and-add-carry行以使编译器使用内在的操作码的方法？

- Randall Meyers

---

如果这个函数是问题点，可以使用内联汇编来编写，这样可以高效处理进位：它非常简短，所以应该很容易处理（甚至更好的是，你可以使用SSE/MMX扩展直接在128位上进行计算）。 - Bruce

@Bruce — 可能是分支指令而不是函数本身。 - Todd Lehman

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）将在加法的进位输出上分支或setc，而不是使用adc，并且只有在使用__int128时才会在add的标志结果上使用adc（带进位相加）。 （或在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 进行的。

- Nemo

---

+1，最后一个指令是你要找的adc指令。 - gordy

@Gordy：确实。我有点惊讶，我无法说服GCC以其他方式生成它...我敢肯定我曾经看到过它这样做（而不是使用“TI”模式类型）。 - Nemo

@Randall：asm解决方案可行，但它只适用于x86_64。128位GCC整数将在任何具有GCC的平台上工作，其他建议将在任何有C++编译器的地方工作。您可能认为可以忽略这些问题，但多年的经验表明，如果您这样做，您将会后悔:-)。只有在无法通过其他方式获得足够的性能时才使用完整的asm路线；如果您确实使用它，请尽可能将其限制为单个模块。 - Nemo

@Nemo：现在gcc在32位平台上是否支持__int128_t？过去它是不支持的。 - Stephen Canon

@StephenCanon，GCC的__int128需要64位。可以通过编译32位（例如使用-m32）轻松检查。 MSVC的_umul128也需要64位。 - Z boson

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被标记为早期破坏操作数，因为它是在其他一些操作数被读取之前写入的。这避免了hiAdd = loWord的错误代码，因为它会阻止gcc使用相同的寄存器来保存两个值。但是，在安全的情况下，它确实阻止编译器在loAdd = loWord情况下使用相同的寄存器。

正如早期破坏问题所指出的那样，在线汇编很容易出错（以难以调试的方式，只有在嵌入到代码中后才会带来麻烦）。

x86和x86-64内联汇编假设会破坏标志位，因此不需要显式使用"cc"破坏。

- Stephen Canon

---

你应该在输出（至少对于 hiWord）上使用早期破坏标志吗？对于 256 位加法（一个加和三个 adc），如果不使用早期破坏标志，将得到错误的结果。 - Z boson

可能是，但我认为你需要在loWord上。 - Stephen Canon

使用 add + adc 绝对是一个好方法。不幸的是，C语言的抽象隐藏了这个事实，即进行128位加法很容易。 - Benoît

@PeterCordes 在x86上的内联汇编中，cc clobber不是隐式的吗？（实际上，在你不需要clobber它的情况下，这是一种痛苦的体验...） - Marc Glisse

@MarcGlisse：哦，我没有意识到！是的，在x86-32（i386）上肯定是这样的，而且看起来有关在x86-64上该怎么做的讨论选择了与i386相同的明智选择。谢谢。 - Peter Cordes