Всем привет, я работаю над оптимизацией проекта C++, чтобы добиться значительного ускорения на процессорах с современной архитектурой x86 или x64. В основном я пытался разделить работу моей программы на потоки, и с помощью алгоритмов синхронизации/мьютекса я смог добиться существенного 18-кратного ускорения на сервере с 56-ядерным процессором. Что хорошо, но!!

В ходе дальнейших исследований я столкнулся с некоторыми пулями, которые помогли получить ВОЛШЕБНУЮ УСКОРЕННОСТЬ в 32 раза (в 32 раза быстрее) в моем коде на C++. Поэтому я подумал, что было бы здорово поделиться этим! Вот основные рекомендации:

Сначала пишите для корректности, а затем оптимизируйте

Прыжки/ветви стоят дорого:

По возможности сведите к минимуму их использование.

• Вызовы функций требуют двух переходов в дополнение к манипулированию памятью стека.

• Предпочитайте итерацию рекурсии. • Используйте встроенные функции для коротких функций, чтобы исключить накладные расходы функций.

• Переместить циклы внутри вызовов функций (например, заменить for(i=0;i‹100;i++) DoSomething(); на DoSomething() { for(i=0;i‹100;i++) { … } } ).

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

Подумайте о порядке индексов массива.

• Двухмерные массивы и выше по-прежнему хранятся в одномерной памяти. Это означает, что (для массивов C/C++) array[i][j] и array[i][j+1] находятся рядом друг с другом, тогда как array[i][j] и array[i+1][j] может быть сколь угодно далеко друг от друга.

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

• Когда современные процессоры загружают данные из основной памяти в кэш процессора, они извлекают более одного значения. Вместо этого они извлекают блок памяти, содержащий запрошенные данные и смежные данные (кэш-строка). Это означает, что после того, как массив[i][j] находится в кеше ЦП, массив[i][j+1] с большой вероятностью уже находится в кеше, тогда как массив [i+1][j], скорее всего, все еще будет находиться в кеше. в основной памяти.

Подумайте о параллелизме на уровне инструкций.

• Несмотря на то, что многие приложения по-прежнему полагаются на однопоточное выполнение, современные ЦП уже имеют значительный уровень параллелизма внутри одного ядра. Это означает, что один ЦП может одновременно выполнять 4 умножения с плавающей запятой, ожидать 4 запроса памяти и выполнять сравнение для предстоящей ветви.

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

• Подумайте о развертывании циклов, чтобы улучшить это.

• Это также хорошая причина для использования встроенных функций.

Избегайте/уменьшайте количество локальных переменных.

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

• (Не переключайтесь, однако, на глобальные переменные!)

Уменьшите количество параметров функции.

• По той же причине, что и сокращение локальных переменных — они также хранятся в стеке. 9. Передавайте структуры по ссылке, а не по значению.

• Я не знаю ни одного случая в трассировщике лучей, где структуры должны передаваться по значению (даже такие простые, как векторы, точки и цвета). 10. Если вам не нужно возвращаемое функцией значение, не определяйте его. 11. По возможности старайтесь избегать кастинга.

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

• Более короткие целочисленные типы (char и short) по-прежнему требуют использования полноразмерного регистра, и их необходимо дополнить до 32/64 бит, а затем преобразовать обратно в меньший размер перед сохранением в памяти. (Однако эту стоимость необходимо сопоставить с дополнительными затратами памяти на больший тип данных.)

Будьте очень осторожны при объявлении объектных переменных C++.

• Использовать инициализацию вместо присваивания (Цвет с(черный); быстрее, чем Цвет с; с = черный;).

Сделайте конструкторы классов по умолчанию как можно более легкими.

• В частности, для простых, часто используемых классов (например, цвет, вектор, точка и т. д.), которыми часто манипулируют.

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

• Используйте списки инициализаторов конструктора. (Используйте Color::Color() : r(0), g(0), b(0) {} вместо Color::Color() { r = g = b = 0; } .)

По возможности используйте операции сдвига ›› и ‹‹ вместо целочисленного умножения и деления.

