Разработка сред управляемого исполнения на примере виртуальной машины Java Занятие 7 Салищев С.И.

Оптимизирующий JIT Компилятор Достоинства и недостатки Особенности систем управляемого исполнения Общая структура оптимизирующего компилятора Отличия JIT компилятора Наиболее важные оптимизации Оптимизации управляемые динамическим профилированием Динамическое профилирование

Достоинства и недостатки По сравнению с интерпретатором и шаблонным JIT компилятором Достоинства Достоинства Ускорение выполнения кода в 4 и более раз Производительность кода сопоставимая с компилируемыми языками (C, C++, Fortran, Ada) Недостатки Недостатки Затраты ресурсов на компиляцию Увеличение времени старта Затруднение отладки пользовательского кода Высокая вероятность ошибки и нарушения семантики пользовательского кода

Особенности систем управляемого исполнения Инкапсуляция Вызов методов для доступа к данным Вызов методов для доступа к даннымНаследование Цепочки вызовов Цепочки вызововПолиморфизм Косвенные вызовы Косвенные вызовы Неопределенное время жизни объектов Выделение всех объектов в куче Выделение всех объектов в куче

Особенности систем управляемого исполнения 2 Промежуточный код (Byte Code) Сокрытие семантики исходного кода Сокрытие семантики исходного кода Ленивая загрузка классов Неполный граф вызовов во время компиляции Неполный граф вызовов во время компиляции JIT Компилятор является частью среды Возможность перекомпиляции при загрузке новых классов и изменении характера нагрузки Возможность перекомпиляции при загрузке новых классов и изменении характера нагрузки Не требуется спекулятивная оптимизация Не требуется спекулятивная оптимизация Компиляция происходит параллельно с выполнением Требуется учитывать время компиляции Требуется учитывать время компиляции За раз компилируется небольшой блок кода За раз компилируется небольшой блок кода

Температура кода Мертвый код Не исполняется никогда Не исполняется никогда Холодный код Исполняется редко, не оказывает влияния на скорость работы системы Исполняется редко, не оказывает влияния на скорость работы системы Теплый код Исполняется регулярно, влияет на скорость работы системы Исполняется регулярно, влияет на скорость работы системы Горячий код Оказывает доминирующее влияние на скорость работы системы Оказывает доминирующее влияние на скорость работы системы

Модель динамической перекомпиляции Загрузка кода Шаблонная компиляцияИнтерпретация Byte Code Executable Code Исполнение Оптимизирующая компиляция Executable Code Исполнение Освобождение памяти Холодный код Теплый код Горячий код Мертвый код

Back End Compiler Core Front End Структура оптимизирующего компилятора Lexer Source code Control Flow Analysis High Level Optimizations HIR LIR Profiler Data Executable Code Parser Data Flow Analysis Code Generation Low Level Optimizations

Структура оптимизирующего компилятора: комментарий Front End (Транслятор) Зависит от языка программирования высокого уровня Зависит от языка программирования высокого уровня Возможно множество трансляторов для различных языков Возможно множество трансляторов для различных языков Compiler Core (Ядро, оптимизатор) Универсален для широкого класса языков и аппаратных архитектур Универсален для широкого класса языков и аппаратных архитектур Наиболее сложен для реализации Наиболее сложен для реализации Составляет основную ценность в структуре компилятора Составляет основную ценность в структуре компилятора Требует высокой гибкости взаимодействия с трансляторами и генераторами кода Требует высокой гибкости взаимодействия с трансляторами и генераторами кода Back End (Генератор Кода) Зависит от аппаратной платформы Зависит от аппаратной платформы Возможно множество генераторов кода для различных платформ Возможно множество генераторов кода для различных платформ Требует тонкой подстройки под конкретную платформу Требует тонкой подстройки под конкретную платформу

