Советы по оптимизации на нижнем уровне C ++ [закрыто]

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

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

77 голосов | спросил 8 revs, 2 users 70%
tenpn
1 Jam1000000amThu, 01 Jan 1970 03:00:00 +030070 1970, 03:00:00

17 ответов


74

Оптимизируйте свой формат данных! (Это относится к большему количеству языков, чем просто C ++)

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

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

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

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

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
82

Очень, очень низкоуровневый наконечник, но тот, который может пригодиться:

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

if (__ builtin_expect (entity-> extreme_unlikely_flag, 0)) {
  //код, который редко выполняется
}

Я видел ускорение на 10-20% при правильном использовании этого.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
36

Первое, что вам нужно понять, это аппаратное обеспечение, на котором вы работаете. Как он обрабатывает ветвление? Как насчет кеширования? Имеет ли он набор команд SIMD? Сколько процессоров он может использовать? Нужно ли ему делиться процессорным временем с чем-либо еще?

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

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

Затем профиль. Профиль, профиль, профиль. Посмотрите на использование памяти, посмотрите на разветвляющие штрафы, посмотрите на служебные вызовы функций, посмотрите на использование конвейера. Определите, что замедляет ваш код. Вероятно, это доступ к данным (я написал статью под названием «The Latency Elephant» об издержках доступа к данным - google it. Я не могу размещать здесь 2 ссылки, так как у меня недостаточно «репутации»), поэтому внимательно изучите это и затем оптимизируйте свой макет данных ( приятные большие плоские однородные массивы являются удивительными ) и доступ к данным (предварительная выборка, где возможно).

Как только вы минимизируете накладные расходы подсистемы памяти, попробуйте определить, являются ли инструкции узким местом (надеюсь, что они есть), а затем посмотрите на реализации SIMD вашего алгоритма. Реализации структуры массивов (SoA) могут быть очень эффективный кеш данных и команд. Если SIMD не подходит для вашей проблемы, тогда могут потребоваться встроенные и ассемблерные уровни.

Если вам все еще требуется больше скорости, переходите параллельно. Если у вас есть преимущество работы на PS3, то SPU - ваши друзья. Используйте их, любите их. Если вы уже написали SIMD-решение, вы получите огромное преимущество в SPU.

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

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

И затем снова профилььте его.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
31

Первый шаг: внимательно подумайте о своих данных относительно ваших алгоритмов. O (log n) не всегда быстрее, чем O (n). Простой пример: хеш-таблица с несколькими клавишами часто лучше заменяется линейным поиском.

Второй шаг: посмотрите на сборку. C ++ приносит много неявного генерации кода в таблицу. Иногда он подкрадывается к вам, не зная.

Но если предположить, что это действительно время от педали до металла: профиль. Шутки в сторону. Случайное применение «трюков производительности» примерно так же больно, как и для помощи.

Тогда все зависит от ваших узких мест.

промахи кэша данных => оптимизируйте структуру данных. Вот хорошая отправная точка: http://gamesfromwithin.com/data-oriented-design

code cache misses => Посмотрите на вызовы виртуальных функций, чрезмерную глубину вызова и т. Д. Общей причиной плохой производительности является ошибочное убеждение в том, что базовые классы должны быть виртуальными.

Другие распространенные возможности C ++:

  • Чрезмерное распределение /освобождение. Если это критическая производительность, не вызывайте ее во время выполнения. Когда-либо.
  • Скопируйте конструкцию. Избегайте, где бы вы ни находились. Если это может быть ссылка на константу, сделайте ее одной.

Все вышесказанное сразу становится очевидным, когда вы смотрите на сборку, поэтому см. выше;)

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
19

Удалить ненужные ветки

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

Архитектура PowerPC (PS3 /x360) предлагает команду выбора с плавающей запятой, fsel. Это можно использовать в месте ветви, если блоки являются простыми назначениями:

float result = 0;
if (foo> bar) {result = 2.0f; }
else {result = 1.0f; }

становится:

float result = fsel (foo-bar, 2.0f, 1.0f);

Когда первый параметр больше или равен 0, возвращается второй параметр, иначе третий.

Цена потери ветки заключается в том, что будут выполняться как блок if {}, так и else {}, поэтому, если одна из них является дорогостоящей операцией или разделяет указатель NULL, эта оптимизация не подходит.

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

Подробнее о ветвлении и fsel:

