Сім видів інтерпретаторів віртуальної машини. У пошуках самого швидкого

Всі проблеми в області Computer Science можуть бути вирішені введенням додаткового рівня побічності. За винятком одного: занадто великого числа рівнів побічності.
All problems in computer science can be solved by another level of indirection, except for the problem of too many layers of indirection.
Програмні інтерпретатори відомі своєю невисокою швидкістю роботи. У цій статті я розповім, як їх можна прискорити.
Я давно вже хотів детальніше зупинитися на створенні інтерпретаторів. Прямо таки обіцяв, у тому числі самому собі. Проте серйозний підхід вимагав використання більш-менш реалістичного коду для прикладів, а також проведення вимірювань продуктивності, що підтверджують (а іноді і спростовують) мої аргументи. Але нарешті-то я готовий представити поважній публіці результати, причому навіть трохи більш цікаві, ніж збирався.
У даній статті буде описано сім способів побудови програмної ВМ для однієї гостьової системи. Від самих повільних ми проследуем більш швидким, по черзі позбавляючись від різних «неэффективностей» в коді, і в кінці порівняємо їх роботу на прикладі однієї програми.
Тих, хто не боїться ассемблерних лістингів, поцяткованого макросами коду на Сі, рясно хімічного адресної арифметикою, goto і навіть longjmp, а також програм, що використовують копіпаст в ім'я швидкості або навіть створюють шматки самих себе, прошу просимо під кат.


Інтерпретатори — клас програм, які аналізують написаний на деякій вхідній мові текст по одній фразі (висловом, твердженням, інструкції, інший смислової одиниці) за раз і негайно виконують визначені цією фразою дії. Цим вони відрізняються, наприклад, від трансляторів, в яких фази розбору вхідного мови і виконання дій рознесені в часі.
Це визначення досить загальне, і під нього потрапляють багато програм, в тому числі реалізують віртуальні машини (ВМ). Останні можна розділити на два класу: мовні і системні.

Слід попередити, що більшість ідей, про які я буду розповідати, були знайдені досить давно [3, 4]. Більше того, подібне порівняння швидкості різних типів інтерпретаторів (для дуже примітивною ВМ) вже проводилося [2]. Є навіть російськомовні книги радянського часу [1] на цю тему.

1. Я дозволю собі обмежитись хазяйської архітектурою Intel® 64. При цьому вимірювання будуть робитися тільки для однієї машини. Я закликаю всіх читачів чітко розуміти, що деталі архітектури та мікроархітектури (такі, як організація провісника переходів) безпосередньо впливають на швидкість роботи програм, особливо інтерпретаторів. Більш того, може виявитися, що алгоритм A, що працює швидше алгоритму B на архітектурі Z, буде програвати йому на системі Y.

2. Приклади коду були зроблені з розрахунком на переносимість між системами. Вони повинні коректно оброблятися популярними в даний час версіями компіляторів GCC і ICC на POSIX-системах. На нечисленні «непортабильные» місця я буду вказувати окремо.

