Методы оптимизации кода

@FiloXSee · Регистрация: 01.07.2011

Студворк — интернет-сервис помощи студентам

Написал статью по оптимизации кода на С++. Ее можно почитать тут:
[ссылка удалена]

А вы какие еще способы оптимизации кода знаете? (я не говорю про оптимизацию алгоритмов. Речь идет про код вообще)

Комментарий модератора

Ссылки на сторонние ресурсы у нас и так не приветствуются, а уж битые и подавно...

@grizlik78 · 01.07.2011, 21:08

микроконтроллеры

Добавлено через 2 часа 44 минуты

Сообщение от FiloXSee

Да, видимо там не очень удачный комментарий. Видимо комментатор там имел в виду, что нужно выносить все сложные вычисления из части условия в раздел объявления переменных, чтобы вычислять верхний предел один раз.

Со strlen() пример действительно не совсем удачный.
Касательно же циклов здесь есть гораздо более важный момент: очень желательно, чтобы к моменту начала цикла было бы известно точное количество итераций (даже вычисленное в рантайме). Это даст компилятору шанс развернуть цикл и использовать векторизацию (SIMD).
Например из кода

C
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main()
{
    unsigned len, i, sum = 0;
    char s[1024];
    scanf("%s",s);
    scanf("%u",&len);
    for (i = 0; s[i]; ++i) /* неизвестно сколько раз */
        sum += s[i];
    printf("%d\n", sum);
    return 0;
}

gcc -O3 на x86_64 делает такой ассемблерный (извините за AT&T

) между scanf и printf

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    call    scanf
    movzbl  16(%rsp), %eax
    testb   %al, %al
    je  .L5
    addq    $1, %rbx
    xorl    %edx, %edx
    .p2align 4,,10
    .p2align 3
.L3:
    movsbl  %al, %eax
    addl    %eax, %edx
    movzbl  (%rbx), %eax
    addq    $1, %rbx
    testb   %al, %al
    jne .L3
.L2:
    xorl    %eax, %eax
    movl    $.LC2, %esi
    movl    $1, %edi
    call    __printf_chk
; .................
 
.L5:
    .cfi_restore_state
    xorl    %edx, %edx
    jmp .L2

Тогда как из кода

C
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main()
{
    unsigned len, i, sum = 0;
    char s[1024];
    scanf("%s",s);
    scanf("%u",&len);
    for (i = 0; i < len; ++i) /* ровно len раз */
        sum += s[i];
    printf("%d\n", sum);
    return 0;
}

получается это:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
    call    scanf
    movl    28(%rsp), %esi
    testl   %esi, %esi
    je  .L8
    movl    %esi, %ecx
    shrl    $4, %ecx
    movl    %ecx, %eax
    sall    $4, %eax
    cmpl    $15, %esi
    jbe .L9
    testl   %eax, %eax
    je  .L9
    pxor    %xmm0, %xmm0
    xorl    %edx, %edx
    pxor    %xmm6, %xmm6
    pxor    %xmm4, %xmm4
    .p2align 4,,10
    .p2align 3
.L4:
    movdqa  (%rbx), %xmm1
    addl    $1, %edx
    movdqa  %xmm6, %xmm3
    addq    $16, %rbx
    movdqa  %xmm1, %xmm2
    cmpl    %edx, %ecx
    pcmpgtb %xmm1, %xmm3
    punpcklbw   %xmm3, %xmm2
    punpckhbw   %xmm3, %xmm1
    movdqa  %xmm4, %xmm3
    movdqa  %xmm2, %xmm5
    pcmpgtw %xmm2, %xmm3
    punpckhwd   %xmm3, %xmm2
    punpcklwd   %xmm3, %xmm5
    movdqa  %xmm1, %xmm3
    paddd   %xmm5, %xmm0
    paddd   %xmm2, %xmm0
    movdqa  %xmm4, %xmm2
    pcmpgtw %xmm1, %xmm2
    punpcklwd   %xmm2, %xmm3
    punpckhwd   %xmm2, %xmm1
    paddd   %xmm3, %xmm0
    paddd   %xmm1, %xmm0
    ja  .L4
    movdqa  %xmm0, %xmm1
    cmpl    %eax, %esi
    psrldq  $8, %xmm1
    paddd   %xmm1, %xmm0
    movdqa  %xmm0, %xmm1
    psrldq  $4, %xmm1
    paddd   %xmm1, %xmm0
    movd    %xmm0, 12(%rsp)
    movl    12(%rsp), %edx
    je  .L2
    .p2align 4,,10
    .p2align 3
