бит хак против условного оператора внутри цикла

Question

У меня есть функция вычисления CRC, которая имеет следующее в своем внутреннем цикле:

if (uMsgByte & 0x80) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x40) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x20) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x10) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x08) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x04) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x02) crc ^= *pChkTableOffset; pChkTableOffset++; 
if (uMsgByte & 0x01) crc ^= *pChkTableOffset; pChkTableOffset++; 

профилирование показало, что много времени тратится на эти заявления. И мне было интересно, могу ли я получить некоторую выгоду, заменив условные выражения на «бит-хаки». Я попытался следующие, но не получил никакого улучшения скорости:

crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x80) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x40) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x20) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x10) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x08) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x04) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x02) - 1); 
crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x01) - 1); 

это должно быть быстрее на недавнем x86 CPU или есть лучший способ реализации этих «бит хаков»?

Answer 1

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

Здесь вы выражаете намерение, как если бы вы писали машинный код

std::uint32_t foo1(std::uint8_t uMsgByte, 
        std::uint32_t crc, 
        const std::uint32_t* pChkTableOffset) 
{ 
    if (uMsgByte & 0x80) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x40) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x20) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x10) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x08) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x04) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x02) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x01) crc ^= *pChkTableOffset; pChkTableOffset++; 

    return crc; 
} 

Здесь выражаю намерение в более алгоритмический ...

std::uint32_t foo2(std::uint8_t uMsgByte, 
        std::uint32_t crc, 
        const std::uint32_t* pChkTableOffset) 
{ 
    for (int i = 0 ; i < 7 ; ++i) { 
     if (uMsgByte & (0x01 << (7-i))) 
      crc ^= pChkTableOffset[i]; 

    } 
    return crc; 
} 

Тогда я скомпилирован с использованием г ++ -O3 и результат был ...

точно такой же код объекта в обеих функциях

Морали: выбрать правильный алгоритм, избежать повторений, писать элегантный код, и пусть оптимизатор делать свое дело.

вот доказательство:

__Z4foo1hjPKj:       ## @_Z4foo1hjPKj 
    .cfi_startproc 
## BB#0: 
    pushq %rbp 
Ltmp0: 
    .cfi_def_cfa_offset 16 
Ltmp1: 
    .cfi_offset %rbp, -16 
    movq %rsp, %rbp 
Ltmp2: 
    .cfi_def_cfa_register %rbp 
    testb $-128, %dil 
    je LBB0_2 
## BB#1: 
    xorl (%rdx), %esi 
LBB0_2: 
    testb $64, %dil 
    je LBB0_4 
## BB#3: 
    xorl 4(%rdx), %esi 
LBB0_4: 
    testb $32, %dil 
    je LBB0_6 
## BB#5: 
    xorl 8(%rdx), %esi 
LBB0_6: 
    testb $16, %dil 
    je LBB0_8 
## BB#7: 
    xorl 12(%rdx), %esi 
LBB0_8: 
    testb $8, %dil 
    je LBB0_10 
## BB#9: 
    xorl 16(%rdx), %esi 
LBB0_10: 
    testb $4, %dil 
    je LBB0_12 
## BB#11: 
    xorl 20(%rdx), %esi 
LBB0_12: 
    testb $2, %dil 
    je LBB0_14 
## BB#13: 
    xorl 24(%rdx), %esi 
LBB0_14: 
    testb $1, %dil 
    je LBB0_16 
## BB#15: 
    xorl 28(%rdx), %esi 
LBB0_16: 
    movl %esi, %eax 
    popq %rbp 
    retq 
    .cfi_endproc 

    .globl __Z4foo2hjPKj 
    .align 4, 0x90 
__Z4foo2hjPKj:       ## @_Z4foo2hjPKj 
    .cfi_startproc 
## BB#0: 
    pushq %rbp 
Ltmp3: 
    .cfi_def_cfa_offset 16 
