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

Анализ совмещений (alias analysis)

Важная часть механизма определения зависимостей.

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

Пример на LPT анализ

Можно ли осуществлять цикловые оптимизации с циклом for?

Межпроцедурный анализ используется для протяжки атрибутов функций. Например, есть атрибуты no_side_effect, always_return и т.д.

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

Продвижение данных (Data promotion). Каждая переменная имеет свою область видимости (scope). IPA позволяет протягивать данные, которые используются только в определенной процедуре, на уровень этой процедуры, что сразу позволяет включить их во многие оптимизации.

Функции, используемые только в одной программе получают атрибут static.

Удаление неиспользуемых глобальных переменных.

Удаление мертвого кода.

В данном случае, функция не будет включаться в исполняемый модуль, если она не входит в граф вызовов или все ее вызовы были подставлены (inline). (Вывод – для улучшения размеров кода и времени компиляции используйте атрибут static).

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

Межпроцедурные оптимизации

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

Протяжка константных аргументов

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

Протяжка возвращаемых значений

Если процедура всегда возвращает константное значение, то возможно протянуть это значение наружу.

То же самое касается передаваемых в процедуру аргументов. Если перед выходом из процедуры значение аргумента константа, то ее также можно протянуть наружу.

Пример. Константа протягивается в функцию через аргумент. Константа протягивается в вызывающую функцию.

Таким образом, протянув константу удалось избавиться от ветвления.

Подстановка (inlining)

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

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

Атрибут функции inline

inline int exforsys(int x1) {
  return 5*x1;
 }
    

Программист "рекомендует" компилятору сделать подстановку такой функции.

Управление подстановкой

Синтаксис:

#pragma inline[recursive]
#pragma forceinline[recursive]
#pragma noinline
    

Аргумент Recursive

Директива

Аналоги для языка Фортран

Компиляторные опции подстановки

/Ob<n>    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:<n>
          set size limit for inlining small routines
/Qinline-min-size-
          no size limit for inlining small routines
/Qinline-max-size:<n>
          set size limit for inlining large routines
/Qinline-max-size-
          no size limit for inlining large routines
/Qinline-max-total-size:<n>
          maximum increase in size for inline function expansion
/Qinline-max-total-size-
          no size limit for inline function expansion
    

/Qinline-max-per-routine:<n>
          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:<n>
          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:<n>
          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());
   }
    

Определение выгодности оптимизаций

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

   z=x*y;
   if(почти_никогда) {
      t=x*y;
   }
    

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

   for(i=0;i<n;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[:<arg>]
          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
    

Последовательность действий при использовании динамического профилировщика:

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

Некоторые оптимизации которые базируются на профилировочной информации:

Динамическое выделение памяти

Объекты и массивы могут инициализироваться динамически во время исполнения приложения с использованием операторов new и delete, malloc и free. Менеджер памяти, это часть приложения, обрабатывающая запросы на выделение и освобождение памяти.

Типичные ситуация, когда динамическое выделение памяти необходимо:

Неудобства динамического выделения памяти:

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

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

Альтернативные менеджеры памяти:

Одним из важных факторов производительности в C++ является компактность размещения в памяти совместно используемых объектов, объединенных в различные связные списки. Связный список менее эффективен чем линейный массив по следующим причинам:

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

Связные списки в памяти

Связный список:
Может располагаться в памяти так:
И в физической памяти:

Контейнеры

Существует популярный способ улучшения работы с динамически выделяемой памятью при помощи контейнеров.

Создание и использование контейнеров это один из примеров эффективного использования шаблонов (template) в С++. Наиболее распространенный набор контейнеров предоставляется Standard Template Library (STL), которая поставляется с современными C++ компиляторами.

Однако STL в основном разрабатывалась для гибкости использования и вопросы производительности имели более низкий приоритет. Поэтому выделение памяти для хранения объектов осуществляется пошагово по мере роста количества объектов, которые необходимо хранить в памяти. Отсутствует гибкая система, позволяющая заранее определять сколько памяти необходимо выделить изначально. В случае расширения контейнера может возникнуть необходимость копирования содержания контейнера. Это копирование происходит с использованием конструкторов копирования.

Еще один популярный метод – это метод пулов памяти. Одно из его отличий состоит в том, что при расширении пула весь блок памяти копируется с помощью memcpy.

Кодогенератор

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

Планирование инструкций (instruction scheduling)

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

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

Планирование инструкций может производиться внутри одного базового блока или внутри суперблока, объединения нескольких базовых блоков. Некоторые инструкции могут передвигаться за границы соответствующих им базовых блоков.

Планирование инструкций может осуществляться как до, так и после распределения регистров.