.L10:
    mov %eax, %ecx
    addl    $1, %eax
    movsbl  32(%rsp,%rcx), %ecx
    addl    %ecx, %edx
    cmpl    %eax, %esi
    ja  .L10
.L2:
    xorl    %eax, %eax
    movl    $.LC2, %esi
    movl    $1, %edi
    call    __printf_chk
; .................
 
.L8:
    .cfi_restore_state
    xorl    %edx, %edx
    jmp .L2
.L9:
    xorl    %edx, %edx
    xorl    %eax, %eax
    .p2align 4,,2
    jmp .L10

что на длинных циклах реально должно получиться эффективнее (считаем что данные в кэше) за счёт активного использования SSE и нечастых проверок с переходами.

@FiloXSee · 29.12.2011, 08:56 **[ТС]**

Мной написаны еще несколько статей по написанию эффективного кода. Надеюсь они будут вам полезны:
http://itw66.ru/blog/c_plus_plus/571.html - Эффективный код на С++
http://itw66.ru/blog/c_plus_plus/491.html - Методы оптимизации памяти

@fasked · 29.12.2011, 09:17

следующее очень плохо:

C
1
2
3
4
5
6
7
8
9
10
int func( int index )
{
   switch( index )
  {
     case 0 : return 10; 
     case 1 : return 20;
..
     case .. :
  }
}

гораздо лучше:

C
1
2
3
4
5
int func( int index )
{
   static int array[] = { 10, 20, ...};
   return array[ index ];
}

Если говорить именно про оптимизацию, то данный код одинаков. Конструкция switch с небольшими промежутками в case, а в данном случае это так и есть (case 0, case 1, case 2 etc) раскрывается в точно такую же таблицу и время доступа будет О(1).

@res · 29.12.2011, 09:28

Сообщение от FiloXSee

Мной написаны еще несколько статей по написанию эффективного кода. Надеюсь они будут вам полезны:
http://itw66.ru/blog/c_plus_plus/571.html - Эффективный код на С++
http://itw66.ru/blog/c_plus_plus/491.html - Методы оптимизации памяти

/facepalm.:cofee2:

@fasked · 29.12.2011, 09:34

Используйте список инициализации конструктора, вместо присвоения значений в его теле. Так поля будут инициализироваться один раз.
Пишите так:

C++
1
2
3
4
5
SomeClass::SomeClass( int val1, int val2 )
   : m_val1( val1 )
   , m_val2( val2 )
{
}

Вместо:

C++
1
2
3
4
5
SomeClass::SomeClass( int val1, int val2 )
{
   m_val1 = val1;
   m_val2 = val2;
}

А во втором случае типа два раза?

Не правильный вариант выделения памяти:

Граммар наци негодуют.

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 8 bit
typedef unsigned char           u8;
typedef signed   char           i8;
 
// 16 bit
typedef unsigned short          u16;
typedef signed   short          i16;
 
// 32 bit
typedef unsigned int            u32;
typedef signed   int            i32;
 
// 64 bit
typedef unsigned long long      u64;
typedef signed   long long      i64;
 
// floats
typedef float                   f32;
typedef double                  f64;

Стандарт языка не гарантирует размер типов, то есть не факт, что int - 32-битный и т.д.. Кроме того есть заголовочный файл stdint.h, в котором объявлены синонимы целочисленных типов с гарантированной шириной:

The following types are required:
int8_t
int16_t
int32_t
uint8_t
uint16_t
uint32_t

В целом серьезно разбирать Вашу статью лениво. Она уныла.

@ValeryLaptev · 29.12.2011, 10:50

Посмотрел статьи. Выглядит как предположения программиста. Не подкрепленные ничем.
Либо тут надо давать измерение времени - профиль.
Либо показывать ассемблерный код.
Тогда будет понятно, где выгода, а где - нет.
Кроме того, возможно автор просто не умеет пользоваться оптимизатором?
gcc вполне себе хорошо оптимизирует и сам проводит все ре рефакторинги, которые приводит автор.
Но которые в коде гораздо менее понятны, чем исходный вариант.

@FiloXSee · 29.12.2011, 13:59 **[ТС]**

Сообщение от fasked

Если говорить именно про оптимизацию, то данный код одинаков. Конструкция switch с небольшими промежутками в case, а в данном случае это так и есть (case 0, case 1, case 2 etc) раскрывается в точно такую же таблицу и время доступа будет О(1).

Если условия идут с 0 и по порядку то да. Однако:
1. switch занимает больше места. Если нужно возвращать статические данные, то в массиве будет понятнее.
2. там могут быть разряженные значения 100, 200... (допустим статический массив на 65535 значений, который переводит индекс юникод чара в литеру в словаре символов). Тогда подобная оптимизация не сработает.
3. вы говорите про конкретную платформу и компилятор. Говорить о том, что в компиляторах под PS3, Xbox360 я бы не стал. На мобильных платформах это тоже может не сработать.

