Глобальные и локальные оптимизации Ануфриенко Андрей Идрисов Ренат

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

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

Протяжка константы через неизвестную функцию Рассмотрим простую программу: test.c: extern void unknown(int *a); int main(){ int 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 утверждение в результирующем коде?

Ассемблер полученный с помощью icl: icс –O2 test.c –S … call _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 … Вывод: В общем случае, когда о вызываемой функции ничего не известно, константа присвоенная переменной не протягивается через функцию, которая может изменить значение этой переменной.

CSE (Удаление общих подвыражений) #include extern void unknown(); float a,b; int main() { 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 работать с этим подвыражением?

icl cse.c –S ….B1.3:: ; 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) Одной из основных задач межпроцедурного анализа является построения графа вызовов и выяснения свойств функций на основе его анализа. (Например, глобальный анализ потоков данных требует знания о том, какие данные каждая функция модифицирует). Граф вызовов может быть полным и неполным. Если при сборе проекта используются библиотеки, свойства функций которых мы не знаем, то граф будет являться неполным и полноценный анализ не будет осуществлен.

FE (C++/C или Fortran) Внутреннее представление Профилировщик Скалярные оптимизации HPO Генератор кода Исходные файлы Обьектные файлы Временный файл или Obj с ВП IP/IPO оптимизации Скалярные оптимизации HPOГенератор кода Исполняемый файл Библиотека Архитектура компилятора

Два вида межпроцедурных оптимизаций: модульная оптимизация для всей программы Qip[-] 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

Изменится ли что-либо, если мы определим некую процедуру unknown и перекомпилируем с –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 Работают ли протяжка констант и удаление общих подвыражений?

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

Пример на LPT анализ #include int p1=1,p2=2; int *a,*b; void init(int **a, int **b) { *a=&p1; *b=&p1; //

Межпроцедурный анализ используется для протяжки атрибутов функций. Например, есть атрибуты 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 … Таким образом, протянув константу удалось избавиться от ветвления.

Подстановка (inlining) Подстановка удаляет накладные расходы связанные с подготовкой к вызову функции, удаляет переходы, которые могут быть источниками неэффективной работы памяти, позволяет эффективнее применять скалярные и оптимизации циклов. Недостаток оптимизации – увеличение размера приложения. Как следствие – увеличение времени компиляции и необходимых для компиляции ресурсов. Эвристики для подстановок пытаются выбрать наиболее выгодные для подстановки функции с тем, чтобы получить максимальный эффект для производительности, не выходя за пределы допустимого увеличения кода. Атрибут функции inline inline int exforsys(int x1) { return 5*x1; } Программист «рекомендует» компилятору сделать подстановку такой функции.

Управление подстановкой Синтаксис: #pragma inline[recursive] #pragma forceinline[recursive] #pragma noinline Аргумент Recursive требует чтобы данная директива применялась ко всем вызовам, которые осуществляются данным вызовом. Директива inline рекомендует инлайнить noinline требует не инлайнить forceinline требует инлайнить Аналоги для языка Фортран cDEC$ ATTRIBUTES INLINE :: procedure cDEC$ ATTRIBUTES NOINLINE :: procedure cDEC$ ATTRIBUTES FORCEINLINE :: procedure 10/17/10

Компиляторные опции подстановки /Ob control inline expansion: 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

10/17/10 /Qinline-max-per-routine: maximum number of inline instances 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()

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

Девиртуализация для C++ Вызов функций через указатели дороже простого вызова. C++ - объектно-ориентированный язык поддерживающий высокий уровень абстракции. Возможность выполнения методов функции в зависимости от типа объекта времени выполнения. A => B => C Все наследуемые классы переопределяют virtual int foo() int process(class A *a) { return(a->foo()); }

FE (C++/C или Fortran) Внутреннее представление Профилировщик Скалярные оптимизации HPO Генератор кода Исходные файлы Обьектные файлы Временный файл или Obj с ВП IP/IPO оптимизации Скалярные оптимизации HPOГенератор кода Исполняемый файл Библиотека Архитектура компилятора

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

выгодно комбинировать вместе «часто» совместно используемые элементы структуры невыгодно тратить время на оптимизацию редко используемых фрагментов кода. Статистический профилировщик вычисляет вероятность условных переходов и вес базовых блоков. Это делается на основе анализа исходного кода. Межпроцедурный анализ пытается рассчитать вес процедур на основе анализа графа вызовов. Анализ исходного кода не может обеспечить точное вычисление весовых характеристик. В общем случае, не известны входные данные исполняемой программы, время вычисления ограничено. Существует встроенная функция 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

Последовательность действий при использовании динамического профилировщика: 1.построить приложение с инструментацией /Qprof_gen 2.запустить инструментированное приложение с представительным набором данных, т.е. одним или несколькими наборами наиболее часто используемых данных. Информация добавляется в файл со статистиками. 3.пересобрать приложение с опцией /Qprof_use для использование собранных статистик при компиляции. 10/17/10

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

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

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

Связные списки в памяти 10/17/10 Связный список: Может располагаться в памяти так: 4GB 2GB 0GB И в физической памяти: P1P2 P3P4

#include #define N typedef struct { int x,y,z; } VecR; typedef VecR* VecP; int main() { int i,k; VecP a[N],b[N]; VecR *tmp,*tmp1; #ifndef PERF for(i=0;iy = 2.0; b[i]->y = 3.0; a[i]->z = 0.0; b[i]->z = 4.0; } for(k=1;ky+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.

FE (C++/C или Fortran) Внутреннее представление Профилировщик Скалярные оптимизации HPO Генератор кода Исходные файлы Обьектные файлы Временный файл или Obj с ВП IP/IPO оптимизации Скалярные оптимизации HPOГенератор кода Исполняемый файл Библиотека Архитектура компилятора

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

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

Спасибо за внимание!