Все исходные коды и примеры из этой статьи доступны здесь.
Когда я первый раз смотрел проект PyPy, мне потребовалось некоторое время, чтобы выяснить, что он из себя представляет. Он состоит из двух вещей:
— набор инструментов для написания интерпретаторов языков программирования;
— реализация Питона с применением этого набора инструментов.
Вероятно, большинство людей думает, что PyPy это только вторая часть, но это руководство не об интерпретаторе Питона. Оно о том, как написать интерпретатор своего языка.
Я взялся за это руководство для того, чтобы лучше понять как работает PyPy и что он из себя представляет. Предполагается, что вы очень мало знаете о PyPy, поэтому я начну с самого начала.
Предположим, что мы хотим написать интерпретатор. Это включает в себя написание парсера исходного кода, цикла исполнения байт-кода и большого количества кода стандартной библиотеки.
Писать парсер и компилятор обычно совсем не весело, поэтому существуют инструменты, которые генерируют парсер и компилятор за вас.
И даже тогда вы должны заботиться об управлении памятью в интерпретаторе и должны будете реализовывать типы данных, такие как целые числа произвольной размерности, таблицы хешей и прочее. Этого достаточно, чтобы многие передумали реализовывать свой интерпретатор.
Разве не было бы замечательно, если бы вы могли реализовать свой язык на высокоуровневом языке, например, Питоне? Вы бы получили в свое распоряжение все преимущества высокоуровневого языка, такие как автоматическое управление памятью и богатый набор типов данных. Но интерпретация языка на другом интерпретируемом языке должна быть очень медленной, верно?
Как можно догадаться, PyPy решает эту проблему. PyPy — это сложный инструментарий для анализа и перевода вашего кода интерпретатора в Си (или JVM или CLI). Этот процесс называется «трансляцией». Он знает как перевести не весь синтаксис Питона, но довольно большую его часть. Все что вы должны сделать — написать свой интерпретатор на языке RPython, подмножестве языка Питон, после этого вы получите очень эффективный интерпретатор.
Потому что написание эффективных интерпретаторов не должно быть проблемой.
Язык, который я выбрал для реализации, ужасно простой. Рантайм языка состоит из ленты целых чисел, инициализированных нулем, и одного указателя на текущую ячейку в этой ленте. Язык имеет всего 8 команд:
< — переместить указатель на предыдущую ячейку.
> — переместить указатель следующую ячейку.
+ — увеличить на один число в текущей ячейке.
- — уменьшить на один число в текущей ячейке.
[ — если число в текущей ячейки — 0, то пропустить все инструкции до соответствующей инструкции ].
] — вернуться назад к соответствующей инструкции [.
. — вывести в стандартный поток вывода один байт из текущей ячейки.
, — прочитать один байт из стандартного потока ввода и положить в текущую ячейку.
Любые нераспознанные символы должны игнорироваться.
Некоторые могли узнать этот язык, это brainfuck.
Сам язык уже является байт-кодом, поэтому не требует отдельного перевода исходного кода в байт-код. Это означает, что главный цикл выполнения нашего интерпретатора будет работать непосредственно с исходным кодом. Это немного упрощает его реализацию.
Давайте начнем с того, что напишем интерпретатор на обычном Питоне. Вот набросок основного цикла выполнения.
Как видите, счетчик команд (pc) хранит указатель на текущую инструкцию. Первое выражение в цикле извлекает инструкцию, затем несколько условных операторов определяют, как её выполнять.
Реализация операторов «[» и «]» опущена, они должны менять счетчик команд на положение совпадающей скобки.
А теперь реализация класса Tape, который хранит ленту целых чисел и указатель на текущее число.
Как видите, лента при необходимости увеличивается. На самом деле стоило бы добавить проверку на ошибки, когда указатель становится отрицательным. Но пока это неважно.
Если в программе будет много комментариев, они будут читаться по одному байту, так что лучше парсить исходный код заранее. Заодно мы сделаем словарь для скобок, чтобы в нем можно было находить парные скобки.
Эта функция возвращает строку только из команд языка и словарь парных скобок.
Осталось соединить это, и у нас получится рабочий интерпретатор brainfuck.
Полный код интерпретатора, включая реализацию квадратных скобок, можно посмотреть в первом примере. example1.py
Теперь вы можете попробовать запустить интерпретатор на Питоне, чтобы убедиться, что он работает.
$ python example1.py 99bottles.b
Но наша цель была не только в написании интерпретатора brainfuck. Что же нужно сделать, чтобы PyPy создал из этого кода супербыстрый исполняемый файл?
В исходниках PyPy, в папке pypy/translator/goal лежат простые примеры, которые придутся кстати. Для начала заглянем в targetnopstandalone.py — простой hello world для PyPy.
Важно то, что модуль содержит функцию target, которая возвращает точку входа. Трансляция начинается с этой точки.
Функция entry_point будет принимать аргументы командной строки, когда вы будете запускать получившийся исполняемый файл.
Давайте поговорим о RPython. PyPy не может транслировать обычный код на Питоне, потому что Питон слегка слишком динамичный. Есть некоторые ограничения, которые накладываются на стандартную библиотеку и синтаксис Питона, чтобы PyPy мог транслировать его. Я не буду перечислять их все, лучше посмотреть их в документации.
В вышеприведенном примере пришлось изменить несколько вещей. Теперь приходится использовать низкоуровневые дескрипторы с функциями os.open и os.read вместо использования файловых объектов. Реализация «.» и «,» тоже немного изменена. Это все изменения, необходимые для того, чтобы PyPy стал переваривать код.
Это было не слишком сложно, правда? Я продолжаю использовать словари, расширяемые списки и даже классы с объектами. И если файловые дескрипторы для вас слишком низкоуровневые, в модуле rlib.streamio, поставляемом вместе со стандартной библиотекой RPython, есть несколько полезных абстракций.
Полный код теперь выглядит так: еxample2.py
Если вы этого еще не сделали, слейте последнюю версию PyPy с репозитория на bitbucket.org.
$ hg clone bitbucket.org/pypy/pypy
Скрипт, который нужно запустить — pypy/translator/goal/translate.py. В качестве параметра он принимает модуль, который нужно оттранслировать.
$ python ./pypy/pypy/translator/goal/translate.py example2.py
Для более быстрой трансляции можно использовать PyPy вместо Питона.
Результатом выполнения станет исполняемый файл — интерпретатор brainfuck. В репозитории лежит генератор фракталов на brainfuck, выполнение которого на моей машине занимает около 45 секунд. Попробуйте сами.
$ ./example2-c mandel.b
И сравните скорость с тем, что выдает этот же интерпретатор, запущенный на Питоне.
$ python example2.py mandel.b
Итак, мы написали интерпретатор на RPython и оттранслировали его с помощью инструментария PyPy.
Трансляция RPython в Си — это конечно круто, но одна из главных фич PyPy — это возможность генерировать компилятор времени выполнения (JIT). Используя всего несколько подсказок о том, как устроен ваш интерпретатор, PyPy сгенерирует JIT-компилятор, который будет переводить интерпретируемый код brainfuck в машинный.
Чтобы это произошло, PyPy должен знать, где начинается цикл выполнения программы. Это позволяет отследить, какие инструкции выполняются на brainfuck.
Мы также должны указать особенности цикла выполнения. Так как в нашем языке нет стека, нам нужно только указать какие переменные относятся к коду программы, а какие к её данным. Это называется зелеными и красными переменными соотвественно.
Вернемся ко второму примеру.
В нашем основном цикле выполнения используются четыре переменных: pc, program, bracket_map и tape. Конечно, pc, program и bracket_map — зеленые переменные, они определяют выполнение интерпретируемой программы. Переменная tape — красная, она изменяется при выполнении интерпретируемой программы.
Давайте сообщим PyPy эти данные. Начнем с импорта класса JitDriver и создания его экземпляра.
И добавим такую строку в самое начало цикла исполнения:
Также нам нужно определить JitPolicy.
Полный текст примера: example3.py
Теперь еще раз оттранслируем код, но уже с флагом --opt=jit:
$ python ./pypy/pypy/translator/goal/translate.py --opt=jit example3.py
Трансляция будет идти значительно дольше, почти 8 минут на моей машине, и получившийся исполняемый файл будет намного больше. После окончания трансляции запустим программу генерации фракталов снова. Разница огромна — примерно 12 секунд против 45 в предыдущем варианте!
Как видите, JIT-компилятор действительно использовал машинный код вместо интерпретации. Несколько первых линий картинки выводятся достаточно быстро, потом программа ускоряется и остальное выводится еще быстрее.
Стоит поговорить о том, как вообще работают трассирующие JIT-компиляторы. Ваш интерпретирующий код запускается в обычном режиме. Когда JIT встречает часто выполняющийся цикл в интерпретируемом языке (brainfuck), цикл помечается для трассировки. Когда в следующий раз достигается этот же цикл, включается логирование каждой выполненной инструкции.
Полученный лог отправляется в оптимизатор, результат работы которого преобразуется в машинный код. Этот код используется для последующих выполнений цикла.
Получившийся машинный код корректен только при некоторых условиях, при которых он был получен. Поэтому перед его использованием данные условия проверяются. Если проверка не проходит, вместо машинного кода вновь запускается интерпретатор.
Больше информации можно найти в Википедии.
Можем ли мы увидеть, что делает JIT?
Давайте добавим функцию get_printable_location, которая будет использоваться для вывода отладочной информации.
Эта функция принимает зеленые переменные и возвращает сроку. Мы выводим код brainfuck, в котором текущая выполняемая инструкция окружена подчеркиваниями.
Оттранслируйте код примера example4.py.
Теперь запустите тестовую программу (test.b просто выводит букву «A» примерно 15 раз) с выводом логов трассировки.
$ PYPYLOG=jit-log-opt:logfile ./example4-c test.b
Файл logfile содержит логи всех произведенных трассировок и позволяет взглянуть на то, какие инструкции были скомпилированы в машинный код. Файл полезен тем, что позволяет увидеть ненужные инструкции или пути для оптимизации.
Каждая трассировка начинается с линии вроде этой:
И заканчивается такой линией:
Сразу после заголовка трассировки идет комментарий с порядковым номером и количество операций. В моем случае первая трассировка выглядит так.
Я немного обрезал слишком длинные строки debug_merge_point.
Этот участок кода принимает четыре параметра: два указателя на объекты (p0 и p1) и два числа (i2 и i3).
Первый оператор «>» начинается на 4-й строке. Он выполняется без инструкций и выглядит окончательно оптимизированным. Этот цикл всегда работает с одной частью ленты, и указатель на текущую ячейку остается постоянным.
Строки с пятой по восьмую — оператор «+». Сначала извлекается элемент массива с индексом i2 из указателя p1 (строка 6), прибавляется единица и сохраняется в i6 (строка 7). Результат помещается обратно в массив (строка 8).
Строка 9 соответствует инструкции «<», но она тоже не требует операций. Судя по всему — i2 и i3 — это два указателя на ячейки ленты, которые вычислены заранее. Также видно, что p1 — это лента команд. Пока не ясно, что такое p0.
Строки с 10 по 13 выполняют оператор «-»: извлекают элемент массива, вычитают и кладут его обратно.
В 14-й строке мы подходим к оператору «]». Строки 15 и 16 проверяют, является ли i9 истиной (т.е. не равно нулю). i9 — это значение, которое мы только что уменьшили на единицу и положили в ленту. Строка 16 — проверка. Если условие не выполняется, исполняется функция с названием <Guard2>, которой передается один параметр, p0.
Если же проверка пройдена, строки с 17 по 23 достают из словаря bracket_map адрес инструкции, к которой нужно перейти. Я не уверен, что именно делают эти строки, но видно, что в них содержится два внешних вызова и 3 проверки. Это слишком расточительно, учитывая, что bracket_map не меняется и результатом будет один и тот же адрес, на который нужно перейти. Но PyPy об этом не знает, а мы знаем, поэтому можем оптимизировать это место.
Строка 24 увеличивает полученный из bracket_map указатель. Строки 25 и 26 проверяют, что он не превысил длину программы.
Кроме этого в строке 27 проводится дополнительная проверка, что указатель строго равен 86. Это нужно для того, чтобы убедится, что прыжок должен быть сделан в начало цикла.
В конце цикл замыкается на строке 28, и в строке 29 происходит прыжок в начало цикла с параметрами p0, p1, i2, i3.
Как было замечено, на каждой итерации цикла происходит поиск в словаре для нахождения парной скобки. Это ужасно неэффективно, потому что цель перехода не меняется на разных итерациях.
Нам нужно дать еще одну подсказку транслятору, чтобы сказать, что запрос к словарю всегда вернет одинаковые элементы для одинаковых индексов словаря.
Чтобы это сделать, мы вынесем обращение к словарю в отдельную функцию и обернем её pypy.rlib.jit.purefunction.
Эта версия может быть найдена в example5.py.
Оттранслируйте этот пример. Мандельброт теперь выполняется за 6 секунд вместо 12!
Давайте взглянем на новый лог трассировки.
Намного лучше! Теперь каждый цикл — это только одно сложение, вычитание, две загрузки из массива, два помещения в массив и проверка при выходе. Код не требует никаких изменений счетчика команд.
Эту оптимизацию мне подсказал Армин Риго в рассылке pypy-dev. У Карла Фридриха есть несколько статей об оптимизации интерпретаторов, которые тоже оказались полезными.
Я надеюсь, эта статья убедила вас в том, что PyPy это не только быстрый интерпретатор Питона.
Для тех из вас, кто хочет больше узнать о JIT-компиляторе PyPy, я рекомендую прочитать статью Tracing the Meta-Level: PyPy's Tracing JIT Compiler.
Когда я первый раз смотрел проект PyPy, мне потребовалось некоторое время, чтобы выяснить, что он из себя представляет. Он состоит из двух вещей:
— набор инструментов для написания интерпретаторов языков программирования;
— реализация Питона с применением этого набора инструментов.
Вероятно, большинство людей думает, что PyPy это только вторая часть, но это руководство не об интерпретаторе Питона. Оно о том, как написать интерпретатор своего языка.
Я взялся за это руководство для того, чтобы лучше понять как работает PyPy и что он из себя представляет. Предполагается, что вы очень мало знаете о PyPy, поэтому я начну с самого начала.
Чем является PyPy
Предположим, что мы хотим написать интерпретатор. Это включает в себя написание парсера исходного кода, цикла исполнения байт-кода и большого количества кода стандартной библиотеки.
Писать парсер и компилятор обычно совсем не весело, поэтому существуют инструменты, которые генерируют парсер и компилятор за вас.
И даже тогда вы должны заботиться об управлении памятью в интерпретаторе и должны будете реализовывать типы данных, такие как целые числа произвольной размерности, таблицы хешей и прочее. Этого достаточно, чтобы многие передумали реализовывать свой интерпретатор.
Разве не было бы замечательно, если бы вы могли реализовать свой язык на высокоуровневом языке, например, Питоне? Вы бы получили в свое распоряжение все преимущества высокоуровневого языка, такие как автоматическое управление памятью и богатый набор типов данных. Но интерпретация языка на другом интерпретируемом языке должна быть очень медленной, верно?
Как можно догадаться, PyPy решает эту проблему. PyPy — это сложный инструментарий для анализа и перевода вашего кода интерпретатора в Си (или JVM или CLI). Этот процесс называется «трансляцией». Он знает как перевести не весь синтаксис Питона, но довольно большую его часть. Все что вы должны сделать — написать свой интерпретатор на языке RPython, подмножестве языка Питон, после этого вы получите очень эффективный интерпретатор.
Потому что написание эффективных интерпретаторов не должно быть проблемой.
Язык
Язык, который я выбрал для реализации, ужасно простой. Рантайм языка состоит из ленты целых чисел, инициализированных нулем, и одного указателя на текущую ячейку в этой ленте. Язык имеет всего 8 команд:
< — переместить указатель на предыдущую ячейку.
> — переместить указатель следующую ячейку.
+ — увеличить на один число в текущей ячейке.
- — уменьшить на один число в текущей ячейке.
[ — если число в текущей ячейки — 0, то пропустить все инструкции до соответствующей инструкции ].
] — вернуться назад к соответствующей инструкции [.
. — вывести в стандартный поток вывода один байт из текущей ячейки.
, — прочитать один байт из стандартного потока ввода и положить в текущую ячейку.
Любые нераспознанные символы должны игнорироваться.
Некоторые могли узнать этот язык, это brainfuck.
Сам язык уже является байт-кодом, поэтому не требует отдельного перевода исходного кода в байт-код. Это означает, что главный цикл выполнения нашего интерпретатора будет работать непосредственно с исходным кодом. Это немного упрощает его реализацию.
Первые шаги
Давайте начнем с того, что напишем интерпретатор на обычном Питоне. Вот набросок основного цикла выполнения.
def mainloop(program):
tape = Tape()
pc = 0
while pc < len(program):
code = program[pc]
if code == ">":
tape.advance()
elif code == "<":
tape.devance()
elif code == "+":
tape.inc()
elif code == "-":
tape.dec()
elif code == ".":
sys.stdout.write(chr(tape.get()))
elif code == ",":
tape.set(ord(sys.stdin.read(1)))
elif code == "[" and value() == 0:
# Skip forward to the matching ]
elif code == "]" and value() != 0:
# Skip back to the matching [
pc += 1Как видите, счетчик команд (pc) хранит указатель на текущую инструкцию. Первое выражение в цикле извлекает инструкцию, затем несколько условных операторов определяют, как её выполнять.
Реализация операторов «[» и «]» опущена, они должны менять счетчик команд на положение совпадающей скобки.
А теперь реализация класса Tape, который хранит ленту целых чисел и указатель на текущее число.
class Tape(object):
def __init__(self):
self.thetape = [0]
self.position = 0
def get(self):
return self.thetape[self.position]
def set(self, val):
self.thetape[self.position] = val
def inc(self):
self.thetape[self.position] += 1
def dec(self):
self.thetape[self.position] -= 1
def advance(self):
self.position += 1
if len(self.thetape) <= self.position:
self.thetape.append(0)
def devance(self):
self.position -= 1Как видите, лента при необходимости увеличивается. На самом деле стоило бы добавить проверку на ошибки, когда указатель становится отрицательным. Но пока это неважно.
Если в программе будет много комментариев, они будут читаться по одному байту, так что лучше парсить исходный код заранее. Заодно мы сделаем словарь для скобок, чтобы в нем можно было находить парные скобки.
def parse(program):
parsed = []
bracket_map = {}
leftstack = []
pc = 0
for char in program:
if char in ('[', ']', '<', '>', '+', '-', ',', '.'):
parsed.append(char)
if char == '[':
leftstack.append(pc)
elif char == ']':
left = leftstack.pop()
right = pc
bracket_map[left] = right
bracket_map[right] = left
pc += 1
return "".join(parsed), bracket_mapЭта функция возвращает строку только из команд языка и словарь парных скобок.
Осталось соединить это, и у нас получится рабочий интерпретатор brainfuck.
def run(input):
program, map = parse(input.read())
mainloop(program, map)
if __name__ == "__main__":
import sys
run(open(sys.argv[1], 'r'))Полный код интерпретатора, включая реализацию квадратных скобок, можно посмотреть в первом примере. example1.py
Теперь вы можете попробовать запустить интерпретатор на Питоне, чтобы убедиться, что он работает.
$ python example1.py 99bottles.b
Трансляция PyPy
Но наша цель была не только в написании интерпретатора brainfuck. Что же нужно сделать, чтобы PyPy создал из этого кода супербыстрый исполняемый файл?
В исходниках PyPy, в папке pypy/translator/goal лежат простые примеры, которые придутся кстати. Для начала заглянем в targetnopstandalone.py — простой hello world для PyPy.
Важно то, что модуль содержит функцию target, которая возвращает точку входа. Трансляция начинается с этой точки.
def run(fp):
program_contents = ""
while True:
read = os.read(fp, 4096)
if len(read) == 0:
break
program_contents += read
os.close(fp)
program, bm = parse(program_contents)
mainloop(program, bm)
def entry_point(argv):
try:
filename = argv[1]
except IndexError:
print "You must supply a filename"
return 1
run(os.open(filename, os.O_RDONLY, 0777))
return 0
def target(*args):
return entry_point, None
if __name__ == "__main__":
entry_point(sys.argv)Функция entry_point будет принимать аргументы командной строки, когда вы будете запускать получившийся исполняемый файл.
RPython
Давайте поговорим о RPython. PyPy не может транслировать обычный код на Питоне, потому что Питон слегка слишком динамичный. Есть некоторые ограничения, которые накладываются на стандартную библиотеку и синтаксис Питона, чтобы PyPy мог транслировать его. Я не буду перечислять их все, лучше посмотреть их в документации.
В вышеприведенном примере пришлось изменить несколько вещей. Теперь приходится использовать низкоуровневые дескрипторы с функциями os.open и os.read вместо использования файловых объектов. Реализация «.» и «,» тоже немного изменена. Это все изменения, необходимые для того, чтобы PyPy стал переваривать код.
Это было не слишком сложно, правда? Я продолжаю использовать словари, расширяемые списки и даже классы с объектами. И если файловые дескрипторы для вас слишком низкоуровневые, в модуле rlib.streamio, поставляемом вместе со стандартной библиотекой RPython, есть несколько полезных абстракций.
Полный код теперь выглядит так: еxample2.py
Трансляция
Если вы этого еще не сделали, слейте последнюю версию PyPy с репозитория на bitbucket.org.
$ hg clone bitbucket.org/pypy/pypy
Скрипт, который нужно запустить — pypy/translator/goal/translate.py. В качестве параметра он принимает модуль, который нужно оттранслировать.
$ python ./pypy/pypy/translator/goal/translate.py example2.py
Для более быстрой трансляции можно использовать PyPy вместо Питона.
Результатом выполнения станет исполняемый файл — интерпретатор brainfuck. В репозитории лежит генератор фракталов на brainfuck, выполнение которого на моей машине занимает около 45 секунд. Попробуйте сами.
$ ./example2-c mandel.b
И сравните скорость с тем, что выдает этот же интерпретатор, запущенный на Питоне.
$ python example2.py mandel.b
Итак, мы написали интерпретатор на RPython и оттранслировали его с помощью инструментария PyPy.
Добавляем JIT
Трансляция RPython в Си — это конечно круто, но одна из главных фич PyPy — это возможность генерировать компилятор времени выполнения (JIT). Используя всего несколько подсказок о том, как устроен ваш интерпретатор, PyPy сгенерирует JIT-компилятор, который будет переводить интерпретируемый код brainfuck в машинный.
Чтобы это произошло, PyPy должен знать, где начинается цикл выполнения программы. Это позволяет отследить, какие инструкции выполняются на brainfuck.
Мы также должны указать особенности цикла выполнения. Так как в нашем языке нет стека, нам нужно только указать какие переменные относятся к коду программы, а какие к её данным. Это называется зелеными и красными переменными соотвественно.
Вернемся ко второму примеру.
В нашем основном цикле выполнения используются четыре переменных: pc, program, bracket_map и tape. Конечно, pc, program и bracket_map — зеленые переменные, они определяют выполнение интерпретируемой программы. Переменная tape — красная, она изменяется при выполнении интерпретируемой программы.
Давайте сообщим PyPy эти данные. Начнем с импорта класса JitDriver и создания его экземпляра.
from pypy.rlib.jit import JitDriver
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'],
reds=['tape'])И добавим такую строку в самое начало цикла исполнения:
fjitdriver.jit_merge_point(pc=pc, tape=tape, program=program,
bracket_map=bracket_map)Также нам нужно определить JitPolicy.
def jitpolicy(driver):
from pypy.jit.codewriter.policy import JitPolicy
return JitPolicy()Полный текст примера: example3.py
Теперь еще раз оттранслируем код, но уже с флагом --opt=jit:
$ python ./pypy/pypy/translator/goal/translate.py --opt=jit example3.py
Трансляция будет идти значительно дольше, почти 8 минут на моей машине, и получившийся исполняемый файл будет намного больше. После окончания трансляции запустим программу генерации фракталов снова. Разница огромна — примерно 12 секунд против 45 в предыдущем варианте!
Как видите, JIT-компилятор действительно использовал машинный код вместо интерпретации. Несколько первых линий картинки выводятся достаточно быстро, потом программа ускоряется и остальное выводится еще быстрее.
Немного о трассирующих JIT-компиляторах
Стоит поговорить о том, как вообще работают трассирующие JIT-компиляторы. Ваш интерпретирующий код запускается в обычном режиме. Когда JIT встречает часто выполняющийся цикл в интерпретируемом языке (brainfuck), цикл помечается для трассировки. Когда в следующий раз достигается этот же цикл, включается логирование каждой выполненной инструкции.
Полученный лог отправляется в оптимизатор, результат работы которого преобразуется в машинный код. Этот код используется для последующих выполнений цикла.
Получившийся машинный код корректен только при некоторых условиях, при которых он был получен. Поэтому перед его использованием данные условия проверяются. Если проверка не проходит, вместо машинного кода вновь запускается интерпретатор.
Больше информации можно найти в Википедии.
Отладка и логи трассировки
Можем ли мы увидеть, что делает JIT?
Давайте добавим функцию get_printable_location, которая будет использоваться для вывода отладочной информации.
def get_location(pc, program, bracket_map):
return "%s_%s_%s" % (
program[:pc], program[pc], program[pc+1:]
)
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape'],
get_printable_location=get_location)Эта функция принимает зеленые переменные и возвращает сроку. Мы выводим код brainfuck, в котором текущая выполняемая инструкция окружена подчеркиваниями.
Оттранслируйте код примера example4.py.
Теперь запустите тестовую программу (test.b просто выводит букву «A» примерно 15 раз) с выводом логов трассировки.
$ PYPYLOG=jit-log-opt:logfile ./example4-c test.b
Файл logfile содержит логи всех произведенных трассировок и позволяет взглянуть на то, какие инструкции были скомпилированы в машинный код. Файл полезен тем, что позволяет увидеть ненужные инструкции или пути для оптимизации.
Каждая трассировка начинается с линии вроде этой:
[3c091099e7a4a7] {jit-log-opt-loopИ заканчивается такой линией:
[3c091099eae17d jit-log-opt-loop}Сразу после заголовка трассировки идет комментарий с порядковым номером и количество операций. В моем случае первая трассировка выглядит так.
1: [3c167c92b9118f] {jit-log-opt-loop
2: # Loop 0 : loop with 26 ops
3: [p0, p1, i2, i3]
4: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
5: debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
6: i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
7: i6 = int_add(i4, 1)
8: setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
9: debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
10: debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
11: i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
12: i9 = int_sub(i7, 1)
13: setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
14: debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
15: i10 = int_is_true(i9)
16: guard_true(i10, descr=<Guard2>) [p0]
17: i14 = call(ConstClass(ll_dict_lookup__dicttablePtr_Signed_Signed), ConstPtr(ptr12), 90, 90, descr=<SignedCallDescr>)
18: guard_no_exception(, descr=<Guard3>) [i14, p0]
19: i16 = int_and(i14, -9223372036854775808)
20: i17 = int_is_true(i16)
21: guard_false(i17, descr=<Guard4>) [i14, p0]
22: i19 = call(ConstClass(ll_get_value__dicttablePtr_Signed), ConstPtr(ptr12), i14, descr=<SignedCallDescr>)
23: guard_no_exception(, descr=<Guard5>) [i19, p0]
24: i21 = int_add(i19, 1)
25: i23 = int_lt(i21, 114)
26: guard_true(i23, descr=<Guard6>) [i21, p0]
27: guard_value(i21, 86, descr=<Guard7>) [i21, p0]
28: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
29: jump(p0, p1, i2, i3, descr=<Loop0>)
30: [3c167c92bc6a15] jit-log-opt-loop}Я немного обрезал слишком длинные строки debug_merge_point.
Этот участок кода принимает четыре параметра: два указателя на объекты (p0 и p1) и два числа (i2 и i3).
Первый оператор «>» начинается на 4-й строке. Он выполняется без инструкций и выглядит окончательно оптимизированным. Этот цикл всегда работает с одной частью ленты, и указатель на текущую ячейку остается постоянным.
Строки с пятой по восьмую — оператор «+». Сначала извлекается элемент массива с индексом i2 из указателя p1 (строка 6), прибавляется единица и сохраняется в i6 (строка 7). Результат помещается обратно в массив (строка 8).
Строка 9 соответствует инструкции «<», но она тоже не требует операций. Судя по всему — i2 и i3 — это два указателя на ячейки ленты, которые вычислены заранее. Также видно, что p1 — это лента команд. Пока не ясно, что такое p0.
Строки с 10 по 13 выполняют оператор «-»: извлекают элемент массива, вычитают и кладут его обратно.
В 14-й строке мы подходим к оператору «]». Строки 15 и 16 проверяют, является ли i9 истиной (т.е. не равно нулю). i9 — это значение, которое мы только что уменьшили на единицу и положили в ленту. Строка 16 — проверка. Если условие не выполняется, исполняется функция с названием <Guard2>, которой передается один параметр, p0.
Если же проверка пройдена, строки с 17 по 23 достают из словаря bracket_map адрес инструкции, к которой нужно перейти. Я не уверен, что именно делают эти строки, но видно, что в них содержится два внешних вызова и 3 проверки. Это слишком расточительно, учитывая, что bracket_map не меняется и результатом будет один и тот же адрес, на который нужно перейти. Но PyPy об этом не знает, а мы знаем, поэтому можем оптимизировать это место.
Строка 24 увеличивает полученный из bracket_map указатель. Строки 25 и 26 проверяют, что он не превысил длину программы.
Кроме этого в строке 27 проводится дополнительная проверка, что указатель строго равен 86. Это нужно для того, чтобы убедится, что прыжок должен быть сделан в начало цикла.
В конце цикл замыкается на строке 28, и в строке 29 происходит прыжок в начало цикла с параметрами p0, p1, i2, i3.
Оптимизация
Как было замечено, на каждой итерации цикла происходит поиск в словаре для нахождения парной скобки. Это ужасно неэффективно, потому что цель перехода не меняется на разных итерациях.
Нам нужно дать еще одну подсказку транслятору, чтобы сказать, что запрос к словарю всегда вернет одинаковые элементы для одинаковых индексов словаря.
Чтобы это сделать, мы вынесем обращение к словарю в отдельную функцию и обернем её pypy.rlib.jit.purefunction.
@purefunction
def get_matching_bracket(bracket_map, pc):
return bracket_map[pc]Эта версия может быть найдена в example5.py.
Оттранслируйте этот пример. Мандельброт теперь выполняется за 6 секунд вместо 12!
Давайте взглянем на новый лог трассировки.
1: [3c29fad7b792b0] {jit-log-opt-loop
2: # Loop 0 : loop with 15 ops
3: [p0, p1, i2, i3]
4: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
5: debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
6: i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
7: i6 = int_add(i4, 1)
8: setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
9: debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
10: debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
11: i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
12: i9 = int_sub(i7, 1)
13: setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
14: debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
15: i10 = int_is_true(i9)
16: guard_true(i10, descr=<Guard2>) [p0]
17: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
18: jump(p0, p1, i2, i3, descr=<Loop0>)
19: [3c29fad7ba32ec] jit-log-opt-loop}Намного лучше! Теперь каждый цикл — это только одно сложение, вычитание, две загрузки из массива, два помещения в массив и проверка при выходе. Код не требует никаких изменений счетчика команд.
Эту оптимизацию мне подсказал Армин Риго в рассылке pypy-dev. У Карла Фридриха есть несколько статей об оптимизации интерпретаторов, которые тоже оказались полезными.
Заключение
Я надеюсь, эта статья убедила вас в том, что PyPy это не только быстрый интерпретатор Питона.
Для тех из вас, кто хочет больше узнать о JIT-компиляторе PyPy, я рекомендую прочитать статью Tracing the Meta-Level: PyPy's Tracing JIT Compiler.
