Отличный вопросительный знак!
Нет. Это не быстрее.
По крайней мере, не для сравнительного анализа, который я провел с clang на процессоре Intel и g cc на процессоре ARM64.
Действительно ? приводит либо к условным переходам, либо к условным инструкциям. Несмотря на это, скомпилированный код для подхода ? оказывается на треть быстрее, чем код, использующий - и &, что позволяет избежать условного выполнения.
См. Приведенный ниже код, используемый для тестирования. Также включены скомпилированные инструкции для этого самого внутреннего утверждения. Я также протестировал другую альтернативу, отличную от тех, которые вы указали. Mark:
crc = (crc >> 1) ^ (crc & 1 ? 0xa001 : 0);
Этот по-прежнему использует условное выражение, но изолирует его от того, что является исключающим-ИЛИ смещенным CR C. Интересно, что это компилируется на Intel с тем же кодом, что и подход «минус и», без условного выполнения. В ARM он компилируется в другой, третий набор инструкций. И для Intel, и для ARM он по-прежнему медленнее, чем первый подход.
В итоге, общий подход с условным выполнением на 30–35% быстрее, чем попытки избежать условного выполнения.
Почему, спросите вы? Насколько я могу судить об ARM, вы в среднем выполняете меньше инструкций, используя условные выражения. Условный подход может использовать тот факт, что в среднем одна инструкция будет выполняться только половину времени. Это, очевидно, перевешивает стоимость непредвиденных ветвей. Также современные процессоры, похоже, очень хорошо справляются с непредсказуемыми ветвями. Для Intel это шесть инструкций в любом случае, и там, где, кажется, нет никакой пользы в половине случаев.
Это только для двух архитектур, технологий и связанных компиляторов. Ваш пробег может отличаться.
// Test the speed of alternative bit-wise CRC implementations. To do this, we
// simply propagate a CRC assuming zeros for the data with an initial value of
// all ones. A down-shifting (reflected) 16-bit CRC is used. All times are for
// one billion iterations, with each iteration cycling eight zero bits.
#include <stddef.h>
// Implementation using a conditional expression. This compiles to use a
// conditional move instruction on Intel or a conditional branch on ARM, and an
// unrolled inner loop on both. There are six instructions per iteration on
// Intel, 2.5 on average on ARM. This compiles to the fastest code on both
// architectures.
//
// Intel i7 (clang 11.0.3 -O3): 6.6 seconds
// movl %eax, %ecx
// shrl %ecx
// movl %ecx, %edx
// xorl $40961, %edx ## imm = 0xA001
// testb $1, %al
// cmovel %ecx, %edx
//
// ARM64 (gcc 6.3.0 -O3): 12.0 seconds
// tbnz x0, 0, .L4
// lsr w0, w0, 1
// .L5:
//---------
// .L4:
// eor w0, w2, w0, lsr 1 ## w2 = 0xa001
// b .L5
unsigned crc16_cond(unsigned crc, size_t len) {
while (len--)
for (unsigned k = 0; k < 8; k++)
crc = crc & 1 ? (crc >> 1) ^ 0xa001 : crc >> 1;
return crc;
}
// Different implementation using a conditional expression as before, but here
// just to select zero or the polynomial. This compiles to use no conditionals
// and an unrolled inner loop. There are six instructions per iteration on
// Intel, three on ARM. This ends up compiling to the exact same instructions
// as the minus implementation on Intel.
//
// Intel i7 (clang 11.0.3 -O3): 8.9 seconds
// movl %eax, %ecx
// shrl %ecx
// andl $1, %eax
// negl %eax
// andl $40961, %eax ## imm = 0xA001
// xorl %ecx, %eax
//
// ARM64 (gcc 6.3.0 -O3): 15.5 seconds
// tst x0, 1
// csel w3, w1, wzr, ne ## w1 = 0xa001
// eor w0, w3, w0, lsr 1
unsigned crc16_cond2(unsigned crc, size_t len) {
while (len--)
for (unsigned k = 0; k < 8; k++)
crc = (crc >> 1) ^ (crc & 1 ? 0xa001 : 0);
return crc;
}
// Implementation using a minus and an and to select zero or the polynomial.
// This compiles as written in an unrolled inner loop. There are six
// instructions per iteration on Intel and three on ARM.
//
// Intel i7 (clang 11.0.3 -O3): 8.9 seconds
// movl %eax, %ecx
// shrl %ecx
// andl $1, %eax
// negl %eax
// andl $40961, %eax ## imm = 0xA001
// xorl %ecx, %eax
//
// ARM64 (gcc 6.3.0 -O3): 16.0 seconds
// sbfx x2, x0, 0, 1
// and w2, w2, w1 ## w1 = 0xa001
// eor w0, w2, w0, lsr 1
unsigned crc16_minus(unsigned crc, size_t len) {
while (len--)
for (unsigned k = 0; k < 8; k++)
crc = (crc >> 1) ^ ((0 - (crc & 1)) & 0xa001);
return crc;
}
#include <stdio.h>
int main(void) {
unsigned crc = crc16_cond2(0xffff, 1000000000);
printf("%04x\n", crc);
return 0;
}