Что такое хороший алгоритм для получения минимального покрытия вершины дерева?

Оптимизация компилятора операторов switch является сложной задачей. Конечно, вам нужно включить оптимизацию (например, попробуйте скомпилировать ваш код с gcc -O2 -fverbose-asm -S с GCC и заглянуть в сгенерированный файл .s ассемблера). Кстати, в обоих ваших примерах мой GCC 7 на Debian / Sid / x86-64 дает просто:

        .type   main, @function
main:
.LFB0:
        .cfi_startproc
# rsp.c:13: }
        xorl    %eax, %eax      #
        ret
        .cfi_endproc

^{(поэтому в этом сгенерированном коде нет никаких следов switch) sup >}

Если вам нужно понять, как компилятор может оптимизировать switch, есть несколько статей на эту тему, например, , эта .

Если у меня будет больше случаев переключения, то порядок падений влияет на производительность?

Не в целом, если вы используете какой-то оптимизирующий компилятор и просить его оптимизировать. Смотрите также этот .

Если это так важно для вас (но это не так, оставьте микрооптимизации для вашего компилятора!), Вам нужно провести тестирование, профилировать и, возможно, изучить сгенерированный ассемблерный код. Кстати, кеширование пропускает и распределение регистров может иметь гораздо большее значение, чем порядок case -s, поэтому я думаю, что вам вообще не стоит беспокоиться. Имейте в виду приблизительные временные оценки современных компьютеров. Поместите case в наиболее читаемый порядок (для следующего следующего разработчика , работающего над тем же исходным кодом). Читайте также о резьбовом коде . Если у вас есть объективные (связанные с производительностью) причины для переупорядочения case -ов (что очень маловероятно и должно произойти не чаще одного раза в жизни), напишите хороший комментарий, объясняющий эти причины.

Если вы так сильно заботитесь о производительности, обязательно выполните тесты и профиля , выберите хороший компилятор и используйте его с соответствующими параметрами оптимизации. Возможно, поэкспериментируйте с несколькими различными настройками оптимизации (и, возможно, с несколькими компиляторами). Вы можете добавить -march=native (в дополнение к -O2 или -O3). Вы можете рассмотреть возможность компиляции и связывания с -flto -O2, чтобы включить оптимизацию во время связи и т. Д. Вы также можете захотеть оптимизации на основе профиля .

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

^{(Не забудьте учесть затраты на разработку; в большинстве случаев они стоят намного больше) sup>}