В этом материале разберём оператор switch, который есть во многих языках программирования, иногда под разными названиями. Он выполняет те же задачи, что и if, то есть организует условия и ветвления. Становится не совсем понятно, зачем он понадобился.
Я буду использовать язык С.
Разберём такой пример с условными операторами if:
Его можно переписать с использованием switch:
Что это нам даёт? Во-первых, можно заметить, что количество различных скобок и знаков == сократилось. Запись стала более "питонистой", появился воздух (и 4 лишние строки). Но с другой стороны, появилась необходимость в конце каждого варианта писать break, что кажется избыточным. Так это или нет, мы посмотрим дальше, а пока просто зададимся вопросом: получается, что switch это просто синтаксический сахар для замены нескольких if?
Посмотрим, какие машинные инструкции генерируют оба варианта. Вот if:
Тут необязательно знать ассемблер, чтобы увидеть повторяющиеся блоки cmp ... jne. Команда cmp делает сравнение, команда jne делает ветвление на метку, если сравнение дало результат "не равно" (jump if not equal). Ну и по значениям 0, 10, 1, 11, 2, 12 можно понять, где переменная a, а где b.
Итого здесь у нас то же самое, что было записано в коде на C: три сравнения и три условных перехода.
А вот switch:
Получилось немножко по-другому, но количество сравнений и условных переходов почти то же самое.
Давайте я переведу оба варианта обратно на язык C, чтобы было понятно, что они функционально одинаковы:
Можно видеть, что логика этих вариантов взаимно инвертирована. Если в if происходит сравнение на неравенство, то в switch на равенство. Но это реально ничего не меняет. Однако же, в варианте switch есть одно лишнее сравнение, а именно if (a > 2). Если a > 2, то можно заведомо не проверять все остальные варианты, то есть мы пропускаем сравнения a == 0 и а == 1. Непонятно, почему при этом сравнение a == 2 расположено выше, чем a > 2. То есть это сравнение произойдёт в любом случае, а зачем?
Опустим эти размышления, и просто согласимся с тем, что эти два варианта мало отличаются друг от друга. И поэтому реально нет разницы, будем мы использовать if или switch.
Таблица переходов
Когда-нибудь, засыпая, мы вспомним про эту маленькую странность switch, и она не даст нам покоя.
В самом деле, это похоже на обрывок какого-то оптимизационного шаблона, а что нужно оптимизировать? Конечно, большое количество условий!
Мне удалось изменить поведение switch, использовав 5 сравнений:
Компилятор решил, что пора уже оптимизировать, и сделал вот так:
Понимаю, что может быть сложно, поэтому обратим внимание вот на эту часть:
Под меткой L4 зарезервировано (каждый .quad это 8 байт) 5 ячеек памяти, в которых хранятся... адреса других меток! Метка L4 это по сути начало массива. А L4[rax * 8] это адрес в массиве с индексом, равным переменной a. Из массива берётся адрес нужной метки и делается прыжок на него.
В переложении обратно на C это будет выглядеть так:
Здесь я сделал массив labels из адресов меток (это не входит в стандарт C, но расширение компилятора GCC позволяет так делать с вот таким синтаксисом), а затем я беру из массива метку с индексом a, и делаю переход на эту метку.
То есть получается, что даже если меток будет тысяча, сам переход будет сделан за O(1) операций, потому что нужная метка берётся по индексу из массива. Это и есть оптимизация. В случае с if её бы не было, и в коде появилась бы тысяча сравнений, которые проверялись бы друг за другом, пока что-то не сработает.
Естественно, нельзя использовать индекс вне массива, и поэтому сначала проверяется, чтобы переменная a не была больше 4.
Но есть нюанс
Использование индексов массива предполагает, что эти индексы идут друг за другом: 0, 1, 2, ... В нашем примере так и есть, потому что переменную a мы сравниваем с 0, 1, 2, ... А если понадобятся значения, которые не идут подряд? Например, 1, 2, 5, 8, 15? Будет ли в этом случае работать оптимизация, и как?
Я сразу перейду к результату, и покажу только массив, который получился:
Переменная a сравнивается с 5-ю значениями, а в массиве их сейчас 16. Посмотрим внимательнее. В массиве повторяется адрес метки L2, который записан в следующих индексах: 0, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14. Все эти индексы не совпадают с нужными нам 1, 2, 5, 8, 15, и метка L2 это там, где переменной b присваивается значение по умолчанию 99:
А вот остальные адреса меток ведут на соответствующие варианты для соответствующих значений.
В итоге: чтобы сделать массив с индексами 1, 2, 5, 8, 15, идущими не подряд, компилятор взял и сделал массив с индексами 0..15, идущими подряд. То есть просто заполнил промежутки. И индексы, которые мы не проверяем, направил на вариант по умолчанию. Компилятор посчитал, что этот расход памяти пренебрежимо мал по сравнению с выигрышем в скорости.
Так как принцип уже понятен, можно вывести некие правила.
Компилятор должен взять минимальное и максимальное значения, с которыми сравнивается переменная a. Эти значения надо нормализовать, то есть привести к виду 0..N. Можно пофантазировать насчёт вычленения каких-то закономерностей. Например, если это значения 0, 100, 200, 300..., то можно разделить их на 100. В моих тестах компилятор C так не делал, но вполне мог бы, если бы захотел. Просто ленится.
Затем компилятор прикидывает, какой получится массив, учитывая промежуточные заполняющие элементы, и будет ли овчинка стоить выделки. К примеру, когда я заменяю 15 на 150, компилятор отказывается от массива и переходит к обычным сравнениям.
Заключение
Если нужно сделать много (пять или больше) сравнений с какими-то числами, которые достаточно плотно расположены, то использование switch может дать выгоду по скорости. Если же не даст, то получится то же самое, что и при использовании if, поэтому мы ничем не рискуем.
Если значения расположены не плотно, то мы можем попробовать трансформировать их так, чтобы они располагались плотно, для общего нашего с компилятором дела.
В языках более высокого уровня switch можно использовать для проверки строковых значений:
Но возможность оптимизации тут под большим вопросом, так как строить массив с индексами-строками, сравнивать строки и т.д. слишком нетривиально. Однако не будем недооценивать эти языки. А вдруг получится? Тем более, что хуже всё равно не будет.
В самом экстремальном случае для организации таблицы переходов может использоваться... хэш-таблица, но это просто мои размышления.
break;
Так, а что насчёт break, зачем он нужен?
Вернёмся к сравнению вариантов:
Можно заметить, что в варианте if условия идут вперемешку с присваиваниями и переходами. А в варианте switch сначала одной группой идут условия, а затем одной группой идут присваивания и переходы.
Давайте пропустим какой-нибудь break:
Что получилось в машинных инструкциях? Ну, сразу напишу эквивалент на C:
Ничего нового, просто сразу после инструкции L4: b = 10 следует инструкция L5: b = 20. Это как раз там, где отсутствует break. То есть после выполнения case 1, где b = 10, сразу же выполняется case 2, где b = 20, и в результате b будет равно 20 и там, и там.
Таким образом, можно направлять несколько case на одну и ту же ветку, например так:
Либо же делать что-то в одном case и доделывать в следующем:
Здесь в case 1 переменной b будет присвоено значение 10, а затем, так как нет break, выполнение продолжится на case 2, где b будет увеличено на единицу. Выполнение case 2 не значит, что a == 2, это значит, что выполнение после case 1 просто продолжилось дальше по порядку. В итоге получим b = 11. Если же мы сразу попадём на case 2, то b будет просто увеличено на единицу.
Именно поэтому в switch сначала расположены все условия, а потом все присваивания и переходы. Посмотрите ещё раз на картинку со сравнением if и switch, и можете убедиться, что в варианте с if так не получится – будут мешать условия. А в switch мы имеем что-то вроде единого последовательного блока выполнения, в который можно зайти с любого места.
Мущщина, вы break забыли!
Отсутствие break часто бывает багом. То есть программист забыл его поставить. Тогда при чтении кода становится непонятно, действительно программист не хотел ставить break или просто забыл. В этом случае рекомендуется ставить комментарий, что да, я это сделал специально.
Компиляторы также могут выдавать предупреждения, когда видят отсутствующий break. Чтобы этого не происходило, можно использовать атрибут [[fallthrough]] в языке C/C++, ну а в других языках тоже есть что-то аналогичное.