Свойства промежуточного представления высокого уровня Сохранение семантики исходного кода Контексты блоков и функций Контексты блоков и функций Типы данных Типы данных Общие подвыражения Общие подвыражения Циклы в явном виде Циклы в явном виде Сохранение метаданных Упрощение оптимизации Наилучший известный HIR - Граф управления (control flow graph) Узлы – блоки, участки кода без переходов Узлы – блоки, участки кода без переходов Дуги – переходы между блоками Дуги – переходы между блоками Возможно параллельное исполнение блоков Возможно параллельное исполнение блоков Хранение дополнительных данных в узлах и дугах Хранение дополнительных данных в узлах и дугах Для описания блоков используется LIR Для описания блоков используется LIR

Анализ потока управления/данных Объединение графов управления отдельных функций Построение SSA Form SSA Form (Single Static Assignment) – каждая переменная присваивается ровно один раз SSA Form (Single Static Assignment) – каждая переменная присваивается ровно один раз Выполнение Escape analysis Escape analysis – нахождение максимального замкнутого подграфа управления содержащего все доступы к значению Escape analysis – нахождение максимального замкнутого подграфа управления содержащего все доступы к значению

Высокоуровневые оптимизации Продвижение констант Арифметические упрощения Удаление общих подвыражений Удаление мертвого кода СкаляризацияДевиртуализация Специализация и клонирование функций Подстановка функций Векторизация циклов Удаление хвостовой рекурсии Вынесение инвариантного кода из циклов Распараллеливание блоков

Свойства промежуточного представления низкого уровня Абстракция системы команд процессора Гибкое представление инструкций процессора Гибкое представление инструкций процессора Расширяемость Расширяемость Удобство оптимизации Сохранение информации высокого уровня Стандартный способ – трехадресный код трехадресный код, квад (quad, three address code (TAC)) – каждая инструкция имеет вид x:=у op z трехадресный код, квад (quad, three address code (TAC)) – каждая инструкция имеет вид x:=у op z Таким образом инструкция – четверка (op, arg0, arg1, result) Таким образом инструкция – четверка (op, arg0, arg1, result) Не все инструкции задействуют все поля, например (goto, label, -, -) Не все инструкции задействуют все поля, например (goto, label, -, -) Дополнительные данные хранятся в метках Дополнительные данные хранятся в метках

Низкоуровневые оптимизации Замена цепочек суперинструкциями Конвейеризация Оптимальное назначение регистров (Register Allocation) Переупорядочивание блоков Предвыборка данных и кода Применение векторных инструкций Развертывание циклов (Loop unrolling) Оптимизация прологов и эпилогов функций

Front End Структура оптимизирующего JIT компилятора Byte Code Byte Code Translator / Idiom recognizer HIR Compiler Core LIR Back End IR Cache Profiler Data Executable Code Scheduler Profiler

Отличия от обычного оптимизирующего компилятора Распознавание Идиом Восстановление семантики исходного кода по промежуточному коду (Byte Code) Восстановление семантики исходного кода по промежуточному коду (Byte Code) Требуется для корректного построения HIR Требуется для корректного построения HIR Обычно является зависимым от компилятора языка (javac) Обычно является зависимым от компилятора языка (javac) Плохо совместим с оптимизацией промежуточного кода Плохо совместим с оптимизацией промежуточного кода Кэширование промежуточного представления Сохранение результатов предыдущих проходов Сохранение результатов предыдущих проходов Оптимизация времени компиляции Оптимизация времени компиляции Прямое взаимодействие с профилировщиком Инструментация рабочего кода Инструментация рабочего кода Более частое обновление данных профилирования Более частое обновление данных профилирования Большее значение профилирования при выборе оптимизаций Большее значение профилирования при выборе оптимизаций Учет не только выигрыша производительности, но и времени оптимизации Использование инкрементальных алгоритмов Использование инкрементальных алгоритмов