Будьте осторожны, используя функции поиска в таблице.

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

Для большинства классов используйте операторы +=, -=, *= и /= вместо операторов +, —, * и /.

• Простые операции требуют создания безымянного временного промежуточного объекта. • Например: Вектор v = Вектор(1,0,0) + Вектор(0,1,0) + Вектор(0,0,1); создает пять безымянных временных векторов: вектор (1,0,0), вектор (0,1,0), вектор (0,0,1), вектор (1,0,0) + вектор (0,1,0). ) и вектор (1,0,0) + вектор (0,1,0) + вектор (0,0,1). • Немного более подробный код: Vector v(1,0,0); v+= Вектор(0,1,0); v+= Вектор(0,0,1); создает только два временных вектора: Vector(0,1,0) и Vector(0,0,1). Это экономит 6 вызовов функций (3 конструктора и 3 деструктора).

Для базовых типов данных используйте операторы + , — , * и / вместо операторов += , -= , *= и /=

Задержка объявления локальных переменных.

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

Для объектов используйте префиксный оператор (++obj) вместо постфиксного оператора (obj++). •

Будьте осторожны при использовании шаблонов.

• Оптимизации для различных экземпляров могут быть разными! • Стандартная библиотека шаблонов достаточно хорошо оптимизирована, но я бы не стал ее использовать, если вы планируете реализовать интерактивный трассировщик лучей. • Почему? Реализуя его самостоятельно, вы будете знать алгоритмы, которые он использует, а значит, вы будете знать наиболее эффективный способ использования кода. • Что еще более важно, по моему опыту, отладочная компиляция библиотек STL выполняется медленно. Обычно это не проблема, за исключением того, что вы будете использовать отладочные версии для профилирования. Вы обнаружите, что конструкторы STL, итераторы и т. д. используют более 15% времени выполнения, что может сделать чтение вывода профиля более запутанным. Избегайте динамического выделения памяти во время вычислений.

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

Находите и используйте информацию о кэше памяти вашей системы.

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

Избегайте ненужной инициализации данных.

• Если вам нужно инициализировать большой кусок памяти, рассмотрите возможность использования memset().

Попробуйте досрочно завершить цикл и досрочно вернуть функцию.

• Рассмотрим пересечение луча и треугольника. «Общий случай» состоит в том, что луч пропустит треугольник. Таким образом, это должно быть оптимизировано для. • Если вы решите пересечь луч с плоскостью треугольника, вы можете немедленно вернуться, если значение пересечения луча и плоскости отрицательно. Это позволяет вам пропустить вычисление барицентрических координат примерно в половине пересечений луча и треугольника. Большая победа! Как только вы узнаете, что пересечения не произошло, функция пересечения должна выйти. • Точно так же некоторые циклы могут быть прерваны досрочно. Например, при съемке теневых лучей местоположение ближайшего пересечения не требуется. Как только будет найдено какое-либо перекрывающее пересечение, процедура пересечения может вернуться.

Упростите свои уравнения на бумаге! • Во многих уравнениях члены сокращаются… либо всегда, либо в некоторых особых случаях. • Компилятор не может найти эти упрощения, а вы можете. Устранение нескольких дорогостоящих операций внутри внутреннего цикла может ускорить вашу программу больше, чем дни, потраченные на другие части.

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

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

• Часто можно избежать sqrt(), особенно при сравнении, когда сравнение квадрата значения дает один и тот же результат. • Если вы неоднократно делите на x, рассмотрите возможность вычисления 1 x и умножения на результат. Раньше это было большой победой для нормализации векторов (3 деления), но недавно я обнаружил, что теперь это жеребьевка. Тем не менее, это все равно должно быть полезно, если вы делаете более 3 делений. • Если вы выполняете цикл, убедитесь, что вычисления, которые не меняются между итерациями, выводятся из цикла. • Подумайте, можете ли вы вычислять значения в цикле постепенно (вместо вычисления с нуля на каждой итерации).

Удачи вам в оптимизации!!!! :)