Отслеживание своевременной компиляции - это метод, используемый виртуальными машинами для оптимизации выполнения программы во время выполнения . Это делается путем записи линейной последовательности часто выполняемых операций, компиляции их в собственный машинный код и их выполнения. Это отличие от традиционных точно в срок (JIT) компиляторов, работа на основе каждого метода.
Обзор
Своевременная компиляция - это метод увеличения скорости выполнения программ путем компиляции частей программы в машинный код во время выполнения. Один из способов классифицировать разные JIT-компиляторы - по их объему компиляции. В то время как JIT-компиляторы, основанные на методах, транслируют один метод за раз в машинный код, JIT-компиляторы трассировки используют часто выполняемые циклы в качестве единицы компиляции. Трассировка JIT основана на предположении, что программы проводят большую часть своего времени в некоторых циклах программы («горячие циклы»), и последующие итерации цикла часто проходят по аналогичным путям. Виртуальные машины с JIT трассировки часто являются средами выполнения в смешанном режиме, что означает, что они имеют либо интерпретатор, либо компилятор методов в дополнение к JIT трассировки.
Технические подробности
JIT-компилятор трассировки проходит различные фазы во время выполнения. Сначала собирается информация о профилировании петель. После определения «горячего» цикла начинается специальная фаза трассировки , на которой записываются все выполненные операции этого цикла. Эта последовательность операций называется трассировкой. Затем трассировка оптимизируется и компилируется в машинный код (трассировка). Когда этот цикл выполняется снова, вместо аналога программы вызывается скомпилированная трассировка.
Эти шаги подробно описаны ниже:
Фаза профилирования
Цель профилирования - выявить горячие петли. Часто это делается путем подсчета количества итераций для каждого цикла. После того, как счетчик цикла превышает определенный порог, цикл считается горячим, и начинается фаза трассировки.
Фаза отслеживания
На этапе трассировки выполнение цикла происходит нормально, но, кроме того, каждая выполненная операция записывается в трассировку. Записанные операции обычно хранятся в дереве трассировки , часто в промежуточном представлении (IR). Трассировка следует за вызовами функций, что приводит к их встраиванию в трассировку. Трассировка продолжается, пока цикл не достигнет своего конца и не вернется к началу.
Поскольку трассировка записывается по одному конкретному пути выполнения цикла, последующие выполнения этой трассировки могут отличаться от этого пути. Чтобы определить места, где это может произойти, в след вставляются специальные инструкции по охране . Одним из примеров такого места являются операторы if. Guard - это быстрая проверка, чтобы определить, выполняется ли исходное условие. В случае отказа защиты выполнение трассировки прерывается.
Поскольку трассировка выполняется во время выполнения, трассировка может содержать информацию времени выполнения (например, информацию о типе ). Эта информация может позже использоваться на этапе оптимизации для повышения эффективности кода.
Этап оптимизации и генерации кода
Трассы легко оптимизировать, поскольку они представляют только один путь выполнения, а это означает, что поток управления не существует и не требует обработки. Типичные оптимизации включают в себя устранение постоянная подвыражения , устранение мертвого кода , распределение регистров , движение инвариантно-код , постоянное складывание и анализ побега . [1]
После оптимизации трасса превращается в машинный код. Как и в случае с оптимизацией, это легко сделать из-за линейного характера трассировок.
Исполнение
После компиляции трассировки в машинный код ее можно выполнять в последующих итерациях цикла. Выполнение трассировки продолжается до тех пор, пока охранник не выйдет из строя.
История
В то время как идея JIT восходит к 1960-м годам, отслеживание JIT стало чаще использоваться только в последнее время. Первое упоминание об идее, аналогичной сегодняшней идее отслеживания JIT, было в 1970 году. [2] Было замечено, что скомпилированный код может быть получен из интерпретатора во время выполнения, просто сохраняя действия, выполняемые во время интерпретации.
Первой реализацией трассировки является Dynamo, «программная система динамической оптимизации, которая способна прозрачно улучшать производительность собственного потока инструкций, когда он выполняется на процессоре». [3] Для этого собственный поток команд интерпретируется до тех пор, пока не будет найдена «горячая» последовательность команд. Для этой последовательности создается, кэшируется и выполняется оптимизированная версия.
Позже Dynamo было расширено до DynamoRIO . Один из проектов на основе DynamoRIO представлял собой основу для построения интерпретатора, сочетающего трассировку и частичную оценку. Он использовался для «динамического удаления накладных расходов интерпретатора из языковых реализаций». [4]
В 2006 году был разработан HotpathVM, первый JIT-компилятор трассировки для языка высокого уровня [ необходима ссылка ] . [5] Эта виртуальная машина была способна динамически идентифицировать часто выполняемые инструкции байт-кода, которые отслеживаются и затем компилируются в машинный код с использованием конструкции статического одиночного присваивания (SSA). Мотивация для HotpathVM заключалась в том, чтобы иметь эффективную JVM для мобильных устройств с ограниченными ресурсами.
Другой пример JIT-трассировки - TraceMonkey , одна из реализаций JavaScript в Mozilla для Firefox (2009 г.). [6] TraceMonkey компилирует часто выполняемые трассировки циклов на динамическом языке JavaScript во время выполнения и специализирует сгенерированный код для реальных динамических типов, встречающихся на каждом пути.
Другой проект, использующий трассировку JIT, - PyPy . Он позволяет использовать JIT для отслеживания языковых реализаций, которые были написаны с помощью цепочки инструментов перевода PyPy, тем самым улучшая производительность любой программы, выполняемой с использованием этого интерпретатора. Это возможно путем отслеживания самого интерпретатора, а не программы, выполняемой интерпретатором. [7]
Трассировка JIT также была исследована Microsoft в проекте SPUR для их Common Intermediate Language (CIL). SPUR - это общий трассировщик для CIL, который также можно использовать для трассировки с помощью реализации JavaScript. [8]
Пример следа
Рассмотрим следующую программу Python, которая вычисляет сумму квадратов последовательных целых чисел, пока эта сумма не превысит 100000:
def square ( x ): вернуть x * xi = 0 y = 0, в то время как True : y + = square ( i ), если y > 100000 : break i = i + 1
След для этой программы может выглядеть примерно так:
loopstart ( i1 , y1 ) i2 = int_mul ( i1 , i1 ) # x * x y2 = int_add ( y1 , i2 ) # y + = i * i b1 = int_gt ( y2 , 100000 ) guard_false ( b1 ) i3 = int_add ( i1 , 1 ) # i = i + 1 скачок ( i3 , y2 )
Обратите внимание, как вызов функции square
встроен в трассировку и как оператор if превращается в guard_false
.
Смотрите также
Рекомендации
- ^ Больц, Карл Фридрих; Куни, Антонио; FijaBkowski, Maciej; Леушель, Майкл; Педрони, Самуэле; Риго, Армин (январь 2011 г.). «Удаление распределения путем частичной оценки в JIT отслеживания» (PDF) . Материалы 20-го семинара ACM SIGPLAN по частичной оценке и манипулированию программами . ПЭПМ '11. С. 43–52. DOI : 10.1145 / 1929501.1929508 . S2CID 15871223 . Проверено 13 декабря 2020 .
- ^ Митчелл, Джеймс Г. (29 июня 1970 г.). Разработка и построение гибких и эффективных систем интерактивного программирования (PhD). Университет Карнеги-Меллона . ISBN 978-0-8240-4414-5. LCCN 79050563 . OCLC 633313022 . S2CID 36249021 . Досье AAI7104538 . Проверено 13 декабря 2020 .
- ^ Бала, Васант; Дюстервальд, Эвелин; Банерджиа, Санджив (май 2000 г.). «Динамо: прозрачная система динамической оптимизации» (PDF) . Материалы конференции ACM SIGPLAN 2000 по проектированию и реализации языков программирования . PLDI '00. С. 1–12. DOI : 10.1145 / 349299.349303 . ISBN 978-1-58113-199-4. S2CID 53223267 . Проверено 13 декабря 2020 .
- ^ Салливан, Грегори Т .; Брюнинг, Дерек Л .; Барон, Ирис; Гарнетт, Тимоти; Амарасингхе, Саман (июнь 2003 г.). «Динамическая оптимизация собственных средств интерпретатора» (PDF) . Труды семинара 2003 г. по интерпретаторам, виртуальным машинам и эмуляторам . IVME '03. С. 50–57. CiteSeerX 10.1.1.14.9819 . DOI : 10.1145 / 858570.858576 . ISBN 978-1-58113-655-5. S2CID 509405 . Проверено 13 декабря 2020 .
- ^ Галь, Андреас ; Probst, Christian W .; Франц, Майкл (июнь 2006 г.). «HotpathVM: эффективный JIT-компилятор для устройств с ограниченными ресурсами» (PDF) . Труды 2-й международной конференции по виртуальным средам исполнения . VEE '06. С. 144–153. DOI : 10.1145 / 1134760.1134780 . ISBN 978-1-59593-332-4. S2CID 17846788 . QID 56580114 . Проверено 13 декабря 2020 .
- ^ Галь, Андреас; Орендорф, Джейсон; Рудерман, Джесси; Смит, Эдвин В .; Рейтмайер, Рик; Бебенита, Майкл; Чанг, Мейсон; Франц, Майкл; Эйх, Брендан; Бритва, Майк; Андерсон, Дэвид; Манделин, Дэвид; Haghighat, Mohammad R .; Каплан, Блейк; Хоар, Грейдон; Збарский, Борис (июнь 2009 г.). «Своевременная специализация типов на основе трассировки для динамических языков» (PDF) . Труды 30-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . PLDI '09. С. 465–478. DOI : 10.1145 / 1542476.1542528 . ISBN 978-1-60558-392-1. S2CID 207172806 . Проверено 13 декабря 2020 .
- ^ Больц, Карл Фридрих; Куни, Антонио; Фиялковски, Мацей; Риго, Армин (июль 2009 г.). «Трассировка мета-уровня: JIT-компилятор трассировки PyPy» (PDF) . Материалы 4-го семинара по реализации, компиляции, оптимизации объектно-ориентированных языков и систем программирования . ICOOOLPS '09. С. 18–25. DOI : 10.1145 / 1565824.1565827 . ISBN 978-1-60558-541-3. S2CID 7478596 . Проверено 13 декабря 2020 .
- ^ Бебенита, Майкл; Бранднер, Флориан; Фандрих, Мануэль; Логоццо, Франческо; Шульте, Вольфрам; Тилльманн, Николай; Вентер, Герман (октябрь 2010 г.). «SPUR: JIT-компилятор на основе трассировки для CIL» (PDF) . Материалы международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования . ОПСЛА '10. С. 708–725. DOI : 10.1145 / 1869459.1869517 . ISBN 978-1-4503-0203-6. S2CID 3395746 . Проверено 13 декабря 2020 .
Внешние ссылки
- Официальный сайт LuaJIT