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

79

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

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

tenpn
источник
1
Что делает этот вопрос вопросом разработки игр, а не общим вопросом программирования, подобным следующему: stackoverflow.com/search?q=c%2B%2B+optimization
Дэнни Варод
@ Дэнни - Возможно, это общий вопрос программирования. Это также вопрос, связанный с программированием игр. Я думаю, что это жизнеспособный вопрос на обоих сайтах.
Smashery
@Smashery Единственное различие между ними состоит в том, что программирование игры может потребовать определенной оптимизации уровня графического движка или оптимизации шейдерного кодера, часть C ++ такая же.
Дэнни Варод
@Danny - правда, некоторые вопросы будут «более» актуальны на одном или другом сайте; но я бы не хотел отвергать какие-либо важные вопросы только потому, что их можно было бы также задать на другом сайте.
Smashery

Ответы:

76

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

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

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

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

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

Эндрю Рассел
источник
Стоит попробовать пример C на связанной странице Cache Coherence. Когда я впервые узнал об этом, я был шокирован тем, насколько это важно.
Нил
9
См. Также прекрасную презентацию «Подводные камни в объектно-ориентированном программировании» (Sony R & D) ( research.scee.net/files/presentations/gcapaustralia09/… ) - и необычные, но увлекательные статьи CellPerformance Майка Актона ( cellperformance.beyond3d.com/articles/) index.html ). Блог Ноэля Льописа «Игры изнутри» также часто затрагивает эту тему ( gamesfromwithin.com ). Я не могу рекомендовать слайды Pitfalls достаточно ...
Леандер
2
Я бы просто предупредил о том, чтобы «сделать данные для каждой итерации как можно меньше и как можно ближе друг к другу в памяти» . Доступ к не выровненным данным может замедлить работу; в этом случае заполнение даст лучшие показатели. Порядок данных является важным тоже, как и упорядоченные данные могут привести к уменьшению заполнения. Скотт Майерс может объяснить это лучше, чем я, хотя :)
Джонатан Коннелл
+1 к презентации Sony. Я читал это раньше, и это действительно дает смысл в том, как оптимизировать данные на уровне платформы, учитывая разделение данных на куски и их правильное выравнивание.
ChrisC
84

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

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

if(__builtin_expect(entity->extremely_unlikely_flag, 0)) {
  // code that is rarely run
}

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

оборота ZorbaTHut
источник
1
Я бы проголосовал дважды, если бы мог.
Tenpn
10
+1, ядро ​​Linux широко использует это для микрооптимизации в коде планировщика, и это существенно меняет некоторые пути кода.
Greyfade
2
К сожалению, в Visual Studio нет хорошего эквивалента. stackoverflow.com/questions/1440570/…
mmyers
1
Так на какой частоте ожидаемое значение обычно должно быть правильным, чтобы получить производительность? 49/50 раз? Или 999999/1000000 раз?
Дуглас
36

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

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

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

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

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

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

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

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

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

Tony Albrecht
источник
31

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

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

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

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

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

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

Другие распространенные приемники производительности C ++:

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

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

Рейчел Блум
источник
19

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

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

Архитектура 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/

оборота тенпн
источник
float result = (foo> bar)? 2.f: 1.f
knight666
3
@ knight666: Это все равно приведет к появлению ветки в любом месте, которое бы сделал "если бы". Я так говорю, потому что в ARM, по крайней мере, такие небольшие последовательности могут быть реализованы с помощью условных инструкций, которые не требуют ветвления.
chrisbtoo
1
@ knight666, если вам повезет, компилятор может превратить это в fsel, но это не точно. FWIW, я обычно писал бы этот фрагмент с третичным оператором, а затем оптимизировал бы для fsel, если профилировщик согласился.
Tenpn
На IA32 у вас вместо этого есть CMOVcc.
Skizz
См. Также blueraja.com/blog/285/… (обратите внимание, что в этом случае, если компилятор хорош, он должен иметь возможность оптимизировать это сам, поэтому вам не о чем обычно беспокоиться)
BlueRaja - Danny Pflughoeft
16

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

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

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

