Оптимизация побитовой логики

В моем коде следующие горячие точки:

int table1[256] = /*...*/;
int table2[512] = /*...*/;
int table3[512] = /*...*/;

int* result = /*...*/;
for(int r = 0; r < r_end; ++r)
{
    std::uint64_t bits = bit_reader.value(); // 64 bits, no assumption regarding bits.

    // The get_ functions are table lookups from the highest word of the bits variable.

    struct entry
    {
        int sign_offset : 5;
        int r_offset    : 4;        
        int x           : 7;        
    };

    // NOTE: We are only interested in the highest word in the bits variable.

    entry e;
    if(is_in_table1(bits)) // branch prediction should work well here since table1 will be hit more often than 2 or 3, and 2 more often than 3.
        e = reinterpret_cast<const entry&>(table1[get_table1_index(bits)]);
    else if(is_in_table2(bits))
        e = reinterpret_cast<const entry&>(table2[get_table2_index(bits)]);
    else
        e = reinterpret_cast<const entry&>(table3[get_table3_index(bits)]);

    r                 += e.r_offset; // r is 18 bits, top 14 bits are always 0.
    int x              = e.x; // x is 14 bits, top 18 bits are always 0.        
    int sign_offset    = e.sign_offset;

    assert(sign_offset <= 16 && sign_offset > 0);

    // The following is the hotspot.

    int sign    = 1 - (bits >> (63 - sign_offset) & 0x2);
    (*result++) = ((x << 18) * sign) | r; // 32 bits

    // End of hotspot

    bit_reader.skip(sign_offset); // sign_offset is the last bit used.
}

Хотя я еще не понял, как его оптимизировать, возможно, что-то из intrinsics для операций в бит-гранулярности, __shiftleft128 или _rot может быть полезно?

Обратите внимание, что я также обрабатываю результирующие данные на графическом процессоре, поэтому важно что-то сделать в result, которое GPU может использовать для вычисления правильного.

Предложения?

EDIT:

Добавлен просмотр таблицы.

EDIT:

            int sign = 1 - (bits >> (63 - e.sign_offset) & 0x2);
000000013FD6B893  and         ecx,1Fh  
000000013FD6B896  mov         eax,3Fh  
000000013FD6B89B  sub         eax,ecx  
000000013FD6B89D  movzx       ecx,al  
000000013FD6B8A0  shr         r8,cl  
000000013FD6B8A3  and         r8d,2  
000000013FD6B8A7  mov         r14d,1  
000000013FD6B8AD  sub         r14d,r8d

Ответ 1

Я думаю, что это самое быстрое решение:

*result++ = (_rotl64(bits, sign_offset) << 31) | (x << 18) | (r << 0); // 32 bits

Затем верните x в зависимости от того, установлен ли бит знака на GPU.

Ответ 2

Я упускал из виду тот факт, что знак +/- 1, поэтому я исправляю свой ответ.

Предполагая, что mask представляет собой массив с правильно определенными битмасками для всех возможных значений sign_offset, этот подход может быть быстрее

  bool sign = (bits & mask[sign_offset]) != 0;
  __int64 result = r;
  if (sign)
    result |= -(x << 18);
  else
    result |= x << 18;

Код, сгенерированный оптимизированной конструкцией VC2010

Код OP (11 инструкций)

; 23   :   __int64 sign = 1 - (bits >> (63 - sign_offset) & 0x2);

    mov rax, QWORD PTR bits$[rsp]
    mov ecx, 63                 ; 0000003fH
    sub cl, BYTE PTR sign_offset$[rsp]
    mov edx, 1
    sar rax, cl

; 24   :   __int64 result  = ((x << 18) * sign) | r; // 32 bits
; 25   :   std::cout << result;

    and eax, 2
    sub rdx, rax
    mov rax, QWORD PTR x$[rsp]
    shl rax, 18
    imul    rdx, rax
    or  rdx, QWORD PTR r$[rsp]

Мой код (8 инструкций)

; 34   :   bool sign = (bits & mask[sign_offset]) != 0;

    mov r11, QWORD PTR sign_offset$[rsp]

