Отраслевое программирование
Я читаю вокруг, что неправильное прогнозирование веток может стать горячим узким местом для производительности приложения. Как я вижу, люди часто демонстрируют ассемблерный код, который раскрывает проблему и заявляет, что программисты обычно могут предсказать, куда ветка может идти большую часть времени, и избежать ошибочных предсказаний ветвления.
Мои вопросы:
1- Можно ли избежать ошибочных предсказаний ветвлений с помощью некоторой техники программирования высокого уровня (т.е. без сборки)?
2- Что я должен иметь в виду, чтобы создавать дружественный к ветвям код на языке программирования высокого уровня (меня больше всего интересуют C и C++)?
Примеры кода и тесты приветствуются!
8 ответов
люди часто... и утверждают, что программисты обычно могут предсказать, куда может пойти ветка
(*) Опытные программисты часто напоминают, что программисты-люди очень плохо предсказывают это.
1- Можно ли избежать ошибочных предсказаний ветвлений с помощью некоторой техники программирования высокого уровня (т.е. без сборки)?
Не в стандарте C++ или c. По крайней мере, не для одной отрасли. Что вы можете сделать, так это минимизировать глубину цепочек зависимостей, чтобы ошибочное прогнозирование ветвей не имело никакого эффекта. Современный процессор выполнит оба пути кода ветви и отбросит тот, который не был выбран. Однако есть предел этому, поэтому предсказание ветвлений имеет значение только в цепочках с глубокими зависимостями.
Некоторые компиляторы предоставляют расширение для предложения прогноза вручную, например __builtin_expect в gcc. Вот вопрос об стеке потока Более того, некоторые компиляторы (например, gcc) поддерживают профилирование кода и автоматически определяют оптимальные прогнозы. Разумно использовать профилирование, а не ручную работу из-за (*).
2- Что я должен иметь в виду, чтобы создавать дружественный к ветвям код на языке программирования высокого уровня (меня больше всего интересуют C и C++)?
Прежде всего, вы должны помнить, что неправильное предсказание ветвления повлияет на вас только в самой важной части вашей программы и не беспокоиться об этом до тех пор, пока вы не определите и не обнаружите проблему.
Но что я могу сделать, когда какой-то профилировщик (valgrind, VTune, ...) сообщает, что в строке n файла foo.cpp я получил штраф за предсказание перехода?
Лундин дал очень дельный совет
- Мера, чтобы узнать, имеет ли это значение.
- Если это имеет значение, то
- Минимизируйте глубину цепочек зависимостей ваших расчетов. Как это сделать, может быть довольно сложным и вне моего опыта, и мало что можно сделать без погружения в сборку. То, что вы можете сделать на языке высокого уровня, это минимизировать количество условных проверок (**). В противном случае вы зависите от оптимизации компилятора. Избегание цепочек с глубокими зависимостями также позволяет более эффективно использовать суперскалярные процессоры не в порядке.
- Сделайте ваши ветви последовательно предсказуемыми. Эффект этого может быть замечен в этом вопросе stackru. В вопросе есть цикл над массивом. Цикл содержит ветку. Ветвь зависит от размера текущего элемента. Когда данные были отсортированы, цикл, как было продемонстрировано, стал намного быстрее при компиляции с конкретным компилятором и запуске на конкретном процессоре. Конечно, поддержание сортировки всех ваших данных также будет стоить процессорного времени, возможно, больше, чем ошибочные прогнозы отрасли, так что измерьте.
- Если проблема не устранена, используйте оптимизацию по профилю (если есть).
Порядок 2. и 3. может быть переключен. Оптимизация кода вручную - большая работа. С другой стороны, сбор данных профилирования может быть затруднен и для некоторых программ.
(**) Один из способов сделать это - преобразовать ваши циклы, например, развернув их. Вы также можете позволить оптимизатору сделать это автоматически. Вы должны измерить, хотя, потому что развертывание повлияет на то, как вы взаимодействуете с кешем, и может оказаться пессимизацией.
В качестве предупреждения, я не волшебник микро-оптимизации. Я не знаю точно, как работает аппаратный предсказатель веток. Для меня это волшебный зверь, против которого я играю в камень-ножницы, и он, кажется, способен читать мои мысли и бить меня все время. Я тип дизайна и архитектуры.
Тем не менее, поскольку этот вопрос касался мышления высокого уровня, я мог бы поделиться некоторыми советами.
профилирование
Как я уже сказал, я не мастер компьютерной архитектуры, но я знаю, как профилировать код с помощью VTune, измерять такие вещи, как неправильные прогнозы веток и ошибки кэширования, и делать это все время, находясь в критической для производительности области. Это самое первое, на что вы должны обратить внимание, если не знаете, как это сделать (профилирование). Большинство из этих горячих точек на микроуровне лучше всего обнаружить задним числом с помощью профилировщика в руке.
Удаление филиалов
Многие люди дают отличные советы низкого уровня о том, как улучшить предсказуемость ваших филиалов. Вы можете даже вручную попытаться помочь предиктору ветвления в некоторых случаях, а также оптимизировать для статического предсказания ветвления (написание if заявления, чтобы проверить для общих случаев сначала, например). Здесь есть исчерпывающая статья о мельчайших подробностях от Intel: https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts.
Тем не менее, сделать это за пределами предвидения общего общего случая / редкого случая очень сложно, и его почти всегда лучше сохранить для последующего измерения. Людям просто сложно точно предсказать природу предсказателя ветвления. Это гораздо сложнее предсказать, чем такие вещи, как сбои страниц и пропуски кэша, и даже те, которые почти невозможно совершенно человечески предсказать в сложной кодовой базе.
Тем не менее, существует более простой и высокоуровневый способ смягчить неправильное предсказание ветвления, и это позволяет полностью избежать ветвления.
Пропуск Малой / Редкой Работы
Одна из ошибок, которые я обычно совершал в начале своей карьеры и видел, как многие сверстники пытаются сделать, когда они только начинают, прежде чем они научились профилировать и все еще догадываются, это попытаться пропустить небольшую или редкую работу.,
Примером этого является запоминание большой справочной таблицы, чтобы избежать повторного выполнения относительно дешевых вычислений, например, использование справочной таблицы, занимающей мегабайты, чтобы избежать повторного вызова cos а также sin, Человеческому мозгу кажется, что это экономит работу, чтобы вычислить и сохранить один раз, за исключением частой загрузки памяти из этого гигантского LUT вниз по иерархии памяти и в регистр, который часто оказывается даже более дорогим, чем вычисления, для которых он был предназначен сохранить.
Другой случай - добавление нескольких небольших веток, чтобы избежать небольших вычислений, которые безвредно выполнять без необходимости (не будет влиять на корректность) по всему коду, как наивная попытка оптимизации, только чтобы найти затраты на ветвление дороже, чем просто делать ненужные вычисления.
Эта наивная попытка ветвления как оптимизации может также применяться даже для немного дорогой, но редкой работы. Возьмите этот пример C++:
struct Foo
{
...
Foo& operator=(const Foo& other)
{
// Avoid unnecessary self-assignment.
if (this != &other)
{
...
}
return *this;
}
...
};
Обратите внимание, что это несколько упрощенный / иллюстративный пример, поскольку большинство людей реализуют назначение копирования с использованием копирования и замены для параметра, передаваемого по значению, и избегают ветвления в любом случае, несмотря ни на что.
В этом случае мы разветвляемся, чтобы избежать самостоятельного назначения. Тем не менее, если самостоятельное назначение выполняет только избыточную работу и не мешает правильности результата, оно часто может дать вам повышение производительности в реальном времени, позволяя просто копировать самостоятельно:
struct Foo
{
...
Foo& operator=(const Foo& other)
{
// Don't check for self-assignment.
...
return *this;
}
...
};
... это может помочь, потому что самоопределение бывает довольно редко. Мы замедляем редкий случай путем избыточного самостоятельного назначения, но мы ускоряем общий случай, избегая необходимости проверять все остальные случаи. Конечно, это вряд ли значительно сократит ошибочные прогнозы ветвления, поскольку существует распространенный / редкий случай с точки зрения ветвления, но эй, ветвь, которая не существует, не может быть неверно предсказана.
Наивная попытка маленького вектора
Как личная история, я раньше работал в крупномасштабной кодовой базе C, в которой часто было много такого кода:
char str[256];
// do stuff with 'str'
... и, естественно, поскольку у нас была довольно обширная база пользователей, некоторые редкие пользователи в конечном итоге набирали имя для материала в нашем программном обеспечении, длина которого превышала 255 символов, и переполняли буфер, что приводило к ошибкам сегмента. Наша команда переходила на C++ и начала переносить многие из этих исходных файлов на C++ и заменять такой код следующим:
std::string str = ...;
// do stuff with 'str'
... который устранял эти переполнения буфера без особых усилий. Однако, по крайней мере, тогда такие контейнеры, как std::string а также std::vector были структуры, расположенные в куче (бесплатный магазин), и мы обнаружили, что торгуем корректностью / безопасностью для эффективности. Некоторые из этих замененных областей были критически важными для производительности (они назывались узкими циклами), и хотя мы удалили множество отчетов об ошибках с этими массовыми заменами, пользователи начали замечать замедления.
Итак, мы хотели что-то похожее на гибрид этих двух техник. Мы хотели иметь возможность что-то добавить, чтобы обеспечить безопасность по сравнению с вариантами фиксированного буфера в стиле C (которые были совершенно нормальными и очень эффективными для сценариев общего случая), но все же работали для сценариев редких случаев, когда буфер был недостаточно велик для пользовательского ввода. Я был одним из фанатов производительности в команде и одним из немногих, кто использовал профилировщик (к сожалению, я работал со многими людьми, которые думали, что они слишком умны, чтобы использовать его), поэтому меня вызвали на задачу.
Моей первой наивной попыткой было что-то вроде этого (значительно упрощенное: в действительности использовалось размещение новых и т. Д., И оно полностью соответствовало стандарту). Он включает использование буфера фиксированного размера (размер, указанный во время компиляции) для общего случая и динамически распределяемый, если размер превышает эту емкость.
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> и показывался как точка доступа профилирования вместо 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 с нулевой стоимостью и не проверяем и не распространяем ошибки вручную, в неисключительных случаях все происходит быстрее, чем в приведенном выше коде. Грубо говоря, это связано с уменьшенным ветвлением. Тем не менее, взамен должно произойти что-то гораздо более дорогое, когда возникает исключение. Тем не менее, этот перекос между общим случаем и редким случаем способствует реальным сценариям. Мы не очень заботимся о скорости сбоя загрузки файла (редкий случай), чем об успешной его загрузке (общий случай), и поэтому многие современные компиляторы C++ реализуют 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
Так или иначе, таковы некоторые стратегии, которые потенциально могут снизить количество неверных прогнозов ветвей в вашем коде с точки зрения высокого уровня. Они лишены высочайшего уровня знаний в компьютерной архитектуре, но я надеюсь, что это подходящий вид полезного ответа, учитывая уровень задаваемого вопроса. Многие из этих советов в некоторой степени размыты с оптимизацией, но я обнаружил, что оптимизация для предсказания ветвлений часто должна быть размыта с оптимизацией за ее пределами (память, распараллеливание, векторизация, алгоритмическая). В любом случае, самая безопасная ставка - убедиться, что у вас есть профилировщик в руке, прежде чем углубляться.
Ядро Linux определяет likely а также unlikely макросы на основе __builtin_expect gcc buildins:
#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)) {
/* ... */
}
В целом, хорошая идея - поддерживать горячие внутренние циклы в правильном соотношении с размерами кеша, с которыми чаще всего сталкиваются. То есть, если ваша программа обрабатывает данные кусками, скажем, менее 32 Кбайт за раз и выполняет с ними приличный объем работы, то вы эффективно используете кэш L1.
Напротив, если ваш горячий внутренний цикл прожирает 100 МБ данных и выполняет только одну операцию с каждым элементом данных, то ЦП будет тратить большую часть времени на выборку данных из DRAM.
Это важно, потому что одна из причин, по которой центральные процессоры в первую очередь имеют предсказание ветвления, заключается в возможности предварительного выбора операндов для следующей инструкции. Последствия неправильного предсказания ветвления могут быть уменьшены за счет организации вашего кода, так что есть большая вероятность, что следующие данные поступят из кэша L1, независимо от того, какая ветвь берется. Хотя кэш-память L1 и не идеальная стратегия, она, похоже, повсеместно застряла на 32 или 64 КБ; это почти постоянная вещь в отрасли. По общему признанию, кодирование таким способом не всегда простое, и полагаться на оптимизацию на основе профилей и т. Д., Как это рекомендовано другими, является, вероятно, самым простым способом.
Независимо от чего-либо еще, возникнет ли проблема с неправильным предсказанием ветвления, зависит от размера кэша ЦП, того, что еще работает на машине, пропускной способности / задержки основной памяти и т. Д.
Возможно, наиболее распространенные методы - это использование отдельных методов для нормального и ошибочного возвратов. У C нет выбора, но у C++ есть исключения. Компиляторы знают, что ветви исключений являются исключительными и, следовательно, неожиданными.
Это означает, что ветви исключений действительно медленные, так как они непредсказуемы, но ветка без ошибок выполняется быстрее. В среднем это чистый выигрыш.
Чтобы ответить на ваши вопросы, позвольте мне объяснить, как работает предсказание ветвлений.
Прежде всего, существует штраф за ветвление, когда процессор правильно предсказывает взятые ветки. Если процессор предсказывает переход как взятый, то он должен знать цель предсказанной ветви, так как поток выполнения будет продолжаться с этого адреса. Предполагая, что целевой адрес филиала уже сохранен в Branch Target Buffer(BTB), он должен получить новые инструкции с адреса, найденного в BTB. Таким образом, вы все еще тратите впустую несколько тактов, даже если ветвь правильно спрогнозирована.
Поскольку BTB имеет ассоциативную структуру кэша, целевой адрес может отсутствовать, и, следовательно, больше тактов может быть потрачено впустую.
С другой стороны, если ЦП прогнозирует ветвь как незанятую и если она правильная, штраф не применяется, поскольку ЦП уже знает, где находятся последовательные инструкции.
Как я объяснил выше, предсказанные не взятые ветви имеют более высокую пропускную способность, чем предсказанные взятые ветви.
Можно ли избежать ошибочного прогнозирования ветвлений с помощью какой-либо техники программирования высокого уровня (т.е. без сборки)?
Да, это возможно. Вы можете избежать этого, организовав свой код таким образом, чтобы все ветви имели повторяющийся шаблон ветвей, такой, который всегда используется или не выполняется.
Но если вы хотите получить более высокую пропускную способность, вы должны организовать филиалы таким образом, чтобы они, скорее всего, не использовались, как я объяснил выше.
Что я должен иметь в виду для создания дружественного к ветвям кода на языке программирования высокого уровня (меня больше всего интересуют C и C++)?
Если возможно, удалите ветки как можно скорее. Если это не так при написании операторов if-else или switch, сначала проверьте наиболее распространенные случаи, чтобы убедиться, что ветви, скорее всего, не будут приняты. Попробуй использовать __builtin_expect(condition, 1) функция, заставляющая компилятор создавать условие, которое будет рассматриваться как неиспользуемое.
1- Можно ли избежать ошибочных предсказаний ветвлений с помощью некоторой техники программирования высокого уровня (т.е. без сборки)?
Избегайте? Возможно нет. Уменьшить? Конечно...
2- Что я должен иметь в виду, чтобы создавать дружественный к ветвям код на языке программирования высокого уровня (меня больше всего интересуют C и C++)?
Стоит отметить, что оптимизация для одной машины не обязательно является оптимизацией для другой. Имея это в виду, оптимизация на основе профилей достаточно хороша для реорганизации ветвей, основываясь на том, какой тестовый ввод вы дадите. Это означает, что вам не нужно программировать, чтобы выполнить эту оптимизацию, и она должна быть относительно адаптирована к любой машине, на которой вы выполняете профилирование. Очевидно, что наилучшие результаты будут достигнуты, когда ваши входные данные теста и машина, на которой вы профилируете, примерно соответствуют тем, что обычно ожидаются... но это также соображения относительно любых других оптимизаций, связанных с предсказанием переходов или иным образом.
Безветвление не всегда лучше, даже если обе стороны ветви тривиальны. Когда предсказание ветвлений работает, это быстрее, чем перенос данных в цикле.
Смотрите флаг оптимизации gcc -O3 делает код медленнее, чем -O2 для случая, когда gcc -O3 превращает if() к коду без ответвлений в случае, когда это очень предсказуемо, делая его медленнее.
Иногда вы уверены, что условие непредсказуемо (например, в алгоритме сортировки или бинарном поиске). Или же вас больше заботит, чтобы в худшем случае не было в 10 раз медленнее, чем в быстром, в 1,5 раза быстрее.
Некоторые идиомы с большей вероятностью компилируются в форму без ветвей (например, cmov инструкция условного перемещения x86).
x = x>limit ? limit : x; // likely to compile branchless
if (x>limit) x=limit; // less likely to compile branchless, but still can
Первый способ всегда пишет x пока второй способ не модифицирует x в одной из веток. Это, кажется, причина того, что некоторые компиляторы имеют тенденцию испускать ветку вместо cmov для if версия. Это относится даже когда x местный int переменная, которая уже находится в регистре, поэтому "запись" не требует сохранения в памяти, просто изменяя значение в регистре.
Компиляторы все еще могут делать все, что хотят, но я обнаружил, что это различие в идиомах может иметь значение. В зависимости от того, что вы тестируете, иногда лучше помочь маске компилятора и AND, а не делать простой старый cmov , Я сделал это в этом ответе, потому что я знал, что компилятор будет иметь то, что ему нужно, чтобы сгенерировать маску с помощью одной инструкции (и посмотреть, как это сделал clang).
TODO: примеры на http://gcc.godbolt.org/