Скорость операторов C++ / простая математика

Question

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

1. Большая часть физического движка отсеивает ненужные вычисления, но в какой момент вычисления настолько малы, что сравнительные проверки не нужны?

   • Например: проверка, пересекаются ли два отрезка. Следует ли проверить, находятся ли они рядом друг с другом, прежде чем просто перейти к простой математике, или дополнительная операция замедлит процесс в долгосрочной перспективе?

2. Сколько времени занимают различные математические вычисления

   • например: (3+8) против (5x4) против (log(8)) и т. д.

3. Сколько времени занимают проверки на неравенство?

   • например: >, <, =

Answer 1

1. Вы должны будете сделать профилирование.

2. Основные операции, такие как сложения или умножения, должны занимать только одну asm инструкции.

   РЕДАКТИРОВАТЬ: Согласно комментариям, хотя принимая одну ассемблерную инструкцию, умножения могут распространяться на микроинструкции.

   Логарифмы занимают больше времени.

3. Также один asm инструкция.

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

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

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

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

Answer 2

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

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

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

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

Answer 3

Ну, это зависит от вашего оборудования. Очень хорошие таблицы с задержкой инструкций: http://www.agner.org/optimize/instruction_tables.pdf

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

2. Обычно сложение / вычитание происходит очень быстро, умножение чисел с плавающей запятой происходит немного медленнее. Деление с плавающей запятой довольно медленное (если вам нужно разделить на константу c, часто лучше предварительно вычислить 1/c и умножить на него). Библиотечные функции обычно (я бы сказал, всегда) медленнее, чем простые операторы, если только компилятор не решит использовать SSE. Например, sqrt() и 1/sqrt() могут быть вычислены с использованием одной инструкции SSE.

3. От одного цикла до нескольких десятков циклов. Текущие процессоры делают прогноз на условиях. Если прогноз верен, он будет быстрым. Однако, если прогноз неверен, процессор должен выбросить все предварительно загруженные инструкции (IIRC Sandy Bridge предварительно загружает до 30 инструкций) и начать обработку новых инструкций.

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

Answer 4

Обычно вы можете считать проверки неравенства, приращение, уменьшение, сдвиг битов, сложение и вычитание очень дешевыми. Умножение и деление, как правило, немного дороже. Сложные математические операции, такие как логарифмы, намного дороже.

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

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

Answer 5

1. Это зависит от сценария, который вы пытаетесь смоделировать. Сколько у вас предметов и как близко они? Они сгруппированы или распределены равномерно? Ваши объекты много двигаются или они статичны? Вам придется запускать тесты. Возможными структурами данных для быстрой проверки близости являются kd-деревья или локальные хеши (могут быть и другие). Я не уверен, подходят ли они для вашего приложения, вам придется проверить, в порядке ли для вас поддержание структуры данных и стоимости поиска.
2. Вам придется запускать тесты. Попробуйте проверить, можете ли вы использовать векторизацию или даже выполнить некоторые вычисления в GPU, используя CUDA или что-то в этом роде.
3. То же, что и выше - вы должны проверить.

Answer 6

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

1. взять отметку времени А
2. сделать 1 000 000 "+" расчетов (или любых других).
3. взять отметку времени B
4. рассчитать разницу между A и B.

тогда вы можете сравнить расчеты.

принять во внимание:

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