http://assemblyrequired.crashworks.org/tag/intrinsics/

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
16

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

Это самая важная вещь для оптимизации на современных процессорах. Вы можете сделать shitload арифметики и даже много неправильных предсказанных ветвей во время ожидания данных из ОЗУ.

Вы также можете прочитать это правило по-другому: Сделайте как можно больше вычислений между обращениями к памяти.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
13

Использовать внутреннюю среду компилятора.

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

Вот ссылка для Visual Studio и здесь для GCC

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
11

Удалить ненужные вызовы виртуальных функций

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

Вы можете сделать это несколькими способами. Иногда вы можете просто переписать классы, чтобы они не нуждались в наследовании - возможно, оказывается, что MachineGun является единственным подклассом Weapon, и вы можете объединить их.

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

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
9

Мой основной принцип: не делать ничего, что не нужно .

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

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

Я всегда стараюсь использовать этот подход перед любыми попытками оптимизации на самом низком уровне.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
9

Используйте SIMD (по SSE), если вы этого не сделаете. Gamasutra имеет приятную статью об этом . Вы можете загрузить исходный код из представленной библиотеки в конце статьи.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
6

Свести к минимуму цепи зависимостей, чтобы лучше использовать процессорную шину.

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

Пример:

float * data = ...;
int length = ...;

//Медленная версия
float total = 0.0f;
int i;
для (i = 0; i <length; i ++)
{
  total + = данные [i]
}

//Быстрая версия
float total1, total2, total3, total4;
для (i = 0; i <длина-3; i + = 4)
{
  total1 + = данные [i];
  total2 + = данные [i + 1];
  total3 + = данные [i + 2];
  total4 + = данные [i + 3];
}
for (; i <length; i ++)
{
  total + = данные [i]
}
total + = (total1 + total2) + (всего 3 + всего4);
ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
4

Не забывайте о своем компиляторе - если вы используете gcc на Intel, вы можете легко получить прирост производительности, например, переключившись на компилятор Intel C /C ++. Если вы ориентируетесь на платформу ARM, ознакомьтесь с коммерческим компилятором ARM. Если вы находитесь на iPhone, Apple просто разрешает использовать Clang, начиная с SDK iOS 4.0.

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

Мой лучший совет - игнорировать оптимизацию на низком уровне и сосредоточиться на более высоких уровнях. Компилятор и процессор не могут изменить ваш алгоритм от O (n ^ 2) до алгоритма O (1), независимо от того, насколько они хороши. Это потребует от вас взглянуть именно на то, что вы пытаетесь сделать, и найти лучший способ сделать это. Пусть компилятор и процессор беспокоятся о низком уровне, и вы фокусируетесь на средних и высоких уровнях.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
4

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

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

Технически «ограничение» не существует в стандартном C ++, но эквивалентные для платформы эквиваленты доступны для большинства компиляторов C ++, поэтому стоит подумать.

См. также: http: //cellperformance.beyond3d .com /статьи /2006/05 /Прояснение-заместитель ограничения-keyword.html

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
2

Const все!

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

void foo (Bar * x) {...;}

становится;

void foo (const Bar * const x) {...;}

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

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

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
2

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

Предполагая, что это сделано ....

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

Избегайте промахов в кэше. Пакетный процесс как можно больше. Избегайте виртуальных функций и других указаний.

В конечном счете, измерьте все. Правила меняются постоянно. То, что использовалось для ускорения работы кода 3 года назад, замедляет его. Хорошим примером является «использование двойных математических функций вместо плавающих версий». Я бы не понял этого, если бы не прочитал его.

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

Отредактировано, чтобы объяснить, почему инициализация по умолчанию отсутствует: Много кода говорит: Vector3 bla; bla = DoSomething ();

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

Vector3 bla (noInit); bla = doSomething ();

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
1

Уменьшить оценку булевых выражений

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

if ((foo & bar) || blah) {...}

становится:

if ((foo & bar) | blah) {...}

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

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

Большой недостаток заключается в том, что вы теряете ленивую оценку - весь блок оценивается, поэтому вы не можете делать foo! = NULL & foo- > разыменовать (). Из-за этого можно утверждать, что это трудно поддерживать, поэтому компромисс может быть слишком большим.

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20
1

Следите за использованием вашего стека

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

ответил Piporron 25 J000000Wednesday12 2012, 04:18:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132