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

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_gen
2.) запустить инструментированное приложение с представительным набором данных, т.е. одним или несколькими наборами наиболее часто используемых данных. Информация добавляется в файл со статистиками.
3.) пересобрать приложение с опцией /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

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

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

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

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

множества переменных программы на множество регистров микропроцессора. Распределение регистров может выполняться в отдельно взятом базовом блоке (локальное распределение регистров) или во всей процедуре (глобальное распределение регистров).
Обычно количество переменных в программе значительно превосходит количество доступных физических регистров, поэтому некоторые переменные приходится откачивать в память. Стоимость откачки в память можно минимизировать, откачивая наименее часто используемые переменные, однако определить, какие переменные используются наименее часто, не всегда легко. Потеря производительности в связи с постоянным обменом между регистрами и памятью называется «вытеснением регистров» (register spilling).
Для распределения регистров используется метод расскрасски графа несовместимости (register coloring).

(програмный регион в котором переменная используется) и каждой присваивается уникальное имя.
2.) Строиться граф несовместимости (interference graph).Каждой переменной соответсвует вершина, если области жизни переменных пересекаются, то соответствующие им вершины соединяются дугой. Нужно расскрасить вершины графа различными цветами, их количество равно количеству свободных регистров, так чтобы вершины, соединенные дугами имели разные цвета.
3.) Если не удается расскрасить граф (существует вершина с количеством дуг больше кол-ва регистров), то одна из вершин распадается на две, (т.е. делается сохранение в память) и делается новая попытка. Попытки продолжаются, пока не удастся расскрасить граф.
Интуитивно понятно, что наибольший успех при распределении регистров будет достигнут если в регистрах храняться наиболее часто используемые данные. Т.е. информация собираемая профилировщиками крайне необходима и в этом случае.

того, чтобы доказать правомерность перестановочных оптимизаций. При кодогенерации возникает другой вариант использования зависимостей – для определения возможностей переиспользования данных при вычислениях. Это позволяет избежать ненужных загрузок из памяти и сохранения в память.
DO I = 1,N
A(I+1) = A(I) +F(…)
END DO
Имеет смысл t <-> A(I+1) c тем, чтобы при следующей итерации не загружать A(I) из памяти.

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

(control flow dependence) заменяется на зависимость по данным. Ветвление исчезает и это ускоряет работу с плохо прогнозируемыми переходами.
#include
int main() {
int volatile t1,t2,t3;
int i,j,aa;
int a[1000];
t1=t2=t3=0;
aa=0;

for(i=1;i<100000;i++) {
for(j=1;j<1000;j++){
if(t1|t2|t3)
aa=2;
else
aa=0;
a[j]=a[j]+aa;
t3=j%2;
}
}
printf("%d\n",a[50]);
}

time ./a.out 0m0.379s
icc test.c -O2 -o b.out time ./b.out 0m0.441s
Ассемблер для первого случая:
..B1.3: # Preds ..B1.9 ..B1.2
movl 4008(%esp), %ebx #12.7
orl 4004(%esp), %ebx #12.10
movl $2, %edx #15.6
orl 4000(%esp), %ebx #12.13
movl $0, %ebx #15.6
cmovne %edx, %ebx #15.6
addl %ebx, (%esp,%eax,4) #16.14
movl %eax, %edx #17.9
andl $-2147483647, %edx #17.9
jge ..B1.9 # Prob 50% #17.9
# LOE eax edx ecx esi edi
..B1.10: # Preds ..B1.3
subl $1, %edx #17.9
orl $-2, %edx #17.9
addl $1, %edx #17.9
# LOE eax edx ecx esi edi
..B1.9: # Preds ..B1.3 ..B1.10
movl %edx, 4000(%esp) #17.4
addl $1, %eax #11.17
cmpl $1000, %eax #11.12
jl ..B1.3

# Preds ..B1.9 ..B1.2
movl 4008(%esp), %ecx #12.7
orl 4004(%esp), %ecx #12.10
orl 4000(%esp), %ecx #12.13
movl $2, %ecx #15.6
jne ..L1 # Prob 50% #15.6
movl $0, %ecx #15.6
..L1: #
addl %ecx, (%esp,%edx,4) #16.14
movl %edx, %ecx #17.9
andl $-2147483647, %ecx #17.9
jge ..B1.9 # Prob 50% #17.9
# LOE eax edx ecx ebx esi edi
..B1.10: # Preds ..B1.3
subl $1, %ecx #17.9
orl $-2, %ecx #17.9
addl $1, %ecx #17.9
# LOE eax edx ecx ebx esi edi
..B1.9: # Preds ..B1.3 ..B1.10
movl %ecx, 4000(%esp) #17.4
addl $1, %edx #11.17
cmpl $1000, %edx #11.12
jl ..B1.3