Отслеживание своевременной компиляции

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

Обзор

Компиляция «точно в срок» — это метод увеличения скорости выполнения программ путем компиляции частей программы в машинный код во время выполнения. Один из способов классифицировать различные JIT-компиляторы — это область их компиляции. В то время как JIT-компиляторы на основе методов транслируют один метод за раз в машинный код, JIT-компиляторы с трассировкой используют часто выполняемые циклы в качестве единицы компиляции. Отслеживание JIT основано на предположении, что программы проводят большую часть своего времени в некоторых циклах программы («горячие циклы»), и последующие итерации цикла часто проходят по схожим путям. Виртуальные машины , имеющие JIT-компилятор трассировки, часто представляют собой среды выполнения смешанного режима, что означает, что в дополнение к JIT-компилятору трассировки у них имеется либо интерпретатор, либо компилятор методов.

Технические детали

Трассирующий JIT-компилятор во время выполнения проходит различные этапы. Сначала профилировании собирается информация о циклов. После того, как «горячий» цикл был идентифицирован, вступает в специальную фазу отслеживания , которая записывает все выполненные операции этого цикла. Эта последовательность операций называется трассировкой. Затем трассировка оптимизируется и компилируется в машинный код. При повторном выполнении этого цикла вместо программного аналога вызывается скомпилированная трассировка.

Эти шаги подробно описаны ниже:

Этап профилирования

Целью профилирования является выявление «горячих петель». Часто это делается путем подсчета количества итераций для каждого цикла. После того, как счетчик цикла превысит определенный порог, цикл считается горячим и начинается фаза отслеживания.

Этап отслеживания

На этапе трассировки выполнение цикла происходит нормально, но, кроме того, каждая выполненная операция записывается в трассировку. Записанные операции обычно сохраняются в дереве трассировки , часто в промежуточном представлении (IR). Трассировка следует за вызовами функций, что приводит к их встраиванию в трассировку. Трассировка продолжается до тех пор, пока цикл не достигнет конца и не вернется к началу.

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

Поскольку трассировка выполняется во время выполнения, трассировка может содержать информацию времени выполнения (например, информацию о типе ). Эту информацию позже можно использовать на этапе оптимизации для повышения эффективности кода.

Фаза оптимизации и генерации кода

Трассировки легко оптимизировать, поскольку они представляют только один путь выполнения, а это означает, что поток управления не существует и не требует обработки. Типичные оптимизации включают в себя устранение константных подвыражений , устранение мертвого кода , выделение регистров , перемещение инвариантного кода , свертывание констант и escape-анализ . ^{[ 1 ]}

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

Исполнение

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

История

Хотя идея JIT возникла еще в 1960-х годах, JIT-отслеживание стало использоваться чаще только в последнее время. Первое упоминание об идее, похожей на сегодняшнюю идею отслеживания JIT, было в 1970 году. ^{[ 2 ]} Было замечено, что скомпилированный код можно получить из интерпретатора во время выполнения, просто сохраняя действия, выполняемые во время интерпретации.

Первой реализацией трассировки является Dynamo, «система динамической оптимизации программного обеспечения, способная прозрачно повышать производительность собственного потока команд при его выполнении на процессоре». ^{[ 3 ]} Для этого собственный поток команд интерпретируется до тех пор, пока не будет найдена «горячая» последовательность команд. Для этой последовательности генерируется, кэшируется и выполняется оптимизированная версия.

Позже «Динамо» было расширено до «ДинамоРИО» . Один проект на базе DynamoRIO представлял собой основу для создания интерпретатора, сочетающую в себе трассировку и частичную оценку. Он использовался для «динамического удаления накладных расходов интерпретатора из языковых реализаций». ^{[ 4 ]}

В 2006 году был выпущен HotpathVM, первый JIT-компилятор трассировки для языка высокого уровня. ^{[ нужна ссылка ]} был разработан. ^{[ 5 ]} Эта виртуальная машина была способна динамически идентифицировать часто выполняемые инструкции байт-кода, которые отслеживаются, а затем компилируются в машинный код с использованием статической конструкции с одним присваиванием (SSA). Мотивом создания HotpathVM было создание эффективной JVM для мобильных устройств с ограниченными ресурсами.

Другим примером JIT-трассировки является TraceMonkey , одна из Firefox реализаций JavaScript Mozilla для ( 2009). ^{[ 6 ]} TraceMonkey компилирует часто выполняемые трассировки циклов на динамическом языке JavaScript во время выполнения и специализирует сгенерированный код для фактических динамических типов, встречающихся на каждом пути.

Еще один проект, использующий JIT-отслеживание, — PyPy . Он позволяет использовать трассировку JIT для языковых реализаций, написанных с помощью цепочки инструментов перевода PyPy, тем самым повышая производительность любой программы, выполняемой с использованием этого интерпретатора. Это возможно путем отслеживания самого интерпретатора, а не программы, которую он выполняет. ^{[ 7 ]}