3. Розповідь орієнтований на інтерпретатори, створювані для потреб симуляції центральних процесорів. Специфіка даної предметної області впливає на структуру рішення. Наприклад, далі звертається увага на нетривіальність фази декодування вхідного машинного мови, тоді як у відомих мені роботах ця задача вважається тривіальною (розв'язуваної за допомогою оператора ідентичності).

4. У цій статті нічого не сказано про розбір граматики, тобто про ту частину інтерпретації, необхідну для побудови інтерпретаторів мов високого рівня. У книзі Terrence Parr [5], творця ANTLR — потужного фреймворку для створення лексеров, парсерів і генераторів, якісно і детально розкривається це питання.

Отже, спершу опис того, що будемо моделювати — специфікація віртуальної машини.

Архітектура досліджуваної ВМ
Повний код прикладів, а також Makefile для складання і скрипт для тестування продуктивності опубліковані тут: github.com/grigory-rechistov/interpreters-comparison.
Далі я буду цитувати деякі шматки коду звідти і відсилати читача до конкретних іменах файлів і функцій.

Для потреб цієї статті я хотів використовувати ВМ, досить просту, щоб встигнути написати і відлагодити кілька варіантів її реалізації за прийнятний час, але при цьому досить складну, щоб на ній виявлялися різні ефекти, властиві реальним проектам, і щоб на ній можна було виконувати хоча б мінімально корисну програму, а не просто нудний псевдовипадковий потік інструкцій.
В цілому ця ВМ натхненна мовою Форт. У порівнянні з ним вона сильно спрощено і має тільки ті інструкції, які були необхідні для ілюстрації описаних у статті ідей. Найважливіші, на мій погляд, її упущення (спрощення) порівняно з нормальним Фортом — відсутність процедурного механізму і словника.
Хочу зазначити, що всі наведені далі приклади можуть бути безпосередньо пристосовані не тільки для стекових, але і регістрових ВМ.

  1. Ширина машинного слова — 32 біта. Всі операнди та інструкції — це знакові або беззнакові 32-бітні цілі числа
  2. Три стану процесора: Running — активне виконання інструкцій; Halted — зупинка після виконання Halt, відповідає нормальному завершення програми; Break — зупинка після будь ненормальною, непідтримуваних або викликала нестандартне стан інструкції, означає помилку в програмі. Іншими словами, ВМ починає працювати в змозі Running. Закінчує роботу вона в змозі Halted, якщо в процесі роботи не сталося ніяких непередбачених подій і виконання досягло інструкції Halt. Якщо відбулося ділення на нуль, вихід за межі коду, переповнення або спустошення стека, або щось ще, що мені не захотілося підтримувати при реалізації, вона зупиняється в режимі Break.
  3. Всі регістри — неявні, а всього їх два. PC — покажчик поточної команди. SP — покажчик вершини стека. На початку роботи PC=0, SP=-1.
  4. Стек параметрів глибиною 32 беззнакових цілих слова. SP вказує на поточний елемент, або ж дорівнює -1, якщо стек порожній.
  5. Програмна пам'ять ємністю 512 слів, доступний тільки на читання. При виході за межі [0; 511] процесор зупиняється в стані Break.
  6. Інструкції можуть мати нуль або один явний операнд (imm). У першому випадку вони мають довжину в одне слово, у другому — два.
  7. Опис усіх машинних інструкцій. Коди операцій, а також інші елементи архітектури ВМ, описані у файлі common.h.
    Опис набору інструкційBreak = 0x0000 — перевести процесор в стан Break. Так як неинициализированная програмна пам'ять заповнена нулями, будь випадковий перехід «повз коду» призводить до зупинки.
    Nop = 0x0001 — порожня команда, не змінює стек і SP.
    Halt = 0x0002 — перевести процесор в стан Halted.
    Push = 0x0003 imm — помістити константу imm на вершину стека.
    Print = 0x0004 — зняти з вершини стека значення і роздрукувати його в десятковому вигляді.
    JNE = 0x0005 imm — зняти з вершини стека значення, і, якщо воно не дорівнює нулю, додати imm до PC. imm при цьому трактується як число зі знаком.
    Swap = 0x0006 — переставити місцями вершину стека і наступний за ний елемент.
    Dup = 0x0007 — помістити на вершину стека копію самого верхнього елементу.
    JE = 0x0008 imm — зняти з вершини стека значення, і, якщо воно дорівнює нулю, додати imm до PC. imm при цьому трактується як число зі знаком.
    Inc = 0x0009 — додати до вершини стека одиницю.
    Add = 0x000a — скласти два верхні елементи стека. Зняти їх зі стека і помістити результат як вершину.
    Sub = 0x000b — відняти з верхнього елемента стека наступний за ним. Зняти їх зі стека і помістити результат на вершину.
    Mul = 0x000c — перемножити два верхні елементи стека. Зняти їх зі стека і помістити результат як вершину.
    Rand = 0x000d — помістити на вершину стека випадкове число.
    Dec = 0x000e — відняти з вершини стека одиницю.
    Drop = 0x000f — зняти з вершини стека число і «викинути» його.
    Over = 0x0010 — помістити на вершину стека копію елемента, який є другим у стеку після вершини.
    Mod = 0x0011 — поділити верхній елемент стеку на наступний за ним. Зняти їх зі стека і помістити залишок від ділення на вершину.
    Jump = 0x0012 imm — додати imm до PC. imm при цьому трактується як число зі знаком.

    Арифметичні операції, що призводять до переповнення (крім ділення на нуль), не викликають переходу в стан Break і ніяк не сигналізуються.
    Зазначу, що всі інструкції, включаючи керуючі виконанням (тобто Jump, JE, JNE), безумовно просувають PC на свою довжину в кінці виконання. Це слід враховувати при обчисленні зміщення адреси переходу. Тобто стрибок вважається від початку інструкції, наступного для поточної.

  8. Виконання будь інструкції, не визначеною в архітектурі явно, еквівалентно виконанню Break.
  9. Для потреб налагодження процесор містить 64-бітний регістр steps, збільшується на одиницю після кожної виконаної інструкції ВМ. Програми дозволяють задати межа числа кроків, після якого симуляція переривається. За замовчуванням він дорівнює LLONG_MAX.
  10. Після завершення програми симуляції виводять стан процесора і стека на екран.


Бенчмарк

Для порівняння продуктивності потрібна була програма, написана для цієї ВМ. Вона повинна бути досить довгою, з нетривіальним потоком управління, не використовувати надмірно введення-виведення, тобто бути обчислювально-складною. І при цьому бути досить простий, щоб такий розсіяний людина, як я зміг би налагодити її в машинних кодах навіть без нормально працюючого симулятора. В результаті вийшло те, що я назвав Простих чисел.
Простих чисел виводить на екран всі прості числа, які містяться на відрізку від 2 до 100000. Її код для ВМ міститься в масиві Простих чисел[], однаково оголошеному у всіх прикладах.
Простихconst Instr_t Простих чисел[PROGRAM_SIZE] = {
Instr_Push, 100000, // nmax (maximal number to test)
Instr_Push, 2, // nmax, c (minimal number to test)
/* back: */
Instr_Over, // nmax, c, nmax
Instr_Over, // nmax, c, nmax, c
Instr_Sub, // nmax, c, c-nmax
Instr_JE, +23, /* end */ // nmax, c
Instr_Push, 2, // nmax, c, divisor
/* back2: */
Instr_Over, // nmax, c, divisor, c
Instr_Over, // nmax, c, divisor, c, divisor
Instr_Swap, // nmax, c, divisor, divisor, c
Instr_Sub, // nmax, c, divisor, c-divisor
Instr_JE, +9, /* print_prime */ // nmax, c, divisor
Instr_Over, // nmax, c, divisor, c
Instr_Over, // nmax, c, divisor, c, divisor
Instr_Swap, // nmax, c, divisor, divisor, c
Instr_Mod, // nmax, c, divisor, c mod divisor
Instr_JE, +5, /* not_prime */ // nmax, c, divisor
Instr_Inc, // nmax, c, divisor+1
Instr_Jump, -15, /* back2 */ // nmax, c, divisor
/* print_prime: */
Instr_Over, // nmax, c, divisor, c
Instr_Print, // nmax, c, divisor
/* not_prime */
Instr_Drop, // nmax, c
Instr_Inc, // nmax, c+1
Instr_Jump, -28, /* back */ // nmax, c
/* end: */
Instr_Halt // nmax, c (== nmax)
};

В моїх запусках вона виконувалася від половини до трьох хвилин. Її алгоритм приблизно (з поправкою на стекову архітектуру) відповідає програмі, що міститься у файлі native.c.
main() з native.cint main() {
for (int i = 2; i < 100000; i++) {
bool is_prime = true;
for (int divisor = 2; divisor < i; divisor++) {
if (i % divisor == 0) {
is_prime = false;
break;
}
}
if (is_prime)
printf("[%d]\n", i);
}
return 0;
}


Зауваження про оптимізацію
Один вводить в оману бенчмарк може допомогти досягти того, що неможливо одержати за роки хорошою інженерної роботи.
A misleading benchmark test can accomplish in minutes what years of good engineering can never do.
dilbert.com/strip/2009-03-02


Я хочу ще раз підкреслити один дуже важливий момент в оптимізації продуктивності додатків: нікому не можна вірити. Особливо якщо хтось говорить щось на кшталт: «використовуй алгоритм X замість твого Y, тому що він завжди швидше». Не можна вірити проспектах виробників апаратури, статтями творців компіляторів, обіцянкам авторів бібліотек. Не можна вірити своєму чуттю — в питаннях пошуку вузьких місць у продуктивності воно бреше ще як. Вірити можна тільки результатами вимірювань і профилировки, і то не завжди.

Тим менше можна вірити мені. Дійсно — програма Простих чисел, яку я використовую для порівняння продуктивності, сміховинно наївна: мало того, що вона навряд чи створює скільки-небудь істотну навантаження на всі підсистеми процесора, так ще й алгоритм, використаний у ній, неоптимален! У самому справі, для великих N немає потреби перевіряти подільність N на N-1, достатньо перевірити дільники від 2 до √N. Вона навіть не використовує всі доступні інструкції, які я так ретельно писав!
Та й ВМ, чого вже там, трохи коштує. Обсяги ресурсів крихітні, навіть 8-розрядні мікроконтролери часто складніше. Без механізмів виклику процедур і обробки виключень далеко не заїдеш. Можливо, в наступному семестрі я змушу студентів розширити її до пуття монструозных розмірів, хехехе!

Але не варто забувати, що весь цей матеріал служить лише ілюстративній меті. Якби симулятор був реалістично складний, а бенчмарк-програма була б реальних розмірів, то деякі захотіли б читати їх.

Зауваження про оптимізацію стосується всього подальшого матеріалу даної статті. На іншому поколінні хазяйських процесорів з іншою версією компілятора цілком може виявитися, що самий повільний код цієї статті обжене всі інші варіанти. Я сам був здивований, отримавши графіки — деякі результати не відповідали моїм очікуванням; більше того, різні компілятори вивели в лідери різних учасників. Але я знову забігаю вперед.

Перемикається (switched)

Перша схема побудови інтерпретатора є найпопулярнішою перемикається інтерпретатор (файл switched.c). Її код природним чином висловлює базовий цикл «вважати код операції — розпізнати — виконати — повторити». Так як це перша ця схема, розглянемо, як всі фази цього циклу виражаються в коді ВМ; надалі будемо звертати увагу лише на відмінності (ніхто ж не хоче читати сотні рядків схожого коду).

Функція fetch() зчитує «сирий код» операції, що знаходиться за адресою PC. Так як інтерпретатор моделює системну ВМ, необхідно бути готовим до виходу PC за кордону пам'яті; за перевірку відповідає fetch_checked().

код fetch() і fetch_checked()static inline Instr_t fetch(const cpu_t *pcpu) {
assert(pcpu);
assert(pcpu->pc < PROGRAM_SIZE);
return pcpu->pmem[pcpu->pc];
};

static inline Instr_t fetch_checked(cpu_t *pcpu) {
if (!(pcpu->pc < PROGRAM_SIZE)) {
printf("PC out of bounds\n");
pcpu->state = Cpu_Break;
return Instr_Break;
}
return fetch(pcpu);
}


Функція decode() повинна завершити розпочате в fetch() — повністю визначити характеристики команди. У нашому випадку це її довжина (1 або 2) та значення літерального операнда для тих інструкцій, у яких він є. Крім того, за прийнятими угодами всі невідомі опкоды вважаються еквівалентними Break. Все це з'ясовується в результаті роботи одного оператора switch.
Особливість обробки «довгих» інструкцій з операндом: вони вимагають додаткового читання пам'яті команд за адресою PC+1, який також необхідно проконтролювати на вихід за її межі.

код decode()static inline decode_t decode(Instr_t raw_instr, const cpu_t *pcpu) {
assert(pcpu);
decode_t result = {0};
result.opcode = raw_instr;
switch (raw_instr) {
case Instr_Nop:
case Instr_Halt:
case Instr_Print:
case Instr_Swap:
case Instr_Dup:
case Instr_Inc:
case Instr_Add:
case Instr_Sub:
case Instr_Mul:
case Instr_Rand:
case Instr_Dec:
case Instr_Drop:
case Instr_Over:
case Instr_Mod:
result.length = 1;
break;
case Instr_Push:
case Instr_JNE:
case Instr_JE:
case Instr_Jump:
result.length = 2;
if (!(pcpu->pc+1 < PROGRAM_SIZE)) {
printf("PC+1 out of bounds\n");
pcpu->state = Cpu_Break;
break;
}
result.immediate = (int32_t)pcpu->pmem[pcpu->pc+1];
break;
case Instr_Break:
default: /* Undefined instructions equal to Break */
result.length = 1;
result.opcode = Instr_Break;
break;
}
return result;
}

Для більш реалістичних архітектур процедура декодування програмної ВМ кілька складніше: доведеться шукати по дереву префіксів, тобто проходити через серію вкладених switch. Але я думаю, що загальну ідею передати вдалося.

Нарешті, виконання — за кодом операції, отриманого з decode(), переходимо на сервісну процедуру (service routine) — блок коду, відповідальний за семантику конкретної гостьовий інструкції. Ще один switch, у всій його красі довжині.
код switchuint32_t tmp1 = 0, tmp2 = 0;
/* Execute — a big switch */
switch(decoded.opcode) {
case Instr_Nop:
/* Do nothing */
break;
case Instr_Halt:
cpu.state = Cpu_Halted;
break;
case Instr_Push:
push(&cpu, decoded.immediate);
break;
case Instr_Print:
tmp1 = (pop&cpu); BAIL_ON_ERROR();
printf("[%d]\n", tmp1);
break;
case Instr_Swap:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1);
push(&cpu, tmp2);
break;
case Instr_Dup:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1);
push(&cpu, tmp1);
break;
case Instr_Over:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp2);
push(&cpu, tmp1);
push(&cpu, tmp2);
break;
case Instr_Inc:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1+1);
break;
case Instr_Add:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 + tmp2);
break;
case Instr_Sub:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 — tmp2);
break;
case Instr_Mod:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp2 == 0) {
cpu.state = Cpu_Break;
break;
}
push(&cpu, tmp1 % tmp2);
break;
case Instr_Mul:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 * tmp2);
break;
case Instr_Rand:
tmp1 = rand();
push(&cpu, tmp1);
break;
case Instr_Dec:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1-1);
break;
case Instr_Drop:
(void) (pop&cpu);
break;
case Instr_JE:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp1 == 0)
cpu.pc += decoded.immediate;
break;
case Instr_JNE:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp1 != 0)
cpu.pc += decoded.immediate;
break;
case Instr_Jump:
cpu.pc += decoded.immediate;
break;
case Instr_Break:
cpu.state = Cpu_Break;
break;
default:
assert("Unreachable" && false);
break;
}