Ltmp4: 
    .cfi_offset %rbp, -16 
    movq %rsp, %rbp 
Ltmp5: 
    .cfi_def_cfa_register %rbp 
    testb $-128, %dil 
    je LBB1_2 
## BB#1: 
    xorl (%rdx), %esi 
LBB1_2: 
    testb $64, %dil 
    je LBB1_4 
## BB#3: 
    xorl 4(%rdx), %esi 
LBB1_4: 
    testb $32, %dil 
    je LBB1_6 
## BB#5: 
    xorl 8(%rdx), %esi 
LBB1_6: 
    testb $16, %dil 
    je LBB1_8 
## BB#7: 
    xorl 12(%rdx), %esi 
LBB1_8: 
    testb $8, %dil 
    je LBB1_10 
## BB#9: 
    xorl 16(%rdx), %esi 
LBB1_10: 
    testb $4, %dil 
    je LBB1_12 
## BB#11: 
    xorl 20(%rdx), %esi 
LBB1_12: 
    testb $2, %dil 
    je LBB1_14 
## BB#13: 
    xorl 24(%rdx), %esi 
LBB1_14: 
    movl %esi, %eax 
    popq %rbp 
    retq 
    .cfi_endproc 

Было бы интересно посмотреть, если компилятор выполняет также так хорошо с версией кода, который использует логические операции, а не условных операторов.

Дано:

std::uint32_t logical1(std::uint8_t uMsgByte, 
         std::uint32_t crc, 
         const std::uint32_t* pChkTableOffset) 
{ 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x80) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x40) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x20) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x10) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x8) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x4) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x2) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x1) - 1); 

    return crc; 
} 

полученный машинный код:

8 много:

movl %edi, %eax  ; get uMsgByte into eax 
    shll $24, %eax  ; shift it left 24 bits so that bit 7 is in the sign bit 
    sarl $31, %eax  ; arithmetic shift right to copy the sign bit into all other bits 
    andl (%rdx), %eax ; and the result with the value from the table 
    xorl %esi, %eax  ; exclusive-or into crc 

так короткий ответ - да она выполняет очень хорошо (eliding избыточные приращения pChkTableOffset)

Быстрее ли это? кто знает. Вероятно, не измеримо - количество извлечений памяти в обоих случаях одинаково. Компилятор может решить, лучше ли избегать ветвей или не намного лучше, чем вы можете (в зависимости от архитектуры, которую оптимизирует компилятор).

Является ли оно более изящным и удобочитаемым? Для меня нет. Это своего рода код, который я имел обыкновение писать, когда:

• с был еще молодой язык
• процессоры были достаточно просты, что я мог бы сделать лучшую работу по оптимизации
• процессоров настолько медленно, что я должен был

Ни один из них не применяется.

Answer 2

Я не могу точно сказать, что такое FASTER, но они определенно разные - это быстрее зависит от того, какой процессор и модель используются, поскольку они ведут себя по-разному на [предположительно непредсказуемых] ветвях. И для дальнейшего усложнения ситуации разные процессоры имеют различное поведение для «зависимых вычислений».

я преобразовал отправил код в это (что делает сгенерированный код около половины до тех пор, но в остальном идентичны на концептуальном уровне):

int func1(int uMsgByte, char* pChkTableOffset) 
{ 
    int crc = 0; 
    if (uMsgByte & 0x80) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x40) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x20) crc ^= *pChkTableOffset; pChkTableOffset++; 
    if (uMsgByte & 0x10) crc ^= *pChkTableOffset; pChkTableOffset++; 

    return crc; 
} 


int func2(int uMsgByte, char* pChkTableOffset) 
{ 
    int crc = 0; 

    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x80) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x40) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x20) - 1); 
    crc ^= *pChkTableOffset++ & (!(uMsgByte & 0x10) - 1); 

    return crc; 
} 

И скомпилирован с clang++ -S -O2:

func1:

