Следующая реализация square производит серию операторов cmp / je, как я и ожидал от цепочки if:
int square(int num) {
if (num == 0){
return 0;
} else if (num == 1){
return 1;
} else if (num == 2){
return 4;
} else if (num == 3){
return 9;
} else if (num == 4){
return 16;
} else if (num == 5){
return 25;
} else if (num == 6){
return 36;
} else if (num == 7){
return 49;
} else {
return num * num;
}
}
И следующее производит таблицу данных для возврата:
int square_2(int num) {
switch (num){
case 0: return 0;
case 1: return 1;
case 2: return 4;
case 3: return 9;
case 4: return 16;
case 5: return 25;
case 6: return 36;
case 7: return 49;
default: return num * num;
}
}
Почему gcc не может оптимизировать верхний в нижний?
Разборка для справки: https://godbolt.org/z/UP_igi
РЕДАКТИРОВАТЬ: интересно, MSVC генерирует таблицу переходов вместо таблицы данных для случая коммутатора. И что удивительно, clang оптимизирует их до того же результата.
c++
c
gcc
optimization
compiler-optimization
chacham15
источник
источник
returns; случаи не имеютbreaks, таким образом, у коммутатора также есть определенный порядок выполнения. Цепочка if / else имеет возвраты в каждой ветви, семантика в этом случае эквивалентна. Оптимизация не невозможна . Как контрпример, ICC не оптимизирует ни одну из функций.Ответы:
Сгенерированный код для
switch-caseусловно использует таблицу переходов. В этом случае прямой возврат через справочную таблицу представляется оптимизацией, использующей тот факт, что каждый случай здесь предполагает возврат. Хотя стандарт не дает никаких гарантий на этот счет, я был бы удивлен, если бы компилятор генерировал серию сравнений вместо таблицы переходов для обычного случая переключения.Теперь, чтобы прийти
if-else, это полная противоположность. Хотяswitch-caseвыполняется в постоянное время, независимо от количества ветвей,if-elseоптимизируется для меньшего количества веток. Здесь вы можете ожидать, что компилятор генерирует серию сравнений в том порядке, в котором вы их написали.Так что, если бы я использовал,
if-elseпотому что ожидал, что большинство вызововsquare()будут для0или1редко для других значений, то «оптимизация» этого для поиска в таблице может фактически привести к тому, что мой код будет выполняться медленнее, чем я ожидал, что противоречит моей цели использованияifвместо оswitch. Таким образом , хотя это спорно, я чувствую НКА делает правильную вещь и лязг является чрезмерно агрессивным в его оптимизации.Кто-то в комментариях поделился ссылкой, где clang выполняет эту оптимизацию и также генерирует код на основе таблицы поиска
if-else. Что-то примечательное происходит, когда мы уменьшаем количество дел до двух (и по умолчанию) с помощью clang. Он снова генерирует идентичный код для if и switch, но на этот раз переключается на сравнение и перемещается вместо метода таблицы поиска, для обоих. Это означает, что даже одобряющий переключение кланг знает, что шаблон «если» более оптимален, когда число случаев невелико!Таким образом, последовательность сравнений
if-elseи таблица переходов дляswitch-case- это стандартный шаблон, которому склонны следовать компиляторы, и разработчики ожидают, когда они пишут код. Однако для определенных особых случаев некоторые компиляторы могут отказаться от этого шаблона, если они считают, что он обеспечивает лучшую оптимизацию. Другие компиляторы могут в любом случае просто придерживаться шаблона, даже если он явно не оптимален, доверяя разработчику знать, чего он хочет. Оба являются подходящими подходами со своими преимуществами и недостатками.источник
0и1)?ifочевидно, быстрее? Теперь вот пример платформы, где и 0, и 1 будут быстрее при использовании,ifчем при использовании switch: godbolt.org/z/wcJhvS (обратите внимание, что здесь также есть несколько других оптимизаций)ifоператорами или автоматически компилятором. Я не эксперт по ARM, поэтому я не совсем уверен, что ваше заявление о том, что выswitchбыстрее, чемifверно. Это будет зависеть от штрафа за неправильно предсказанные ветви, и это будет зависеть от того, какой ARM.Одним из возможных объяснений является то, что если более низкие значения
numболее вероятны, например всегда 0, сгенерированный код для первого может быть быстрее. Сгенерированный код для переключения занимает одинаковое время для всех значений.Сравнивая лучшие случаи, согласно этой таблице . Смотрите этот ответ для объяснения таблицы.
Если
num == 0для «если» у вас есть xor, test, je (с прыжком), ret. Задержка: 1 + 1 + прыжок. Однако xor и test независимы, поэтому фактическая скорость выполнения будет выше, чем 1 + 1 циклов.Если
num < 7для «switch» у вас есть mov, cmp, ja (без прыжка), mov, ret. Задержка: 2 + 1 + без прыжка + 2.Инструкция перехода, которая не приводит к прыжку, быстрее, чем инструкция, которая приводит к прыжку. Тем не менее, таблица не определяет задержку для прыжка, поэтому мне не ясно, какой из них лучше. Вполне возможно, что последний всегда лучше, и GCC просто не может его оптимизировать.
источник