Почему медленная инструкция ветвления процессора?

Question

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

Хорошо, хотя ни одна из статей не объясняла, почему я должен это делать.Что именно происходит, когда CPU декодирует инструкцию перехода и решает выполнить переход?И что за «вещь» делает ее медленнее других инструкций (например, сложение)?

Answer 1

Инструкция ветвления не медленнее, чем любая другая инструкция.

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

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

Это причина, по которой существуют такие вещи, как прогноз ветвления и интервалы задержки ветвления .

Answer 2

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

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

Однако, когда такое предсказание не выполняется, что называется неправильное предсказание ветвления , это повлияет на производительность выполнения.Поскольку конвейер после ветки должен быть отброшен, и начинать сначала с правильной инструкции.

Answer 3

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

Подробнее об оптимизации на C ++ можно прочитать в компиляторе Microsoft здесь - оптимизатор профиля использует информацию времени выполнения (т. Е. Какие части кода используются чаще всего) для оптимизации вашего кода.Ускорение находится в диапазоне 20%.

Одна из операций - это, например, «Условная оптимизация ветвления» - при условии, что большую часть времени я равняюсь 6 - это быстрее:

if (i==6)
{
    //...
}

else
{
    switch (i)
    {
        case 1: //
        case 2: //
        //...
    }
}

чем:

switch (i)
{
    case 1: //
    //...
    case 6: //
    case 7: //
}

Вот сообщение в блоге о других оптимизациях: http://bogdangavril.wordpress.com/2011/11/02/optimizating-your-native-program/