Отслеживание JIT также изучалось Microsoft в проекте SPUR для их общего промежуточного языка (CIL). SPUR — это универсальный трассировщик для CIL, который также можно использовать для трассировки реализации JavaScript. ^{[ 8 ]}

Пример трассировки

Рассмотрим следующую программу Python, которая вычисляет сумму квадратов последовательных целых чисел до тех пор, пока эта сумма не превысит 100 000:

def square(x):
    return x * x

i = 0
y = 0
while True:
    y += square(i)
    if y > 100000:
        break
    i = i + 1

Трассировка этой программы может выглядеть примерно так:

 loopstart(i1, y1)
 i2 = int_mul(i1, i1)		# i*i
 y2 = int_add(y1, i2)		# y += i*i
 b1 = int_gt(y2, 100000)
 guard_false(b1)
 i3 = int_add(i1, 1)		# i = i+1
 jump(i3, y2)

Обратите внимание, как вызов функции square встроен в трассировку и как оператор if превращается в guard_false.

См. также

Ссылки

^ Больц, Карл Фридрих; Куни, Антонио; ФияБковски, Мацей; Леушель, Майкл; Педрони, Самуэле; Риго, Армин (январь 2011 г.). «Удаление распределения путем частичной оценки в отслеживании JIT» (PDF) . Материалы 20-го семинара ACM SIGPLAN по частичной оценке и манипуляциям с программами . ПЭПМ '11. стр. 43–52. дои : 10.1145/1929501.1929508 . S2CID 15871223 . Проверено 13 декабря 2020 г.
^ Митчелл, Джеймс Г. (29 июня 1970 г.). Проектирование и построение гибких и эффективных систем интерактивного программирования (доктор философии). Университет Карнеги-Меллон . ISBN 978-0-8240-4414-5 . LCCN 79050563 . OCLC 633313022 . S2CID 36249021 . Квитанция AAI7104538 . Проверено 13 декабря 2020 г.
^ Бала, Васант; Дюстервальд, Эвелин; Банерджиа, Санджив (май 2000 г.). «Динамо: прозрачная система динамической оптимизации» (PDF) . Материалы конференции ACM SIGPLAN 2000 по проектированию и реализации языков программирования . ПЛДИ '00. стр. 1–12. дои : 10.1145/349299.349303 . ISBN 978-1-58113-199-4 . S2CID 53223267 . Проверено 13 декабря 2020 г.
^ Салливан, Грегори Т.; Брюнинг, Дерек Л.; Барон, Ирис; Гарнетт, Тимоти; Амарасингхе, Саман (июнь 2003 г.). «Динамическая собственная оптимизация интерпретаторов» (PDF) . Материалы семинара 2003 года «Интерпретаторы, виртуальные машины и эмуляторы» . ИВМЕ '03. стр. 50–57. CiteSeerX 10.1.1.14.9819 . дои : 10.1145/858570.858576 . ISBN 978-1-58113-655-5 . S2CID 509405 . Проверено 13 декабря 2020 г.
^ Галь, Андреас ; Пробст, Кристиан В.; Франц, Майкл (июнь 2006 г.). «HotpathVM: эффективный JIT-компилятор для устройств с ограниченными ресурсами» (PDF) . Материалы 2-й международной конференции «Виртуальные среды исполнения» . ВЭЭ '06. стр. 144–153. дои : 10.1145/1134760.1134780 . ISBN 978-1-59593-332-4 . S2CID 17846788 . ИДЕНТИФИКАТОР 56580114 . Проверено 13 декабря 2020 г.
^ Галь, Андреас; Орендорф, Джейсон; Рудерман, Джесси; Смит, Эдвин В.; Рейтмайер, Рик; Бебенита, Майкл; Чанг, Мейсон; Франц, Майкл; Эйх, Брендан; Шейвер, Майк; Андерсон, Дэвид; Манделин, Дэвид; Хагигат, Мохаммад Р.; Каплан, Блейк; Хоар, Грейдон; Збарский, Борис (июнь 2009 г.). «Специализация типов Just-in-Time на основе трассировки для динамических языков» (PDF) . Материалы 30-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . ПЛДИ '09. стр. 465–478. дои : 10.1145/1542476.1542528 . ISBN 978-1-60558-392-1 . S2CID 207172806 . Проверено 13 декабря 2020 г.
^ Больц, Карл Фридрих; Куни, Антонио; Фиялковски, Мацей; Риго, Армин (июль 2009 г.). «Отслеживание метауровня: трассирующий JIT-компилятор PyPy» (PDF) . Материалы 4-го семинара «Внедрение, компиляция, оптимизация объектно-ориентированных языков и систем программирования» . ICOOOLPS '09. стр. 18–25. дои : 10.1145/1565824.1565827 . ISBN 978-1-60558-541-3 . S2CID 7478596 . Проверено 13 декабря 2020 г.
^ Бебенита, Майкл; Бранднер, Флориан; Фандрих, Мануэль; Логоццо, Франческо; Шульте, Вольфрам; Тильманн, Николай; Вентер, Герман (октябрь 2010 г.). «SPUR: JIT-компилятор на основе трассировки для CIL» (PDF) . Материалы международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования . УПСЛА '10. стр. 708–725. дои : 10.1145/1869459.1869517 . ISBN 978-1-4503-0203-6 . S2CID 3395746 . Проверено 13 декабря 2020 г.

