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

Question

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

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

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

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

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

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

   • Например:>, <, = </li>

Answer 1

1. Вам придется выполнить профилирование.

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

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

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

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

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

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

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

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

Answer 2

Ну, это зависит от вашего оборудования.Очень хорошие таблицы с задержкой инструкций: 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 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

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

учтите:

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