Наиболее важные оптимизации Скаляризация (scalarizing) Разложение массивов и объектов на локальные переменные Разложение массивов и объектов на локальные переменные Уменьшает затраты на выделение памяти и сборку мусора Уменьшает затраты на выделение памяти и сборку мусора Улучшает локальность данных Улучшает локальность данных Девиртуализация (devirtualization) Замена виртуального вызова на прямой вызов Замена виртуального вызова на прямой вызов Уменьшает затраты на косвенные вызовы Уменьшает затраты на косвенные вызовы Необходима для подстановки Необходима для подстановки Специализация и клонирование методов (specialization and cloning) Разделение методов по типам параметров Разделение методов по типам параметров Требуется для межпроцедурной оптимизации Требуется для межпроцедурной оптимизации Подстановка (inlining) Подстановка тела метода вместо вызова Подстановка тела метода вместо вызова Подстановка констант Подстановка констант Уменьшение затрат на вызовы Уменьшение затрат на вызовы Улучшает локальность кода и данных Улучшает локальность кода и данных

Оптимизации управляемые профилированием Защищенные оптимизации Перед исполнением оптимизированного кода проверяется условие оптимизации Перед исполнением оптимизированного кода проверяется условие оптимизации Например тип параметров или размер массива Например тип параметров или размер массива В случае невыполнения условия выполняется неоптимизированный код В случае невыполнения условия выполняется неоптимизированный код Основные типы защищенная скаляризация защищенная скаляризация Защищенная девиртуализация Защищенная девиртуализация Защищенная специализация Защищенная специализация Защищенная подстановка Защищенная подстановка

Профилирование Определение временных метрик кода Время исполнения блока кода Время исполнения блока кода Количество попаданий в контрольную точку Количество попаданий в контрольную точку Вероятность попадания в контрольную точку Вероятность попадания в контрольную точку Вероятность нахождения контрольной точки на стеке вызовов Вероятность нахождения контрольной точки на стеке вызовов Вероятность последовательности верхних элементов стека вызовов в момент попадания в контрольную точку Вероятность последовательности верхних элементов стека вызовов в момент попадания в контрольную точку Вероятность значений и типов параметров при нахождении контрольной точки на стеке вызовов Вероятность значений и типов параметров при нахождении контрольной точки на стеке вызовов Методы профилирования Инструментация Инструментация Семплирование Семплирование

Инструментация Модификация кода для изменения счетчиков Является точным методом Уменьшает производительность пользовательского кода Используется в неоптимизированном коде для быстрой реакции на разогрев кода Инструментальный код часто вставляется в безопасные точки (GC Safe Point) Обычно запрос на перекомпиляцию является частью инструментального кода

Семплирование Остановка пользовательского кода в случайные моменты времени и анализ стека вызовов Почти не влияет на производительность пользовательского кода Является вероятностным методом, имеет сравнительно низкую чувствительность Для определения момента остановки может использоваться таймер или отладочное событие (переполнение счетчика инструкций, промахов кэша) Для остановки часто используются безопасные точки Используется для обнаружения горячего кода

Замена кода Ленивая замена кода Новый код исполняется при следующем вызове Новый код исполняется при следующем вызове Требует сохранения предыдущей версии кода если она исполняется в момент завершения компиляции Требует сохранения предыдущей версии кода если она исполняется в момент завершения компиляции Требуется отслеживать ссылки на старую версию кода для освобождения памяти Требуется отслеживать ссылки на старую версию кода для освобождения памяти В случае глубокой подстановки может привести к существенным потерям производительности из-за невозможности заменить долго исполняемый код В случае глубокой подстановки может привести к существенным потерям производительности из-за невозможности заменить долго исполняемый код Замена кода на стеке Версия кода заменяется в момент завершения компиляции Версия кода заменяется в момент завершения компиляции Требует трансформации параметров на стеке в соответствие с новой версией кода Требует трансформации параметров на стеке в соответствие с новой версией кода Сложность реализации Сложность реализации