Программирование с учетом веток

Ответ 1

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

(*) Опытные программисты часто напоминают, что программисты-люди очень плохо предсказывают это.

1- Можно ли избежать неверных предсказаний ветвления с использованием какого-либо метода программирования высокого уровня (т.е. нет сборки)?

Не в стандартном С++ или c. По крайней мере, не для одной ветки. То, что вы можете сделать, - это минимизировать глубину ваших цепочек зависимостей, так что неверное предсказание отрасли не будет иметь никакого эффекта. Современный cpus выполнит оба пути кода ветки и отбросит тот, который не был выбран. Тем не менее, существует предел для этого, и именно поэтому предсказание ветки имеет значение только в цепочках с большой зависимостью.

Некоторые компиляторы предоставляют расширение для подсказки вручную, например __ builtin_expect в gcc. Вот об этом вопрос fooobar.com/questions/58913/.... Еще лучше, некоторые компиляторы (например, gcc) поддерживают профилирование кода и автоматически определяют оптимальные прогнозы. Разумно использовать профилирование, а не ручную работу из-за (*).

2- Что я должен иметь в виду, чтобы создать дружественный для ветки код на языке программирования высокого уровня (меня больше всего интересуют C и С++)?

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

Но что мне делать, когда какой-то профайлер (valgrind, VTune,...) сообщает, что на строке n foo.cpp я получил штраф предсказания ветвления?

Лундин дал очень разумный совет

• Чтобы узнать, важно ли это.
• Если это имеет значение, то
  • Минимизировать глубину цепочек зависимостей ваших вычислений. Как это сделать может быть довольно сложным и выше моего опыта, и вы не можете обойтись без погружения в сборку. Что вы можете сделать на языке высокого уровня - это минимизировать количество условных проверок (**). В противном случае вы будете во власти оптимизации компилятора. Избежание цепей с повышенной зависимостью также позволяет более эффективно использовать сверхскалярные процессоры вне порядка.
  • Сделайте ваши ветки стабильно предсказуемыми. Эффект этого можно увидеть в этом вопросе fooobar.com/questions/58913/.... В этом вопросе есть петля над массивом. Цикл содержит ветвь. Ветвь зависит от размера текущего элемента. Когда данные были отсортированы, цикл может быть продемонстрирован намного быстрее при компиляции с конкретным компилятором и запуске на определенном процессоре. Разумеется, сохранение всех отсортированных данных также будет стоить процессорное время, возможно, больше, чем в случае неверных предсказаний ветки, поэтому измерьте.
• Если это все еще проблема, используйте оптимизацию с помощью профиля (если доступно).

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

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

Ответ 2

Ядро Linux определяет макросы likely и unlikely на основе __builtin_expect gcc builtins:

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

(см. здесь для определения макросов в include/linux/compiler.h)

Вы можете использовать их как:

if (likely(a > 42)) {
    /* ... */
} 

или

if (unlikely(ret_value < 0)) {
    /* ... */
}

Ответ 3

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

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

Ответ 4

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

Тем не менее, поскольку этот вопрос касался мышления высокого уровня, я мог бы внести некоторые советы.

Профилирование

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

Устранение ветвей

Многие люди дают несколько отличных советов низкого уровня о том, как улучшить предсказуемость ваших веток. В некоторых случаях вы даже можете вручную попытаться помочь предсказателю ветвления, а также оптимизировать предсказание статического ветвления (записывать операторы if, чтобы сначала проверить обычные случаи, например). Здесь есть исчерпывающая статья о подробных подробностях здесь от Intel: https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts.

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

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

Пропуск малой/редкой работы

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

Примером этого является memoising для большой таблицы поиска, чтобы избежать многократного выполнения некоторых относительно дешевых вычислений, например, используя таблицу поиска, которая охватывает мегабайты, чтобы избежать неоднократного вызова cos и sin. Для человеческого мозга это похоже на то, что он экономит работу, чтобы вычислить ее один раз и сохранить ее, за исключением того, что часто загружает память из этого гигантского LUT вниз по иерархии памяти и в регистр часто заканчивается даже более дорогостоящим, чем вычисления, которые они предназначали для сохранения.

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

Эта наивная попытка разветвления как оптимизации может также применяться даже для дорогостоящей, но редкой работы. Возьмите этот пример С++:

struct Foo
{
    ...
    Foo& operator=(const Foo& other)
    {
        // Avoid unnecessary self-assignment.
        if (this != &other)
        {
            ...
        }
        return *this;
    }
    ...
};

_{Обратите внимание, что это несколько упрощенный/иллюстративный пример, так как большинство людей реализует назначение копирования с помощью copy-and-swap по параметру, переданному по значению, и во избежание разветвления, несмотря ни на что.}

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

struct Foo
{
    ...
    Foo& operator=(const Foo& other)
    {
        // Don't check for self-assignment.
        ...
        return *this;
    }
    ...
};

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

Наивная попытка небольшого вектора

Как личная история, я раньше работал в крупномасштабной C-кодовой базе, которая часто имела много кода:

char str[256];
// do stuff with 'str'

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

std::string str = ...;
// do stuff with 'str'

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

Итак, нам нужно что-то похожее на гибрид между этими двумя методами. Мы хотели, чтобы у вас была возможность ударить что-то там, чтобы обеспечить безопасность по сравнению с вариантами фиксированного буфера C-стиля (которые были совершенно точными и очень эффективными для сценариев с обычным сценарием), но все же работают для редких сценариев, где буфер был 't достаточно большой для пользовательских входов. Я был одним из разработчиков в команде, и один из немногих использовал профилировщик (я, к сожалению, работал с большим количеством людей, которые думали, что они слишком умны, чтобы использовать их), поэтому я получил вызов в эту задачу.

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

