Какие способы избежать условного ветвления вы знаете?

Question

Иногда цикл, в котором центральный процессор проводит большую часть времени, очень часто приводит к некоторому промедлению (неправильному прогнозированию) ветвления (около 0,5 вероятности). Я видел несколько методов для очень изолированных потоков, но никогда не представлял собой список. Те, которые я знаю, уже исправляют ситуации, когда условие может быть превращено в bool и что 0/1 каким-то образом используется для изменения. Есть ли другие условные ветви, которых можно избежать?

например. (Псевдокод)

loop () {
  if (in[i] < C )
    out[o++] = in[i++]
  ...
}

Можно переписать, возможно, потеряв читабельность, примерно так:

loop() {
  out[o] = in[i]  // copy anyway, just don't increment
  inc = in[i] < C  // increment counters? (0 or 1)
  o += inc
  i += inc
}

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

Answer 1

На примере Мэтта Джойнера:

if (b > a) b = a;

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

bool if_else = b > a;
b = a * if_else + b * !if_else;

Answer 2

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

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

Вот пример следующего кода C:

if (b > a) b = a;

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

sub eax, ebx ; = a - b
sbb edx, edx ; = (b > a) ? 0xFFFFFFFF : 0
and edx, eax ; = (b > a) ? a - b : 0
add ebx, edx ; b = (b > a) ? b + (a - b) : b + 0

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

Answer 3

Обобщением приведенного вами примера является «заменить условную оценку на математику»; избегание условного перехода в значительной степени сводится к этому.

Что происходит с заменой && на &, так это то, что, поскольку && является коротким замыканием, оно само по себе является условной оценкой. & дает одинаковые логические результаты, если обе стороны равны 0 или 1, и не имеет короткого замыкания. То же самое относится к || и |, за исключением того, что вам не нужно следить за тем, чтобы стороны были ограничены 0 или 1 (опять же, только для логических целей, т.е. вы используете результат только логически).

Answer 4

На этом уровне все зависит от оборудования и от компилятора. Является ли используемый вами компилятор достаточно умным, чтобы компилировать его <без потока управления? gcc на x86 достаточно умен; <a href="http://www.cs.princeton.edu/software/lcc/" rel="nofollow noreferrer"> lcc нет. На старых или встроенных наборах команд может быть невозможно вычислить <без потока управления. </p>

Помимо этого Кассандровидного предупреждения трудно сделать какие-либо полезные общие заявления. Итак, вот некоторые общие утверждения, которые могут оказаться бесполезными:

• Современное аппаратное предсказание ветвления ужасно хорошо. Если бы вы могли найти настоящую программу, в которой плохое прогнозирование ветвлений стоит более чем на 1–2%, я был бы очень удивлен.

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

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

  • Развертывание цикла повторяет тела цикла и дает оптимизатору больше потока управления для работы.

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

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

Answer 5

GCC уже достаточно умен, чтобы заменить условные обозначения более простыми инструкциями. Например, более новые процессоры Intel обеспечивают cmov (условное перемещение). Если вы можете использовать его, SSE2 предоставляет некоторые инструкции для сравнения 4 целых чисел (или 8 коротких или 16 символов) за раз.

Дополнительно для вычисления минимума, который вы можете использовать (см. Эти фокусы ):

min(x, y) = x+(((y-x)>>(WORDBITS-1))&(y-x))

Однако обратите внимание на такие вещи, как:

c[i][j] = min(c[i][j], c[i][k] + c[j][k]);   // from Floyd-Warshal algorithm

даже скачки не подразумеваются, намного медленнее, чем

int tmp = c[i][k] + c[j][k];
if (tmp < c[i][j])
    c[i][j] = tmp;

Мое лучшее предположение заключается в том, что в первом фрагменте вы чаще загрязняете кэш, а во втором - нет.

Answer 6

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

if (a) {
  if (b) {
    result = q;
  } else {
    result = r;
  }
} else {
  if (b) {
    result = s;
  } else {
    result = t;
  }
}

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

// assuming a and b are bools and thus exactly 0 or 1 ...
static const table[] = { t, s, r, q };
unsigned index = (a << 1) | b;
result = table[index];

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

Answer 7

Большинство процессоров обеспечивают прогноз ветвления, который лучше, чем 50%. На самом деле, если вы получите улучшение прогноза ветвей на 1%, вы можете опубликовать статью. Есть множество статей на эту тему, если вам интересно.

Вам лучше беспокоиться о попаданиях и промахах кэша.

Answer 8

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

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

Answer 9

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