_Z5func1jPh:       # @_Z5func1jPh 
     xorl %eax, %eax 
     testb %dil, %dil 
     jns  .LBB0_2 
     movzbl (%rsi), %eax 
.LBB0_2:        # %if.end 
     testb $64, %dil 
     je  .LBB0_4 
     movzbl 1(%rsi), %ecx 
     xorl %ecx, %eax 
.LBB0_4:        # %if.end.6 
     testb $32, %dil 
     je  .LBB0_6 
     movzbl 2(%rsi), %ecx 
     xorl %ecx, %eax 
.LBB0_6:        # %if.end.13 
     testb $16, %dil 
     je  .LBB0_8 
     movzbl 3(%rsi), %ecx 
     xorl %ecx, %eax 
.LBB0_8:        # %if.end.20 
     retq 

func2:

_Z5func2jPh:       # @_Z5func2jPh 
     movzbl (%rsi), %eax 
     movl %edi, %ecx 
     shll $24, %ecx 
     sarl $31, %ecx 
     andl %eax, %ecx 
     movzbl 1(%rsi), %eax 
     movl %edi, %edx 
     shll $25, %edx 
     sarl $31, %edx 
     andl %edx, %eax 
     xorl %ecx, %eax 
     movzbl 2(%rsi), %ecx 
     movl %edi, %edx 
     shll $26, %edx 
     sarl $31, %edx 
     andl %ecx, %edx 
     movzbl 3(%rsi), %ecx 
     shll $27, %edi 
     sarl $31, %edi 
     andl %ecx, %edi 
     xorl %edx, %edi 
     xorl %edi, %eax 
     retq 

Как вы можете видеть, компилятор генерирует ветви для первой версии, и использует логические операции на второй версии - несколько больше в случае.

Я мог бы написать код для тестирования каждого из циклов, но я гарантирую, что результат будет сильно отличаться для разных версий процессоров x86.

Я не уверен, является ли это общим вычислением CRC, но большинство вычислений CRC имеют оптимизированные версии, которые выполняют правильный расчет быстрее, чем это, используя таблицы и другие «умные вещи».

Answer 3

Если эта контрольная сумма действительно является CRC, существует гораздо более эффективный способ ее реализации.

Предполагая, что это CRC16:

Заголовок:

class CRC16 
{ 
public: 
    CRC16(const unsigned short poly); 
    unsigned short CalcCRC(unsigned char * pbuf, int len); 

protected: 
    unsigned short CRCTab[256]; 
    unsigned long SwapBits(unsigned long swap, int bits); 
}; 

Реализация:

CRC16::CRC16(const unsigned short poly) 
{ 
    for(int i = 0; i < 256; i++) { 
     CRCTab[i] = SwapBits(i, 8) << 8; 
     for(int j = 0; j < 8; j++) 
      CRCTab[i] = (CRCTab[i] << 1)^((CRCTab[i] & 0x8000) ? poly : 0); 
     CRCTab[i] = SwapBits(CRCTab[i], 16); 
    } 
} 

unsigned long CRC16::SwapBits(unsigned long swap, int bits) 
{ 
    unsigned long r = 0; 
    for(int i = 0; i < bits; i++) { 
     if(swap & 1) r |= 1 << (bits - i - 1); 
     swap >>= 1; 
    } 
    return r; 
} 

unsigned short CRC16::CalcCRC(unsigned char * pbuf, int len) 
{ 
    unsigned short r = 0; 
    while(len--) r = (r >> 8)^CRCTab[(r & 0xFF)^*(pbuf++)]; 
    return r; 
} 

Как вы можете видеть, каждый байт сообщения используется только один раз, а не в 8 раз ,

Аналогичная реализация для CRC8.

Answer 4

Из интереса, простираясь отличное предложение Alain по предварительно рассчитав таблицу CRC, это происходит со мной, что этот класс может быть изменен, чтобы воспользоваться C++ 14-х constexpr:

