Автор разбирает, как GCC с оптимизацией -O3 преобразует оператор switch в машинный код. Для плотного набора значений компилятор строит таблицу переходов: проверяет границы диапазона и использует входное значение как индекс. Постоянное смещение меток не мешает оптимизации — оно просто вычитается перед обращением к таблице. Если значения разрежены, GCC выбирает дерево сравнений. Эксперименты показывают порог примерно в восемь элементов таблицы на одно сравнение, но реальная эвристика учитывает не число меток case, а стоимость их проверки.
Это различие видно на последовательных диапазонах, ведущих в один блок кода. Несколько соседних меток заменяются двумя сравнениями границ, поэтому большая таблица может оказаться невыгодной даже при десятках case. Компилятор также умеет выделять плотные подмножества: отдельное выбивающееся значение проверяется ветвлением, а остальные обрабатываются таблицей переходов.
Для небольшого набора символов GCC применяет третью стратегию — битовую маску. Значение сдвигается к нулевой базе, проверяется по границам, а инструкция bt выбирает бит из константы. Единицы в ней соответствуют допустимым меткам. Такой вариант устраняет и цепочку сравнений, и косвенный переход.
В исходниках GCC за выбор отвечает pass_lower_switch и функция analyze_switch_statement. Сначала метки объединяются в кластеры с диапазонами, выходными ветвями и вероятностями из профилирования. Динамическое программирование ищет разбиения с минимальным числом битовых масок и таблиц, после чего эвристики отбрасывают невыгодные варианты. Битовые проверки ограничены шириной регистра, обычно 64 значениями, и не более чем тремя разными выходами. Минимальное число меток зависит от количества выходов: три для одного, пять для двух и шесть для трёх.
Для таблиц учитываются диапазон, число сравнений и накладные расходы на проверку границ и косвенный переход. При оптимизации скорости допустимый коэффициент роста равен восьми, при оптимизации размера — двум. Оставшиеся кластеры превращаются в дерево решений, листьями которого могут быть таблицы и битовые проверки.