Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 35, средняя оценка - 4.74
FiloXSee
18 / 9 / 0
Регистрация: 01.07.2011
Сообщений: 25
01.07.2011, 07:48     Методы оптимизации кода #1
Написал статью по оптимизации кода на С++. Ее можно почитать тут:
[ссылка удалена]

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

 Комментарий модератора 
Ссылки на сторонние ресурсы у нас и так не приветствуются, а уж битые и подавно...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2011, 07:48     Методы оптимизации кода
Посмотрите здесь:

подскажите по оптимизации кода C++
C++ Методы оптимизации памяти
C++ Разработать классы для описанных ниже объектов. Включить в класс методы set (…), get (…), show (…). Определить другие методы
C++ Создать класс Triad (тройка чисел) - определить методы; определить производный класс Date - переопределить методы
C++ Методы Оптимизации: Метод параллельных касательных - нужен алгоритм
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
01.07.2011, 21:08     Методы оптимизации кода #41
микроконтроллеры

Добавлено через 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
18 / 9 / 0
Регистрация: 01.07.2011
Сообщений: 25
29.12.2011, 08:56  [ТС]     Методы оптимизации кода #42
Мной написаны еще несколько статей по написанию эффективного кода. Надеюсь они будут вам полезны:
http://itw66.ru/blog/c_plus_plus/571.html - Эффективный код на С++
http://itw66.ru/blog/c_plus_plus/491.html - Методы оптимизации памяти
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
29.12.2011, 09:17     Методы оптимизации кода #43
следующее очень плохо:
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
56 / 9 / 1
Регистрация: 05.04.2010
Сообщений: 143
29.12.2011, 09:28     Методы оптимизации кода #44
Цитата Сообщение от FiloXSee Посмотреть сообщение
Мной написаны еще несколько статей по написанию эффективного кода. Надеюсь они будут вам полезны:
http://itw66.ru/blog/c_plus_plus/571.html - Эффективный код на С++
http://itw66.ru/blog/c_plus_plus/491.html - Методы оптимизации памяти
/facepalm.:cofee2:
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
29.12.2011, 09:34     Методы оптимизации кода #45
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Используйте список инициализации конструктора, вместо присвоения значений в его теле. Так поля будут инициализироваться один раз.
Пишите так:
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
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
29.12.2011, 10:50     Методы оптимизации кода #46
Посмотрел статьи. Выглядит как предположения программиста. Не подкрепленные ничем.
Либо тут надо давать измерение времени - профиль.
Либо показывать ассемблерный код.
Тогда будет понятно, где выгода, а где - нет.
Кроме того, возможно автор просто не умеет пользоваться оптимизатором?
gcc вполне себе хорошо оптимизирует и сам проводит все ре рефакторинги, которые приводит автор.
Но которые в коде гораздо менее понятны, чем исходный вариант.
FiloXSee
18 / 9 / 0
Регистрация: 01.07.2011
Сообщений: 25
29.12.2011, 13:59  [ТС]     Методы оптимизации кода #47
Цитата Сообщение от fasked Посмотреть сообщение
Если говорить именно про оптимизацию, то данный код одинаков. Конструкция switch с небольшими промежутками в case, а в данном случае это так и есть (case 0, case 1, case 2 etc) раскрывается в точно такую же таблицу и время доступа будет О(1).
Если условия идут с 0 и по порядку то да. Однако:
1. switch занимает больше места. Если нужно возвращать статические данные, то в массиве будет понятнее.
2. там могут быть разряженные значения 100, 200... (допустим статический массив на 65535 значений, который переводит индекс юникод чара в литеру в словаре символов). Тогда подобная оптимизация не сработает.
3. вы говорите про конкретную платформу и компилятор. Говорить о том, что в компиляторах под PS3, Xbox360 я бы не стал. На мобильных платформах это тоже может не сработать.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
29.12.2011, 14:41     Методы оптимизации кода #48
Цитата Сообщение от fasked Посмотреть сообщение
А во втором случае типа два раза?
1 раз инициализация, 2 раз присваивание?

