実際、コードを慎重に記述すれば、gcc はキャリーを自動的に使用します...
現在の GCC は/ (x86 の add-with-carry) に 最適hiWord += (loWord < loAdd);化できます。この最適化は GCC5.3 で導入されました。addadc
(編集者注: もちろん難しいのは、キャリーインとキャリーアウトを伴う正しい全加算器を書くことです。これは C では難しく、GCC は私が見たものを最適化する方法を知りません。)
また関連: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.htmlは、署名されていない、または署名されたオーバーフロー検出からキャリーアウトを提供できます。
GCC4.5 のような古い GCC は、setcを使用する代わりに、 add からのキャリーアウトで or に分岐し、 if you usedからのフラグ結果adcでのみadc(add-with-carry)使用されます。(または32 ビット ターゲット)。gcc に 128 ビット整数はありますか?を参照してください。- GCC4.1 以降でサポートされている 64 ビット ターゲットのみ。add__int128uint64_t
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
2 番目のバージョンには条件分岐がないことに注意してください。
[編集]
また、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
これは、実際には 3 つのコードの中で最もタイトなコードです。
...OKなので、実際にキャリーを自動的に使用した人はいません:-)。しかし、彼らは条件付き分岐を避けています。これはおそらく遅い部分です (分岐予測ロジックが半分の時間で間違っているため)。
[編集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;
}
この 1 つのアセンブリは、次のようになります。
.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 を使用しています。