Сравнение интерпретатора, обычного и JIT компиляторов

Рассказывает автор блога Nick Desaulniers

Интерпретаторы и компиляторы — программы, которые используются для трансляции или запуска других программ. Интерпретируемые программы пишутся на языках вроде JavaScript, Ruby, Python, PHP и Perl. Программы, которым требуется компиляция — на C, C++ и, в какой-то степени, Java и C#.

Перевод в машинный код перед запуском (AOT — Ahead-Of-Time) занимает дополнительное время, однако даёт выигрыш в скорости работы. С другой стороны, интерпретатор может приступать к работе без задержек. Между этими двумя мирами есть золотая середина — JIT (Just-In-Time) компиляция. Интерпретация, обычная и JIT компиляция — эти способы могут выглядеть совершенно разными, но, на самом деле, они поразительно похожи. В этой статье я докажу это, продемонстрировав программные коды всех троих (для языка Brainfuck). Каждый занимает примерно 100 строк кода на C и доступен на GitHub.

Немного о самом Brainfuck

Brainfuck — очень интересный (правда, сложный для чтения) полный по Тьюрингу язык. У него есть всего 8 операторов — > < + - . , [ ]. Всё просто, каждый оператор — это символ, посторонние символы игнорируются. В этой статье мы пропустим валидацию кода, сосредоточившиь на интерпретации и компиляции.

Программы на Brainfuck работают с массивом байтов из 30 000 ячеек, инициализированных нулями. Есть также указатель, который изначально указывает на первый элемент этого массива. Операторы же выполняют следующее:

