Оптимизация выбора

#c++ #оптимизация

Имеет ли смысл в операторе switch или инструкциях типа if (...) ... else if (...)
... else ... условия указывать в порядке уменьшения возможности возникновения? Т.е.,
например, если мы знаем, что в массиве больше троек и двоек, чем единиц, то делать
такую проверку:

if (x==3) ... else if (x==2) else ...

, а не наоборот?
    

Ответы

Ответ 1

Нет. Компилятор все равно будет их перемешивать.
If-ы компилятор может переписать в switch. Для switch компилятор может построить
бинарное дерево поиска на if-ах.

Для такой оптимизации кода надо использовать profile-guided optimization (PGO) -
компилятор сам будет смотреть какие ветви используются чаще, и располагать их в оптимальном
порядке.


Ответ 2

Добавлю, что в процессоре есть такой модуль как branch prediction, который позволяет
оптимизировать такого рода инструкции за счет предсказания какая ветка будет выполнена.
Цитата из вики:


  Без предсказания переходов конвейер должен дождаться выполнения
  инструкции условного перехода, чтобы произвести следующую выборку.
  Предсказатель переходов позволяет избежать траты времени, пытаясь
  выяснить ответвление. Ответвление выбирается по предыдущим результатам
  проверки условия. Предполагаемое ответвление затем загружается и
  частично выполняется. Если затем обнаруживается, что предсказание было
  выполнено неверно, отменяются результаты неверного ветвления и в
  конвейер загружается правильное ответвление, производя задержку.
  Величина задержки зависит от длины конвейера. Для процессора Intel
  Core i7 глубина конвейера составляет 14 стадий.


Поэтому такого рода оптимизации не стоит использовать без предварительного анализа
его необходимости. Используя gcc, есть возможность добавить подсказки для модуля branch
prediction, например (из ядра Linux):

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

if (likely(condition)) {
   ...
}