Share
Embed
Чётная магия JIT компиляции
JIT (Just in Time) компиляция – неотъемлемая часть многих популярных платформ (JavaScript, Java). Задача компиляции в момент выполнения существенно отличается от классической AOT (Ahead of Time) компиляции.
Эволюция технологий JIT и AOT компиляции во многом идут параллельными путями.
В докладе рассказано о новейших достижениях JIT компиляторов для Java и JavaScript платформ, а так же о фундаментальных отличиях JIT и AOT компиляторов.
aragozin
March 27, 2019
Transcript
44 slides
-
В докладе Скорость динамических языков – всё не так
просто как кажется Подходы к компиляции Интерпретаторы – а так ли нужна компиляция? Трюки JIT компиляции различных языков Graal / Truffle – технологии будущего -
Три кита ООП И н к а п с
у л я ц и я П о л и м о р ф и з м Н а с л е д о в а н и е -
Старый добрый С++ Переменная Объект в памяти Таблица виртуальных методов
Сегмент кода Виртуальный вызов метода Object reference VTABLE 00: methodA 02: methodC 03: methodD 04: methodE 0101010101010101 0101010101010101 0101010101010101 1010101010101010 1010101010101010 1010101010101010 1010101010101010 1010101010101010 1010101010100101 01: methodB -
Три кита ООП И н к а п с
у л я ц и я П о л и м о р ф и з м Н а с л е д о в а н и е -
Статические языки XXI века Переменная Таблица виртуальных методов Сегмент кода
Полиморфный вызов метода VTABLE reference 00: methodA 02: methodC 03: methodD 04: methodE 0101010101010101 0101010101010101 0101010101010101 1010101010101010 1010101010101010 1010101010101010 1010101010101010 1010101010101010 1010101010100101 01: methodB Object reference Объект в памяти -
Цена непредсказуемости Branch misprediction penalty • Intel Core2 – 15
cycles • Intel Nehalem – 17 cycles • Intel Sandy/Ivy bridge – 15 cycles • Intel Haskwell / Broadwell / Skylake – 15 - 20 cycles • AMD K8 / K10 – 13 cycles • AMD Buldozer – 19 - 22 cycles • AMD Ryzen – 18 cycles http://www.agner.org/optimize/microarchitecture.pdf -
Цена непредсказуемости Memory access timings (Skylake) • L1 cache –
4 cycle • L2 cache – 14 cycle • L3 cache – 34-85 cycles • RAM – 50-100 ns -
Челенжи JIT компиляции Полиморфизм / method dispatch Доступ
к полям объектов Функциональная композиция -
The source code for a simple computer program written in
the C programming language. When compiled and run, it will give the output "Hello, world!". A programming language is a formal language, which comprises a set of instructions that produce various kinds of output. Programming languages are used in computer programming to implement algorithms. 0111010010 1110100101 1101001011 1010010111 0100101110 1001011101 0010111010 0101110100 0 getstatic com.oracle. 3 iconst_0 4 anewarray java.lang.O 7 invokevirtual java.la 10 checkcast java.net.So 13 areturn 14 astore_0 15 new java.lang.Asserti 18 dup 19 aload_0 20 invokespecial java.la 23 athrow 24 astore_0 25 new java.lang.Asserti 28 dup 29 aload_0 30 invokespecial java.la Как реализовать свой язык? Исходный код AST Интерпретатор Байт-код Машинный код Интерпретатор байт-кода -
Компиляция Ahead of Time (AOT) Компиляция всего кода до
начала выполнения Специальная генерация кода для отладки Различные уровни оптимизации Just in Time (JIT) Компиляция по мере выполнения Компиляция должна быть быстрой Использование статистики выполнения кода при компиляции -
Трассирующий компилятор loop do if untill foo() bar() if return
call Трасса: 010001101011011010101011010110101110011 010110110101010110101101011100110101101 101010101101011010111001101011011010101 Линейная последовательность операций Компилируется в блок машинного кода Нарушение гарда переводит выполнение в режим интерпретации -
Инлайн кэш вызовов int size = list.size(); int size; if
(List.class == ArrayList.class) { size = ArrayList::size(list); } else { size = VM::dispatch(List::size, list); } Мономорфная точка вызова Псевдокод -
Инлайн кэш доступа к свойству obj.value = x HREFK: if
(hash[17].key != key) goto exit HSTORE: hash[17].value = x LuaJIT трасса Синергия со спекулятивным и суперскалярным выполнением на современном ЦПУ Честное выполнение Вычисление хэша Деление по модулю Сравнение ключа по индексу -
Грязные трюки JIT Спекулятивное выполнение Инлайн кэширование динамических вызовов
Инлайн кэширование структурной информации Спекулятивное выполнение ветвлений Агрессивный инлайнинг кода Возможен за счёт спекуляции -
Трассирующие JIT на практике Платформы использующие трассирующий JIT Flash
Mozilla TraceMonkey PyPy / RPython LuaJIT Проблемы трассирующего JITа Трассировка тормозит интерпретатор Очень медленный “разогрев” -
А нужна ли магия? Что если генерировать код по-простому? Интерпретатор
может оказаться быстрее! V8 TurboFan Vs. V8 Ignition HIPHOPVM Vs. PHP 7 kdb “Building fast interpreters in Rust” @blog.cloudflare.com https://blog.cloudflare.com/building-fast-interpreters-in-rust/ -
Интерпретатор HotSpot JVM • Для каждой инструкции байт-кода написана процедура
на ассемблере • Байт-код – индекс в таблице адресов процедур • Вход в процедуру инструкции - jump • Каждая процедура заканчивается jump на вход интерпретатора Интерпретация кода в одном кадре стека Код и таблица переходов кэшируются Конвейер процессора остаётся загруженным -
Method based JIT JVM / V8 / SpiderMonkey Многоуровневая
компиляция Компилируются методы/функции Спекуляция на базе статистики Агрессивный инлайнинг Глобальные оптимизации Hidden classes для JavaScript Динамическая деоптимизация -
Escape analysis public String toString() { StringBuffer buf = new
StringBuffer(); buf.append("X=").append(x); buf.append(",Y=").append(y); return buf.toString(); } Наследие Java тёмных лет - StringBuffer buf не используется за пределами метода все вызовы методов buf заинлайнены Синхронизацию можно убрать -
Scalar replacement double length() { return distance( new Point(this.ax, this.ay),
new Point(this.bx, this.by)); } double distance(Point a, Point b) { double w = a.x - b.x; double h = a.y - b.y; return Math.sqrt(w*w + h*h); } double length() { double w = this.ax - this.bx; double h = this.ay - this.by; return Math.sqrt(w*w + h*h); } включение distance объекты a и b не убегают объекты a и b декомпозируются в набор полей -
Функциональная композиция c(a,b) = (x -> a(b(x))) инлайн кэш
может плохо работать в универсальном коде необходимо независимо компилировать отдельные экземпляры функций JVM invokedynamic байт-инструкция и InvocationHandler API -
Всё так сложно JIT компилятор Генерация кода
Специфика языка Оптимизации Интерпретатор Супер-оптимизированный код Привязка к архитектуре ЦПУ -
PyPy – Питон на Питоне Программа на Python Интерпретатор на
RPython Трассирующий JIT -
PyPy – Питон на Питоне Программа на Python Интерпретатор на
RPython Трассирующий JIT AST Трасса интерпретации узлов AST -
Graal & Truffle Оптимизирующий JIT компилятор Написанный на
Java 150+ видов/фаз оптимизации Понимает JVM байт-код, но не только Использует промежуточное графовое представление код Может использоваться вместо C2 в JDK 11 Truffle – языковой фасад для Graal -
Graal + Truffle Исходный код Интерпретатор на Truffle Graal JIT
JVM AST Граф алгоритма интерпретатора специализированный узлом AST -
Truffle Реализуем трюфельный JIT рантайм 1. Пишем интерпретатор AST на
Java 2. Включаем Graal компилятор в JVM 3. Добавляем JIT оптимизации декларативно -
Truffle https://github.com/graalvm/simplelanguage public final ConditionProfile condition = ConditionProfile.createCountingProfile(); ... @Override
public void executeVoid(VirtualFrame frame) { if (condition.profile(evaluateCondition(frame))) { /* Execute the then-branch. */ thenPartNode.executeVoid(frame); } else { /* Execute the */ if (elsePartNode != null) { elsePartNode.executeVoid(frame); } } } -
Truffle https://github.com/graalvm/simplelanguage @Specialization(limit = "INLINE_CACHE_SIZE", // guards = "function.getCallTarget() ==
cachedTarget", // assumptions = "callTargetStable") @SuppressWarnings("unused") protected static Object doDirect(SLFunction function, Object[] arguments, @Cached("function.getCallTargetStable()") Assumption callTargetStable, @Cached("function.getCallTarget()") RootCallTarget cachedTarget, @Cached("create(cachedTarget)") DirectCallNode callNode) { /* Inline cache hit, we are safe to execute the cached call target. */ return callNode.call(arguments); } @Specialization(replaces = "doDirect") protected static Object doIndirect(SLFunction function, Object[] arguments, @Cached("create()") IndirectCallNode callNode) { /* SL has a quite simple call lookup: just ask the function for * the current call target, and call it. */ return callNode.call(function.getCallTarget(), arguments); } -
Ссылки LuaJIT https://web.archive.org/web/20180721041742/http://article.gmane.org/gmane.comp.lang.lua.general/58908 https://github.com/lukego/blog/issues?q=is%3Aissue+is%3Aopen+label%3Aluajit Incremental Dynamic Code Generation with Trace
Trees https://www.cs.montana.edu/ross/classes/fall2009/cs550/resources/Tracemonkey-01.pdf V8 Design blog https://v8.dev/blog | https://v8.dev/blog/jitless RPython https://rpython.readthedocs.io/en/latest/jit/index.html http://tratt.net/laurie/research/pubs/papers/bolz_tratt__the_impact_of_metatracing_on_vm_design_and_implementation.pdf Интерпретаторы https://blog.cloudflare.com/building-fast-interpreters-in-rust/ https://badootech.badoo.com/when-pigs-fly-optimising-bytecode-interpreters-f64fb6bfa20f -
Ссылки Graal https://github.com/oracle/graal/blob/master/docs/Publications.md https://www.graalvm.org https://chrisseaton.com/rubytruffle/pppj14-om/pppj14-om.pdf – object layout for TruffleRuby
https://www.youtube.com/watch?v=FJY96_6Y3a4 – 3 hours Truffle introduction https://github.com/graalvm/graal-js-jdk11-maven-demo – out-of box Java 11 + Graal JIT setup Partial escape analysis http://www.ssw.uni-linz.ac.at/Research/Papers/Stadler14/Stadler2014-CGO-PEA.pdf