Тут і далі BAIL_ON_ERROR служить для перехоплення можливих винятків, що виникли в ході виконання окремих команд:

#define BAIL_ON_ERROR() if (cpu.state != Cpu_Running) break;

На жаль, це Сі, і використовувати нормальний try-catch не вийде (однак стривайте, ближче до кінця статті буде дещо схоже на нього).
Спостережливий читач може здивуватися — навіщо використовуються два switch: decode() і в main(), — адже вони викликаються один за іншим і управляються однією і тією ж величиною, тобто можуть бути об'єднані. Необхідність такого поділу стане зрозуміла в наступній секції, де ми позбавимося від необхідності постійно викликати decode().

Попереднє декодування (pre-decoding)

Перше, від чого слід позбутися — це декодування на кожному кроці симуляції (файл predecoded.c). У самому справі, вміст програми не змінюється в процесі роботи, або змінюється дуже нечасто: при завантаженні нових додатків або динамічних бібліотек, зрідка самим додатком (JIT-програма, дописывающая свої шматки). У нашій ВМ взагалі немає можливості змінити програму в процесі виконання, і цим треба скористатися.

код predecode_program()static void predecode_program(const Instr_t *prog,
decode_t *dec, int len) {
assert(prog);
assert(dec);
/* The program is short, so we can decode it as a whole.
Otherwise, some sort of lazy decoding will be required */
for (int i=0; i < len; i++) {
dec[i] = decode_at_address(prog, i);
}
}


Оскільки в пам'яті програм цієї ВМ всього 512 слів, нам доступна можливість декодувати її всю відразу і зберегти результат в масиві, індексованому значенням PC. У реальних ВМ з обсягами гостьовий пам'яті 232–2⁶⁴ байт цей трюк не пройшов би. Довелося б використовувати структуру а-ля кеш з витісненням, який в обмеженому обсязі хазяйської пам'яті зберігав би робоче безліч відповідностей «PC → decode_t». При цьому доводилося б вносити нові запису в кеш декодованих інструкцій при симуляції. Однак і в цьому випадку був би виграш у швидкості. При повторному виконанні нещодавно виконаних інструкцій їх не довелося б заново декодувати.

Ну а так — викличемо predecode_program() до виконання:
Код з попередніми декодуваннямdecode_t decoded_cache[PROGRAM_SIZE];
predecode_program(cpu.pmem, decoded_cache, PROGRAM_SIZE);

while (cpu.state == Cpu_Running && cpu.steps < steplimit) {
if (!(cpu.pc < PROGRAM_SIZE)) {
printf("PC out of bounds\n");
cpu.state = Cpu_Break;
break;
}

decode_t decoded = decoded_cache[cpu.pc];
uint32_t tmp1 = 0, tmp2 = 0;
/* Execute — a big switch */
switch(decoded.opcode) {
case Instr_Nop:
/* Do nothing */
break;
case Instr_Halt:
cpu.state = Cpu_Halted;
break;
case Instr_Push:
push(&cpu, decoded.immediate);
break;
case Instr_Print:
tmp1 = (pop&cpu); BAIL_ON_ERROR();
printf("[%d]\n", tmp1);
break;
case Instr_Swap:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1);
push(&cpu, tmp2);
break;
case Instr_Dup:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1);
push(&cpu, tmp1);
break;
case Instr_Over:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp2);
push(&cpu, tmp1);
push(&cpu, tmp2);
break;
case Instr_Inc:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1+1);
break;
case Instr_Add:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 + tmp2);
break;
case Instr_Sub:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 — tmp2);
break;
case Instr_Mod:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp2 == 0) {
cpu.state = Cpu_Break;
break;
}
push(&cpu, tmp1 % tmp2);
break;
case Instr_Mul:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 * tmp2);
break;
case Instr_Rand:
tmp1 = rand();
push(&cpu, tmp1);
break;
case Instr_Dec:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1-1);
break;
case Instr_Drop:
(void) (pop&cpu);
break;
case Instr_JE:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp1 == 0)
cpu.pc += decoded.immediate;
break;
case Instr_JNE:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp1 != 0)
cpu.pc += decoded.immediate;
break;
case Instr_Jump:
cpu.pc += decoded.immediate;
break;
case Instr_Break:
cpu.state = Cpu_Break;
break;
default:
assert("Unreachable" && false);
break;
}
cpu.pc += decoded.length; /* Advance PC */
cpu.steps++;
}


Два зауваження.
1. Попереднє декодування призводить до того, що на етапі виконання команд не виконується фаза Fetch. При цьому виникає ризик некоректної симуляції архітектурних ефектів, з нею пов'язаних, таких як спрацьовування апаратних точок зупину. Ця проблема вирішувана акуратним стеженням за введеним кешем.
2. На відміну від системних ВМ, у мовних ВМ, які зазвичай мають дуже просту структуру команд, фази fetch і decode тривіальні. Тому для них подібне кешування незастосовне.

