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

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

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

На этом уровне все очень зависит от оборудования и компилятора. Достаточно ли умен ли компилятор, чтобы скомпилировать <без потока управления? gcc на x86 достаточно умен; lcc - нет. В старых или встроенных наборах инструкций может быть невозможно вычислить <без потока управления.

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

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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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. Однако, если вложение становится настолько глубоким, вы хотите убедиться, что тестирование всех из них действительно быстрее, чем выполнение только минимальных тестов, предлагаемых оценкой короткого замыкания.