Почему невыгодно встраивать функции с помощью циклов или операторов переключения?

Встраивание функций с условными ветвями затрудняет точное прогнозирование операторов ветвления ЦП, поскольку каждый экземпляр ветвления независим.

Если имеется несколько операторов ветвления, успешное предсказание ветвления экономит намного больше циклов, чем затраты на вызов функции.

Аналогичная логика применяется к развертыванию циклов с помощью операторов switch.

В упомянутом руководстве Google ничего не упоминается о функциях, возвращающих значения, поэтому я предполагаю, что ссылка находится в другом месте и требует другого вопроса с явной ссылкой.

Хотя в вашем случае снижение производительности, похоже, вызвано неверными предсказаниями ветвей, я не думаю, что это причина, по которой руководство по стилю Google выступает против встроенных функций, содержащих циклы или операторы переключения. Есть случаи использования, когда предсказатель ветвления может выиграть от встраивания.

Цикл часто выполняется сотни раз, поэтому время выполнения цикла намного больше, чем время, сэкономленное за счет встраивания. Таким образом, выигрыш в производительности незначителен (см. Закон Амдала). OTOH, встраивание функций приводит к увеличению размера кода, что отрицательно сказывается на кэше инструкций.

В случае операторов switch я могу только догадываться. Объяснение может заключаться в том, что таблицы переходов могут быть довольно большими, тратя гораздо больше памяти в сегменте кода, чем очевидно.

Я думаю, что ключевое слово здесь рентабельно. Функции, требующие большого количества циклов или памяти, обычно не стоит встраивать.

Цель руководства по стилю кодирования - сказать вам, что если вы его читаете, вряд ли вы добавили оптимизацию в настоящий компилятор, еще менее вероятно, что добавили полезную оптимизацию (измеренную другими людьми на реалистичных программах в широком диапазоне). процессоров), поэтому вряд ли удастся угадать тех, кто это сделал. По крайней мере, не вводите их в заблуждение, например, помещая ключевое слово volatile перед всеми своими переменными.

Встраивание решений в компилятор имеет мало общего с «Делаем простой предсказатель переходов счастливым». Или менее запутанный.

Во-первых, целевой ЦП может даже не иметь предсказания ветвления.

Во-вторых, конкретный пример:

Представьте компилятор, у которого нет других оптимизаций (включенных), кроме встраивания. Тогда единственным положительным эффектом встраивания функции является то, что учет вызовов функций (сохранение регистров, настройка локальных переменных, сохранение адреса возврата и переходы к и обратно) устраняются. Стоимость заключается в дублировании кода в каждом месте, где вызывается функция.

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

int f(int s)
{
 ...;
 switch (s) {
   case 1: ...; break;
   case 2: ...; break;
   case 42: ...; return ...;
 }
 return ...;
}

void g(...)
{
  int x=f(42);
  ...
}

Когда компилятор решает встроить f, он заменяет правую часть присваивания телом f. Он заменяет фактический параметр 42 на формальный параметр s и внезапно обнаруживает, что переключатель находится на постоянном значении ... поэтому он отбрасывает все другие ветви, и, надеюсь, известное значение позволит дальнейшие упрощения (т.е. они каскадируются).

Если вам действительно повезет, все вызовы функции будут встроенными (и если f не будет виден снаружи), исходный f полностью исчезнет из вашего кода. Таким образом, ваш компилятор устранил всю бухгалтерию и уменьшил размер кода во время компиляции. И сделал код более локальным во время выполнения.

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

Сложнее привести хороший пример, когда полезны встроенные циклы, потому что нужно предполагать другие оптимизации и взаимодействия между ними.

Дело в том, что чертовски сложно предсказать, что произойдет с фрагментом кода, даже если вы знаете все способы, которыми компилятор может его изменить. Я не могу вспомнить, кто это сказал, но нельзя распознать исполняемый код, созданный оптимизирующим компилятором.

Думаю, стоит расширить пример @ user1666959. Я отвечу, чтобы предоставить более чистый пример кода. Рассмотрим такой сценарий.

/// Counts odd numbers in range [0;number]
size_t countOdd(size_t number)
{
    size_t result = 0;
    for (size_t i = 0; i <= number; ++i)
    {
        result += (i % 2);
    }
    return result;
}

int main()
{
    return countOdd(5);
}

Если функция не встроена и использует внешние ссылки, она выполнит весь цикл. Представьте, что происходит, когда вы встраиваете его.

int main()
{
    size_t result = 0;
    for (size_t i = 0; i <= 5; ++i)
    {
        result += (i % 2);
    }
    return result;
}

Теперь давайте включим оптимизацию разворачивания цикла. Здесь мы знаем, что он повторяется от 0 до 5, поэтому его можно легко развернуть, удалив нежелательные условия в коде.

int main()
{
    size_t result = 0;
    // iteration 0
    size_t i = 0
    result += (i % 2);
    // iteration 1
    ++i
    result += (i % 2);
    // iteration 2
    ++i
    result += (i % 2);
    // iteration 3
    ++i
    result += (i % 2);
    // iteration 4
    ++i
    result += (i % 2);
    // iteration 5
    ++i
    result += (i % 2);
    return result;
}

Нет условий, уже быстрее, но это еще не все. Мы знаем значение i, так почему бы не передать его напрямую?

int main()
{
    size_t result = 0;
    // iteration 0
    result += (0 % 2);
    // iteration 1
    result += (1 % 2);
    // iteration 2
    result += (2 % 2);
    // iteration 3
    result += (3 % 2);
    // iteration 4
    result += (4 % 2);
    // iteration 5
    result += (5 % 2);
    return result;
}

Еще проще, но эти операции constexpr, мы можем вычислить их во время компиляции.

int main()
{
    size_t result = 0;
    // iteration 0
    result += 0;
    // iteration 1
    result += 1;
    // iteration 2
    result += 0;
    // iteration 3
    result += 1;
    // iteration 4
    result += 0;
    // iteration 5
    result += 1;
    return result;
}

Итак, теперь компилятор видит, что некоторые из этих операций не имеют никакого эффекта, оставляя только те, которые изменяют значение. После этого он удаляет ненужные временные переменные и выполняет столько вычислений, сколько может во время компиляции, ваш код заканчивается:

int main()
{
    return 3;
}