Наскільки позбавлення від декодування прискорило симуляцію? Дозволю собі зберегти інтригу до кінця статті, де будуть порівнюватися всі варіанти інтерпретаторів. А поки що спробуємо зрозуміти, як далі прискорити наш інтерпретатор.
Як я вже писав, інтуїція в цьому випадку — поганий помічник. Звернемося до неупередженим інструментів: використовуємо Intel® VTune Amplifier XE 2015 Update 4 для проведення «General Exploration» для predecoded. В оглядовому звіті червоним виділені проблемні, з точки зору аналізатора, аспекти роботи програми:



«Bad speculation»??? Який-такий спекулянт? Незрозуміло. «Branch Mispredict» — вже ясніше. Якийсь умовний або непрямий перехід в нашій програмі постійно викликає помилку провісника переходів. При цьому подію замість корисної роботи процесор змушений спустошити конвеєр і почати виконання іншої інструкції. При цьому виникає простий в пару десятків тактів.
Але звідки в такій простій програмі така проблема? Починаємо спускатися нижче. Клікаю на «Branch Mispredict», відкривається вид Bottom-up, в якому показується головний підозрюваний — main().



Нда, зрозуміліше не стало. Спробуємо пошукати рядок програми. Клікаємо на main(), відкривається вид на исходник програми (завчасно зібраної з символьною інформацією). Відкриваємо обидва види — Source і Assembly, і уважно дивимося на стовпці «Branch Mispredict». Зізнатися, не відразу мені вдалося знайти те, що треба, хоч я й знав, де і що шукати.



На цьому скріншоті підсвічені блакитним рядки вихідного коду і відповідного йому коду машинного. Ось це так — наш головний switch і відповідна йому команда «jmpq 0x400f20(,%rdx,8)» мають стовідсотково (1.000) неправильні передбачення! Як так? Причина — в обмеженнях апаратури з передрікання таких переходів.

Провісник адрес непрямих переходів (branch target predictor) намагається передбачити, куди відбудеться перехід в поточному виконанні jmp, грунтуючись на обмеженому наборі історичних даних, таких як адреса самій інструкції та історія переходів з неї. У нашому випадку історія переходів — це історія виконання команд гостя всередині ВМ. Однак для Простих вона абсолютно хаотична — після push може йти як ще один push, так і over, після over можуть йти over, sub, swap; число ітерацій внутрішнього циклу велика і весь час змінюється і т. д.
Умовні переходиДуже хороший практичний приклад, який ілюструє аналогічне вплив провісника умовних переходів на швидкість роботи програми, мається на Stackoverflow: попереднє сортування випадкового масиву прискорює алгоритм фільтрації на ньому.


Пенальті від неправильного пророкування адреси переходу тим вірогідніше, чим більше число інструкцій є в ВМ — за цієї причини я відмовився від ідеї використовувати BF-машину в якості піддослідного: всього 8 інструкцій могли виявитися недостатніми.

Шитий (threaded)
«СЕПУЛЬКИ — важливий елемент цивілізації ардритов з планети Энтеропия. См. СЕПУЛЬКАРИИ».
Я послухався поради і прочитав:
«СЕПУЛЬКАРИИ — пристрої для сепуления».
Я пошукав «Сепуление»; там значилося:
«СЕПУЛЕНИЕ — заняття ардритов з планети Энтеропия. См. СЕПУЛЬКИ».

Станіслав Лем. «Зоряні щоденники Ійона Тихого. Подорож чотирнадцяте.»


З причиною низької продуктивності розібралися. Почнемо її усувати. Необхідно допомогти віщуну переходів. При цьому, звичайно, непогано б знати, як він працює, в деталях. За відсутністю (або небажанням звертатися до) деталей використовуємо загальні міркування. Згадаймо, що провісник використовує адресу самої інструкції для асоціації з нею історії переходів. От би вдалося «розмазати» єдиний jmp за кількома місцями; з кожним з них пов'язана своя локальна історія, яка, можна сподіватися, буде менш хаотичної для здійснення адекватних прогнозів.
Саме це я намагався зробити у файлах threaded.c і threaded-cached.c (варіант, що включає також попереднє декодування).
Суть рішення: після виконання поточної сервісної процедури не повертатися в загальну точку (switch), а переходити відразу на сервісну процедуру наступної інструкції.
Погана новина №1 для переходу по мітці доведеться використовувати оператор goto. Так, так, знаю, goto це погано, мкей, я і сам писав про це. Заради швидкості — у всі тяжкі. У коді ВМ це буде заховане в макросі DISPATCH:
Код DISPATCH#define DISPATCH() do {\
goto *service_routines[decoded.opcode]; \
} while(0);


Погана новина №2: доведеться використовувати нестандартне (відсутнє в стандарті Сі) розширення мови GCC — оператор взяття адреси мітки &&:
Визначення масиву міток service_routines:const void* service_routines[] = {
&&sr_Break, &&sr_Nop, &&sr_Halt, &&sr_Push, &&sr_Print,
&&sr_Jne, &&sr_Swap, &&sr_Dup, &&sr_Je, &&sr_Inc,
&&sr_Add, &&sr_Sub, &&sr_Mul, &&sr_Rand, &&sr_Dec,
&&sr_Drop, &&sr_Over, &&sr_Mod, &&sr_Jump, NULL
};

Цей нестандартний оператор підтримується компіляторами GCC і ICC для мови Сі (але, наскільки мені відомо, не для C++).
В результаті головний «цикл» (який насправді не робить ні однієї ітерації) інтерпретатора виглядає ось так:
Код main() з threaded-cached.cdecode_t decoded = {0};
DISPATCH();
do {
sr_Nop:
/* Do nothing */
ADVANCE_PC();
DISPATCH();
sr_Halt:
cpu.state = Cpu_Halted;
ADVANCE_PC();
/* No need to dispatch after Halt */
sr_Push:
push(&cpu, decoded.immediate);
ADVANCE_PC();
DISPATCH();
sr_Print:
tmp1 = (pop&cpu); BAIL_ON_ERROR();
printf("[%d]\n", tmp1);
ADVANCE_PC();
DISPATCH();
sr_Swap:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1);
push(&cpu, tmp2);
ADVANCE_PC();
DISPATCH();
sr_Dup:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1);
push(&cpu, tmp1);
ADVANCE_PC();
DISPATCH();
sr_Over:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp2);
push(&cpu, tmp1);
push(&cpu, tmp2);
ADVANCE_PC();

DISPATCH();
sr_Inc:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1+1);
ADVANCE_PC();
DISPATCH();
sr_Add:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 + tmp2);
ADVANCE_PC();
DISPATCH();
sr_Sub:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 — tmp2);
ADVANCE_PC();
DISPATCH();
sr_Mod:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp2 == 0) {
cpu.state = Cpu_Break;
break;
}
push(&cpu, tmp1 % tmp2);
ADVANCE_PC();
DISPATCH();
sr_Mul:
tmp1 = (pop&cpu);
tmp2 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1 * tmp2);
ADVANCE_PC();
DISPATCH();
sr_Rand:
tmp1 = rand();
push(&cpu, tmp1);
ADVANCE_PC();
DISPATCH();
sr_Dec:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
push(&cpu, tmp1-1);
ADVANCE_PC();
DISPATCH();
sr_Drop:
(void) (pop&cpu);
ADVANCE_PC();
DISPATCH();
sr_Je:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp1 == 0)
cpu.pc += decoded.immediate;
ADVANCE_PC();
DISPATCH();
sr_Jne:
tmp1 = (pop&cpu);
BAIL_ON_ERROR();
if (tmp1 != 0)
cpu.pc += decoded.immediate;
ADVANCE_PC();
DISPATCH();
sr_Jump:
cpu.pc += decoded.immediate;
ADVANCE_PC();
DISPATCH();
sr_Break:
cpu.state = Cpu_Break;
ADVANCE_PC();
/* No need to dispatch after Break */
} while(cpu.state == Cpu_Running);


Симуляція починається з першого DISPATCH і потім відбувається як чехарда стрибків між сервісними процедурами. Число хазяйських інструкцій непрямих переходів в коді зросла, і кожен їх них тепер має асоційовану історію для пари гостьових інструкцій. Ймовірність невдалого передбачення при цьому падає (в [4] стверджується, що з 100% до 50%).