template <class T, int N>
class SmallVector
{
public:
    ...
    T& operator[](int n)
    {
        return num < N ? buf[n]: ptr[n];
    }
    ...
private:
    T buf[N];
    T* ptr;
};

Эта попытка была полной неудачей. Несмотря на то, что цена кучи/свободного хранилища не оплачивалась, разветвление в operator[] делало его еще хуже, чем std::string и std::vector<char>, и отображалось как профилирующий hotspot вместо malloc (наш реализация поставщика std::allocator и operator new используется malloc под капотом). Итак, я быстро получил идею просто назначить ptr buf в конструкторе. Теперь ptr указывает на buf даже в общем случае, и теперь operator[] можно реализовать следующим образом:

T& operator[](int n)
{
    return ptr[n];
}

... и с этой простой ликвидацией ветвей наши горячие точки ушли. Теперь у нас был универсальный, совместимый с стандартом контейнер, который мы могли бы использовать, это было примерно так же быстро, как и прежнее решение с фиксированным буфером C-стиля (только разница была одним дополнительным указателем и несколькими инструкциями в конструкторе), но могут обрабатывать эти редкие сценарии, где размер должен быть больше, чем N. Теперь мы используем это даже больше, чем std::vector (но только потому, что наши варианты использования одобряют множество маленьких, временных, смежных, случайных контейнеров). И быстрое ускорение сводилось к простому отключению ветки в operator[].

Общепринятый случай/резкое искажение случая

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

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

Обработка исключений с нулевой стоимостью

Примером обхода обычного случая/редкого случая является техника обработки исключений, используемая во многих современных компиляторах. Они применяют нулевую стоимость EH, которая на самом деле не является "нулевой стоимостью" по всей доске. В случае, если исключение выбрасывается, они теперь медленнее, чем когда-либо прежде. Тем не менее, в случае, когда исключение не выбрасывается, они теперь быстрее, чем когда-либо прежде, и часто быстрее в успешных сценариях, чем такой код:

if (!try_something())
    return error;
if (!try_something_else())
    return error;
...

Если вместо этого мы используем нулевую стоимость EH и избегаем проверки и распространения ошибок вручную, вещи, как правило, идут еще быстрее в не исключительных случаях, чем этот стиль кода выше. Грубо говоря, это связано с уменьшением разветвления. Но взамен что-то гораздо более дорогое должно произойти, когда возникает исключение. Тем не менее этот перекос между обычным случаем и редким случаем имеет тенденцию помогать реальным сценариям. Нам не все равно, что скорость загрузки файла (редкий случай), как загрузка его успешно (обычный случай), и почему многие современные компиляторы С++ реализуют "нулевую стоимость" EH. Это снова в интересах искажения общего случая и редкого случая, отталкивающего их дальше от каждого с точки зрения производительности.

Виртуальная отправка и однородность

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

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

for each entity in world:
    entity.do_something() // virtual call

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

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

for each human in world.humans():
    human.do_something()
for each orc in world.orcs():
    orc.do_something()
for each creature in world.creatures():
    creature.do_something()

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

Оптимизация данных

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

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

Это часто помогает, даже если ваша цель - уменьшить неверное предсказание отрасли, чтобы больше сосредоточиться на потреблении данных. Например, я нашел отличные выигрыши от недифференцированного SIMD, но мышление все еще находилось в курсе потребления данных быстрее (что было сделано и благодаря некоторой помощи здесь на SO, вроде Гарольда).

TL; DR

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

Ответ 5

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

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

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

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

Ответ 6

1- Можно ли избежать неверных предсказаний ветвления с использованием какого-либо метода программирования высокого уровня (т.е. нет сборки)?

Избегайте? Возможно нет. Уменьшить? Конечно...

2- Что я должен иметь в виду, чтобы создать дружественный для ветки код на языке программирования высокого уровня (меня больше всего интересуют C и С++)?

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

Ответ 7

Чтобы ответить на ваши вопросы, позвольте мне объяснить, как работает предсказание ветвей.

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

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

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

Возможно ли избежать неверного предсказания ветвления с использованием какого-либо метода программирования высокого уровня (т.е. нет сборки)?

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

Что я должен иметь в виду, чтобы создать благоприятный для отрасли код в высоком (меня больше всего интересуют C и С++)?

Если возможно, устраните ветки, насколько это возможно. Если это не так, когда вы пишете инструкции if-else или switch, сначала проверьте наиболее распространенные случаи, чтобы убедиться, что ветки скорее всего не будут приняты. Попытайтесь использовать функцию _ _builtin_expect(condition, 1), чтобы заставить компилятор произвести условие, которое должно рассматриваться как не принятое.

Ответ 8

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

Иногда вы уверены, что условие непредсказуемо (например, в алгоритме сортировки или двоичном поиске). Или вы больше заботитесь о том, чтобы худший случай был не в 10 раз медленнее, чем в случае с быстрым случаем в 1,5 раза быстрее.

Некоторые идиомы, скорее всего, скомпилируются в ветвящуюся форму (например, инструкция условного перемещения cmov x86).

x = x>limit : limit : x;   // likely to compile branchless

if (x>limit) x=limit;      // less likely to compile branchless

Первый способ всегда записывается в x, а второй способ не изменяет x в одной из ветвей. Похоже, что некоторые компиляторы имеют тенденцию испускать ветвь вместо cmov для версии if. Это применимо даже тогда, когда x является локальной переменной int, которая уже существует в регистре, поэтому "запись" не включает в себя память в памяти, просто изменяя значение в регистре.

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

TODO: примеры на http://gcc.godbolt.org/