; 35   :   __int64 result = r;
; 36   :   if (sign)
; 37   :     result |= -(x << 18);

    mov rdx, QWORD PTR x$[rsp]
    mov rax, QWORD PTR mask$[rsp+r11*8]
    shl rdx, 18
    test    rax, QWORD PTR bits$[rsp]
    je  SHORT [email protected]
    neg rdx
[email protected]:

; 38   :   else
; 39   :     result |= x << 18;

    or  rdx, QWORD PTR r$[rsp]

ИЗМЕНИТЬ по Skizz

Чтобы избавиться от ветки:

shl rdx, 18
lea rbx,[rdx*2]
test rax, QWORD PTR bits$[rsp]
cmove rbx,0
sub rdx,rbx
or rdx, QWORD PTR r$[rsp]

Ответ 3

Пусть выполнены эквивалентные преобразования:

int sign = 1 - (bits >> (63 - sign_offset) & 0x2);
int result  = ((x << 18) * sign) | r; // 32 bits

Возможно, процессор найдет смещение 32-битных значений дешевле - замените определение HIDWORD тем, что ведет к прямому доступу к DWORD высокого порядка без сдвига. Кроме того, для подготовки следующего шага позвольте переставить сдвиг во втором присвоении:

#define HIDWORD(q) ((uint32_t)((q) >> 32))
int sign = 1 - (HIDWORD(bits) >> (31 - sign_offset) & 0x2);
int result  = ((x * sign) << 18) | r; // 32 bits

Заметим, что в двух-дополнении q * (-1) равно ~q + 1 или (q ^ -1) - (-1), а q * 1 равно (q ^ 0) - 0. Это оправдывает второе преобразование, которое избавляется от неприятного умножения:

int mask = -(HIDWORD(bits) >> (32 - sign_offset) & 0x1);
int result  = (((x ^ mask) - mask) << 18) | r; // 32 bits

Теперь переставьте снова смещение:

int mask = (-(HIDWORD(bits) >> (32 - sign_offset) & 0x1)) << 18;
int result  = (((x << 18) ^ mask) - mask) | r; // 32 bits

Напомним тождество относительно - и ~:

int mask = (~(HIDWORD(bits) >> (32 - sign_offset) & 0x1) + 1) << 18;

Снова перестроить сдвиг:

int mask = (~(HIDWORD(bits) >> (32 - sign_offset) & 0x1)) << 18 + (1 << 18);

Кто может, наконец, отменить это? (Преобразуются ли преобразования в любом случае?)

(Обратите внимание, что только профилирование на реальном CPU может оценить производительность. Меры, такие как количество команд, не будут выполняться. Я даже не уверен, что преобразования помогли вообще.)

Ответ 4

Чтобы вычислить знак, я бы предложил следующее:

int sign = (int)(((int64_t)(bits << sign_offset)) >> 63);

Это всего две инструкции (shl и sar).

Если sign_offset больше, чем я ожидал:

int sign = (int)(((int64_t)(bits << (sign_offset - 1))) >> 63);

Что еще неплохо. Должно быть только 3 инструкции.

Это дает ответ как 0 или -1, с которым вы можете это сделать:

(*result++) = (((x << 18) ^ sign) - sign) | r;

Ответ 5

Доступ к памяти обычно является корнем всех задач оптимизации на современных процессорах. Вы вводите в заблуждение инструментами производительности относительно того, где происходит замедление. Возможно, компилятор переупорядочивает код примерно так: -

int sign    = 1 - (bits >> (63 - get_sign_offset(bits)) & 0x2);
(*result++) = ((get_x(bits) << 18) * sign) | (r += get_r_offset(bits));

или даже: -

(*result++) = ((get_x(bits) << 18) * (1 - (bits >> (63 - get_sign_offset(bits)) & 0x2))) | (r += get_r_offset(bits));

Это выделит линии, которые вы определили как горячие точки.

Я бы посмотрел, как вы организуете свою память и какие функции выполняют функции get_. Можете ли вы публиковать функции get_ вообще?