Дана техніка має назву шитий код, по-англійськи — threaded code; врахуйте, що сучасний термін «thread — потік» з'явився значно пізніше і не має відношення до теми.
Дана оптимізація і в наш час використовується у цілком популярних проектах. Процитую пост Utter_step habrahabr.ru/post/261575 від 1 липня цього року:
Vamsi Parasa з команди оптимізації серверних скриптових мов Intel запропонував патч <...>, переводить блок switch, відповідальний за обробку Python-байткода, на використання computed goto, як це вже зроблено в Python 3. пояснював Eli Bendersky, в такому величезному switch-блоці, як в блоці розбору байткода в CPython (що складається з більш ніж 2000(!) рядків), це дає прискорення близько 15-20%. Це відбувається з двох причин: computed goto, на відміну від switch-case, не виробляє граничних перевірок, необхідних для оператора switch за стандартом C99, і, що, можливо, більш важливо, CPU може краще прогнозувати розгалуження в таких ситуаціях <...>


Однак при вимірі швидкості інтерпретатора, одержуваного з threaded.c з прапорами компіляції за замовчуванням (програма threaded-notune), я одержав несподіваний результат. Швидкість роботи програми виявилася на 10%-20% нижче switched. Аналіз VTune показав, що причина гальм все та ж — 100% Branch Mispredict на одному з непрямих переходів усередині DISPATCH:



Однак щось тут не так — для всіх інших DISPATCH взагалі немає ніякої статистики. Більш того, VTune не показує для них асемблерний код. Перевірка дизассемблированием з допомогою objdump підтвердила підозри — у всьому тілі main() був тільки один непрямий перехід, пов'язаний з переходом на сервісні процедури:

$ objdump-d threaded-notune| grep 'jmpq\s*\*%rdx'
4006c8: ff e2 jmpq *%rdx
400ae7: ff e2 jmpq *%rdx

(Другий jmpq за адресою 400ae7 — з функції register_tm_clones, — не відноситься до справи). Що ж виходить — компілятор GCC в результаті процесу оптимізації послужливо сплющила всі DISPATCH в один, фактично заново побудувавши перемикається інтерпретатор!

Компілятор — заклятий друг
Тут почалася моя боротьба з компілятором. Я витратив досить багато часу, щоб змусити GCC генерувати код з незалежними непрямими переходами для кожної сервісної процедури.
  • Перевірив різні рівні оптимізації. Правильний код виходив тільки при-Og, рівні оптимізацій з-O1 по-O3 схлопывали DISPATCH.
  • Намагався замінити goto на ассемблерну вставку і тим самим приховати від компілятора сам факт переходу по мітці:

    #define DISPATCH() \
    __asm__ __volatile__("mov(%0, %1, 8), %%rcx\n" \
    "jmpq *%%rcx\n" \
    :: "r"(&service_routines), "r"((uint64_t)decoded.opcode): "%rcx");

    У цьому випадку компілятор все одно об'єднував схожі блоки коду. При цьому всі мітки (sr_Add, sr_Nop і т. д.) стали вказувати в одне і те ж місце, і всі значення в масиві service_routines стали однаковими. Програма перестала коректно працювати.
  • Спробував вивести заповнення масиву service_routines з-під контролю компілятора, щоб він не зміг пересувати мітки: зробив вміст невизначеним і лише потім заповнював масив. Ігри з невизначеним поведінкою не могли закінчитися добре. На цей раз GCC законно порахував весь код після першого DISPATCH недосяжним і повністю видалив його!


Якщо ніщо інше не допомагає, прочитайте, нарешті, інструкцію.
Аксіома Кана


Отже, груба сила не допомогла. Довелося все-таки читати документацію і намагатися зрозуміти, яка оптимізація заважає моїм задумом. На третьому вікні списку опцій оптимізацій я побачив наступне:
Please note the warning under-fgcse about invoking-O2 on programs that use computed gotos.
<...>
Note: When compiling a program using computed gotos, a GCC extension, you may get better run-time performance if you disable the global common subexpression elimination pass by adding-fno-gcse to the command line.


Попалася! Це оптимізація-fgcse перетворювала код threaded в ассемблерное спагетті. Схоже, що з подібною проблемою стикалися і інші, див. наприклад, коментар до посту «Fast interpreter using gcc's computed goto»:
I have the same problem as Philip. With G++ the compiler seems to go though incredible contortions to preserve a single indirect jump. Even going so far as to combine jumps separate from the tables — with a series of direct jumps. This seems utterly bewildering behaviour as it specially breaks the performance gain having a jmp \*%eax for each interpreter leg.


Після з'ясування питання з-fno-gcse генерований код став більше схожий на те, що вимагалося:
Пошук непрямих переходів в threaded c допомогою objdump$ objdump-d threaded| grep 'jmpq\s*\*%rdx'
4006c8: ff e2 jmpq *%rdx
40070d: ff e2 jmpq *%rdx
40084e: ff e2 jmpq *%rdx
4008bd: ff e2 jmpq *%rdx
40093d: ff e2 jmpq *%rdx
4009b1: ff e2 jmpq *%rdx
400a3b: ff e2 jmpq *%rdx
400aa2: ff e2 jmpq *%rdx
400b15: ff e2 jmpq *%rdx
400b89: ff e2 jmpq *%rdx
400c0b: ff e2 jmpq *%rdx
400c80: ff e2 jmpq *%rdx
400cd8: ff e2 jmpq *%rdx
400d3f: ff e2 jmpq *%rdx
400d90: ff e2 jmpq *%rdx
400dea: ff e2 jmpq *%rdx
400e44: ff e2 jmpq *%rdx
400e8c: ff e2 jmpq *%rdx
400f97: ff e2 jmpq *%rdx


Ще раз про те, за рахунок чого повинно виникнути прискорення. З допомогою реорганізації коду ми розв'язали один вузол у виконанні всіх симулируемых інструкцій, замінивши його на більш дрібні вузли локальних переходів між парами інструкцій. Мабуть, цю ідею можна розвинути і далі — допомогти віщуну переходів правильно запам'ятовувати історію виконання трійок, четвірок і т. д. за рахунок відповідного «розбухання» коду. Наприклад, мати по дві копії всіх сервісних процедур, і всередині DISPATCH вибирати тільки одну з них, в залежності від коду попередньої інструкції та її адреси, або якогось іншого критерію. Однак залишу це в якості вправи зацікавився дослідникам.

Після виключення невдалої оптимізації швидкість threaded стала краще. Наскільки — описано в кінці статті. А зараз перейдемо до наступного типу інтерпретатора.

Процедурний (subroutined)
Але що це я все про goto та інші гидоти. Пора згадати про нормальний і загальноприйнятий спосіб організації програм — процедурний механізм (файл subroutined.c). Оформимо код кожної сервісної процедури у вигляді функції типу service_routine_t:

typedef void (*service_routine_t)(cpu_t *pcpu, decode_t* pdecode);

Приклад сервісної процедури:

void sr_Dec(cpu_t *pcpu, decode_t *pdecoded) {
uint32_t tmp1 = pop(pcpu);
BAIL_ON_ERROR();
push(pcpu, tmp1-1);
}

Ініціалізація масиву service_routines[] тепер використовує стандартний оператор взяття адреси функції:
Масив service_routinesservice_routine_t service_routines[] = {
&sr_Break, &sr_Nop, &sr_Halt, &sr_Push, &sr_Print,
&sr_Jne, &sr_Swap, &sr_Dup, &sr_Je, &sr_Inc,
&sr_Add, &sr_Sub, &sr_Mul, &sr_Rand, &sr_Dec,
&sr_Drop, &sr_Over, &sr_Mod, &sr_Jump
};


Сам головний цикл інтерпретації тепер виглядає набагато більш компактно. На кожній ітерації виконується функція за адресою, відповідного опкоду операції.
main() для subroutinedwhile (cpu.state == Cpu_Running && cpu.steps < steplimit) {
decode_t decoded = fetch_decode(&cpu);
if (cpu.state != Cpu_Running) break;
service_routines[decoded.opcode](&cpu, &decoded); /* Call the SR */
cpu.pc += decoded.length; /* Advance PC */
cpu.steps++;
}