@OstapBender · 29.12.2011, 14:41

Сообщение от fasked

А во втором случае типа два раза?

1 раз инициализация, 2 раз присваивание?

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

а можно вопрос , как в данном случае связаны передача параметров и возврат значения?

@FiloXSee · 29.12.2011, 15:10 **[ТС]**

Сообщение от fasked

А во втором случае типа два раза?

Да. В первом случае переменная создается и инициализируется сразу значением (одна операция). Во втором случае переменная сначала создается, а затем идет присвоение ей значения (две операции). Это наиболее ощутимо, если эта переменная - класс. Тогда в первом случае вызовется только конструктор, а во втором конструктор и функция.

Сообщение от ValeryLaptev

Но которые в коде гораздо менее понятны, чем исходный вариант.

Поэтому я и написал, что подобные вещи нужно применять тогда, когда это необходимо. Простой пример: есть статья как проводилась оптимизация в игре Uncharted2. Берется цикл, который выполняется за 280ms и реорганизацией кода + побитовыми операциями + разверткой цикла + векторизацией некоторых данных доводится до 34 милисекунд, а после переводится на асемблер и выполняется 7ms. Про асемблер я нечего не говорил, но и без него оптимизация в 8 раз. Понятно, что сразу такое не написать. Это была оптимизация уже конкретного кода под конкретную платформу.

