Почему хорошо избегать ветвления команд, где это возможно? - PullRequest
7 голосов
/ 14 апреля 2011

Я часто читал, что плохо с точки зрения перфорирования, что ветвление, вроде на уровне инструкции по сборке, плохо. Но я действительно не видел, почему это так. Итак, почему?

Ответы [ 5 ]

12 голосов
/ 14 апреля 2011

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

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

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

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

2 голосов
/ 14 апреля 2011

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

1 голос
/ 14 апреля 2011

Помимо проблем с предварительной выборкой, если вы прыгаете, вы не выполняете другую работу ...

1 голос
/ 14 апреля 2011

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

0 голосов
/ 14 апреля 2011

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

Конвейер команд в процессоре работает точно так же, в нем нет сотен шагов, ноИдея та же: для поддержания одной или нескольких команд на частоту выполнения тактов (X количество автомобилей в день) необходимо поддерживать бесперебойную работу этого конвейера.Таким образом, вы выполняете предварительную выборку, которая записывает цикл памяти, который обычно медленный, но слои кэширования помогают.Декодирование, занимает другие часы, выполнить, может занять много часов esp на CISC, как x86.Когда вы выполняете ветвление, на большинстве процессоров вы должны отбрасывать инструкцию в execute и prefetch, в основном на 2/3 от вашего конвейера, если вы думаете с точки зрения общего упрощенного конвейера.Затем вы должны подождать эти часы для получения и декодировать, прежде чем вы вернетесь к плавному выполнению.Кроме того, выборка, по определению, не являющаяся следующей инструкцией, некоторый процент времени больше, чем кешлайн, и некоторый процент времени, что означает выборку из памяти или кеш более высокого уровня, который еще больше часовциклов, чем если бы вы выполняли линейно.Другое распространенное решение состоит в том, что некоторые процессоры утверждают, что независимо от того, какая команда находится после инструкции ветвления или иногда две команды после инструкции ветвления, всегда выполняются.Таким образом, вы выполняете, когда очищаете канал, хороший компилятор организует инструкции так, чтобы после каждой ветки было что-то другое.Хотя ленивый способ - просто ставить nop или два после каждой ветви, создавая новый удар по производительности, но для этой платформы большинство людей будут использовать это.Третий путь - это то, что делает ARM, имея условное исполнение.Для коротких прямых переходов, которые не являются чем-то необычным, вместо того, чтобы произносить ветвление, если условие, вы помечаете несколько инструкций, которые вы пытаетесь выполнить, с выполнением, если не условием, они переходят в декодирование и выполняются и исполняются как nops и pipeпродолжает двигаться.ARM полагается на традиционную очистку и пополнение для более длинных или обратных ветвей.

Старые руководства по x86 (8088/86), а также другие не менее старые руководства по процессорам для других процессоров, а также руководства по микроконтроллерам (новые и старые)будет по-прежнему публиковать тактовые циклы для выполнения каждой инструкции.И для инструкций ветвления будет написано добавление х числа часов, если ветвь произойдет.Ваши современные x86 и даже ARM и другие процессоры, предназначенные для запуска windows или linux или других (громоздких и медленных) операционных систем, не беспокоятся, они часто просто говорят, что они выполняют одну инструкцию за такт, или говорят о мегапикселях в мегагерц или тому подобное и не обязательноесть таблица часов на инструкцию.Вы просто предполагаете одну и помните, что это как одна машина в день, это последние часы выполнения, а не другие часы, которые туда попадают.В частности, люди, работающие с микроконтроллерами, имеют дело не с одним тактом на инструкцию и должны быть более осведомлены о времени выполнения, чем обычное настольное приложение.Посмотрите на спецификации для некоторых из них: Microchip PIC (не PIC32, который является mips), msp430, определенно 8051, хотя они сделаны или были сделаны очень многими различными компаниями, их характеристики синхронизации сильно различаются.

В итоге, для настольных приложений или даже драйверов ядра в операционной системе, компилятор не настолько эффективен, а операционная система добавляет гораздо больше накладных расходов, что вы вряд ли заметите экономию времени. Переключитесь на микроконтроллер и вставьте слишком много веток, и ваш код будет работать в 2 или 3 раза медленнее. Даже с компилятором, а не с ассемблером. Если вы используете компилятор (не пишите на ассемблере), это может / сделает ваш код в 2–3 раза медленнее, вы должны сбалансировать разработку, обслуживание и переносимость с производительностью.

...