Домашняя страница Оптимизация кода на С++
Публикация
Отменить

Оптимизация кода на С++

Время публикации 31/08/2010 Обновлено 10/07/2023
Автор Deynega Vasiliy
12 минут чтения

Иногда бывает сложно решить, какую конструкцию лучше использовать i++ или ++i, либо выбрать между конструкцией if-else и switch. В этой статье, написанной специально для сообщества iT works, представлены наиболее реальные средства оптимизации кода, которые должен знать каждый профессиональный программист.

Некоторые считают, что времена оптимизации на уровне кода прошли навсегда, однако это не так. Сейчас существует множество платформ в которых нет таких могущественных компиляторов как в Microsoft Visual Studio. Например шейдерные языки (hlsl, glsl) или код для CUDA, PlayStation3, SPU или мобильные платформы. В зависимости от организации кода, может в десятки раз отличаться его эффективность иногда из-за неэффективности компилятора, на чаще из-за доступа к памяти.

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

Если вы являетесь программистом в VS под Windows, то скорее всего со многими описанными приемами оптимизации компилятор эффективно справится. Обратите внимание на пункты работы с памятью, а так же я рекомендую ознакомиться с техникой Data oriented design. Некоторые советы по ее использования ищите в статье Методы оптимизации памяти.

Итак, начнем:

  1. Используйте векторизацию данных и векторные команды их обработки (например SSE в CPU или упаковывайте данные если используете шейдеры или CUDA). Это позволит использовать SIMD (Single Instruction, Multiple Data) архитектуру, что значительно повысит скорость вычислений. Если вы решите использовать этот метод, то не забывайте про выравнивание данных в памяти.
  2. Эффективнее складывать и умножать в перемешку, чем сначала все сложить, а потом все умножить. Это происходит от того, что сложение и умножение выполняются разными модулями процессора и могут выполняться одновременно.
    1
2
3
4
5
6
7
8
9
10
11
12
13
14

     int [float, double, single, unsigned] a,b,c,k,m,n,t,f1,f2,f3,g1,g2,g3;
 a = b + с;
 k = m + n;
 t = a + k;
 f1 = f2 * f3;
 g1 = g2 * g3;
    
    
 Менее эффективно чем:
 a = b + с;
 f1 = f2 * f3;
 k = m + n;
 g1 = g2 * g3;
 t = a + k;
  3. Нет разницы по скорости в работе с float и double при сложении и умножении. Они выполняются за равное число тактов процессора и используют одни и те же регистры. При делении и извлечении корня, float работает быстрее. Однако если вы будете использовать большие объемы данных, то за счет кеша быстрее будет работать тот тип, который занимает меньше памяти (т.е. float), поэтому в общем случае именно его предпочтительно использовать. Выбирать double имеет смысл когда нужна большая точность. 4.Допустим есть.
    1
2
3

     const float a = 100.0f;
 float some1 = some3 * 1.0f / a;
 float some2 = some4 * 1.0f / a;

    более эффективно написать не:

    1
2
3

     const float a_inv = 1.0f / a;
 some1 = some3 * a_inv;
 some2 = some4 * a_inv;

    а так:

    1
2

     some1 = some3 * (1.0f / a);
 some2 = some4 * (1.0f / a);

    Почему это будет эффективнее? Операторы с равным приоритетом выполняются последовательно. Это значит, что будет выполнено сначала умножение, а затем деление. Если же обрамить операцию деления в скобки, то ее выполнит компилятор, а в реальном времени будет выполняться только операция умножения. Что качается отличий варианта 3 от варианта 2, то в 3-ем варианте не создается дополнительной переменной, нет нужны глядя на код думать о том, что это за переменная. А эффективность 2-го и 3-го варианты будет одинаковой.

  4. На больших объемах данных и вычислений на них float выгоднее чем double (из за cache miss’ов, см. пункт 3).
  5. a, b - любое выражение, Func1, Func2 - функции, которые вызовутся для вычисления условия
    1
2
3

     if( a && b ) - нужно первым ставить менее вероятное условие, для большей эффективности
 if( a || b ) - нужно первым ставить более вероятное условие, для большей эффективности
 if( Func1() && Func2() ) - нужно ставить более быстрый оператор первым
  6. пусть
    1
