Почему переключатель не оптимизирован так же, как цепочка, если еще в c / c ++?

Question

Следующая реализация 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;
    }
}

Почему g cc не может оптимизировать верхний в нижний?

Разборка для справки: https://godbolt.org/z/UP_igi

РЕДАКТИРОВАТЬ: интересно, MSV C создает таблицу переходов вместо таблицы данных для случая коммутатора. И что удивительно, clang оптимизирует их до того же результата.

Answer 1

Сгенерированный код для switch-case традиционно использует таблицу переходов. В этом случае прямой возврат через справочную таблицу представляется оптимизацией, использующей тот факт, что каждый случай здесь предполагает возврат. Хотя стандарт не дает никаких гарантий на этот счет, я был бы удивлен, если бы компилятор генерировал серию сравнений вместо таблицы переходов для обычного случая переключения.

Теперь перейдем к if-else, это полная противоположность. В то время как switch-case выполняется в постоянное время, независимо от количества ветвей, if-else оптимизируется для меньшего количества ветвей. Здесь вы можете ожидать, что компилятор в основном сгенерирует серию сравнений в том порядке, в котором вы их написали.

Так что, если бы я использовал if-else, потому что я ожидаю, что большинство вызовов square() будут для 0 или 1 и редко для других значений, тогда «оптимизация» этого для поиска в таблице может фактически привести к тому, что мой код будет работать медленнее, чем я ожидаю, что лишит меня цели использовать if вместо switch. Таким образом, хотя это спорно, я чувствую G CC делает правильную вещь и лязг является чрезмерно агрессивным в его оптимизации.

1016 * Кто-то, в комментариях, поделился ссылкой, где лязг делает это оптимизация и генерирует код на основе таблицы поиска для if-else. Что-то примечательное происходит, когда мы уменьшаем количество дел до двух (и по умолчанию) с помощью clang Он снова генерирует идентичный код для if и switch, но на этот раз переключается на сравнение и перемещает вместо метода таблицы поиска, для обоих. Это означает, что даже одобряющий переключение клан знает, что шаблон «если» более оптимален, когда число случаев невелико!

В итоге, последовательность сравнений для if-else и таблица переходов для switch-case - это стандартный шаблон, которому, как правило, следуют компиляторы, и разработчики ожидают, когда они пишут код. Однако для некоторых особых случаев некоторые компиляторы могут отказаться от этого шаблона, если они считают, что он обеспечивает лучшую оптимизацию. Другие компиляторы могут в любом случае просто придерживаться шаблона, даже если он явно не оптимален, доверяя разработчику знать, чего он хочет. Оба являются действительными подходами со своими преимуществами и недостатками.

Answer 2

Одним из возможных объяснений является то, что если более низкие значения num более вероятны, например всегда 0, сгенерированный код для первого из них может быть быстрее. Сгенерированный код для переключения занимает одинаковое время для всех значений.

Сравнение лучших вариантов, согласно этой таблицы . См. этот ответ для объяснения таблицы.

Если num == 0, для "если" у вас есть xor, test, je (with jump), ret. Задержка: 1 + 1 + прыжок. Тем не менее, xor и test независимы, поэтому фактическая скорость выполнения будет быстрее, чем 1 + 1 циклов.

Если num < 7, для «switch» у вас есть mov, cmp, ja (без перехода), mov, RET. Задержка: 2 + 1 + без перехода + 2.

Инструкция перехода, которая не приводит к прыжку, быстрее, чем та, которая приводит к прыжку. Тем не менее, таблица не определяет задержку для прыжка, поэтому мне не ясно, какой из них лучше. Возможно, последний всегда лучше, и G CC просто не может его оптимизировать.