Проте аналіз у VTune показує всю ту ж проблему — поганий прогноз для переходів для єдиного непрямого переходу при виклику функції:



Поки що незрозуміло, чи буде subroutined працювати швидше switched. Звичайно, можна застосувати попереднє декодування — залишу це в якості вправи. Ми ж спробуємо на основі subroutined зробити зшитий інтерпретатор. При цьому «той, хто нам заважає, той нам допоможе!». Я кажу про компіляторі.

Процедурний з хвостової рекурсією (tailrecursive)
Ноги, крила… Головне — хвіст!


Прошу читачів звернути увагу на код файлу tailrecursive.c. Порівняно з subroutined.c в ньому відбулися такі зміни.
Кожна сервісна процедура тепер закінчується викликом fetch_decode() для наступної за нею інструкції і макросом DISPATCH():

void sr_Dec(cpu_t *pcpu, decode_t *pdecoded) {
uint32_t tmp1 = pop(pcpu);
BAIL_ON_ERROR();
push(pcpu, tmp1-1);
ADVANCE_PC();
*pdecoded = fetch_decode(pcpu);
DISPATCH();
}

Код макросу DISPATCH:

#define DISPATCH() service_routines[pdecoded->opcode](pcpu, pdecoded);

Тобто кожна процедура наприкінці викликають процедуру, эмулирующую наступну інструкцію, і потім завершується. Код main(), в якому начебто має відбуватися цикл інтерпретації, виглядає не менш дивно:

decode_t decoded = fetch_decode(&cpu);
service_routines[decoded.opcode](&cpu, &decoded);

І все. Тобто просто викликається сервісна процедура для першої гостьовий інструкції. Вона ж, як ми бачили, в кінці своєї роботи викликає процедуру для наступної інструкції, та — для третьої…
Але постійте, як це може працювати?! Адже, заглиблюючись в симуляцію, ми отримаємо зростаючий стек викликів, який вмить переповниться, і програма впаде. Однак цього не відбувається.
Причина в тому, що перехід в викликану процедуру відбувається перед самим виходом з зухвалою — так званий хвостовий виклик. При цьому ніякого контексту для викликаючої процедури зберігати не потрібно — вона фактично завершилася. Тому і на стеку зберігати нічого не обов'язково. Досить розумний компілятор замінить фінальний call на jmp, при цьому стек викликів не збільшиться.
У GCC за таку оптимізацію відповідає прапор-foptimize-sibling-calls (включений, починаючи з-O1). Якщо її вимкнути (програма tailrecursive-noopt), то симуляція працює, але швидко падає. У мене вона не добігла до 90000 інструкції:

$ ./tailrecursive-noopt 90000 > /dev/null
Segmentation fault (dumped core)

Аналіз tailrecursive в VTune показав наступне. По-перше, верхні місця в списку «гарячого» коду зайняли fetch(_decode) і decode:



Мабуть, подальшим кроком має бути оптимізація (позбавлення) декодування.

По-друге, компілятор дійсно оптимізував хвостові виклики, замінивши call на jmpq. Наприклад, ось код функції sr_Swap(), що викликає безліч Branch Mispredict:



Рудиментарний двійковий транслятор (binary translation)
Для тих відважних читачів, що добралися до цього місця, я підготував ще одну реалізацію ВМ (файл translated.c). Формально ця програма відноситься до класу інтерпретаторів: у ній є генерація машинного коду, відповідного вхідний гостьовій програмі (трансляція). Однак, як ми побачимо, translated недалеко пішла від інтерпретаторів. Так, в ній теж присутня фаза попереднього декодування, виконання, як і в шитом коді, стрибає від однієї сервісної процедури до іншої.

Є і важлива відмінність. Весь наведений раніше код — це Сі, і він може бути скомпільовано і запущений на будь-POSIX-платформі.
На чому тестувалися прикладиНу, може бути, з незначними правками під особливості конкретної платформи. Зрештою, я тестував його всього на двох системах: Ubuntu 12.04 і Windows 8.1 (Cygwin). Всі інтерпретатори працюють. А ось translated під Cygwin мені поки що запустити не вдалося — виклик mprotect() повертає «Invalid argument».
translated ж явно зав'язаний на хазяйську архітектуру Intel 64 (x86_64, AMD64, x64...), і не запрацює ні на який інший. Потрібна суттєва модифікація функції translate_program() і ще декількох місць.

Цей транслятор «рудиментарний», так як його автор полінувався зробити капсули по-людськи. Він служить лише ілюстративним цілям. Я описав два способи побудови двійкових трансляторів у цій статті.

Розберемо найбільш важливі місця в коді програми.

Перевірка платформи#ifndef __x86_64__
/* The program generates machine code, only specific platforms are supported */
#error This program is designed to compile only on Intel64/AMD64 platform.
#error Sorry.
#endif

Як я вже сказав, програма запрацює тільки на Intel 64. В іншому випадку препроцесор видасть помилку ще на стадії компіляції.

Прибиваємо цвяхами pcpu до R15/* Global pointer to be accessible from generated code.
Uses GNU extension to statically occupy host R15 register. */
register cpu_t * pcpu asm("r15");

Для прискорення доступу до найбільш часто використовуваної структурі cpu_t, зберігає архітектурну стан модельованого процесора, статично виділяється хазяйський регістр R15. Для цього використовується нестандартне GNU-розширення, і тому програма компілюється з прапором-std=gnu11 (дивись Makefile), тоді як всі інші — із прапором-std=c11.

Область для генерованого кодуchar gen_code[JIT_CODE_SIZE] __attribute__ ((section (".text#")))
__attribute__ ((aligned(4096)));

Масив gen_code отримав два атрибута. По-перше, адресу його початку повинен бути вирівняний на розмір сторінки. По-друге, я розміщую його в секції коду (.text), а не в секції даних.data), де взагалі-то місце нормальним змінним. Оскільки ми будемо в нього писати код, краще, щоб він був ближче до решти коду програми. Однак писати в gen_code поки що не можна — секція .text за замовчуванням захищена від запису.

Вхід і вихід з згенерованого кодуstatic void enter_generated_code(void* addr) {
__asm__ __volatile__ ( "jmp *%0"::"r"(addr):);
}

static void exit_generated_code() {
longjmp(return_buf, 1);
}

Вхід в транслированный код відбувається простим стрибком на початок необхідного блоку всередині масиву gen_code. Вихід зроблений через longjmp() — визначений у стандарті Сі механізм нелокального goto (ніби звичайного goto було мало). Ця штука дозволяє вистрибнути з функції в будь-яку іншу з ланцюжка викликали її, місце, позначене з допомогою setjmp() з тим же значенням аргументу (return_buf).
Цей механізм досить корисний при написанні двійкового транслятора, оскільки спрощує логіку обробки виняткових ситуацій. exit_generated_code() викликається всюди в коді, де необхідно сигналізувати про перехід до стану Halted/Break, а також при нелінійному зміну PC. Зізнатися, я, схоже, бовкнув зайвого — розкидав longjmp по всьому коду.

Код сервісних процедурvoid sr_Drop() {
(void) (pop pcpu);
ADVANCE_PC(1);
}

void sr_Je(int32_t immediate) {
uint32_t tmp1 = pop(pcpu);
if (tmp1 == 0)
pcpu->pc += immediate;
ADVANCE_PC(2);
if (tmp1 == 0) /* Non-sequential PC change */
exit_generated_code();
}

Процедури для інструкцій ВМ, що не мають операнда (наприклад, Drop), оперують тільки глобально певним pcpu. Процедури для інструкцій з операндом (наприклад, Je) отримують його в першому аргументі. Якщо згенерований код буде викликати їх, то він повинен дотримуватися ABI господарської системи. У разі System V ABI (використовується в Linux) перший аргумент — це регістр RDI.

