Глобальные и локальные оптимизации презентация

кода и использование подпрограмм для повторяющихся вычислений.
Принцип реализации утилит как «черного ящика».

Модульность исходного кода усложняет задачу по его оптимизации.

Обсуждаемые в предыдущих разделах оптимизации процедурного уровня:
эффективно работают только с локальными переменными
всякий вызов функции - «черный ящик»
неизвестны многие свойства переданных в процедуру параметров
неизвестны свойства глобальных переменных

Для решения этих проблем необходимо исследование программы в целом.

скалярных оптимизаций необходимы знания о свойствах функций, вызываемых внутри процедуры.
2.) Оптимизации циклических конструкций:
Для таких оптимизаций необходимо
корректное определение объектов, которые могут ссылаться на одну память
знание свойств функций внутри циклов (не изменяют итерационные переменные, не содержат выхода из программы и т.д.)
оценка количества итераций цикла
3.) Векторизация:
необходима информация о выравнивании объектов в памяти

a,b,c;

a=5;
c=a;
unknown(&a);
if(a==5)
printf("a==5\n");
b=a;
printf("%d %d %d\n",a,b,c);
return(1);
}

Сохранится ли if утверждение в результирующем коде?

_unknown ;9.1
; LOE ebx esi
.B1.9: ; Preds .B1.8
add esp, 8 ;9.1
; LOE ebx esi
.B1.2: ; Preds .B1.9
mov edi, DWORD PTR [a.3.0.1] ;10.4
cmp edi, 5 ;10.7
jne .B1.4 ; Prob 0% ;10.7
; LOE ebx esi edi
…

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

{
float c,d;
scanf_s("%f",&a);
scanf_s("%f",&b);
c=0;
if(sqrt(a+b)>3)
c=a+b;
else
unknown();
d=sqrt(a+b)+c;
printf("d=%f\n",d);
return 1;
}
Здесь есть общее подвыражение sqrt(a+b). Будет ли CSE работать с этим подвыражением?

; Preds .B1.2
movss xmm0, DWORD PTR [a] ;15.9
pxor xmm14, xmm14 ;14.1
addss xmm0, DWORD PTR [b] ;15.11
cvtps2pd xmm1, xmm0 ;15.11
sqrtsd xmm1, xmm1 ;15.4
comisd xmm1, QWORD PTR [_2il0floatpacket.0] ;15.14
jbe .B1.5 ; Prob 22% ;15.14
; LOE rbx rbp rsi rdi r12 r13 r14 r15 xmm0 xmm1 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.4:: ; Preds .B1.3
movaps xmm14, xmm0 ;16.3
jmp .B1.7 ; Prob 100% ;16.3
; LOE rbx rbp rsi rdi r12 r13 r14 r15 xmm1 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.5:: ; Preds .B1.3
call unknown ;19.3
; LOE rbx rbp rsi rdi r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.6:: ; Preds .B1.5
movss xmm0, DWORD PTR [a] ;21.8
addss xmm0, DWORD PTR [b] ;21.10
cvtps2pd xmm1, xmm0 ;21.10
sqrtsd xmm1, xmm1 ;21.3
…

необходим дополнительный проход. Но поскольку, каждая функция в свою очередь может вызывать другие функции, а также себя (рекурсия), то необходимо произвести анализ графа вызовов (Call graph).
Граф вызовов представляет взаимоотношение вызовов между процедурами в программе. Каждая вершина представляет процедуру и каждая грань (f,g) указывает, что процедура f вызывает процедуру g.
Граф может быть статическим, вычисленным на этапе компиляции или динамическим, т.е. отражающим реальные вызовы при выполнении программы. (VTune)
Одной из основных задач межпроцедурного анализа является построения графа вызовов и выяснения свойств функций на основе его анализа. (Например, глобальный анализ потоков данных требует знания о том, какие данные каждая функция модифицирует).
Граф вызовов может быть полным и неполным. Если при сборе проекта используются библиотеки, свойства функций которых мы не знаем, то граф будет являться неполным и полноценный анализ не будет осуществлен.

Obj с ВП

IP/IPO оптимизации

Скалярные оптимизации

HPO

Генератор кода

Исполняемый файл
Библиотека

Архитектура компилятора

enable(DEFAULT)/disable single-file IP optimization
within files
/Qipo[n] enable multi-file IP optimization between files
/Qipo-c generate a multi-file object file (ipo_out.obj)
/Qipo-S generate a multi-file assembly file (ipo_out.asm)
/Qipo-jobs
specify the number of jobs to be executed simultaneously during the
IPO link phase