Внешние ссылки

Официальный сайт LuaJIT

[BolzCuni2011-1] Больц, Карл Фридрих; Куни, Антонио; ФияБковски, Мацей; Леушель, Майкл; Педрони, Самуэле; Риго, Армин (январь 2011 г.). «Удаление распределения путем частичной оценки в отслеживании JIT» (PDF) . Материалы 20-го семинара ACM SIGPLAN по частичной оценке и манипуляциям с программами . ПЭПМ '11. стр. 43–52. дои : 10.1145/1929501.1929508 . S2CID 15871223 . Проверено 13 декабря 2020 г.

[Mitchell1970-2] Митчелл, Джеймс Г. (29 июня 1970 г.). Проектирование и построение гибких и эффективных систем интерактивного программирования (доктор философии). Университет Карнеги-Меллон . ISBN 978-0-8240-4414-5 . LCCN 79050563 . OCLC 633313022 . S2CID 36249021 . Квитанция AAI7104538 . Проверено 13 декабря 2020 г.

[BalaDuesterwald2000-3] Бала, Васант; Дюстервальд, Эвелин; Банерджиа, Санджив (май 2000 г.). «Динамо: прозрачная система динамической оптимизации» (PDF) . Материалы конференции ACM SIGPLAN 2000 по проектированию и реализации языков программирования . ПЛДИ '00. стр. 1–12. дои : 10.1145/349299.349303 . ISBN 978-1-58113-199-4 . S2CID 53223267 . Проверено 13 декабря 2020 г.

[SullivanBruening2003-4] Салливан, Грегори Т.; Брюнинг, Дерек Л.; Барон, Ирис; Гарнетт, Тимоти; Амарасингхе, Саман (июнь 2003 г.). «Динамическая собственная оптимизация интерпретаторов» (PDF) . Материалы семинара 2003 года «Интерпретаторы, виртуальные машины и эмуляторы» . ИВМЕ '03. стр. 50–57. CiteSeerX 10.1.1.14.9819 . дои : 10.1145/858570.858576 . ISBN 978-1-58113-655-5 . S2CID 509405 . Проверено 13 декабря 2020 г.

[GalProbst2006-5] Галь, Андреас ; Пробст, Кристиан В.; Франц, Майкл (июнь 2006 г.). «HotpathVM: эффективный JIT-компилятор для устройств с ограниченными ресурсами» (PDF) . Материалы 2-й международной конференции «Виртуальные среды исполнения» . ВЭЭ '06. стр. 144–153. дои : 10.1145/1134760.1134780 . ISBN 978-1-59593-332-4 . S2CID 17846788 . ИДЕНТИФИКАТОР 56580114 . Проверено 13 декабря 2020 г.

[GalOrendorff2009-6] Галь, Андреас; Орендорф, Джейсон; Рудерман, Джесси; Смит, Эдвин В.; Рейтмайер, Рик; Бебенита, Майкл; Чанг, Мейсон; Франц, Майкл; Эйх, Брендан; Шейвер, Майк; Андерсон, Дэвид; Манделин, Дэвид; Хагигат, Мохаммад Р.; Каплан, Блейк; Хоар, Грейдон; Збарский, Борис (июнь 2009 г.). «Специализация типов Just-in-Time на основе трассировки для динамических языков» (PDF) . Материалы 30-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . ПЛДИ '09. стр. 465–478. дои : 10.1145/1542476.1542528 . ISBN 978-1-60558-392-1 . S2CID 207172806 . Проверено 13 декабря 2020 г.

[BolzCuni2009-7] Больц, Карл Фридрих; Куни, Антонио; Фиялковски, Мацей; Риго, Армин (июль 2009 г.). «Отслеживание метауровня: трассирующий JIT-компилятор PyPy» (PDF) . Материалы 4-го семинара «Внедрение, компиляция, оптимизация объектно-ориентированных языков и систем программирования» . ICOOOLPS '09. стр. 18–25. дои : 10.1145/1565824.1565827 . ISBN 978-1-60558-541-3 . S2CID 7478596 . Проверено 13 декабря 2020 г.

[BebenitaBrandner2010-8] Бебенита, Майкл; Бранднер, Флориан; Фандрих, Мануэль; Логоццо, Франческо; Шульте, Вольфрам; Тильманн, Николай; Вентер, Герман (октябрь 2010 г.). «SPUR: JIT-компилятор на основе трассировки для CIL» (PDF) . Материалы международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования . УПСЛА '10. стр. 708–725. дои : 10.1145/1869459.1869517 . ISBN 978-1-4503-0203-6 . S2CID 3395746 . Проверено 13 декабря 2020 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]