В связи с этим ответом: qaru.site/info/1/...
В приведенном выше ответе он упомянул, как избежать предсказания ветвления, избегая ветвей.
Пользователь демонстрирует это, заменив:
if (data[c] >= 128)
{
sum += data[c];
}
С
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
Как эти два эквивалента (для определенного набора данных, а не строго эквивалентного)?
Какие общие способы я могу делать с подобными вещами в подобных ситуациях? Всегда ли это было бы с помощью >> и ~?
int t = (data[c] - 128) >> 31;
Трюк здесь в том, что если data[c] >= 128, то data[c] - 128 неотрицательно, в противном случае оно отрицательно. Самый старший бит в int, знаковый бит, равен 1, если и только если это число отрицательно. >> - это сдвиг, который расширяет знаковый бит, поэтому сдвиг вправо на 31 делает весь результат 0, если он был неотрицательным, и все 1 бит (который представляет -1), если он был отрицательным. Итак, t есть 0, если data[c] >= 128 и -1 в противном случае. ~t переключает эти возможности, поэтому ~t -1, если data[c] >= 128 и 0 в противном случае.
x & (-1) всегда равен x, а x & 0 всегда равен 0. Итак, sum += ~t & data[c] увеличивает sum на 0, если data[c] < 128, а в противном случае - на data[c].
Многие из этих трюков могут быть применены в другом месте. Этот трюк, безусловно, может быть обычно применен для того, чтобы число было 0 тогда и только тогда, когда одно значение больше или равно другому значению, а -1 в противном случае, и вы можете с ним немного поработать, чтобы получить <=, < и т.д. Подобное битное сближение - это общий подход к созданию математических операций без ветвей, хотя он, конечно же, не всегда будет построен из одних и тех же операций; ^ (xor) и | (или) также иногда появляются в игре.
В то время как ответ Луи Вассермана верен, я хочу показать вам более общий (и гораздо более ясный) способ писать нераспространяемый код. Вы можете просто использовать оператор ? ::
int t = data[c];
sum += (t >= 128 ? t : 0);
JIT-компилятор видит из профиля выполнения, что условие плохо предсказано здесь. В таких случаях компилятор достаточно умен, чтобы заменить условную ветвь условной инструкцией перемещения:
mov 0x10(%r14,%rbp,4),%r9d ; load R9d from array
cmp $0x80,%r9d ; compare with 128
cmovl %r8d,%r9d ; if less, move R8d (which is 0) to R9d
Вы можете убедиться, что эта версия работает одинаково быстро для отсортированного и несортированного массива.
Необработанный код означает, как правило, оценивать все возможные исходы условного оператора с весом из набора [0, 1], так что Sum {weight_i} = 1. Большинство вычислений по существу отбрасываются. Некоторая оптимизация может возникнуть из-за того, что E_i не должно быть правильным, если соответствующий вес w_i (или mask m_i) равен нулю.
result = (w_0 * E_0) + (w_1 * E_1) + ... + (w_n * E_n) ;; or
result = (m_0 & E_0) | (m_1 & E_1) | ... | (m_n * E_n)
где m_i обозначает битмаску.
Скорость может быть достигнута также путем параллельной обработки E_i с горизонтальным коллапсом.
Это противоречит семантике if (a) b; else c; или тройной сокращенности a ? b : c, где оценивается только одно выражение из [b, c].
Таким образом, тройная операция не является волшебной пулей для нераспределенного кода. Достойный компилятор создает нераспространяемый код в равной степени для
t = data[n];
if (t >= 128) sum+=t;
против.
movl -4(%rdi,%rdx), %ecx
leal (%rax,%rcx), %esi
addl $-128, %ecx
cmovge %esi, %eax
Варианты нераспределенного кода включают представление проблемы через другие ветвящиеся нелинейные функции, такие как ABS, если они присутствуют на целевой машине.
например.
2 * min(a,b) = a + b - ABS(a - b),
2 * max(a,b) = a + b + ABS(a - b)
или даже:
ABS(x) = sqrt(x*x) ;; caveat -- this is "probably" not efficient
В дополнение к << и ~, возможно, выгодно использовать bool и !bool вместо (возможно, undefined) (int → 31). Аналогично, если условие оценивается как [0, 1], можно сгенерировать рабочую маску с отрицанием:
-[0, 1] = [0, 0xffffffff] in 2 complement representation