с –ipo:
#include
extern float a,b;

void unknown() {
printf("a=%f b=%f\n",a,b);
}
icl –Qipo test.c unknown.c –Ob0 –Qipo-S
Работают ли протяжка констант и удаление общих подвыражений?

глобальных и статических указателей (Local point to analysis - LPT)
Важная часть механизма определения зависимостей.

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

{
*a=&p1;
*b=&p1; // <= a and b poins to p1
}

int main() {
int i,ar[100];
init(&a,&b);
printf("*a= %d *b=%d\n",*a,*b);

for(i=0;i<100;i++) {
ar[i]=i*(*a)*(*a);
*b+=1; // *a is changed through *b
}
printf("ar[50]= %d p2=%d\n",ar[50],p2);
}
Можно ли осуществлять цикловые оптимизации с циклом for?

no_side_effect, always_return и т.д.
IPA используется для протяжки атрибутов переменных. Например, переменные помеченные атрибутом «адрес был взят» исключаются из многих оптимизаций. Этот атрибут для глобальных переменных устанавливает IPA.
Продвижение данных (Data promotion). Каждая переменная имеет свою область видимости (scope). IPA позволяет протягивать данные, которые используются только в определенной процедуре, на уровень этой процедуры, что сразу позволяет включить их во многие оптимизации.
Функции, используемые только в одной программе получают атрибут static.
Удаление неиспользуемых глобальных переменных.
Удаление мертвого кода.
В данном случае, функция не будет включаться в исполняемый модуль, если она не входит в граф вызовов или все ее вызовы были подставлены (inline). (Вывод – для улучшения размеров кода и времени компиляции используйте атрибут static).
Протяжка информации о выравнивании аргументов. Если актуальные аргументы функции всегда выровнены, то мы можем улучшить векторизацию внутри процедуры.

оптимизировать одну или несколько процедур или выяснить, как они соотносятся друг с другом.
Протяжка константных аргументов
если при каждом вызове процедуры f(i,j,k) в программе в качестве аргумента i всегда передается некая константа, то это позволяет присвоить первому формальному аргументу значение этой константы в коде процедуры f().
Протяжка возвращаемых значений.
Если процедура всегда возвращает константное значение, то возможно протянуть это значение наружу.
То же самое касается передаваемых в процедуру аргументов. Если перед выходом из процедуры значение аргумента константа, то ее также можно протянуть наружу.

функцию.
cat test.c
#include
extern void known(int variant,int *var);
int main() {
int var;
int ttt;

var=2;
ttt=3;
known(var,&ttt);
printf("ttt=%i\n",ttt);
}

cat known.c
void known(int var,int *ttt) {
if(var>0)
(*ttt)++;
else
(*ttt)--;
}

icc –Ob0 test.c known.c -fast -ipo-S
…
known:
# parameter 1: %edi
# parameter 2: %rsi
..B2.1: # Preds ..B2.0
..___tag_value_known.8: #1.30
addl $1, (%rsi) #3.3
ret #6.1
.align 16,0x90
…
Таким образом, протянув константу удалось избавиться от ветвления.

функции, удаляет переходы, которые могут быть источниками неэффективной работы памяти, позволяет эффективнее применять скалярные и оптимизации циклов. Недостаток оптимизации – увеличение размера приложения. Как следствие – увеличение времени компиляции и необходимых для компиляции ресурсов.
Эвристики для подстановок пытаются выбрать наиболее выгодные для подстановки функции с тем, чтобы получить максимальный эффект для производительности, не выходя за пределы допустимого увеличения кода.

Атрибут функции inline
inline int exforsys(int x1) { return 5*x1; }
Программист «рекомендует» компилятору сделать подстановку такой функции.

ко всем вызовам, которые осуществляются данным вызовом.
Директива inline рекомендует инлайнить
noinline требует не инлайнить
forceinline требует инлайнить
Аналоги для языка Фортран
cDEC$ ATTRIBUTES INLINE :: procedure
cDEC$ ATTRIBUTES NOINLINE :: procedure
cDEC$ ATTRIBUTES FORCEINLINE :: procedure

10/17/10

n=0 disable inlining
n=1 inline functions declared with __inline, and perform C++ inlining
n=2 inline any function, at the compiler's discretion
/Qinline-min-size:
set size limit for inlining small routines
/Qinline-min-size-
no size limit for inlining small routines
/Qinline-max-size:
set size limit for inlining large routines
/Qinline-max-size-
no size limit for inlining large routines
/Qinline-max-total-size:
maximum increase in size for inline function expansion
/Qinline-max-total-size-
no size limit for inline function expansion

