Предупреждаю, что я не мастер микрооптимизации. Я точно не знаю, как работает аппаратный предсказатель ветвления. Для меня это волшебный зверь, против которого я играю «ножницы-бумага-камень», и он, кажется, может читать мои мысли и все время бить меня. Я занимаюсь дизайном и архитектурой.
Тем не менее, поскольку этот вопрос касался высокого уровня мышления, я мог бы дать несколько советов.
Профилирование
Как уже было сказано, я не мастер компьютерной архитектуры, но я знаю, как профилировать код с помощью 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
Так или иначе, это некоторые стратегии, которые потенциально могут уменьшить количество ошибочных предсказаний ветвлений во всем вашем коде с точки зрения высокого уровня. Они лишены высочайшего уровня знаний в области компьютерной архитектуры, но я надеюсь, что это уместный полезный ответ, учитывая уровень задаваемого вопроса. Многие из этих советов нечетко связаны с оптимизацией в целом, но я обнаружил, что оптимизацию для прогнозирования ветвлений часто необходимо размывать с оптимизацией за ее пределами (память, распараллеливание, векторизация, алгоритмическая обработка). В любом случае, самая безопасная ставка - убедиться, что у вас есть профилировщик, прежде чем вы рискуете глубже.
person
Community
schedule
14.12.2015