Код translate_program()static void translate_program(const Instr_t *prog,
char *out_code, void **entrypoints, int len) {
assert(prog);
assert(out_code);
assert(entrypoints);

/* An IA-32 instruction "MOV RDI, imm32" is used to pass a parameter
to a function invoked by following a CALL. */
#ifdef __CYGWIN__ /* Win64 ABI, use RCX instead of RDI */
const char mov_template_code[]= {0x48, 0xc7, 0xc1, 0x00, 0x00, 0x00, 0x00};
#else
const char mov_template_code[]= {0x48, 0xc7, 0xc7, 0x00, 0x00, 0x00, 0x00};
#endif
const int mov_template_size = sizeof(mov_template_code);

/* An IA-32 instruction "CALL rel32" is used as a trampoline to invoke
service routines. A template for it is "call .+0x00000005" */
const char call_template_code[] = { 0xe8, 0x00, 0x00, 0x00, 0x00 };
const int call_template_size = sizeof(call_template_code);

int i = 0; /* Address of current guest instruction */
char* cur = out_code; /* Where to put new code */

/* The program is short, so we can translate it as a whole.
Otherwise, some sort of lazy decoding will be required */
while (i < len) {
decode_t decoded = decode_at_address(prog, i);
entrypoints[i] = (void*) cur;

if (decoded.length == 2) { /* Guest instruction has an immediate */
assert(cur + mov_template_size — out_code < JIT_CODE_SIZE);
memcpy(cur, mov_template_code, mov_template_size);
/* Patch template with correct immediate value */
memcpy(cur + 3, &decoded.immediate, 4);
cur += mov_template_size;
}

assert(cur + call_template_size — out_code < JIT_CODE_SIZE);
memcpy(cur, call_template_code, call_template_size);
intptr_t offset = (intptr_t)service_routines[decoded.opcode]
— (intptr_t)cur — call_template_size;
if (offset != (intptr_t)(int32_t)offset) {
fprintf(stderr, "Offset to service routine for opcode %d"
" does not fit in 32 bits. Cannot generate code for it, sorry",
decoded.opcode);
exit(2);
}
uint32_t offset32 = (uint32_t)offset;
/* Patch template with correct offset */
memcpy(cur + 1, &offset, 4);
i += decoded.length;
cur += call_template_size;
}
}


Самий складний блок програми вимагає детального розгляду. В результаті роботи цієї функції по вмісту гостьової програми prog довжиною len повинні бути заповнені два масиви: out_code — хазяйським гостьовим кодом, симулирующим послідовність інструкцій з prog, і масив покажчиків entrypoints на початку індивідуальних капсул всередині out_code.
Кожна гостьова інструкція декодується, після чого транслюється в одну або дві хазяйських інструкції. Для гостьових інструкцій без операндів це «call rel32», для інструкцій з операндом — пара «mov imm, %rdi; call rel32». RDI тут, тому що викликаються процедури очікують побачити в ньому свій аргумент.
rel32 — це 32-бітовий зсув адреси викликається функції по відношенню до поточної інструкції. Для кожної нової інструкції CALL воно різне, тому воно кожен раз вираховується (offset32) щодо поточного стану.
Чому я використовував тут відносні адреси, а не абсолютні? Тому що господарська система використовує 64-бітові адреси, і для передачі 64 біт в CALL потрібна була б ще одна інструкція і ще один регістр. З-за цього gen_code розміщений у секції коду — щоб всі зміщення вміщалися в 32 біта. Адже секція даних може бути поміщена дуже далеко від коду.
Зауважте, що як код шаблонів (mov_template_code і call_template_code), так і подальші маніпуляції з ними (виклики memcpy()) залежать способи кодування хазяйських інструкцій. При портуванні перекладена на іншу архітектуру їх доведеться виправити в першу чергу.

Результат трансляції програми Простих, отриманий з допомогою GDB у момент закінчення роботи translate_program():
Хазяйський код для Простих(gdb) disassemble gen_code, gen_code+4096
Dump of assembler code from 0x403000 to 0x404000:
0x0000000000403000 <gen_code+0>: mov $0x186a0,%rdi
0x0000000000403007 <gen_code+7>: callq 0x4020c0 <sr_Push>
0x000000000040300c <gen_code+12>: mov $0x2,%rdi
0x0000000000403013 <gen_code+19>: callq 0x4020c0 <sr_Push>
0x0000000000403018 <gen_code+24>: callq 0x4029a0 <sr_Over>
0x000000000040301d <gen_code+29>: callq 0x4029a0 <sr_Over>
0x0000000000403022 <gen_code+34>: callq 0x402720 <sr_Sub>
0x0000000000403027 <gen_code+39>: mov $0x17,%rdi
0x000000000040302e <gen_code+46>: callq 0x4021a0 <sr_Je>
0x0000000000403033 <gen_code+51>: mov $0x2,%rdi
0x000000000040303a <gen_code+58>: callq 0x4020c0 <sr_Push>
0x000000000040303f <gen_code+63>: callq 0x4029a0 <sr_Over>
0x0000000000403044 <gen_code+68>: callq 0x4029a0 <sr_Over>
0x0000000000403049 <gen_code+73>: callq 0x4027e0 <sr_Swap>
0x000000000040304e <gen_code+78>: callq 0x402720 <sr_Sub>
0x0000000000403053 <gen_code+83>: mov $0x9,%rdi
0x000000000040305a <gen_code+90>: callq 0x4021a0 <sr_Je>
0x000000000040305f <gen_code+95>: callq 0x4029a0 <sr_Over>
0x0000000000403064 <gen_code+100>: callq 0x4029a0 <sr_Over>
0x0000000000403069 <gen_code+105>: callq 0x4027e0 <sr_Swap>
0x000000000040306e <gen_code+110>: callq 0x4028c0 <sr_Mod>
0x0000000000403073 <gen_code+115>: mov $0x5,%rdi
0x000000000040307a <gen_code+122>: callq 0x4021a0 <sr_Je>
0x000000000040307f <gen_code+127>: callq 0x402300 <sr_Inc>
0x0000000000403084 <gen_code+132>: mov $0xfffffffffffffff1,%rdi
0x000000000040308b <gen_code+139>: callq 0x402080 <sr_Jump>
0x0000000000403090 <gen_code+144>: callq 0x4029a0 <sr_Over>
0x0000000000403095 <gen_code+149>: callq 0x402460 <sr_Print>
0x000000000040309a <gen_code+154>: callq 0x4022a0 <sr_Drop>
0x000000000040309f <gen_code+159>: callq 0x402300 <sr_Inc>
0x00000000004030a4 <gen_code+164>: mov $0xffffffffffffffe4,%rdi
0x00000000004030ab <gen_code+171>: callq 0x402080 <sr_Jump>
0x00000000004030b0 <gen_code+176>: callq 0x402060 <sr_Halt>
0x00000000004030b5 <gen_code+181>: callq 0x4020a0 <sr_Break>
0x00000000004030ba <gen_code+186>: callq 0x4020a0 <sr_Break>
0x00000000004030bf <gen_code+191>: callq 0x4020a0 <sr_Break>
0x00000000004030c4 <gen_code+196>: callq 0x4020a0 <sr_Break>
0x00000000004030c9 <gen_code+201>: callq 0x4020a0 <sr_Break>
0x00000000004030ce <gen_code+206>: callq 0x4020a0 <sr_Break>
<...>

Ще раз зазначу: на момент початку роботи translated цього коду не існувало.
Звичайно, замість того, щоб без кінця їх викликати, правильніше було б підставити тіла самих сервісних процедур в out_code. При цьому було б заощаджено часу на входах і виходах в функції. Але довелося б щось робити з прологами-эпилогами процедур, тобто вчитися инлайнить код за списной у компілятора. Я залишу це вправа читачам, що бажають глибше розібратися з питаннями кодогенерации.

Нарешті, вивчимо відбувається в main():
main() всередині translate/* Code section is protected from writes by default, un-protect it */
if (mprotect(gen_code, JIT_CODE_SIZE, PROT_READ | PROT_WRITE | PROT_EXEC)) {
perror("mprotect");
exit(2);
}
/* Pre-populate resulting code buffer with INT3 (machine code 0xCC).
This will help to catch jumps to wrong locations */
memset(gen_code, 0xcc, JIT_CODE_SIZE);
void* entrypoints[PROGRAM_SIZE] = {0}; /* a map of guest PCs to capsules */