4. Если нужно чтобы функция вернула структуру размером более 4 байт, то передайте эту структуру в функцию по указателю или ссылке. Пусть функция инициализирует ее поля через указатель.
а можно вопрос , как в данном случае связаны передача параметров и возврат значения?
FiloXSee
18 / 9 / 0
Регистрация: 01.07.2011
Сообщений: 25
29.12.2011, 15:10  [ТС]     Методы оптимизации кода #49
Цитата Сообщение от 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
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.12.2011, 10:55     Методы оптимизации кода #50
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от FiloXSee Посмотреть сообщение
Если условия идут с 0 и по порядку то да. Однако:
1. switch занимает больше места. Если нужно возвращать статические данные, то в массиве будет понятнее.
2. там могут быть разряженные значения 100, 200... (допустим статический массив на 65535 значений, который переводит индекс юникод чара в литеру в словаре символов). Тогда подобная оптимизация не сработает.
Каким образом связаны статичность данных и читабельность кода?
Также я что-то не понял как Вы собираетесь в массив разреженные индексы заталкивать. Так же с нуля и по порядку. Иначе придется создавать заведомо больший массив. Как правило, компилятор сам выбирает что лучше (память или скорость) при использовании switch'a.
switch занимает больше места? Вы имеете в виду по количеству кода? С этим тоже можно поспорить кстати. Все зависит от размера массива, его же тоже надо инициализировать. Что в своем примере Вы опустили. Плюс ко всему к случаю с массивом придется добавить проверку валидности индекса. Этого в Вашем примере тоже нет.
Цитата Сообщение от FiloXSee Посмотреть сообщение
Говорить о том, что в компиляторах под PS3, Xbox360 я бы не стал. На мобильных платформах это тоже может не сработать.
Ровно как и говорить обратное тоже не стоит.
Цитата Сообщение от FiloXSee Посмотреть сообщение
Да. В первом случае переменная создается и инициализируется сразу значением (одна операция). Во втором случае переменная сначала создается, а затем идет присвоение ей значения (две операции). Это наиболее ощутимо, если эта переменная - класс. Тогда в первом случае вызовется только конструктор, а во втором конструктор и функция.
Так и надо было писать про классы, а не скалярные типы.

Не поймите меня неправильно. Я не агитирую всех и всюду использовать switch. Просто все Ваши рекомендации в отрыве от контекста смотрятся бестолковыми. В любом случае я против ручной оптимизации, особенно не своевременной. Я за читабельность. Если какой-то метод смотрится красиво - я предпочту использовать его, а не другой может быть несколько более быстрый.
FiloXSee
18 / 9 / 0
Регистрация: 01.07.2011
Сообщений: 25
30.12.2011, 11:15  [ТС]     Методы оптимизации кода #51
Цитата Сообщение от fasked Посмотреть сообщение
Иначе придется создавать заведомо больший массив.
Да, иногда ради сложность доступа O(1) лучше создать больший массив, чем бегать по маленькому.

Цитата Сообщение от fasked Посмотреть сообщение
Как правило, компилятор сам выбирает что лучше (память или скорость)
Если проектируешь некую систему, то иногда нужно самому такое решение принять.

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

Например: у меня есть система частиц. Я хочу использовать для параметра size каждой частицы не float а 16-ти битные целые числа с фиксированной точкой. И как тут понять, это даст результат или нет? И читабельность - тоже спорное понятие, человеку который с этим знаком будет без разницы, ну а новичку будет сложно разобраться. С одной стороны - вся математика будет в целых числах. С другой стороны нужно будет иногда паковать и распаковывать данные. На практике такая оптимизация дает 30% прироста производительности за счет того, что структура начинает занимать в 2 раза меньше памяти. Но принимать решение о такой оптимизации нужно в каждом конкретном случае.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.12.2011, 11:51     Методы оптимизации кода #52
Цитата Сообщение от FiloXSee Посмотреть сообщение
Если проектируешь некую систему, то иногда нужно самому такое решение принять.
Если проектируешь некую систему, надо бы размышлять на более высоком уровне абстракции, чем данные.
Цитата Сообщение от FiloXSee Посмотреть сообщение
Что такое "потенциально лучше" решается в каждом конкретном случае.
Например профайлером.
Цитата Сообщение от FiloXSee Посмотреть сообщение
Просто удобно не сидеть в раздумье "что делать", а пробовать типовые шаблоны и смотреть на результат. Некоторые шаблоны я и описал.
А Вы сможете мне привести конкретный код, где бы оптимизации подобного рода реально работали? Какой-нибудь небольшой примерчик.
Все же, как правило, прирост в эффективности достигается "алгоритмическими" (асимптотическая оценка со всеми вытекающими) оптимизациями.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2011, 14:28     Методы оптимизации кода
Еще ссылки по теме:

C++ Курсовая. Методы оптимизации
C++ Дублирование кода и константные методы
Методы оптимизации C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
FiloXSee
18 / 9 / 0
Регистрация: 01.07.2011
Сообщений: 25
30.12.2011, 14:28  [ТС]     Методы оптимизации кода #53
Цитата Сообщение от 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
Yandex
Объявления
30.12.2011, 14:28     Методы оптимизации кода
Ответ Создать тему
Опции темы

Текущее время: 23:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru