GCC выбирает таблицу переходов вместо дерева сравнений, считая сравнения, а не метки

Три стратегии в фиксированном порядке

Разбор показывает, что pass_lower_switch в GCC перебирает битовые тесты, затем таблицы переходов, затем бинарное дерево решений. Битовый тест требует суммарного диапазона меньше 64, не более трёх разных целей и минимального числа меток, а проверку принадлежности делает инструкцией x86 bt. Случаи от '0' до 'E' превращаются в одну инструкцию bt с константой 2753205. Таблицы переходов по умолчанию требуют не меньше пяти меток и достаточной плотности.

Правило плотности объясняет странности. GCC разрешает таблицу, которая в 8 раз больше числа сравнений, которые она заменяет, ради скорости (при -Os — в 2 раза). Двадцать меток, растянутых от 0 до 87, сводятся к 10 сравнениям, а 10 × 8 = 80 меньше 88, поэтому таблицы нет.

«Упущенная» оптимизация, которой нет

В посте отмечено, что GCC не делит x на 8 перед переходом в случае с шагом 8.

«Не могла, потому что тогда 7 значений для каждого случая обрабатывались бы вызовами функций вместо ветки default: 0/8 равно 0, но и 3/8 тоже равно 0» — комментатор, отвечающий на это замечание

Чего компиляторы не делают

Разработчик компиляторов сказал, что Clang и GCC до сих пор не реализуют идеальные хеши для больших разреженных switch-таблиц, хотя сам он добавил их в свой C-компилятор за день и говорит, что они помогли бы в работе с Unicode. Патч для LLVM отклонили десять лет назад. Автор крейта на Rust пришёл к тому же выводу: LLVM компилировал огромный switch с MAC-адресами вендоров около получаса с включёнными оптимизациями, поэтому он перешёл на идеальное хеширование.