Штраф за промах кеша при ветвлении
Интересно, быстрее ли заменить ветвление с 2 умножениями или нет (из-за потери промаха кэша)?
Вот мой случай:
float dot = rib1.x*-dir.y + rib1.y*dir.x;
if(dot<0){
dir.x = -dir.x;
dir.y = -dir.y;
}
И я пытаюсь заменить его на:
float dot = rib1.x*-dir.y + rib1.y*dir.x;
int sgn = (dot < 0.0) - (0.0 < dot ); //returns -1 or 1 (no branching here, tested)
dir.x *= sgn;
dir.y *= sgn;
Решение
Стоимость умножения зависит от нескольких факторов: от того, используете ли вы 32-разрядные или 64-разрядные числа с плавающей запятой, а также от того, используете ли вы SSE или нет. Стоимость двух умножений с плавающей точкой составляет 10 циклов в соответствии с этим источником: http://www.agner.org/optimize/instruction_tables.pdf
Стоимость филиала также зависит от нескольких факторов. Как правило, не беспокойтесь о ветвях в вашем коде. Точное поведение предиктора ветвления на процессоре будет определять производительность, но в этом случае вы, вероятно, должны ожидать, что ветвь будет в лучшем случае непредсказуемой, так что это может привести к множеству неправильных предсказаний ветвления. Стоимость ошибочного прогноза отрасли составляет 10-30 циклов согласно этому источнику: http://valgrind.org/docs/manual/cg-manual.html
Лучший совет, который кто-либо может дать здесь, — это профиль и тестирование. Я думаю, что на современном Core i7 два умножения должны быть быстрее, чем ветвь, if the range of input varies sufficiently as to cause sufficient branch mispredictions as to outweigh the cost of the additional multiplication,
Предполагая, что промах составляет 50%, стоимость ветви в среднем составляет 15 циклов (30 * 0,5), а стоимость флотационного мульта составляет 10 циклов.
РЕДАКТИРОВАТЬ: Добавлены ссылки, обновлена ориентировочная стоимость инструкций.
Другие решения
Ветвление не влечет за собой пропадание кэша: нарушается только предварительная выборка / конвейеризация инструкций, поэтому вы можете заблокировать некоторую оптимизацию SSE во время компиляции.
С другой стороны, если используются только инструкции x86, спекулятивное исполнение позволит процессору правильно запустить выполнение наиболее используемой ветви.
С другой стороны, если вы введете if для 50% случаев, вы находитесь в худшем состоянии: в этом случае я бы попытался найти конвейерную обработку SSE и оптимизировать выполнение с помощью SSE, вероятно, получая некоторые подсказки от эта почта, в соответствии с вашим вторым блоком кода.
Однако сравните ваш код, проверьте созданный ассемблер, чтобы найти лучшее решение для этой оптимизации, и получите правильное представление. И в конечном итоге держать нас в курсе 🙂