КС:2015:Проект:jit

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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