Если против скорости переключения - PullRequest
108 голосов
/ 15 января 2009

Операторы Switch обычно быстрее, чем эквивалентные операторы if-else-if (как, например, описано в этой статье ) из-за оптимизации компилятора.

Как на самом деле работает эта оптимизация? У кого-нибудь есть хорошее объяснение?

Ответы [ 7 ]

176 голосов
/ 15 января 2009

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

У него асимптотически лучшее время выполнения, чем у многих цепочечных if тестов, и на самом деле он быстрее даже при относительно небольшом количестве строк.

29 голосов
/ 15 января 2009

Конрад правильно. В случае включения смежных диапазонов целых чисел (например, когда у вас есть случай 0, случай 1, случай 2 ... случай n), компилятор может сделать что-то еще лучше, потому что ему даже не нужно создавать хеш-таблицу; он просто хранит массив указателей на функции и, таким образом, может загружать свою цель перехода в постоянное время.

13 голосов
/ 15 января 2009

Это небольшое упрощение, так как обычно любой современный компилятор встречает последовательность if..else if .., которая может быть легко преобразована человеком в оператор switch, компилятор тоже. Но просто для дополнительного удовольствия компилятор не ограничен синтаксисом, поэтому может генерировать «переключатели», например, внутренние операторы, которые имеют сочетание диапазонов, одиночных целей и т. Д., И они могут (и делают) это как для switch, так и if. .else заявления.

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

switch(a) { case 0: ...; break; case 1: ...; break; }

Если компилятор фактически сгенерировал таблицу переходов для этого, он, вероятно, будет медленнее, чем альтернативный код стиля if..else if.., из-за того, что таблица переходов не справляется с предсказанием ветвлений.

5 голосов
/ 15 января 2009

Как сказал Конрад, компилятор может создать таблицу переходов.

В C ++ это может быть вызвано ограниченностью переключателей.

4 голосов
/ 27 июля 2014

Операторы switch / case обычно бывают быстрее на 1 уровень, но когда вы начинаете входить в 2 или более, операторы switch / case начинают в 2-3 раза дольше, чем вложенные операторы if / else.

В этой статье приводятся некоторые сравнения скоростей , выделяющие различия в скорости, когда такие операторы вложены.

Например, согласно их тестам, пример кода, подобный следующему:

if (x % 3 == 0)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else if (x % 3 == 1)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else if (x % 3 == 2)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;

завершено за половина времени, которое потребовалось для выполнения эквивалентного оператора switch / case:

switch (x % 3)
    {
        case 0:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
        case 1:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
    case 2:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
    default:
        switch (y % 3)
        {
            case 0: total += 3;
                break;
            case 1: total += 2;
                break;
            case 2: total += 1;
                break;
            default: total += 0;
                break;
        }
        break;
    }

Да, это элементарный пример, но он иллюстрирует суть.

Таким образом, можно сделать вывод об использовании switch / case для простых типов, которые имеют глубину только на один уровень, но для более сложных сравнений и нескольких вложенных уровней используйте классические конструкции if / else?

4 голосов
/ 15 января 2009

Статистика не может быть хорошей.

Если вы на самом деле загружаете исходный код, значения совпадений, как известно, равны 21, как в случае if, так и в переключателе. Компилятор должен уметь абстрагироваться, зная, какой оператор должен выполняться в любое время, а ЦП должен уметь правильно предсказывать переходы.

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

0 голосов
/ 06 апреля 2018

Единственным преимуществом случая if over является заметное увеличение частоты появления первого случая.

Не знаю точно, где находится пороговое значение, но я использую синтаксис регистра, если только первое «почти всегда» не проходит первый тест.

...