我在我的 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%。 killer 锏是 loWord 测试。如果我删除它,我显然会得到错误的答案,但运行时开销会从 20% 下降到 4%!所以那个携带测试特别贵!
我的问题:C++ 是否公开了硬件携带标志,即使作为 GCC 的扩展? 如果实际编译的指令使用 add using last carry 指令进行 hiWord 添加,则似乎可以在没有上面的 test-and-add-carry 行的情况下完成添加。 有没有办法重写 test-and-add-carry 行来让编译器使用内部操作码?
最佳答案
其实gcc会自动使用进位,如果你仔细写你的代码...
当前的 GCC 可以优化 hiWord += (loWord < loAdd);
进入 add
/ adc
(x86 的 add-with-carry)。 此优化是在 GCC5.3 中引入的。
- 与单独的
uint64_t
64 位模式下的 block :https://godbolt.org/z/S2kGRz . - 在 32 位模式下与
uint32_t
相同 block :https://godbolt.org/z/9FC9vc
(编者注:当然,困难的部分是编写一个 正确 带有进位和进位的全加器;这在 C 中很难,而且 GCC 不知道如何优化我的任何东西'见过。)
还相关:https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html可以为您提供无符号或有符号溢出检测。
较旧的 GCC,如 GCC4.5,将分支或 setc
在 add 的结转上,而不是使用 adc
, 并且只使用了 adc
(add-with-carry) 来自 add
的标志结果如果您使用 __int128
. (或 uint64_t
在 32 位目标上)。见 Is there a 128 bit integer in gcc? - 仅适用于 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。
关于c++ - 使用进位标志的高效 128 位加法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6659414/