Реалистичные примеры оптимизации путем удаления ветви

Question

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

Есть ли дополнительные и разнообразные (до & после) примеры удаления ветвей для оптимизации?

Answer 1

У этого tutorial есть еще несколько примеров. Помимо того, что здесь, я могу думать об использовании операторов switch или sentinel values. Я также нашел это other tutorial из более неясных способов избежать, если утверждения.

Если вы работаете над оптимизацией, я настоятельно рекомендую использовать инструмент профилирования, такой как callgrind/kcachegrind, и сосредоточиться на тех частях кода, где вы проводите больше всего времени. Оптимизация кода определенными способами может запутать его или сделать его в противном случае более сложным для поддержания, и, по моему опыту, оптимизация для оптимизации - это действительно плохая идея.

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

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

Answer 2

Оптимальное упорядочивание блоков может сделать немного разницу и встречается в каждом фрагменте кода. И я бы не стал просто отвергать примеры, данные Intel как «нереальные».

Answer 3

Если устранение ветвей является вашей целью, вы можете рассмотреть математику или некоторые непереносимые решения.

Рассмотрим следующий пример:

if (a < b) 
    y = C; 
else 
    y = D; 

Это может быть переписана в виде ...

x = -(a < b); /* x = -1 if a < b, x = 0 if a >= b */ 
x &= (C - D); /* x = C - D if a < b, x = 0 if a >= b */ 
x += D;   /* x = C if a < b, x = D if a >= b */ 

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

Стоило ли? Иногда, но обычно нет. Если неверное предсказание ветвления или ветви вас дорого стоит, потому что оно не смещено в сторону одной ветви или другой, то может того стоить. Но, вероятно, нет. Как всегда, профиль.

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

Надеюсь, это поможет.