Оптимизация C/C++ кода

Данная статья является вольным переводом статьи Optimizing C++/Code optimization/Faster operations. Оригинал найти можно по ссылке.

Предисловие

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

Часть 1

Расположение членов в структурах/классах

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

Предположим, что есть некая структура:

struct {
    char msg[400];
    double d;
    int i;
};

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

struct {
    double d;
    int i;
    char msg[400];
};

На некоторых процессорах адресация элемента более эффективна, если его расстояние от начала структуры меньше 128 байт. В первом примере для адресации полей d и i, с использованием указателя на начало структуры, требуется смещение не менее 400 байт, тогда как во втором, смещения составляет всего несколько байтов, что позволяет использовать более компактные инструкции.

Другой пример:

struct {
    bool b;
    double d;
    short s;
    int i;
};

Если посчитать размер структуры, 1 (bool) + 7 (padding) + 8 (double) + 2 (short) + 2 (padding) + 4 (int), то мы получим 24 байта, 9 из котороых будут использованы для выравнивания, что относительно размера структуры довольно много. Давайте перепишем эту же структуру таким образом:

struct {
    double d;
    int i;
    short s;
    bool b;
};

Снова проведем подсчет — 8 (double) + 4 (int) + 2 (short) + 1 (bool) + 1 (padding). Теперь наша структура займет 16 байт. Сортировка устранила ненужные вызванные, и поэтому мы получили более компактную структуру.

Преобразование типа с плавающей точкой в целочисленный

Язык C++ не предоставляет примитивную операцию округления чисел с плавающей точкой. Самым простым методом преобразования числа с плавающей точкой x в ближайшее целое число n будет оператор:

n = int(floor(x + 0.5f));

Используя такой метод, если x будет точно посередине между двумя целыми числами, то n будет округлено в большую сторону. Например, 0,5 -> 1; 1,5 -> 2; -0,5 -> 0; -1,5 -> -1;...

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

#if defined(__unix__) || defined(__GNUC__)
    // For 32-bit Linux, with Gnu/AT&T syntax
    __asm ("fldl %1 \n fistpl %0 " : "=m"(n) : "m"(x) : "memory" );
#else
    // For 32-bit Windows, with Intel/MASM syntax
    __asm fld qword ptr x;
    __asm fistp dword ptr n;
#endif

Код, приведенный выше, округляет x до ближайшего целого числа, но если значение x находится точно между целыми числами, то n будет ближайшим четным целым числом. Например, 0,5 -> 0; 1,5 -> 2; -0,5 -> 0; -1,5 -> -2;...

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

Работа с битами

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

Размер ячеек массива

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

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

Однако, при доступе к ячейкам многомерного массива, в котором константа достигает достаточной большой степени двойки, то вы рискуете конфликт данных(data cache contention), что может замедлить вычисление в 10 и более раз. Это происходит только тогда, когда ячейки массива превышают определенный размер, который зависит от кэша данных, но составляет от 1 до 8 КБ. Следовательно, в случае, если алгоритм должен обрабатывать массив, чьи ячейки имеют или могут иметь размер равный 1024 байта, то стоит определить, имеет ли место конфликт данных, чтобы попробовать его избежать.

Например, матрица размером 100 x 512 float — это 100 массивов по 512 эелементов. Каждая ячейка массива первого уровня имеет размер 512 x 4 = 2048 байт, и поэтому она подвержена риску конфликта данных.

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

• Добавьте один или несколько неиспользуемых елементов в конец каждого массива последнего уровня. Например, массив double a [100] [1024] может стать double a [100] [1026], даже если полезные данные будут находиться также до 1024.
• Храните размеры массива, разделяйте его на прямоугольные блоки и обрабатывайте все ячейки в одном блоке за раз.

Продолжение во второй части.