2
3
4
5
6
7
8

     void Func( int* a )
 {
    int b = 10;
    
   Следующие строки одинаковые по эффективности (по времени выполнения):
    b = 100;
    *a = 100;
 }

    Это происходит по тому, что доступ к стековой переменной осуществляется по указателю на стек. Тоже идет разыменование указателя.

  7. Если есть большой массив структур, то нужно делать размер его элементов равным степени двойки. Тогда проход по такому массиву будет значительно быстрее (в 4 -6 раз), за счет выравнивания указателя на каждую структуру в массиве.
  8. пусть
    1
2
3

     int a[ 1000 ];
 for( int i =0; i<1000; ++i )
    a[ i ] = 50;

    Значительно эффективнее будет:

    1
2
3

     int* p = a;
 for( int i =0; i<1000; ++i, ++p )
   *p = 50;
  9. пусть
    1
2
3

    SomeClass* p; - указатель на массив элементов
x = *(p++); - значительно эффективнее
x = *(++p);

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

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

    int mas[ 10 ][ 16  -  количество колонок желательно должно быть равно степени двойки ]
  11. пусть
    1
2
3

    u32 a; f32 b;
b = (f32)(i32)a; - быстрее
b = (f32)a;
  12. Избегайте операции приведения типов.
    1
2
3

    float f; int a;
float b = (float)a; - долго
int m = (int)f; - очень долго
  13. Разумно используйте операции округления:
    1
2
3
4

    только для unsigned:
(u32)x are 10x times faster than 'u32(floor(x))'
u32( x + 1.0f ) are 10x times faster than 'u32(cell(x))'
u32( x + 0.5f ) are 10x times faster than 'u32(round(x))'
  14. пусть
    1
2
3

    float f = 1.0f;
*(int*)&f ^= 0x80000000; - быстрее чем
f  *=  -1.0f;
  15. Если в switch используются последовательные значения параметров case ( case 0: case 1: case 2:…) то switch значительно эффективнее чем if-else. Это происходит за счет того, что при if-else будет вычисляться значение каждого условия, а в случае таких параметров в конструкции switch значение будет вычислено один раз, а затем будет переход сразу к нужному пункту.

  16. Ветвления - это зло. Старайтесь сокращать их количество. Не делайте их внутри больших циклов. switch - это тоже ветвление. Процессор старается предсказывать результат условия (branch prediction) и если значение выражение почти всегда одно и то же, то ветвление не отразится на скорости выполнения кода. Однако в общем случае, предсказание ветвления будет не верно в 50% случаев, что будет замедлять выполнение алгоритма. Каждое ветвление - это переход к последовательности команд процессора. Такой переход ломает конвейер команд процессора и стоит достаточно дорого. Это особенно актуально для шейдеров, SPU подпрограмм, CUDA подпрограмм и в алгоритмах, где идет обработка большого количества данных. Если вам нужно для ста тысяч частиц выполнить какой то код, то постарайтесь минимизировать количество ветвлений. Это может существенно ускорить выполнение кода.

    1
2

    const int NN = 12500000;
const int N = 10;

    следующее плохо (200ms на моей машине):

    1
2
3
4
5
6
7
8
9
10
11

    for( int i = 0; i < NN; ++i )
{
    switch( i % N )
    {
    case 0:        res += 10; break;
    case 3:        res += 30; break;
    case 5:        res += 50; break;
    case 6:        res += 60; break;
    case 8:        res += 80; break;
    }
}

    гораздо лучше (120 ms на моей машине):

    1
2
3

    const int arr[] = { 10, 0, 0, 30, 0, 50, 60, 0, 80, 0 };
