Эффективное 128-битное сложение с использованием флага переноса
Я использую 128-битный счетчик целых чисел в самых внутренних циклах моего кода C++. (Неактуальный фон: фактическое приложение оценивает уравнения с конечными разностями на регулярной сетке, которая включает в себя многократно увеличивающиеся большие целые числа, и даже 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 выше, если фактические скомпилированные инструкции использовали сложение с использованием последней инструкции переноса для добавления hiWord. Есть ли способ переписать строку test-and-add-carry, чтобы компилятор использовал встроенный код операции?
2 ответа
На самом деле, 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, кстати.
Лучший ответ, конечно, это использовать встроенный __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 помечен как ранний операнд clobber, потому что он написан до того, как прочитаны некоторые другие операнды. Это позволяет избежать неправильного кода для hiAdd = loWord потому что это остановит gcc от использования одного и того же регистра для хранения обоих. Это мешает компилятору использовать тот же регистр для loAdd = loWord Дело, однако, там, где это безопасно.
Как указывает этот вопрос раннего начала, встроенный asm действительно легко ошибиться (сложными для отладки способами, которые вызывают проблемы только после некоторого изменения в коде, в который он встроен).
Предполагается, что встроенные ассемблеры x86 и x86-64 заглатывают флаги, поэтому явный "cc" clobber не нужен.