Вчера девы firefox наконец-таки влили tracemonkey в mozilla-central и бампнули версию nightly до 12a1. Наконец-таки jit в js-машине!
Ещё одна отвлечённая мысль. Считается, что whole-program optimization делает возможными какие-то нелокальные преобразования и это очень хорошо. С другой стороны, та же самая trace-based компиляция (или проход вверх по стеку, как в #1478860) это и есть те самые глобальные оптимизации, не доступные обычному не whole-program компилятору.
В больших программах на C++ в пять раз больше вызовов функций, чем в программах на C.
Средний размер виртуальных функций в C++ всего 30 инструкций — в 6 раз меньше чем средняя функция на C.
Т.е. выгода от правильно заинлайненых методов может быть значительной.
В функциональных языках, думаю, функции ещё меньше. Но, в случае, например, хаскеля, само понятние вызова размазано во времени и пространстве.
Средний размер виртуальных функций в C++ всего 30 инструкций — в 6 раз меньше чем средняя функция на C.
Т.е. выгода от правильно заинлайненых методов может быть значительной.
В функциональных языках, думаю, функции ещё меньше. Но, в случае, например, хаскеля, само понятние вызова размазано во времени и пространстве.
Ещё про adaptive recompilation.
В динамической компиляции есть два важных вопроса:
— when: как долго ждать пока соберётся достаточно статистики о выполнении программы;
— what: какой код больше выиграет от компиляции.
Про when я уже слегка упоминал в самом начале: у каждого метода есть счётчик вызовов и когда он достигает какого-то предела, принимается решение, есть ли смысл этот метод оптимизировать. Можно придумать более интересные эвристики, но как оказалось, важнее правильно определять что оптимизировать. Поэтому простые и быстрые счётчики лучше хитрых.
Например, если переполняется счётчик метода возвращающего константу, то, очевидно, что такой метод нисколько не выиграет от оптимизации, зато если заинлайнить его в вызывающем методе, то будет польза. Т.е. нужно пройтись вверх по стеку (чаще всего на один-два вызова).
В общем случае, лучше оптимизировать маленькие методы (меньше затрат на компиляцию), с замыканиями (которые можно заинлайнить) и содержащие вызовы других маленьких методов (которых тоже заинлайнить можно).
Поэтому, в заголовке каждого метода хранится дополнительная информация:
— size: размер метода в инструкциях
— count: сколько раз вызывался
— sends: сколько в нём вызовов других методов
— version: сколько раз метод уже компилировался (если много, то видимо, выгоды от ещё одной перекомпиляции будет не много).
В динамической компиляции есть два важных вопроса:
— when: как долго ждать пока соберётся достаточно статистики о выполнении программы;
— what: какой код больше выиграет от компиляции.
Про when я уже слегка упоминал в самом начале: у каждого метода есть счётчик вызовов и когда он достигает какого-то предела, принимается решение, есть ли смысл этот метод оптимизировать. Можно придумать более интересные эвристики, но как оказалось, важнее правильно определять что оптимизировать. Поэтому простые и быстрые счётчики лучше хитрых.
Например, если переполняется счётчик метода возвращающего константу, то, очевидно, что такой метод нисколько не выиграет от оптимизации, зато если заинлайнить его в вызывающем методе, то будет польза. Т.е. нужно пройтись вверх по стеку (чаще всего на один-два вызова).
В общем случае, лучше оптимизировать маленькие методы (меньше затрат на компиляцию), с замыканиями (которые можно заинлайнить) и содержащие вызовы других маленьких методов (которых тоже заинлайнить можно).
Поэтому, в заголовке каждого метода хранится дополнительная информация:
— size: размер метода в инструкциях
— count: сколько раз вызывался
— sends: сколько в нём вызовов других методов
— version: сколько раз метод уже компилировался (если много, то видимо, выгоды от ещё одной перекомпиляции будет не много).
dynamically dispatched calls это один из(??) способов сделать инкапсуляцию и полиморфизм. К сожалению, даже без позднего связывания dynamic dispatch довольно накладная операция (как минимум сброс кэша инструкций и конвейера).
Пусть у нас есть два класса:
class CartesianPoint:
def getX (self): return self._x
class PolarPoint:
def getX (self): return self._rho * cos (self._theta)
...
x = p.getX () # вызов метода где-то в программе
...
Собрав во время выполнения программы статистику о том, какая из реализаций метода getX чаще всего вызывается в данной строчке, можно перекомпилировать кусок кода и заинлайнить этот метод в место вызова.
Например, вместо p.getX() будет:
...
if p.__class == CartesianPoint:
x = p._x
else:
x = p.getX()
...
Получается adaptive recompilation.
Если в polymorphic inline cache добавить счётчик вызовов для каждого из методов, то у компилятора будет вся необходимая информация, чтобы проделать такой трюк. Собственно это и есть type feedback.
Btw, это один из тех случаев, когда динамический компилятор генерит более эффективный код чем статический.
Пусть у нас есть два класса:
class CartesianPoint:
def getX (self): return self._x
class PolarPoint:
def getX (self): return self._rho * cos (self._theta)
...
x = p.getX () # вызов метода где-то в программе
...
Собрав во время выполнения программы статистику о том, какая из реализаций метода getX чаще всего вызывается в данной строчке, можно перекомпилировать кусок кода и заинлайнить этот метод в место вызова.
Например, вместо p.getX() будет:
...
if p.__class == CartesianPoint:
x = p._x
else:
x = p.getX()
...
Получается adaptive recompilation.
Если в polymorphic inline cache добавить счётчик вызовов для каждого из методов, то у компилятора будет вся необходимая информация, чтобы проделать такой трюк. Собственно это и есть type feedback.
Btw, это один из тех случаев, когда динамический компилятор генерит более эффективный код чем статический.
Итак, 95% вызовов мономорфны, однако оставшиеся 5% могут давать значительный вклад в производительность программы.
Например, если в списке лежат объекты разных типов, и мы в цикле для каждого объекта вызываем какой-то метод:
foreach w in widgets: w.draw ()
В этом случае inline cache малоэффективен. Сплошные промахи будут: в начале каждого метода стоит проверка, что тип объекта для которого он вызван действительно такой как ожидается. Если это не так, происходит поиск нужного метода (через lookup) и ссылка на него подставляется в место вызова.
Urs Hölzle решил, что для по-настоящему полиморфных вызовов было бы неплохо кэшировать сразу несколько ссылок на методы, для этого придумал после первого промаха подставлять в место вызова ссылку на специальный кусок кода polymorphic inline cache. Т.е. как-то так:
...
% push args
push obj
call pic_123
...
pic_123:
switch (obj.type) {
case Window: jump to draw_window
case Button: jump to draw_button
default:
method_ref = lookup (method_name)
update_pic (obj.type, method_name)
jump to method_ref
}
Если при следующем вызове окажется, что obj это не Window и не Button, то в switch добавится новый кейс.
Размер кэша ограничен десятком записей.
Прирост производительности типичной программы от PIC в пределах 5-10%. Не так много, но, в качестве побочного эффекта, PIC предоставляет компилятору type feedback, правильное использование которого вроде как ещё десяток процентов добавляет.
Например, если в списке лежат объекты разных типов, и мы в цикле для каждого объекта вызываем какой-то метод:
foreach w in widgets: w.draw ()
В этом случае inline cache малоэффективен. Сплошные промахи будут: в начале каждого метода стоит проверка, что тип объекта для которого он вызван действительно такой как ожидается. Если это не так, происходит поиск нужного метода (через lookup) и ссылка на него подставляется в место вызова.
Urs Hölzle решил, что для по-настоящему полиморфных вызовов было бы неплохо кэшировать сразу несколько ссылок на методы, для этого придумал после первого промаха подставлять в место вызова ссылку на специальный кусок кода polymorphic inline cache. Т.е. как-то так:
...
% push args
push obj
call pic_123
...
pic_123:
switch (obj.type) {
case Window: jump to draw_window
case Button: jump to draw_button
default:
method_ref = lookup (method_name)
update_pic (obj.type, method_name)
jump to method_ref
}
Если при следующем вызове окажется, что obj это не Window и не Button, то в switch добавится новый кейс.
Размер кэша ограничен десятком записей.
Прирост производительности типичной программы от PIC в пределах 5-10%. Не так много, но, в качестве побочного эффекта, PIC предоставляет компилятору type feedback, правильное использование которого вроде как ещё десяток процентов добавляет.
продолжаю читать что пишет Urs Hölzle.
Всякие петоны [имхо] популярны, в числе прочего, из-за позднего связывания (late binding).
Идея в том, что узнать какие у объекта есть методы (и где они реализованы) мы можем только в рантайме: у каждого объекта есть ссылочка на класс от которого он инстанцирован (или на прототип), пройдя по ссылочке можно поискать в описании класса нужный метод по имени. Таким образом получается duck typing и полиморфизм.
Late binding штука накладная (особенно если иерархия наследования развесистая), поэтому компилятору полезно как-то полиморфные вызовы оптимизировать.
Lookup cache. После того как обошли родительские классы и таки нашли нужный метод можно результат поиска запомнить в хэше (ключом будет имя метода и вышеуказанная ссылочка на класс объекта, а значением — адрес реализации метода).
В Berkeley Smalltalk'е lookup cache даёт 37% производительности. Но, всё равно, даже поиск в кэше — это оверхед по сравнению с простым вызовом метода по адресу.
К счастью, оказалось, что вызовы методов преимущественно мономорфные. Т.е. если в конкретном методе в переменной win лежит экземпляр класса Window, то в 95% последующих вызовов этого метода там будет тоже Window (объект может быть другим, но тоже экземпляр окна).
In-line cache. Т.е. лучше всего кэшировать в месте вызова, подменяя вызов lookup'а на вызов самого метода.
После компиляции win.draw (...) выглядит как-то так:
...
% push аргументы всякие
push win
push "draw"
call lookup % получаем на стеке адрес нужной реализации draw
call [esp]
...
Когда lookup нашёл нужный метод, он может вместо вызова себя поставить непосредственно вызов draw:
...
% push аргументы
push win
nop
nop
call draw
..
Естественно, никто не может гарантировать что вызов действительно мономорфный и в следующий раз в win не будет лежать экземпляр другого класса (например, дочернего для Window). Поэтому в начале draw должна быть проверка: если объект другого класса, то вызываем старый добрый lookup.
Btw, in-line cache не отменяет lookup caсhe (который прячется внутри функции lookup).
Всякие петоны [имхо] популярны, в числе прочего, из-за позднего связывания (late binding).
Идея в том, что узнать какие у объекта есть методы (и где они реализованы) мы можем только в рантайме: у каждого объекта есть ссылочка на класс от которого он инстанцирован (или на прототип), пройдя по ссылочке можно поискать в описании класса нужный метод по имени. Таким образом получается duck typing и полиморфизм.
Late binding штука накладная (особенно если иерархия наследования развесистая), поэтому компилятору полезно как-то полиморфные вызовы оптимизировать.
Lookup cache. После того как обошли родительские классы и таки нашли нужный метод можно результат поиска запомнить в хэше (ключом будет имя метода и вышеуказанная ссылочка на класс объекта, а значением — адрес реализации метода).
В Berkeley Smalltalk'е lookup cache даёт 37% производительности. Но, всё равно, даже поиск в кэше — это оверхед по сравнению с простым вызовом метода по адресу.
К счастью, оказалось, что вызовы методов преимущественно мономорфные. Т.е. если в конкретном методе в переменной win лежит экземпляр класса Window, то в 95% последующих вызовов этого метода там будет тоже Window (объект может быть другим, но тоже экземпляр окна).
In-line cache. Т.е. лучше всего кэшировать в месте вызова, подменяя вызов lookup'а на вызов самого метода.
После компиляции win.draw (...) выглядит как-то так:
...
% push аргументы всякие
push win
push "draw"
call lookup % получаем на стеке адрес нужной реализации draw
call [esp]
...
Когда lookup нашёл нужный метод, он может вместо вызова себя поставить непосредственно вызов draw:
...
% push аргументы
push win
nop
nop
call draw
..
Естественно, никто не может гарантировать что вызов действительно мономорфный и в следующий раз в win не будет лежать экземпляр другого класса (например, дочернего для Window). Поэтому в начале draw должна быть проверка: если объект другого класса, то вызываем старый добрый lookup.
Btw, in-line cache не отменяет lookup caсhe (который прячется внутри функции lookup).
Несколько тезисов по мотивам вводной части.
Как работает компилятор Self.
Сначала исходники очень простым компилятором (NIC — Non Inlining Compiler) транслируются в нейтивкод.
В каждом методе ставятся заглушки считающие число вызовов метода.
Когда счётчик достигает какого-то предела, метод перекомпилируется более умным компилятором.
Если появляется дополнительная информация (например, что метод не полиморфный и есть возможность его специализировать), метод может перекомпилироваться заново.
Если возникает исключительная ситуация (например, если арифметическое переполнение, то результатом будет уже не просто int, а double или Integer какой-нибудь) или программу пытаются дебагером тыкать, то оптимизированный метод может перекомпилироваться обратно без оптимизации (deoptimization).
Счётчик на самом деле затухает со временем (counter decay): раз в пару секунд все счётчики делятся на константу.
Т.е. если программа работает неделю, то методы, доля которых в общем числе вызовов невелика, всё равно не будут оптимизироваться.
(Кстати, как я понял, trace based компиляция так и не выстрелила из-за своей сложности по сравнению с простыми счётчиками.)
Btw, есть версия, что исходники — наиболее компактное представление программы (т.е. байткод и ast хранить не надо).
А неоптимизированный нейтивкод может быть побочным продуктом интерпретации (это вроде в Smalltalk'е каком-то было).
Поскольку ничего нового я пока не написал, пара вопросов.
Какие бенефиты от jit:
— быстрая компиляция;
— у оптимизирующего компилятора больше информации (от рантайма);
— сам компилятор проще (без сложных статических анализов);
— edit-run вместо edit-compile-link-run;
— редактирование кода в рантайме без перезапуска программы (через deoptimization).
— что ещё?
Какие недостатки:
— тормозит;
— сложно сделать whole program optimization, т.е. все оптимизации преимущественно локальные;
— что ещё?
Как работает компилятор Self.
Сначала исходники очень простым компилятором (NIC — Non Inlining Compiler) транслируются в нейтивкод.
В каждом методе ставятся заглушки считающие число вызовов метода.
Когда счётчик достигает какого-то предела, метод перекомпилируется более умным компилятором.
Если появляется дополнительная информация (например, что метод не полиморфный и есть возможность его специализировать), метод может перекомпилироваться заново.
Если возникает исключительная ситуация (например, если арифметическое переполнение, то результатом будет уже не просто int, а double или Integer какой-нибудь) или программу пытаются дебагером тыкать, то оптимизированный метод может перекомпилироваться обратно без оптимизации (deoptimization).
Счётчик на самом деле затухает со временем (counter decay): раз в пару секунд все счётчики делятся на константу.
Т.е. если программа работает неделю, то методы, доля которых в общем числе вызовов невелика, всё равно не будут оптимизироваться.
(Кстати, как я понял, trace based компиляция так и не выстрелила из-за своей сложности по сравнению с простыми счётчиками.)
Btw, есть версия, что исходники — наиболее компактное представление программы (т.е. байткод и ast хранить не надо).
А неоптимизированный нейтивкод может быть побочным продуктом интерпретации (это вроде в Smalltalk'е каком-то было).
Поскольку ничего нового я пока не написал, пара вопросов.
Какие бенефиты от jit:
— быстрая компиляция;
— у оптимизирующего компилятора больше информации (от рантайма);
— сам компилятор проще (без сложных статических анализов);
— edit-run вместо edit-compile-link-run;
— редактирование кода в рантайме без перезапуска программы (через deoptimization).
— что ещё?
Какие недостатки:
— тормозит;
— сложно сделать whole program optimization, т.е. все оптимизации преимущественно локальные;
— что ещё?
Случайно распечатал диссертацию товарища Urs Hölzle (http://www.cs.ucsb.edu/~urs/oocsb/papers/urs-thesis.html).
Пишет про трюки, которые он в 1994 году реализовал для jit-компилятора языка self.
Читается очень легко, постараюсь сюда конспект накидать.
Внимание, вопрос! Что можно почитать про современное состояние дел в динамической компиляции (например про javascript)?
Пишет про трюки, которые он в 1994 году реализовал для jit-компилятора языка self.
Читается очень легко, постараюсь сюда конспект накидать.
Внимание, вопрос! Что можно почитать про современное состояние дел в динамической компиляции (например про javascript)?
mo.pp.ru сдох штоле?
Чего-то icq.jabber.snc.ru странно обрабатывает авторизацию — меня не могут авторизовать. А icq.mova.org меж тем продолжает лежать пластом. Вот тебе, бабушка, и аськокапец.
morepypy.blogspot.com Очень интересный jit-компилятор для пайтона, написанный на пайтоне. Удивительно, но ускорение исполнения программы в 6-8 раз. В некоторых случаях в десятки раз быстрее. Круто по-моему!