Сравнение интерпретатора, обычного и 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_end
    bracket_0_start:
    
      cmpb $0, (%r12)
      jne bracket_0_start
    bracket_0_end:
    
      cmpb $0, (%r12)
      je bracket_1_end
    bracket_1_start:
    
      cmpb $0, (%r12)
      jne bracket_1_start
    bracket_1_end:
    

    …А для вложенных ([[]]) — следующим (обратите внимание на индексы):

     cmpb $0, (%r12)
      je bracket_0_end
    bracket_0_start:
    
      cmpb $0, (%r12)
      je bracket_1_end
    bracket_1_start:
    
      cmpb $0, (%r12)
      jne bracket_1_start
    bracket_1_end:
    
      cmpb $0, (%r12)
      jne bracket_0_start
    bracket_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(&amp;instruction_stream, opcodes, sizeof(opcodes));
      }
      break;
    case '<':
      {
        char opcodes [] = {
          0x49, 0xFF, 0xCC // dec %r12
        };
        vector_push(&amp;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»