• > < — сдвигают указатель на одну ячейку вправо или влево соответственно;
• + - — увеличивают или уменьшают значение в ячейке на единицу;
• . — выводит в виде символа значение ячейки, на которой находится указатель;
• , — записывает в виде ASCII кода введённое значение в ячейку, на которой находится указатель;
• [ — если значение текущей ячейки нулевое, перейти вперёд к оператору ] (с учётом вложенности);
• ] — если значение текущей ячейки не нулевое, перейти назад к оператору [ (c учётом вложенности).

Интерпретатор

• Инициализация массива и указателя:// Создание массива из 30 000 нулейunsigned char tape [30000] = { 0 };// Установка указателя на первый элементunsigned char* ptr = tape;
• Операторы перемещения указателя:case '>': ++ptr; break;case '<': --ptr; break;
• Инкремент и декремент:case '+': ++(*ptr); break;case '-': --(*ptr); break;
• Ввод и вывод:case '.': putchar(*ptr); break;case ',': *ptr = getchar(); break;
• Операторы цикла:case '[': if (!(*ptr)) { int loop = 1; // Используется для хранения уровня вложенности while (loop > 0) { unsigned char current_char = input[++i]; // i - номер исполняемого опреатора if (current_char == ']') { --loop; } else if (current_char == '[') { ++loop; } } } break;case ']': if (*ptr) { int loop = 1; // Используется для хранения уровня вложенности while (loop > 0) { unsigned char current_char = input[--i];// i - номер исполняемого опреатора if (current_char == '[') { --loop; } else if (current_char == ']') { ++loop; } } } break;

Как видите, в интерпретаторе нет ничего сложного. Получившийся код занимает порядка пятидесяти строк и может выполнить все необходимые операции (правда, не слишком быстро).

Компилятор

Примечание: нижеследующий код предполагает, что вы работаете с x86-64 ISA (Instruction Set Architecture – Архитектура набора команд) и UNIX ABI (Application Binary Interface – Двоичный интерфейс приложений).

В нашем компиляторе мы снова будем проходить по всем символам данной программы, пропуская их через switch. Но вместо того, чтобы выполнять действие, мы будем выводить в stdout инструкции ассемблера. Такой подход требует перенаправления stdout в файл, после чего на этом файле нужно будет запустить ассемблер и компоновщик. Мы с вами сосредоточимся именно на компилировании, а не на ассемблировании и компоновке.

• Для начала подготовим память для нашего компилятора:const char* const prologue = ".text\n" ".globl _main\n" "_main:\n" " pushq %rbp\n" " movq %rsp, %rbp\n" " pushq %r12\n" // Это будет нашим указателем " subq $30008, %rsp\n" // Размещаем 30 008 байтов в стеке " leaq (%rsp), %rdi\n" // Адрес начала нашего хранилища " movl $0, %esi\n" // Заполняем нулями " movq $30000, %rdx\n" // На 30 000 байтов " call _memset\n" // Вызываем memset " movq %rsp, %r12";puts(prologue);Если бы мы выделили 30000 байтов, то результатом выполнения memset стал бы segfault, ведь нам нужно место под указатели. Подробнее о работе со стеком в ассемблере вы можете прочитать в моей предыдущей статье (англ.)
• С операторами сдвига указателя (> <) и инкремента\декремента (+ -) всё просто:case '>': puts(" inc %r12"); break;case '<': puts(" dec %r12"); break;case '+': puts(" incb (%r12)"); break;case '-': puts(" decb (%r12)"); break;
• Для вывода (.) нам нужно скопировать байт с места, на котором стоит указатель, в место для первого аргумента putchar. Однако putchar принимает в качестве аргумента int. В x86-64 есть инструкция, котрая нам нужна – movzXX, где первый X — начальный размер (b, w), а второй — конечный (w, l, q).case '.': puts(" movzbl (%r12), %edi"); puts(" call _putchar"); break;
• Со вводом (,) всё тоже просто — вызываем getchar, перемещаем первые восемь бит в ячейку, помеченную указателем.case ',': puts(" call _getchar"); puts(" movb %al, (%r12)"); //%al - первые восемь бит из 64 %rax break;
• Как и в прошлый раз, с операторами цикла ([ и ]) работы будет больше. Хорошим решением будет использовать прыжки к соответствующим меткам, но проблема в том, что имена меток должны быть уникальными. Я предлагаю следующее — у нас будет переменная, в которой будет хранится количество встреченых открывающих скобок, и стек, в который каждый раз, когда будет встречена открывающая скобка, будет записываться её номер. Когда же будет встречена закрывающая скобка — ей будет соответствовать индекс верхнего элемента стека. Вот, как это выглядит в коде:case '[': stack_push(&stack, num_brackets); // Записываем номер последней встреченной открывающей скобки puts(" cmpb $0, (%r12)"); /// Условие: если в текущей ячейке ноль... printf(" je bracket_%d_end\n", num_brackets); // Если условие выполняется, осуществить прыжок к соответсвующей метке ниже printf("bracket_%d_start:\n", num_brackets++); // Поставить метку начала цикла с соответствующим номером break;case ']': stack_pop(&stack, &matching_bracket); // Достаём из стека номер последней открытой скобки puts(" cmpb $0, (%r12)"); // Условие: если в текущей ячейке ноль... printf(" jne bracket_%d_start\n", matching_bracket); // Если условие НЕ выолняется, осуществить прыжок к соответствующей метке выше printf("bracket_%d_end:\n", matching_bracket); // Поставить метку конца с соответствующим номером break;Таким образом, для соседствующих циклов ([][]) ассемблерный код будет следующим: cmpb $0, (%r12) je bracket_0_endbracket_0_start: cmpb $0, (%r12) jne bracket_0_startbracket_0_end: cmpb $0, (%r12) je bracket_1_endbracket_1_start: cmpb $0, (%r12) jne bracket_1_startbracket_1_end:…А для вложенных ([[]]) — следующим (обратите внимание на индексы): cmpb $0, (%r12) je bracket_0_endbracket_0_start: cmpb $0, (%r12) je bracket_1_endbracket_1_start: cmpb $0, (%r12) jne bracket_1_startbracket_1_end: cmpb $0, (%r12) jne bracket_0_startbracket_0_end:
• В конце нам нужно высвободить ресурсы:const char* const epilogue = " addq $30008, %rsp\n" " popq %r12\n" " popq %rbp\n" " ret\n";puts(epilogue);

Если вам понадобится отладить ваш Brainfuck код, с компилятором это будет ужасно — вам нужно будет компилировать код Brainfuck в код ассемблера, затем ассемблировать его, затем компоновать, и лишь потом вы сможете его запустить. Конечно, с интерперетатором всё проще — он выполняет код сразу же, платя за это быстродействием. Насколько велика разница в скорости, я напишу ниже.

Разве не было бы великолепно, если был бы способ совместить быстродействие компилятора и удобство интерпретатора? Такой способ есть — JIT компиляция.

JIT компилятор

Вы можете ознакомиться с моей предыдущей статьёй (англ.) на эту тему, сейчас мы будем делать ровно то же самое — создадим выполняемую память, запишем туда байткод, потом приведём эту память к ссылке на функцию и вызовем её. Как и в предыдущих разделах, мы будем выполнять действия по мере чтения символов из Brainfuck исходника, однако теперь мы будем записывать опкоды в динамический массив. Он будет равномерно увеличиваться по мере нашего чтения, что в дальнейшем упростит вычисление оффсетов для операторов ветвления.

Ещё одна особенность заключается в том, что мы будем передавать адреса наших libc функций (memset, putchar и getchar) нашим JIT функциям прямо во время исполнения. Я имею в виду, что мы будем делать так:

			typedef void* fn_memset (void*, int, size_t);
typedef int fn_putchar (int);
typedef int fn_getchar ();
void (*jitted_func) (fn_memset, fn_putchar, fn_getchar) = mem;
jitted_func(memset, putchar, getchar);
		

Итак, приступим.

Наш «пролог» — операции для подготовки памяти — достаточно сложный, поэтому я буду расписывать его пошагово.

• Начнём как обычно:

			char prologue [] = {

  0x55, // push rbp
  0x48, 0x89, 0xE5, // mov rsp, rbp
		

• Теперь нам нужно сохранить указатели на наши функции: 0x41, 0x54, // pushq %r12 0x41, 0x55, // pushq %r13 0x41, 0x56, // pushq %r14 0x49, 0x89, 0xFC, // movq %rdi, %r12 (memset) 0x49, 0x89, 0xF5, // movq %rsi, %r13 (putchar) 0x49, 0x89, 0xD6, // movq %rdx, %r14 (getchar)
• Затем выделим 30 008 байт на стеке: 0x48, 0x81, 0xEC, 0x38, 0x75, 0x00, 0x00, // subq $30008, %rspЗдесь мы столкнулись с числом больше байта. Где же в этой инструкции число 30 008? Оно в следующих четырёх байтах: 0x38, 0x75, 0x00, 0x00. Замечу, что если человек привык воспринимать числа в системе «Big Endian», в которой младшие разряды находятся справа, то здесь необходимо использовать «Little Endian». То есть, 0x38, 0x75, 0x00, 0x00 в «Little Endian» — это 0x00, 0x00, 0x75, 0x38 в «Big Endian», оба обозначают 7*16^3+5*16^2+3*16^1+8*16^0 или 30008 в десятичной системе.
• Теперь подготавливаем и запускаем memset: // Адрес начала хранилища 0x48, 0x8D, 0x3C, 0x24, // leaq (%rsp), %rdi // Заполняем нулями 0xBE, 0x00, 0x00, 0x00, 0x00, // movl $0, %esi // Длина 30,000 байтов 0x48, 0xC7, 0xC2, 0x30, 0x75, 0x00, 0x00, // movq $30000, %rdx // Вызываем memset 0x41, 0xFF, 0xD4, // callq *%r12
• На этом этапе нам больше не нужен memset, поэтому его место (%r12) занимает указатель на текущую ячейку: 0x49, 0x89, 0xE4 // movq %rsp, %r12};

С «прологом» на этом всё.

• Добавим «пролог» в наш динамический массив:vector_push(&instruction_stream, prologue, sizeof(prologue))
• Теперь перебираем символы Brainfuck программы. С инкрементом и декрементом всё по-старому:case '+': { char opcodes [] = { 0x41, 0xFE, 0x04, 0x24 // incb (%r12) }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;case '-': { char opcodes [] = { 0x41, 0xFE, 0x0C, 0x24 // decv (%r12) }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;Дополнительный блок кода ({ char opcodes...}) нужен из-за того, что в C\C++ мы не можем создавать переменные прямо внутри switch.
• Сдвиги указателя:сase '>': { char opcodes [] = { 0x49, 0xFF, 0xC4 // inc %r12 }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;case '<': { char opcodes [] = { 0x49, 0xFF, 0xCC // dec %r12 }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;
• Ввод и вывод:case '.': { char opcodes [] = { 0x41, 0x0F, 0xB6, 0x3C, 0x24, // movzbl (%r12), %edi 0x41, 0xFF, 0xD5 // callq *%r13 }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;case ',': { char opcodes [] = { 0x41, 0xFF, 0xD6, // callq *%r14 0x41, 0x88, 0x04, 0x24 // movb %al, (%r12) }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;
• Мы дошли до операторов цикла — это самая интересная часть. При написании компилятора мы оставили вычисление оффсетов (отступов) ассемблеру. Теперь нам придётся самим решать следующую проблему: на сколько байтов нам нужно перескочить вперёд, чтоб мы попали к закрывающей скобке, которую мы ещё не видели? Мы поступим следующим образом:case '[': { char opcodes [] = { 0x41, 0x80, 0x3C, 0x24, 0x00, // cmpb $0, (%r12) // Будет исправлено: 0x0F, 0x84, 0x00, 0x00, 0x00, 0x00 // je <32b relative offset, 2's compliment, LE> }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } stack_push(&relocation_table, instruction_stream.size); // создаём метку break;Сейчас мы оставили оффсет пустым (четыре нулевых байта), но мы позже вернёмся к этому. Сейчас мы записываем в relocation_table текущий размер массива инструкций, а по совместительству — место последней встреченной открывающей скобки. Вся магия раскрывается, когда мы встретим закрывающую скобку. Сначала мы просто записываем незаконченные инструкции в динамический массив, как и в случае с открывающей скобкой:ase ']': { char opcodes [] = { 0x41, 0x80, 0x3C, 0x24, 0x00, // cmpb $0, (%r12) // Будет исправлено: 0x0F, 0x85, 0x00, 0x00, 0x00, 0x00 // jne <33b relative offset, 2's compliment, LE> }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); }…Затем мы вычисляем оффсет: // ... stack_pop(&relocation_table, &relocation_site); relative_offset = instruction_stream.size - relocation_site; // ...…А теперь записываем его вместо нулей (4 — не магическая константа, это количество байт, которые мы оставили пустыми): // ... vector_write32LE(&instruction_stream, instruction_stream.size - 4, -relative_offset); vector_write32LE(&instruction_stream, relocation_site - 4, relative_offset); break;
• Снова подчищаем за собой:char epilogue [] = { 0x48, 0x81, 0xC4, 0x38, 0x75, 0x00, 0x00, // addq $30008, %rsp 0x41, 0x5E, // popq %r14 0x41, 0x5D, // popq %r13 0x41, 0x5C, // popq %r12 0x5d, // pop rbp 0xC3 // ret};vector_push(&instruction_stream, epilogue, sizeof(epilogue));
• Теперь запускаем наши инструкции и чистим всё в последний раз:void* mem = mmap(NULL, instruction_stream.size, PROT_WRITE | PROT_EXEC, MAP_ANON | MAP_PRIVATE, -1, 0);memcpy(mem, instruction_stream.data, instruction_stream.size);void (*jitted_func) (fn_memset, fn_putchar, fn_getchar) = mem;jitted_func(memcpy, putchar, getchar);munmap(mem, instruction_stream.size);vector_destroy(&instruction_stream);

Тесты, сравнение и заключение

Теперь уже должно быть понятно, что интерпретатор, обычный и JIT компиляторы по своей структуре не сильно-то различаются. Сравните сдвиг указателя вправо во всех трёх:

• Интерпретатор:case '>': ++ptr; break;
• Компилятор:case '>': puts(" inc %r12"); break;
• JIT компилятор:case '>': { char opcodes [] = { 0x49, 0xFF, 0xC4 // inc %r12 }; vector_push(&instruction_stream, opcodes, sizeof(opcodes)); } break;

Или сравните исходники интерпретатора, обычного и JIT компиляторов.

Давайте теперь проверим их быстродействие. Одна из самых «тяжёлых» программ, которую я смог найти — вывод в консоль множества Мандельброта в виде ASCII арта.

			$ time ./interpreter ../samples/mandelbrot.b
43.54s user 0.03s system 99% cpu 43.581 total

$ ./compiler ../samples/mandelbrot.b > temp.s; ../assemble.sh temp.s; time ./a.out
3.24s user 0.01s system 99% cpu 3.254 total

$ time ./jit ../samples/mandelbrot.b
3.27s user 0.01s system 99% cpu 3.282 total
		

Интерпретатор оказался гораздо медленнее остальных — это из-за того, что его переходы по [ ] выполняются за О(N), когда остальные имеют возможность выполнить прыжок за О(1). Интерпретатор просматривает исходник в поисках оператора, затем его выполняет, после чего снова возращается к файлу. Компиляторы сначала транслируют код, затем выполняют его, не смешивая.

Обычный компилятор, как и предполагалось, оказался самым быстрым. Однако что, если мы попробуем посчитать время вместе с компиляцией?

			$ time (./compiler ../samples/mandelbrot.b > temp.s; ../assemble.sh temp.s; ./a.out)
3.27s user 0.08s system 99% cpu 3.353 total
		

Теперь он работает чуть-чуть дольше, чем JIT. Какой из этого можно сделать вывод? Если время компиляции невелико (как у Brainfuck) — стоит выбирать JIT компилятор. Однако, если вам необходимо выполнять массивные программы на настоящих языках, а время компиляции будет значительным — вы явно захотите потратить время на компиляцию лишь один раз, а значит — выберете обычный компилятор.

Перевод статьи «Interpreter, Compiler, JIT»