in any function
/Qinline-max-per-routine-
no maximum number of inline instances in any function
/Qinline-max-per-compile:
maximum number of inline instances in the current compilation
/Qinline-max-per-compile-
no maximum number of inline instances in the current compilation
/Qinline-factor:
set inlining upper limits by n percentage
/Qinline-factor-
do not set set inlining upper limits
/Qinline-forceinline
treat inline routines as forceinline
/Qinline-dllimport
allow(DEFAULT)/disallow functions declared __declspec(dllimport) to be inlined
/Qinline-calloc directs the compiler to inline calloc() calls as malloc()/memset()

x=3 в другом, то возможно заменить вызов функции f на вызовы f2 и f3.
Частичная подстановка
Если в функции f содержится вначале функции код, зависящий только от формальных аргументов, то этот код может быть подставлен в вызывающую функцию и удален из функции f.

C++ - объектно-ориентированный язык поддерживающий высокий уровень абстракции.
Возможность выполнения методов функции в зависимости от типа объекта времени выполнения.

A => B => C
Все наследуемые классы переопределяют virtual int foo()

int process(class A *a) {
return(a->foo());
}

Obj с ВП

IP/IPO оптимизации

Скалярные оптимизации

HPO

Генератор кода

Исполняемый файл
Библиотека

Архитектура компилятора

используется только одно подвыражение
z=x*y;
if(почти_никогда) {
t=x*y;
}
невыгодно выносить инвариант из цикла, если он может ни разу не использоваться при расчетах
for(i=0;i …
if(почти_никогда) {
t = invariant; break; }
}
выгодно группировать вместе наиболее «часто» используемые фрагменты программы
невыгодно выполнять подстановку функции, которая «редко» вызывается в процессе выполнения программы.

оптимизацию редко используемых фрагментов кода.

Статистический профилировщик вычисляет вероятность условных переходов и вес базовых блоков. Это делается на основе анализа исходного кода. Межпроцедурный анализ пытается рассчитать вес процедур на основе анализа графа вызовов.

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

Существует встроенная функция builtin_expect предназначенная для передачи компилятору информации о вероятности ветвления.

if(x) => if(__builtin_expect(x,1))

запуске инструментированного приложения. Инструментация в данном случае– снабжение приложения механизмами для сбора статистики.
/Qprof-gen[:keyword]
instrument program for profiling.
Optional keyword may be srcpos or globdata

/Qprof-use[:]
enable use of profiling information during optimization
weighted - invokes profmerge with -weighted option to scale data
based on run durations
[no]merge - enable(default)/disable the invocation of the profmerge
tool

приложение с представительным набором данных, т.е. одним или несколькими наборами наиболее часто используемых данных. Информация добавляется в файл со статистиками.
пересобрать приложение с опцией /Qprof_use для использование собранных статистик при компиляции.

10/17/10

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

Некоторые оптимизации которые базируются на профилировочной информации:
перестановки базовых блоков
группировка часто используемых функций
вынос «холодных» базовых блоков за пределы функции (расщепление функций)

10/17/10

исполнения приложения с использованием операторов new и delete, malloc и free. Менеджер памяти, это часть приложения, обрабатывающая запросы на выделение и освобождение памяти.
Типичные ситуация, когда динамическое выделение памяти необходимо:
Необходимо создать большой массив размер которого неизвестен во время компиляции.
Массив может быть очень большим для того чтобы расположить его на стеке.
Объекты должны создаваться во время работы программы, но количество необходимых объектов неизвестно.
Неудобства динамического выделения памяти:
Выделение и освобождение памяти имеет свою цену.
Выделенная память становится фрагментированной, когда выделяются объекты различного типа в произвольном порядке. Это делает неэффективным кэширование данных.
Если необходимо изменить размер созданного объекта, но нет возможности расширить блок, возникает потребность в копировании содержания старого блока памяти в новый блок.
Необходима сборка мусора, поскольку в процессе работы могут исчезнуть блоки памяти необходимого размера.

приложения.
Различные менеджеры памяти реализуют различные алгоритмы выделения памяти и пытаются снизить затраты на работу с динамической памятью.
Альтернативные менеджеры памяти:
Smartheap
dlmalloc
Одним из важных факторов производительности в C++ является компактность размещения в памяти совместно используемых объектов, объединенных в различные связные списки. Связный список менее эффективен чем линейный массив по следующим причинам:
Каждый объект создаётся отдельно. Выделение и освобождение объекта имеет свою цену.
Объекты в памяти хранятся не последовательно. При обходе связного списка вероятность попадания в кэш снижается. Процессорная предвыборка данных неэффективна.
Необходима дополнительная память для хранения ссылок и информации о выделенных блоках памяти.