#include <iostream> 
#include <utility> 
#include <string> 

class CRC16 
{ 
private: 

    // the storage for the CRC table, to be computed at compile time 
    unsigned short CRCTab[256]; 

    // private template-expanded constructor allows folded calls to SwapBits at compile time 
    template<std::size_t...Is> 
    constexpr CRC16(const unsigned short poly, std::integer_sequence<std::size_t, Is...>) 
    : CRCTab { SwapBits(Is, 8) << 8 ... } 
    {} 

    // swap bits at compile time 
    static constexpr unsigned long SwapBits(unsigned long swap, int bits) 
    { 
     unsigned long r = 0; 
     for(int i = 0; i < bits; i++) { 
      if(swap & 1) r |= 1 << (bits - i - 1); 
      swap >>= 1; 
     } 
     return r; 
    } 


public: 

    // public constexpr defers to private template expansion... 
    constexpr CRC16(const unsigned short poly) 
    : CRC16(poly, std::make_index_sequence<256>()) 
    { 
     //... and then modifies the table - at compile time 
     for(int i = 0; i < 256; i++) { 
      for(int j = 0; j < 8; j++) 
       CRCTab[i] = (CRCTab[i] << 1)^((CRCTab[i] & 0x8000) ? poly : 0); 
      CRCTab[i] = SwapBits(CRCTab[i], 16); 
     } 
    } 

    // made const so that we can instantiate constexpr CRC16 objects 
    unsigned short CalcCRC(const unsigned char * pbuf, int len) const 
    { 
     unsigned short r = 0; 
     while(len--) r = (r >> 8)^CRCTab[(r & 0xFF)^*(pbuf++)]; 
     return r; 
    } 

}; 



int main() 
{ 
    // create my constexpr CRC16 object at compile time 
    constexpr CRC16 crctab(1234); 

    // caclulate the CRC of something... 
    using namespace std; 
    auto s = "hello world"s; 

    auto crc = crctab.CalcCRC(reinterpret_cast<const unsigned char*>(s.data()), s.size()); 

    cout << crc << endl; 

    return 0; 
} 

Тогда конструктор CRC16 (1234) приятно сводится к следующему:

__ZZ4mainE6crctab: 
    .short 0      ## 0x0 
    .short 9478     ## 0x2506 
    .short 18956     ## 0x4a0c 
    .short 28426     ## 0x6f0a 
    .short 601      ## 0x259 
    .short 10079     ## 0x275f 
    .short 18517     ## 0x4855 
    .short 27987     ## 0x6d53 
... etc. 

и вычисление CRC всей строки становится это:

 leaq __ZZ4mainE6crctab(%rip), %rdi ; <- referencing const data :) 
     movzwl (%rdi,%rdx,2), %edx 
     jmp  LBB0_8 
LBB0_4: 
     xorl %edx, %edx 
     jmp  LBB0_11 
LBB0_6: 
     xorl %edx, %edx 
LBB0_8:         ## %.lr.ph.i.preheader.split 
     testl %esi, %esi 
     je  LBB0_11 
## BB#9: 
     leaq __ZZ4mainE6crctab(%rip), %rsi 
     .align 4, 0x90 
LBB0_10:        ## %.lr.ph.i 
             ## =>This Inner Loop Header: Depth=1 
     movzwl %dx, %edi 
     movzbl %dh, %edx # NOREX 
     movzbl %dil, %edi 
     movzbl (%rcx), %ebx 
     xorq %rdi, %rbx 
     xorw (%rsi,%rbx,2), %dx 
     movzwl %dx, %edi 
     movzbl %dh, %edx # NOREX 
     movzbl %dil, %edi 
     movzbl 1(%rcx), %ebx 
     xorq %rdi, %rbx 
     xorw (%rsi,%rbx,2), %dx 
     addq $2, %rcx 
     addl $-2, %eax 
     jne  LBB0_10 
LBB0_11: