Эффективное добавление 128 бит с использованием флага переноса

Я использую 128-битный целочисленный счетчик в самых внутренних циклах моего кода на С++. (Неприемлемый фон: фактическое приложение оценивает конечные разностные уравнения на регулярной сетке, которая включает в себя повторное увеличение больших целых чисел, и даже 64 бита недостаточно точны, потому что небольшое округление накапливается достаточно, чтобы повлиять на ответы.)

Я представлял целое число как два 64-битных unsigned longs. Теперь мне нужно увеличить эти значения с помощью 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%! Так что перенос теста особенно дорог!

Мой вопрос: Предоставляет ли С++ флаги переноса оборудования, даже как расширение для GCC? Похоже, что дополнения могут быть сделаны без линии тестирования и добавления-переноса выше, если фактические скомпилированные инструкции использовали добавление с использованием последней инструкции переноса для добавления hiWord. Есть ли способ переписать строку test-and-add-carry, чтобы заставить компилятор использовать внутренний код операции?

Ответ 1

На самом деле 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

На самом деле это самый сложный код из трех.

... ОК, поэтому никто из них фактически не использовал перенос автоматически:-). Но они избегают условной ветки, и я уверен, что это медленная часть (поскольку логика предсказания ветвления будет ошибочной в два раза).

[edit 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

(Не знаю, откуда появился push/pop из ebx, но это все еще неплохо.)

Все это с GCC 4.5.2, кстати.

Ответ 2

Лучший ответ, конечно, заключается в использовании встроенной поддержки __int128_t.

В качестве альтернативы используйте встроенный asm. Я предпочитаю использовать форму named-argument:

__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, хотя он безопасен.

Как указывает тот вопрос раннего клобера, inline asm действительно легко ошибаться (в жестких для отладки способах, которые только вызывают проблемы после некоторого изменения кода, в который он встроен).

x86 и x86-64 inline asm предполагается clobber флагов, поэтому явный "clcber" cc не нужен.