КС:2015:Проект:jit — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Итоговая оценка)
 
(не показано 8 промежуточных версии этого же участника)
Строка 5: Строка 5:
  
 
=== Что требуется ===
 
=== Что требуется ===
Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.
+
Вам предлагается реализовать JIT компиляцию регулярных выражений, поддерживаемых re2, в машинный код x86-64.
  
 +
=== Слайды ===
 +
[https://yadi.sk/d/ymlaks89jK69x Лежат тут.]
 
== Чему вы научитесь ==
 
== Чему вы научитесь ==
 
1. Узнаете, как устроена JIT компиляция.
 
1. Узнаете, как устроена JIT компиляция.
Строка 24: Строка 26:
  
 
=== Требования на зачет в конце 1-го модуля ===
 
=== Требования на зачет в конце 1-го модуля ===
В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].
+
Нужно написать библиотеку, которая использует [https://github.com/google/re2/ re2] для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций для виртуальной машины в re2 и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Полученная конструкция работает корректно (re2 и re2jit на поддерживаемых регулярных выражениях дают один и тот же результат).
 +
 
 +
Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].
  
 
=== Итоговая оценка ===
 
=== Итоговая оценка ===
 
* '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.
 
* '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.
 
* '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.
 
* '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.
* '''+N баллов'''. N = 8 * max(0, Sum(1 - Time(jit) / Time(re2))) за обгон re2 на предложенных тестах.
+
* '''+N баллов'''. N = 8 * max(0, aver(1 - T<sub>re2jit</sub> / T<sub>re2</sub>)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).

Текущая версия на 13:09, 25 сентября 2015

Что это за проект

Введение

JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.

Что требуется

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

Слайды

Лежат тут.

Чему вы научитесь

1. Узнаете, как устроена JIT компиляция.

2. Научитесь профилировать код и искать узкие места в производительности.

3. Научитесь писать интерпретаторы с JIT.

Начальные требования

1. Технический английский язык.

2. Знание C++.

3. Любознательность.

Критерии оценивания

Требования на зачет в конце 1-го модуля

Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций для виртуальной машины в re2 и может при помощи libyasm, sljit или libjit компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Полученная конструкция работает корректно (re2 и re2jit на поддерживаемых регулярных выражениях дают один и тот же результат).

Пример того, как можно запустить JIT код, описан в этой статье.

Итоговая оценка

  • 4 балла. Реализованы требования на зачёт в конце первого модуля.
  • 8 баллов. Все инструкции re2 VM компилируются в JIT.
  • +N баллов. N = 8 * max(0, aver(1 - Tre2jit / Tre2)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).