GCC превращает switch в битовую маску: как компилятор выбирает стратегию
Switch Lowering in GCC
Разбор того, как GCC понижает оператор switch: от таблицы переходов до дерева сравнений и битового теста. Автор показывает на ассемблере, что компилятор оценивает выгоду преобразования, учитывая количество сравнений, а не меток case, и умеет распознавать плотные подмножества значений. Отдельно рассматривается исходный код pass_lower_switch и эвристики, стоящие за выбором стратегии.
Компилятор понимает, что case-метки идут подряд, и может реализовать их двумя сравнениями вместо четырёх.
- LarsKrimi
> Switch в sparse_8 можно было бы упростить, разделив x на восемь перед переходом. Интересно, что gcc не находит это упрощение.
Он не мог, потому что это привело бы к тому, что 7 значений для каждого случая обрабатывались бы вызовами функций вместо случая по умолчанию — 0/8 равно 0, но 3/8 тоже равно 0
- rurban
Какой позор для clang и gcc! Они до сих пор не реализуют идеальные хеши для больших разреженных таблиц switch. Я недавно сделал это для своего C-компилятора rcc, и это заняло всего один день работы. Особенно полезно для работы с Unicode. Патч для LLVM отклонили десять лет назад. У Gcc есть несколько патчей для Unicode, лежащих в ветках, которым это тоже понадобилось бы
- p-t
Предполагаю, что 34 в compact_7() должно было быть 35, а edx должен был где-то использоваться в bittest() (если только я что-то не упускаю, лол)
- tsukikage
Зачем эта косвенность? — почему бы таблице переходов не ссылаться напрямую на f0..fX, вместо того чтобы прыгать на прыжок?
- Andi
Помню, я реализовывал подобные вещи в JavaScript (генерируя код) для неизменяемых Map и Set — никакого значительного прироста производительности в современных движках. Для регулярных выражений со сложными диапазонами Unicode ускорение было примерно в 2 раза!