В случае работы с массивами непрерывный массив также выгоднее чем массив указателей по причине лучшей работы системы памяти.

физической памяти:

P1

P2

P3

P4

VecP;
int main() {
int i,k;
VecP a[N],b[N];
VecR *tmp,*tmp1;
#ifndef PERF
for(i=0;i a[i]=(VecP)malloc(sizeof(VecR));
b[i]=(VecP)malloc(sizeof(VecR));
}
#else
tmp=(VecR*)malloc(sizeof(VecR)*N);
tmp1=(VecR*)malloc(sizeof(VecR)*N);
for(i=0;i a[i]=(VecP)&tmp[i];
b[i]=(VecP)&tmp1[i];
}
#endif

for (i=0;i a[i]->x = 1.0; b[i]->x = 2.0;
a[i]->y = 2.0; b[i]->y = 3.0;
a[i]->z = 0.0; b[i]->z = 4.0;
}

for(k=1;k for (i=k;i a[i]->x = b[i+10]->y+1.0;
a[i]->y = b[i+10]->x+a[i+1]->y;
a[i]->z = (a[i-1]->y - a[i-1]->x)/b[i+10]->y;
}
}
printf("%d \n",a[100]->z);
}

icc struct.c -fast -o a.out
icc struct.c -fast -DPERF -o b.out
time ./a.out real 0m0.998s
time ./b.out real 0m0.782s

контейнеров.
Создание и использование контейнеров это один из примеров эффективного использования шаблонов (template) в С++. Наиболее распространенный набор контейнеров предоставляется Standard Template Library (STL), которая поставляется с современными C++ компиляторами.
Однако STL в основном разрабатывалась для гибкости использования и вопросы производительности имели более низкий приоритет. Поэтому выделение памяти для хранения объектов осуществляется пошагово по мере роста количества объектов, которые необходимо хранить в памяти. Отсутствует гибкая система, позволяющая заранее определять сколько памяти необходимо выделить изначально. В случае расширения контейнера может возникнуть необходимость копирования содержания контейнера. Это копирование происходит с использованием конструкторов копирования.
Еще один популярный метод – это метод пулов памяти. Одно из его отличий состоит в том, что при расширении пула весь блок памяти копируется с помощью memcpy.

Obj с ВП

IP/IPO оптимизации

Скалярные оптимизации

HPO

Генератор кода

Исполняемый файл
Библиотека

Архитектура компилятора

синтаксически корректную программу в последовательность инструкций, которые могут выполнятся на машине. При этом могут применятся различные, в первую очередь машинно-зависимые оптимизации. Часто кодогенератор является общей частью для множества компиляторов, каждый из которых генерирует промежуточный код, подаваемый на вход кодогенератору.
Конвертация утверждений и выражений внутреннего представления в инструкции процессора данной архитектуры.
Специфические архитектурные оптимизации.
Удаление ветвления с помощью условных присваиваний.
Подставляет тела простейших встроенных функций.
Выравнивает базовые блоки в памяти.
Подготовка вызовов процедур, т.е. загрузка необходимых переменных в регистры и/или на стек для передачи в вызываемую процедуру.
То же самое для вызываемой процедуры. Выделение места на стеке для локальных переменных. Сохранение и восстановление используемых внутри процедуры регистров.
Планирование инструкций.
Планирование переходов.
Учет задержки обращения к памяти.
Распределение регистров.
Вычисление дистанций для переходов.

уровня инструкционного параллелизма. Оптимизация обычно осуществляться за счет изменения порядка инструкций для уменьшения задержек процессорного конвейера.
Процессор имеет собственный механизм для планирования инструкций и распределения их по исполняющим устройствам. Этот механизм предусматривает упреждающий просмотр поступающих инструкций. Но он может быть недостаточно эффективен поскольку «окно упреждающего просмотра» ограничено. Инструкции могут переставляться в соответствии со следующими соображениями:
вынос чтения из памяти как можно дальше от использования результатов чтения.
смешение инструкций использующих разные исполняемые устройства процессора.
сближение инструкций использующих одну и ту же переменную, для упрощения выделения регистров.
Планирование инструкций может производиться внутри одного базового блока или внутри суперблока, объединения нескольких базовых блоков. Некоторые инструкции могут передвигаться за границы соответствующих им базовых блоков.
Планирование инструкций может осуществляться как до, так и после распределения регистров.