Аксель Гнейтинг
источник
13

Используйте встроенные функции компилятора.

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

Вот ссылка для Visual Studio , а вот ссылка для GCC

AShelly
источник
11

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

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

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

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

tenpn
источник
9

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

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

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

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

mmyers
источник
2
Этот вопрос предполагает, что вы уже сделали все структурные вещи, которые можете.
Tenpn
2
Оно делает. Но часто вы предполагаете, что у вас есть, а у вас нет. Так что действительно, каждый раз, когда дорогая функция должна быть оптимизирована, спросите себя, нужно ли вам вызывать эту функцию.
Рэйчел Блум
2
... но иногда вычисление может быть быстрее, даже если вы собираетесь потом отбрасывать результат, а не переходить.
Tenpn
9

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

Peter Mortensen
источник
6

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

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

Пример:

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

// Slow version
float total = 0.0f;
int i;
for (i=0; i < length; i++)
{
  total += data[i]
}

// Fast version
float total1, total2, total3, total4;
for (i=0; i < length-3; i += 4)
{
  total1 += data[i];
  total2 += data[i+1];
  total3 += data[i+2];
  total4 += data[i+3];
}
for (; i < length; i++)
{
  total += data[i]
}
total += (total1 + total2) + (total3 + total4);
Адам
источник
4

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

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

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

Деннис Манси
источник
Я понимаю, что вы говорите, но наступает момент, когда вы достигли O (logN), и вы больше не собираетесь выходить из структурных изменений, когда оптимизация низкого уровня может вступить в игру и получить вас это лишние полсекунды.
Tenpn
1
Смотрите мой ответ re: O (log n). Кроме того, если вы ищете половину миллисекунды, вам, возможно, придется посмотреть на более высокий уровень. Это 3% вашего времени кадра!
Рэйчел Блум
4

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

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

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

Смотрите также: http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

Kylotan
источник
2

Const все!

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

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

становится;

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

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

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

sheredom
источник
И ваш приятель по кодам будет любить вас!
Tenpn
4
constне улучшает оптимизацию компилятора. Правда, компилятор может сгенерировать лучший код, если он знает, что переменная не изменится, но constне дает достаточно сильной гарантии.
deft_code
3
Нет. «restrict» гораздо полезнее, чем «const». См. Gamedev.stackexchange.com/questions/853/…
Justicle
+1 человек сказал, что const не может помочь, это неправильно ... infoq.com/presentations/kixeye-scalability
NoSenseEtAl
2

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

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

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

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

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

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

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

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

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

кая
источник
/ Не инициализировать ваши члены в конструкторах? Как это поможет?
Tenpn
Смотрите отредактированный пост. Не помещается в поле для комментариев.
Кай
const Vector3 = doSomething()? Тогда оптимизация возвращаемого значения может вступить в действие и, вероятно, создать назначение или два.
Tenpn
1

Уменьшить оценку логического выражения

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

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

становится:

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

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

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

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

tenpn
источник
1
Это довольно вопиющий компромисс ради производительности, главным образом потому, что не сразу очевидно, что это было задумано.
Боб Сомерс
Я почти полностью согласен с вами. Я сказал, что это было отчаянно!
Tenpn
3
Не нарушит ли это также короткое замыкание и сделает ли прогноз предсказания более ненадежным?
Эгон
1
Если foo равно 2, а bar равно 1, тогда код не ведет себя одинаково. Это, а не ранняя оценка, является самым большим недостатком, я думаю.
1
На самом деле, логические значения в C ++ гарантированно равны 0 или 1, поэтому, пока вы делаете это только с bools, вы в безопасности. Подробнее: altdevblogaday.org/2011/04/18/understanding-your-bool-type
tenpn
1

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

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

neilogd
источник