Те приемы которые я описал это информация к сведению. Если вы столкнетесь, с необходимостью оптимизации, то статьи подскажет вам некоторые варианты реорганизации кода, которые могут помочь. Некоторые пункты в статьях подходят как best practice (вроде инициализации переменных класса в списке инициализации, а не в теле конструктора.

Сообщение от ValeryLaptev

Посмотрел статьи. Выглядит как предположения программиста. Не подкрепленные ничем.

Да это так. Проблема в том, что я занимаюсь разработкой под разные платформы (PC, MacOsX, Ps3, Xbox360, iOs + есть еще SPU и шейдеры) и везде свои тонкости. То что компилятор оптимизирует в одном месте он не будет делать в другом. В статьях я собрал в виде списка рекомендаций приемы, которые помогали в различных ситуациях.

Добавлено через 9 минут

Сообщение от OstapBender

а можно вопрос , как в данном случае связаны передача параметров и возврат значения?

Синтаксис не имеет значения. Допустим вы планируете написать функцию, которая вам вернет некие данные. На этапе формулировки задачи не важно как она вернет, через параметр функции или через return. Эта рекомендация говорит, что если объем передаваемых данных больше чем 4 байте (тем более если намного больше) то лучше передать память по ссылке или указателю и заполнить ее, чем возвращать сами данные.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
Вместо:
Struct GetData()
{
  Struct st;....
  return st;
}
 
Писать так:
void GetData( Struct& st ) // ну или по указателю передать
{
   st.value = ...;
   ...
}

@fasked · 30.12.2011, 10:55

Сообщение от FiloXSee

Если условия идут с 0 и по порядку то да. Однако:
1. switch занимает больше места. Если нужно возвращать статические данные, то в массиве будет понятнее.
2. там могут быть разряженные значения 100, 200... (допустим статический массив на 65535 значений, который переводит индекс юникод чара в литеру в словаре символов). Тогда подобная оптимизация не сработает.

Каким образом связаны статичность данных и читабельность кода?
Также я что-то не понял как Вы собираетесь в массив разреженные индексы заталкивать. Так же с нуля и по порядку. Иначе придется создавать заведомо больший массив. Как правило, компилятор сам выбирает что лучше (память или скорость) при использовании switch'a.
switch занимает больше места? Вы имеете в виду по количеству кода? С этим тоже можно поспорить кстати. Все зависит от размера массива, его же тоже надо инициализировать. Что в своем примере Вы опустили. Плюс ко всему к случаю с массивом придется добавить проверку валидности индекса. Этого в Вашем примере тоже нет.

Сообщение от FiloXSee

Говорить о том, что в компиляторах под PS3, Xbox360 я бы не стал. На мобильных платформах это тоже может не сработать.

Ровно как и говорить обратное тоже не стоит.

Сообщение от FiloXSee

Да. В первом случае переменная создается и инициализируется сразу значением (одна операция). Во втором случае переменная сначала создается, а затем идет присвоение ей значения (две операции). Это наиболее ощутимо, если эта переменная - класс. Тогда в первом случае вызовется только конструктор, а во втором конструктор и функция.

Так и надо было писать про классы, а не скалярные типы.

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

@FiloXSee · 30.12.2011, 11:15 **[ТС]**

Сообщение от fasked

Иначе придется создавать заведомо больший массив.

Да, иногда ради сложность доступа O(1) лучше создать больший массив, чем бегать по маленькому.

Сообщение от fasked

Как правило, компилятор сам выбирает что лучше (память или скорость)

Если проектируешь некую систему, то иногда нужно самому такое решение принять.

Сообщение от fasked

В любом случае я против ручной оптимизации, особенно не своевременной.

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

Например: у меня есть система частиц. Я хочу использовать для параметра size каждой частицы не float а 16-ти битные целые числа с фиксированной точкой. И как тут понять, это даст результат или нет? И читабельность - тоже спорное понятие, человеку который с этим знаком будет без разницы, ну а новичку будет сложно разобраться. С одной стороны - вся математика будет в целых числах. С другой стороны нужно будет иногда паковать и распаковывать данные. На практике такая оптимизация дает 30% прироста производительности за счет того, что структура начинает занимать в 2 раза меньше памяти. Но принимать решение о такой оптимизации нужно в каждом конкретном случае.

@fasked · 30.12.2011, 11:51

Сообщение от FiloXSee

Если проектируешь некую систему, то иногда нужно самому такое решение принять.

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

Сообщение от FiloXSee

Что такое "потенциально лучше" решается в каждом конкретном случае.

Например профайлером.

Сообщение от FiloXSee

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

А Вы сможете мне привести конкретный код, где бы оптимизации подобного рода реально работали? Какой-нибудь небольшой примерчик.
Все же, как правило, прирост в эффективности достигается "алгоритмическими" (асимптотическая оценка со всеми вытекающими) оптимизациями.

@FiloXSee · 30.12.2011, 14:28 **[ТС]**

Сообщение от fasked

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

Данные - это самое главное. Правильная их организация в памяти сейчас является ключевым фактором. Процессор сейчас очень быстрый и узким местом является память. Data Oriented Design рулит.

Сообщение от fasked

Например профайлером.

Именно им. Сделал -> протестировал -> нашел узкое место -> сделал ->... Я писал про способы в пункте "сделал".

Сообщение от fasked

А Вы сможете мне привести конкретный код, где бы оптимизации подобного рода реально работали? Какой-нибудь небольшой примерчик. Все же, как правило, прирост в эффективности достигается "алгоритмическими"

Слишком много сейчас играют данные. Я уже описал один пример - использование 16-ть бит fixed-point вместо float для переменных структуры частицы. +30% прироста производительности. Я уже запутался по какой именно из статей вопрос, поэтому я приведу пример замечательной презентации по Data Oriented Design. Эта одна из лучших презентаций по теме, которая меняет представление с "как правило, прирост в эффективности достигается алгоритмическими" на "проектирование любой системы нужно начинать с организации данных"!!!

Вот эта статья:
research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_ GCAP_09.pdf

Новые блоги и статьи Все статьи Все блоги /
[golang] Двоичная куча, min-heap alhaos 20.05.2026 Двоичная куча Двоичная куча — структура данных, которая всегда держит самый важный элемент наготове. Представьте очередь к хилеру в игре, и очередь из игроков в приоритете те у кого меньше. . .	[golang] Breadth-First Search alhaos 19.05.2026 BFS (Breadth-First Search) — это базовый алгоритм обхода графа в ширину, который поуровнево исследует все связанные вершины. Он начинает с выбранной точки и проверяет всех соседей, прежде чем. . .	[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;
FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .

Методы оптимизации кода

Решение

Решение

@FiloXSee 19 / 10 / 0 Регистрация: 01.07.2011 Сообщений: 25
	29.12.2011, 08:56 [ТС]
	Мной написаны еще несколько статей по написанию эффективного кода. Надеюсь они будут вам полезны: http://itw66.ru/blog/c_plus_plus/571.html - Эффективный код на С++ http://itw66.ru/blog/c_plus_plus/491.html - Методы оптимизации памяти 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	29.12.2011, 10:50
	Посмотрел статьи. Выглядит как предположения программиста. Не подкрепленные ничем. Либо тут надо давать измерение времени - профиль. Либо показывать ассемблерный код. Тогда будет понятно, где выгода, а где - нет. Кроме того, возможно автор просто не умеет пользоваться оптимизатором? gcc вполне себе хорошо оптимизирует и сам проводит все ре рефакторинги, которые приводит автор. Но которые в коде гораздо менее понятны, чем исходный вариант. 0