for( int i = 0; i < NN; ++i )
    res += arr[ i % N ];

  17. Рассмотрим пример. Двумерный спрайт содержит массив вершин vertex[ 4 ]. Гораздо эффективнее было бы сделать одно хранилище вершин, а в спрайте индекс смещения относительно первого элемента. Это по памяти сэкономит 16 байт на каждый спрайт, а по скорости будет процентов на 30 быстрее проход по вершинам. Это data orientad design. Для С# он так же справедлив.

    Основные направления оптимизаций:

    1. Уменьшение числа ветвлений
    2. Группировка данных по одинаковым типам в памяти (в C# никто еще не отменял массивы структур)
    3. Уменьшение размеров структур

  18. inline функции:

    ’* дает выигрыш в скорости ‘+ увелечивает код ‘+ добавляет в код зависимости (*.h файлов) при компиляции. Это увеличивает время и объем компиляции при изменении кода в функции

    Факты:

    1. компилятор может не встроить функцию (даже _forceinlie - нет горантии встраивания)
    2. VS компилятор при включенной оптимизацией по скорости встраивает любые функции по своему усмотрению, даже если они не объявлены как inline.

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

  19. Рассмотрим результат смены порядка переменных в структуре.
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    struct s1
{
  short int a;
  double b;
  int d; 
}
sizeof(s1[ 10 ]) == 24 * 10
    
struct s2
{
  double b;
  int d; 
  short int a;
}
sizeof(s1[ 10 ]) == 16 * 10

    double по 8 выравнивается всегда

  20. От перестановки мест слогаемых для float value, сумма меняется:
    1
2

    1e+8f + 1.23456 - 1e+8f == 0 но
1e+8f - 1e+8f + 1.23456 ==  1.23456
  21. Бинарный поиск не следует использовать на малом количестве элементов. Если количество элементов меньше чем 40-60 (это число может варьироваться от реализации алгоритмов, но имеет примерно такой порядок), бинарный поиск будет медленнее линейного.
  22. Можно так:
    1
2

    bool b;
int a = b ? x : y;

    Но быстрее:

    1
2

    int b; ( 0 - false, -1 - true)
int a = (x & b) | (y & ~b);
  23. пусть ```cpp int a, b;
    1. int x = (a >= b ? 1 : 0);
    2. int x = (a >= b ? -1 : 0); ```

    Можно заменить на:

    1
2

    1. int x = (b - a) >> 31;
2. int x = (b - a) & 0x80000000;
  24. пусть
    1

    i32 iIndex;

    Условие:

    1

    if( iIndex < 0 && iIndex >= iSize )

    Можно заменить таким:

    1

    if( (u32)iIndex >= iSize )

    Условие:

    1

    if( i >= min && i <= max )

    Можно заменить таким:

    1

    if( (u32)(i-min) <= (u32)max - min )
  25. Выше был пример, как можно switch превратить в static const array и обращаться по индексу. Это применимо например для rtti (run time type identification). Если таким образом определены switch указателей на функции, то замена его доступом к нужной функции за константное время - может быть крайне полезна. То же самое - если это машина состояний. Вместо того, чтобы добавлять новый элемент в свитч, его можно добавлять в массив выше. Но помните про пункт 16.
    1
2
3
4
5
6
7
8
9
10
11
12

    int func( int index )
{
   switch( index )
  {
     case 0 : return f_Func1(); 
     case 3 : return f_Func2();
     case 4 : return f_Func2();
..
     case .. return f_FuncN():
  }
  return 0;
}

    заменить на:

    1
2
3
4
5
6
7
8
9
10
11
12

    int func( int index )
{
   static funcPtr array[] = 
   { 
      &f_Func1,
      NULL,
      &f_Func2,
      ...
      &f_FuncN
   }
   return array[ index ]();
}

Дополнительно

Дополнительные рекомендации по написанию более эффективного кода, можно найти в статьях:

Для более глубокого понимания способов оптимизации советую почитать этот мануалы:

Книги по оптимизации:

Комментарии

mrdekk, 4 сент. 2010, 13:28

Еще одной хорошей практикой является следующее:

Пусть у нас есть цикл

1
2
3

for ( int i = 0; i &lt; strlen( string ); ++i )
{
}

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

1
2
3

for ( int i = 0, size = strlen( string ); i &lt; size; ++i )
{
}

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

FiloXSee, 1 июля 2011, 17:43

Подсказали хороший пример, как сделать код быстрее:

1
2
3

for (int i = 0; str[i]; ++i)
{
}

FiloXSee, 1 июля 2011, 17:44

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

FiloXSee, 1 июля 2011, 17:55

Мне тут подсказали такой вариант:

1

for (int i = 0; str[i]; ++i){}

Предполагалось, что он будет еще быстрее, но это не так.

Вариант

1

for ( int i = 0, size = strlen( string ); i &lt; size; ++i )

будет в каждом витке цикла сравнивать две целые стековые переменные, а вариант

1

for (int i = 0; str[i]; ++i)

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

Saturn812, 14 мая 2011, 22:34

Многие из этих вещей (особенно примитивные ++i vs i++) компилятор уже давно научился оптимизировать сам. А так вообще полезно для общего сведения.

FiloXSee, 17 мая 2011, 10:34

Ты не совсем прав. Действительно в теле цикла разницы между вариантами

1

for( int i = 0; i &lt; 10; i++ )

FiloXSee, 17 мая 2011, 11:17

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

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

C++
c++ оптимизация
Публикация защищена лицензией CC BY 4.0 .
Недавно обновлено
Содержание

Как избавится от vcredist'a

Тест на быстродействие: Hash Map vs Vector