translate_program(cpu.pmem, gen_code, entrypoints, PROGRAM_SIZE);

setjmp(return_buf); /* Will get here from generated code. */

while (cpu.state == Cpu_Running && cpu.steps < steplimit) {
if (cpu.pc > PROGRAM_SIZE) {
cpu.state = Cpu_Break;
break;
}
enter_generated_code(entrypoints[cpu.pc]); /* Will not return */
}


По-перше, обов'язково необхідно дозволити запис у gen_code. Це робиться за допомогою системного виклику mprotect(). Потім на всякий випадок заповнимо gen_code цілком однобайтовим інструкцією INT3 — 0xcc. Якщо при виконанні згенерованого коду щось піде не так, і управління передадуть на незаповнений ділянку масиву, відразу відбудеться переривання, що полегшить налагодження.
Потім транслюємо програму і встановлюємо точку повернення з допомогою setjmp(). Саме сюди, на початок циклу while(), буде повертатися виконання.

Цикл while кожен раз буде передавати управління, використовуючи в якості адреси значення з відображення entrypoints для поточного PC. Можливо, виникло питання — а навіщо взагалі виходити з gen_code до закінчення роботи згенерованого коду?

Зверніть свою увагу ще раз на лістинг gen_code вище. У ньому немає жодної інструкції галуження — все MOV і CALL виконуватися послідовно. Однак у вихідній програмі були цикли!
Трансляція гостьових інструкцій переходів — це складний момент: зміщення адрес гостьового коду в загальному випадку нелінійним чином пов'язані зі зсувами між капсулами коду хазяйського. Я обійшов цю складність, використовуючи наступний трюк. Всі сервісні процедури, що змінили PC нелінійним чином (тобто Jump, JE, JNE), зобов'язані викликати exit_generated_code(). І вже зовнішній код, використовуючи збережені значення в entrypoints, заново зайде в гостьовій код за правильною адресою. Для інших, «звичайних» сервісних процедур, longjmp не потрібен — вони просто провалюються на наступну за кодом процедуру.

У мене є ідея, як обійтися без longjmp усередині процедур для JNE, JE і Jump. Можна дізнатися наступну точку входу з entrypoints відразу усередині процедури, і помістити додаткове значення адреси повернення RIP на стеку так, щоб при виході з поточної процедури виявитися не викликала її функції, а відразу в потрібній процедурі! Ще одна вправа для допитливого читача — реалізувати цю ідею.

Вузькі місця змінилися. Тепер VTune позначив головною проблемою «Front End Bound»:


В верх списку потрапили сервісні процедури, що можна певною мірою вважати успіхом:


Зазначу, що для динамічно створюваного коду VTune очікувано не може асоціювати символьну інформацію. Однак цей інструмент надає JIT Profiling API, дозволяє відзначити вхід і вихід в регіони генерованого коду. translated його не використовує, але для серйозної профилировки він явно став би в нагоді.

Хто кого — вимірювання

Для тестових прогонів використовувався старий, але все ще жвавий ноутбук Lenovo Thinkpad X220i.
  • ОС: Ubuntu 12.04.5 LTS, Linux версії 3.2.0-75-generic x86_64
  • Процесор: Intel® Core(TM) i3-2310M CPU @ 2.10 GHz
  • 4 Гбайт ОЗУ


Компілятори:
  • GCC 4.8.1-2ubuntu1~12.04
  • ICC 15.0.3 20150407


Порівнювані варіанти програм.
  • switched — перемикається інтерпретатор.
  • threaded — шитий інтерпретатор.
  • predecoded — перемикається інтерпретатор з попередніми декодуванням.
  • subroutined — процедурний інтерпретатор.
  • threaded-cached — шитий з попередніми декодуванням інтерпретатор.
  • tailrecursive — процедурний інтерпретатор з оптимізованими хвостовими викликами.
  • translated — двійковий транслятор.
  • native — реалізація алгоритму Простих Сі. Не зовсім чесно порівнювати статичну програму з реалізаціями ВМ, здатної виконати довільний код. Тим не менше, в порівнянні native бере участь, щоб показати потенціал до можливого прискорення.


Проведення експериментів автоматизировалось з допомогою скрипта measure.sh. Для кожного варіанту вимірювався час виконання п'яти прогонів програми і обчислювалося середнє значення.

Для GCC:


predecoded працює лише трохи швидше switched. З незрозумілих мені причин простий threaded так і залишився повільніше switched. А ось поєднання попереднього декодування з шитим кодом, threaded-cached, дало помітний приріст. Дивно добре показали себе процедурний інтерпретатор subroutined і процедурний з хвостовими оптимизациями tailrecursive. Очікувано було і те, що translated обійшов всі інтерпретатори.

Для ICC:


Ці результати ще більш дивні. Абсолютно найгірший результат показав threaded, незважаючи на всі мої старання. predecoded ж, навпаки, настільки швидкий, що у мене виникли сумніви в коректності його виконання. Однак додаткові перевірки і повторні вимірювання не виявили проблем. threaded-cached обійшов по швидкості процедурні варіанти, майже зрівнявшись з translated, який, у свою чергу, не найшвидший.

Зазначу, що ICC не зрозумів мої спроби допомогти з генерацією коду для шитих варіантів, оскільки не всі опції GCC він розуміє:

icc-std=c11-O2-Wextra-Werror-gdwarf-3-fno-gcse-fno-thread-jumps-fno-cse-follow-jumps-fno-crossjumping-fno-cse-skip-blocks-fomit-frame-pointer threaded-cached.c-o threaded-cached
icc: command line warning #10006: ignoring unknown option '-fno-gcse'
icc: command line warning #10006: ignoring unknown option '-fno-thread-jumps'
icc: command line warning #10006: ignoring unknown option '-fno-cse-follow-jumps'
icc: command line warning #10006: ignoring unknown option '-fno-crossjumping'
icc: command line warning #10006: ignoring unknown option '-fno-cse-skip-blocks'

Звичайно, дуже цікаво було б вивчити причини аномалій, виявлених на збірках ICC. Але стаття і без цього розбухла до непристойних розмірів, так що дозволю собі відкласти цей аналіз на наступний раз.

Висновок

Як і очікувалося, різні техніки побудови інтерпретаторів розрізняються по швидкості. Однак не можна заздалегідь, тільки з структури коду ВМ, зробити висновки про те, який з варіантів буде швидше на практиці. Більше того, різні техніки можна комбінувати, але що при цьому виникають ефекти не підсумовуються: подивіться, як змінювалася продуктивність при використанні тільки попереднього декодування або шитого коду, і який ефект вийшов від їх спільного використання.
Чималу, і не завжди позитивну роль при цьому відіграє компілятор. В залежності від застосованих їм оптимізацій дуже проста схема інтерпретації може показати себе добре, а ось супернавороченная опинитися у хвості списку.
Стаття написана, совість моя перед самим собою чиста, пора і у відпустку. Спасибі за увагу!

Література

  1. Баранов С. Н., Ноздрунов Н. Нар. Мова Форт і його реалізації. 1988 Видавництво «Машинобудування» 2.1. Шитий код і його різновиди www.netlib.narod.ru/library/book0001/ch02_01.htm
  2. M. Anton Ertl. 2007. Speed of various interpreter dispatch techniques V2 www.complang.tuwien.ac.at/forth/threading
  3. James E. Smith and Ravi Nair. Virtual machines – Versatile Platforms for Systems and Processes. Elsevier, 2005. ISBN 978-1-55860-910-5.
  4. M. Anton Ertl and David Gregg. The structure and performance of efficient interpreters // Journal of Instruction-Level Parallelism 5 (2003), pp. 1-25. www.jilp.org/vol5/v5paper12.pdf
  5. Terrence Parr. Language Implementation Patterns — The Pragmatic Bookshelf, 2010. ISBN-10: 1-934356-45-X ISBN-13: 978-1-934356-45-6

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.