07.11.2018 15:01
VlK 41 8400 Источник


"No matter how hard you try, you can't make a racehorse out of a pig. You can, however, make a faster pig" (комментарий в исходном коде Емакса)

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


Во второй части серии статей об интерпретаторах байт-кодов я на примере небольшой стековой виртуальной машины ПВМ («Поросячья Виртуальная Машина») постараюсь показать, что не всё потеряно для трудолюбивых поросят с амбициями и что в рамках (в основном) стандартного C вполне возможно ускорить работу таких интерпретаторов по меньшей мере в полтора раза.


ПоросенокВМ


Давайте знакомиться.


«ПоросёнокВМ» — заурядная стековая машина, основанная на примере из первой части серии статей. Наша свинка знает только один тип данных — 64-битное машинное слово, а все (целочисленные) вычисления производит на стеке максимальной глубиной в 256 машинных слов. Помимо стека, у этого поросёнка имеется рабочая память объёмом 65 536 машинных слов. Результат выполнения программы — одно машинное слово — можно либо поместить в регистр-результат, либо просто вывести в стандартный вывод (stdout).


Всё состояние в машине «ПоросёнокВМ» хранится в единственной структуре:


static struct {
    /* Current instruction pointer */
    uint8_t *ip;

    /* Fixed-size stack */
    uint64_t stack[STACK_MAX];
    uint64_t *stack_top;

    /* Operational memory */
    uint64_t memory[MEMORY_SIZE];

    /* A single register containing the result */
    uint64_t result;
} vm;

Вышеперечисленное позволяет отнести эту машину к низкоуровневым виртуальным машинам, почти все накладные расходы в которых приходятся на обслуживание главного цикла программы:


interpret_result vm_interpret(uint8_t *bytecode)
{
    vm_reset(bytecode);

    for (;;) {
        uint8_t instruction = NEXT_OP();
        switch (instruction) {
        case OP_PUSHI: {
            /* get the argument, push it onto stack */
            uint16_t arg = NEXT_ARG();
            PUSH(arg);
            break;
        }
        case OP_ADD: {
            /* Pop 2 values, add 'em, push the result back to the stack */
            uint64_t arg_right = POP();
            *TOS_PTR() += arg_right;
            break;
        }

        /*
        * ...
        * Lots of other instruction handlers here
        * ...
        */

        case OP_DONE: {
            return SUCCESS;
        }
        default:
            return ERROR_UNKNOWN_OPCODE;
        }
    }

    return ERROR_END_OF_STREAM;
 }

Из кода видно, что на каждый опкод поросёнок должен:


  1. Извлечь опкод из потока инструкций.
  2. Убедиться, что опкод входит в допустимый интервал значений опкодов (эту логику добавляет компилятор C при генерации кода switch).
  3. Перейти к телу инструкции.
  4. Извлечь аргументы инструкции из стека или декодировать аргумент инструкции, размещённый непосредственно в байт-коде.
  5. Выполнить операцию.
  6. Если есть результат вычисления, поместить его в стек.
  7. Передвинуть указатель с текущей инструкции на следующую.

Полезная нагрузка здесь только в пятом пункте, всё остальное — накладные расходы: декодирование или извлечение из стека аргументов инструкции (пункт 4), проверка значения опкода (пункт 2), многократное возвращение в начало главного цикла и последующий труднопредсказуемый условный переход (пункт 3).


Словом, у хрюшки явно превышен рекомендованный индекс массы тела, и если мы хотим привести её в форму, то придётся со всеми этими излишествами бороться.


Свинский язык ассемблера и решето Эратосфена


Для начала определимся с правилами игры.


Писать программы для виртуальной машины прямо в C — моветон, но и создавать язык программирования — долго, поэтому мы с поросёнком решили ограничиться свинским языком ассемблера.


Программа, вычисляющая сумму чисел от 1 до 65 536, на этом ассемблере выглядит примерно так:


# sum numbers from 1 to 65535

# init the current sum and the index
PUSHI 1
PUSHI 1
# stack s=1, i=1
STOREI 0
# stack: s=1

# routine: increment the counter, add it to the current sum
incrementandadd:

# check if index is too big
LOADI 0
# stack: s, i
ADDI 1
# stack: s, i+1
DUP
# stack: s, i+1, i+1
GREATER_OR_EQUALI 65535
# stack: s, i+1, 1 or 0
JUMP_IF_TRUE done
# stack: s, i+1
DUP
# stack: s, i+1, i+1
STOREI 0
# stack: s, i+1
ADD
# stack: s+i+1
JUMP incrementandadd

done:
DISCARD
PRINT
DONE

Не Python, конечно, но всё необходимое для поросячьего счастья тут есть: комментарии, метки, условные и безусловные переходы по ним, мнемоники для инструкций и возможность указывать непосредственные аргументы инструкций.


В комплекте с машиной «ПоросёнокВМ» идут ассемблер и дизассемблер, которые смелые духом и имеющие много свободного времени читатели могут самостоятельно опробовать в бою.


Числа суммируются очень быстро, поэтому для тестирования производительности я написал другую программу — наивную реализацию решета Эратосфена.


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


Первая версия нашей неоптимизированной свиньи бегает примерно так:


> ./pigletvm runtimes test/sieve-unoptimized.bin 100 > /dev/null
PROFILE: switch code finished took 545ms

Полсекунды! Сравнение, безусловно, нечестное, но тот же алгоритм на Python сто пробежек делает чуть медленнее:


> python test/sieve.py > /dev/null
4.66692185402

4,5 секунды, или в девять раз медленнее. Надо отдать должное поросёнку — способности у него есть! Ну а теперь давайте посмотрим, может ли наша свинья накачать пресс.


Упражнение первое: статические суперинструкции


Первое правило быстрого кода — не делать лишней работы. Второе правило быстрого кода — не делать лишней работы никогда. Так какую лишнюю работу делает «ПоросёнокВМ»?


Наблюдение первое: профилирование нашей программы показывает, что есть последовательности инструкций, встречающиеся чаще других. Не будем сильно мучить нашу свинью и ограничимся только парами инструкций:


  1. LOADI 0, ADD — положить в стек число из памяти по адресу 0 и прибавить его к числу на вершине стека.
  2. PUSHI 65536, GREATER_OR_EQUAL — положить в стек число и сравнить его с числом, бывшим до этого на вершине стека, положив результат сравнения (0 или 1) обратно в стек.
  3. PUSHI 1, ADD — положить в стек число, прибавить его к числу, бывшему до этого на вершине стека, и положить результат сложения обратно в стек.

В машине «ПоросёнокВМ» чуть больше 20 инструкций, а для кодирования используется целый байт — 256 значений. Внесение новых инструкций не проблема. Что мы и сделаем:


for (;;) {
    uint8_t instruction = NEXT_OP();
    switch (instruction) {
    /*
     * Other instructions here
     * */
    case OP_LOADADDI: {
        /* get immediate argument as an memory address , add it to value from the address to the top
         * of the stack */
        uint16_t addr = NEXT_ARG();
        uint64_t val = vm.memory[addr];
        *TOS_PTR() += val;
        break;
    }
    case OP_GREATER_OR_EQUALI:{
        /* get the immediate argument, compare it with the value from the address to the top of the stack */
        uint64_t arg_right = NEXT_ARG();
        *TOS_PTR() = PEEK() >= arg_right;
        break;
    }
    case OP_ADDI: {
        /* Add immediate value to the top of the stack */
        uint16_t arg_right = NEXT_ARG();
        *TOS_PTR() += arg_right;
        break;
    }
    /*
     * Other instructions here
     * */
}

Ничего сложного. Давайте посмотрим, что из этого получилось:


> ./pigletvm runtimes test/sieve.bin 100 > /dev/null
PROFILE: switch code finished took 410ms

Ого! Кода всего-то на три новых инструкции, а выиграли мы полторы сотни миллисекунд!


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


Это называется статическими суперинструкциями, поскольку дополнительные инструкции определяются статически, то есть программистом виртуальной машины на этапе разработки. Это простая и эффективная техника, которую в той или иной форме используют все виртуальные машины языков программирования.


Главная проблема статических суперинструкций заключается в том, что без конкретной программы невозможно определить, какие именно инструкции стоит объединить. Разные программы пользуются разными последовательностями инструкций, и узнать эти последовательности можно только на этапе запуска конкретного кода.


Следующим шагом могла бы стать динамическая компиляция суперинструкций в контексте конкретной программы, то есть динамические суперинструкции (в 90-е и в начале 2000-х этот приём играл роль примитивной JIT-компиляции).


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


Упражнение второе: проверка интервала значений опкодов


Следуя нашим правилам быстрого кода, ещё раз зададимся вечным вопросом: что можно не делать?


Когда мы знакомились с устройством машины «ПоросёнокВМ», я перечислял все действия, которые виртуальная машина выполняет для каждого опкода. И пункт 2 (проверка значения опкода на вхождение в допустимый интервал значений switch) вызывает больше всего подозрений.


Присмотримся к тому, как GCC компилирует конструкцию switch:


  1. Строится таблица переходов, то есть таблица, отображающая значение опкода на адрес исполняющего тело инструкции кода.
  2. Вставляется код, который проверяет, входит ли полученный опкод в интервал всех возможных значений switch, и отправляет к метке default, если для опкода нет обработчика.
  3. Вставляется код, переходящий к обработчику.

Но зачем делать проверку интервала значений на каждую инструкцию? Мы считаем, что опкод бывает либо правильный — завершающий исполнение инструкцией OP_DONE, либо неправильный — вышедший за пределы байт-кода. Хвост потока опкодов отмечен нулём, а ноль — опкод инструкции OP_ABORT, завершающей исполнение байт-кода с ошибкой.


Выходит, эта проверка вообще не нужна! И поросёнок должен уметь доносить эту мысль до компилятора. Попробуем немного поправить главный switch:


uint8_t instruction = NEXT_OP();
/* Let the compiler know that opcodes are always between 0 and 31 */
switch (instruction & 0x1f) {
   /* All the instructions here */
   case 26 ... 0x1f: {
       /*Handle the remaining 5 non-existing opcodes*/
       return ERROR_UNKNOWN_OPCODE;
   }
}

Зная, что инструкций у нас всего 26, мы накладываем битовую маску (восьмеричное значение 0x1f — это двоичное 0b11111, покрывающее интервал значений от 0 до 31) на опкод и добавляем обработчики на неиспользованные значения в интервале от 26 до 31.


Битовые инструкции — одни из самых дешёвых в архитектуре x86, и они уж точно дешевле проблемных условных переходов вроде того, который использует проверка на интервал значений. Теоретически мы должны выигрывать несколько циклов на каждой исполняемой инструкции, если компилятор поймёт наш намёк.


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


Пробуем:


> ./pigletvm runtimes test/sieve.bin  100 > /dev/null
PROFILE: switch code finished took 437ms
PROFILE: switch code (no range check) finished took 383ms

Ещё 50 миллисекунд! Поросёнок, ты будто бы в плечах раздался!..


Упражнение третье: трассы


Какие ещё упражнения могут помочь нашему поросёнку? Самую большую экономию времени мы получили благодаря суперинструкциям. А они уменьшают количество выходов в главный цикл и позволяют избавиться от соответствующих накладных расходов.


Центральный switch — главное проблемное место для любого процессора с внеочередным выполнением инструкций. Современные предсказатели ветвлений научились неплохо прогнозировать даже такие сложные непрямые переходы, но «размазывание» точек ветвлений по коду может помочь процессору быстро переходить от инструкции к инструкции.


Другая проблема — это побайтовое чтение опкодов инструкций и непосредственных аргументов из байт-кода. Физические машины оперируют 64-битным машинным словом и не очень любят, когда код оперирует меньшими значениями.


Компиляторы часто оперируют базовыми блоками, то есть последовательностями инструкций без ветвлений и меток внутри. Базовый блок начинается либо с начала программы, либо с метки, а заканчивается концом программы, условным ветвлением или прямым переходом к метке, начинающей следующий базовый блок.


У работы с базовыми блоками много преимуществ, но нашу свинью интересует именно её ключевая особенность: инструкции в пределах базового блока выполняются последовательно. Было бы здорово как-нибудь выделять эти базовые блоки и выполнять инструкции в них, не теряя времени на выход в главный цикл.


В нашем случае можно даже расширить определение базового блока до трассы. Трасса в терминах машины «ПоросёнокВМ» будет включать в себя все последовательно связанные (то есть при помощи безусловных переходов) базовые блоки.


Помимо последовательного выполнения инструкций, неплохо было бы ещё заранее декодировать непосредственные аргументы инструкций.


Звучит всё это довольно страшно и напоминает динамическую компиляцию, которую мы решили не использовать. Поросёнок даже немного засомневался в своих силах, но на практике всё оказалось не так плохо.


Давайте сначала подумаем, как можно представить входящую в трассу инструкцию:


struct scode {
    uint64_t arg;
    trace_op_handler *handler;
};

Здесь arg — заранее декодированный аргумент инструкции, а handler — указатель на функцию, выполняющую логику инструкции.


Теперь представление каждой трассы выглядит так:


typedef scode trace[MAX_TRACE_LEN];

То есть трасса — это последовательность s-кодов ограниченной длины. Сам кеш трасс внутри виртуальной машины выглядит так:


trace trace_cache[MAX_CODE_LEN];

Это просто массив из трасс длиной, не превышающей возможную длину байт-кода. Решение ленивое, практически для экономии памяти имеет смысл использовать хеш-таблицу.


В начале работы интерпретатора первый обработчик каждой из трасс будет сам себя компилировать:


for (size_t trace_i = 0; trace_i < MAX_CODE_LEN; trace_i++ )
    vm_trace.trace_cache[trace_i][0].handler = trace_compile_handler;

Главный цикл интерпретатора теперь выглядит так:


while(vm_trace.is_running) {
   scode *code = &vm_trace.trace_cache[vm_trace.pc][0];
   code->handler(code);
}

Компилирующий трассу обработчик чуть сложнее, и, помимо сборки трассы, начинающейся от текущей инструкции, он делает следующее:


static void trace_compile_handler(scode *trace_head)
{
    scode *trace_tail = trace_head;
   /*
     * Trace building here
     */
   /* now, run the chain that has a trace_compile_handler replaced with proper instruction handler
     * function pointer */
    trace_head->handler(trace_head);
}

Нормальный обработчик инструкции:


static void op_add_handler(scode *code)
{
    uint64_t arg_right = POP();
    *TOS_PTR() += arg_right;

    /*
    * Call the next trace handler
    * */

    /* scodes are located in an array so we can use pointer arithmetic to get the next handler */
    code++;
    code->handler(code);
}

Завершает работу каждой трассы обработчик, не делающий никаких вызовов в хвосте функции:


static void op_done_handler(scode *code)
{
    (void) code;

    vm_trace.is_running = false;
    vm_trace.error = SUCCESS;
}

Всё это, конечно, сложнее, чем добавление суперинструкций, но давайте посмотрим, дало ли это нам что-нибудь:


> ./pigletvm runtimes test/sieve.bin  100 > /dev/null
PROFILE: switch code finished took 427ms
PROFILE: switch code (no range check) finished took 395ms
PROFILE: trace code finished took 367ms

Ура, ещё 30 миллисекунд!


Как же так? Вместо простых переходов по меткам мы делаем цепочки вызовов обработчиков инструкций, тратим время на вызовы и передачу аргументов, но наш поросёнок всё равно бегает по трассам быстрее простого switch с его метками.


Такой выигрыш в производительности трасс достигается благодаря трём факторам:


  1. Предсказать ветвления, разбросанные по разным местам кода, легко.
  2. Аргументы обработчиков всегда предекодированы в полное машинное слово, и делается это только один раз — во время компиляции трассы.
  3. Сами цепочки функций компилятор превращает в единственный вызов первой функции-обработчика, что возможно благодаря оптимизации хвостового вызова.

Прежде чем подвести итоги наших тренировок, мы с поросёнком решили испробовать ещё одну древнюю технику интерпретации программ — шитый код.


Упражнение четвертое: "шитый" код


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


Вызовы функций — дело дорогое и особого смысла в наши дни не имеющее; большая часть других версий шитого кода нереализуема в рамках стандартного C. Даже техника, о которой речь пойдёт ниже, использует широко распространённое, но всё же нестандартное расширение C — указатели на метки.


В версии шитого кода (англ. token threaded code), которую я выбрал для достижения наших свинских целей, мы сохраняем байт-код, но перед началом интерпретации создаём таблицу, отображающую опкоды инструкций на адреса меток обработчиков инструкций:


const void *labels[] = {
    [OP_PUSHI] = &&op_pushi,
    [OP_LOADI] = &&op_loadi,
    [OP_LOADADDI] = &&op_loadaddi,
    [OP_STORE] = &&op_store,
    [OP_STOREI] = &&op_storei,
    [OP_LOAD] = &&op_load,
    [OP_DUP] = &&op_dup,
    [OP_DISCARD] = &&op_discard,
    [OP_ADD] = &&op_add,
    [OP_ADDI] = &&op_addi,
    [OP_SUB] = &&op_sub,
    [OP_DIV] = &&op_div,
    [OP_MUL] = &&op_mul,
    [OP_JUMP] = &&op_jump,
    [OP_JUMP_IF_TRUE] = &&op_jump_if_true,
    [OP_JUMP_IF_FALSE] = &&op_jump_if_false,
    [OP_EQUAL] = &&op_equal,
    [OP_LESS] = &&op_less,
    [OP_LESS_OR_EQUAL] = &&op_less_or_equal,
    [OP_GREATER] = &&op_greater,
    [OP_GREATER_OR_EQUAL] = &&op_greater_or_equal,
    [OP_GREATER_OR_EQUALI] = &&op_greater_or_equali,
    [OP_POP_RES] = &&op_pop_res,
    [OP_DONE] = &&op_done,
    [OP_PRINT] = &&op_print,
    [OP_ABORT] = &&op_abort,
};

Обратите внимание на символы && — это указатели на метки с телами инструкций, то самое нестандартное расширение GCC.


Для начала выполнения кода достаточно прыгнуть по указателю на метку, соответствующую первому опкоду программы:


goto *labels[NEXT_OP()];

Никакого цикла здесь нет и не будет, каждая из инструкций сама делает прыжок к следующему обработчику:


op_pushi: {
        /* get the argument, push it onto stack */
        uint16_t arg = NEXT_ARG();
        PUSH(arg);
        /* jump to the next instruction*/
        goto *labels[NEXT_OP()];
    }

Отсутствие switch «размазывает» точки ветвлений по телам инструкций, что в теории должно помочь предсказателю ветвлений при внеочередном выполнении инструкций. Мы как бы встроили switch прямо в инструкции и вручную сформировали таблицу переходов.


Вот и вся техника. Поросёнку она понравилась своей простотой. Посмотрим, что получается на практике:


> ./pigletvm runtimes test/sieve.bin  100 > /dev/null
PROFILE: switch code finished took 443ms
PROFILE: switch code (no range check) finished took 389ms
PROFILE: threaded code finished took 477ms
PROFILE: trace code finished took 364ms

Упс! Это самая медленная из всех наших техник! Что же случилось? Выполним те же тесты, выключив все оптимизации GCC:


> ./pigletvm runtimes test/sieve.bin  100 > /dev/null
PROFILE: switch code finished took 969ms
PROFILE: switch code (no range check) finished took 940ms
PROFILE: threaded code finished took 824ms
PROFILE: trace code finished took 1169ms

Здесь шитый код показывает себя лучше.


Тут играют роль три фактора:


  1. Оптимизирующий компилятор сам построит таблицу переходов не хуже нашей ручной таблички с метками.
  2. Современные компиляторы замечательно избавляются от лишних вызовов функций.
  3. Примерно начиная с поколения Haswell процессоров Intel предсказатели ветвлений научились точно прогнозировать переходы через единственную точку ветвлений.

По старой памяти эту технику ещё используют в коде, например, интерпретатора Python VM, но, честно говоря, в наши дни это уже архаизм.


Давайте, наконец, подведём итоги и оценим успехи, которых добилась наша свинья.


Разбор поросячьих полетов



Не уверен, что это можно назвать полётом, но, давайте признаем, наш поросёнок прошёл большой путь от 550 миллисекунд на сто пробежек по «решету» до финальных 370 миллисекунд. Мы использовали разные техники: суперинструкции, избавление от проверки интервалов значений, сложную механику трасс и, наконец, даже шитый код. При этом мы, в общем-то, действовали в рамках вещей, реализованных во всех популярных компиляторах C. Ускорение в полтора раза, как мне кажется, это неплохой результат, и поросёнок заслужил лишнюю порцию отрубей в корыте.


Одно из неявных условий, которое мы со свиньёй себе поставили, — сохранение стековой архитектуры машины «ПоросёнокВМ». Переход к регистровой архитектуре, как правило, уменьшает количество необходимых для логики программ инструкций и, соответственно, может помочь избавиться от лишних выходов в диспетчер инструкций. Думаю, ещё 10—20% времени на этом можно было бы срезать.


Основное же наше условие — отсутствие динамической компиляции — тоже не закон природы. Накачать свинью стероидами в виде JIT-компиляции в наши дни очень даже несложно: в библиотеках вроде GNU Lightning или LibJIT вся грязная работа уже сделана. Но время на разработку и общий объём кода даже с использованием библиотек здорово увеличиваются.


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


PS Отдельная благодарность моей сестре, Ренате Казановой, за эскизы иллюстраций, и нашему иллюстратору, Владимиру Шопотову (https://www.instagram.com/vovazomb/), за финальные рисунки.


PPS Оригинальный поросенок не очень разговорчив в целом, и понимает только примитивный ассемблер. Но true-grue каким-то волшебным образом за несколько часов сделал для него небольшой язык — PigletC. Теперь можно хрюкать без ограничений!

Комментарии (41)


  1. picul
    07.11.2018 19:06
    #19335698

    Зачем вообще проверять инструкции на корректность в рантайме? Как минимум можно это сделать отдельно от выполнения — тогда в случае циклов не будем дублировать эти проверки над одними и теми же данными.
    Еще возможно стоит попробовать организовать хранение нескольких верхних значений стека в регистрах, а не в памяти — скорость доступа к ним наиболее важна.
    P. S. Примечательно, что суперинструкции дали такой прирост. Ждем поддержку SIMD))


    1. VlK Автор
      07.11.2018 19:28
      #19335768

      Я не уверен, что понял про корректность в рантайме. Инструкции нигде ничего лишнего не проверяют. Или вы про что?

      Хранение вершины стека в регистрах надо делать на ассемблере, это отдельная статья потребуется. Я тут решил не маньячить так прям сильно. Кстати, именно так работает GForth, основанный на vmgen. Там хитро жонглируются инструкции и аргументы инструкций так, чтобы все время держать один-два элемента в регистрах. Говоря, дает 10-15% примерно.

      Суперинструкции — первое, что стоит делать: легко, быстро, хорошо работает. Но, с другой стороны, их делают все, тут что-то особенное не получится.

      SIMD не SIMD, но любопытно, как бы так заюзать возможность тащить и выполнять несколько инструкций разом при условии, что между ними нет зависимостей. Типа как процессор делает… Это так, мысли вслух.


      1. picul
        07.11.2018 20:08
        #19335984

        Про корректность — имеется в виду упражнение второе. В конце концов, все равно делается побитовое «и». Мне кажется, лучше было бы вообще не проверять корректность инструкции на данном этапе:

        uint8_t instruction = NEXT_OP();
/* Let the compiler know that opcodes are always between 0 and 31 */
switch (instruction) {
   /* All the instructions here */
   default: {
        __builtin_unreachable();
   }
}

        В этом случае лишних действий вообще нет. А если есть риск, что код может оказаться некорректным, просто предварительно пройтись по буферу и сделать чисто проверки на корректность.

        Про SIMD — имелось в виду введение непосредственно инструкций, аналогичных Intel SSE, например взять из стека два вектора значений, просуммировать, и результат засунуть в стек. Но вообще это шутка была.


        1. VlK Автор
          07.11.2018 21:30
          #19336306

          Про корректность. Разницы никакой не будет. Это, считай, просто еще одна инструкция в таблице переходов, которую сгенерит компилятор. Озвучить же проблемы байт-кода всегда бывает полезно. Например, когда указатель текущей инструкции сбился, или ассемблер какую-нибудь ерунду влепил в байт-код, мало ли.

          Ходить лишний раз по байт-коду и валидировать… Зачем? Это должен делать компилятор в байт-код. Хотя в данном случае компилятором работал я сам :-)

          Я шутку понял :-) Про внеочередное выполнение байт-кода — ответная шутка.


          1. picul
            07.11.2018 21:48
            #19336370

            Что-то я запутался — то кто-то влепил в байт-код ерунду, то его валидирует компилятор. Допускается ли ситуация, что байт-код на входе будет невалидным? Если да, то предлагается предварительно пройтись по всему буферу байт-кода, и для каждого байта проверить, что он является валидной инструкцией. Профит тут очевиден — когда в программе есть циклы (всегда), мы вместо N проверок на валидность тела цикла проверим его только один раз.
            Тогда, использовав в switch'е пометку про недостижимость ветки default, информируем компилятор о том, что все инструкции валидны. Тогда если сравнивать с изначальным вариантом, то мы избавляемся от лишнего прыжка, если с оптимизированным — от лишнего логического «и».


            1. VlK Автор
              07.11.2018 22:01
              #19336416

              Пардон, я все не понял сначала.

              При условии полной валидности байт-кода да, конечно, так и будет. Можно убрать этот хвост и маску, и посмотреть, что компилятор сделает с __builtin_unreachable. Разумно предположить, что компилятор догадается, о чем речь.

              А вы проверяли?

              В принципе, это то же самое, хотя на стандартном Си эту мысль изложить трудней. Я эта в статье указывал.


              1. picul
                07.11.2018 22:22
                #19336502

                Ну, статья про оптимизацию вроде, вот я и указал как еще больше улучшить.
                Только что проверил тут, вроде все как надо.


                1. VlK Автор
                  07.11.2018 23:33
                  #19336698

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

                  Мне нравится, признаться unreachable за то, что название как бы явно говорит, что, мол, такого-то быть не может, и этого быть не должно. Единственный недостаток — нестандартность.

                  По производительности разницы не будет, если верить godbolt.org :-)


  1. tekord
    07.11.2018 20:30
    #19336090

    > в библиотеках вроде GNU Lightning или LibJIT вся грязная работа уже сделана. Но время на разработку и общий объём кода даже с использованием библиотек здорово увеличиваются.

    А всё же на сколько трудно и долго будет прикрутить jit для этого? В чём основная сложность? Делаю самопальную виртуальную машину для самообразования, и с темой интеграции jit'ом пока вообще не соприкасался.

    P.S. Поделюсь своим скриптиком для генерации H-файла с опкодами на основе описания в Yaml файле github.com/tekord/cpp-opcode-generator, мелочь, конечно, но вдруг кому-нибудь пригодится.


    1. VlK Автор
      07.11.2018 21:25
      #19336294

      Ну, jit-компиляторы и техники компиляции бывают очень разные по сложности. В самой простой форме, с полной компиляцией байт-кода примитивной машинки уровня Поросенка и на libjit, можно за пару недель что-то быстрое сделать.

      Я делал кое-что с libjit, но особого профита не получил. В финале разработки понял, наконец, что было неправильно, но время кончилось, и код пришлось выбросить. Мораль: надо знать, как и что делать, и выяснение этих вопросов — тоже календарное время.

      Сюрпризы, встреченные по дороге:
      1. Компиляция занимает ощутимое время.
      2. Вызов кода через динамический линковщик не бесплатен. Скачки между динамическим кодом и кодом родительским тяжелее обычных вызовов функций. Работа по возможности производиться без перехода между ними.
      3. Для коротких одноразовых последовательностей байт-кода простой интепретатор всегда будет быстрее.

      Без libjit, на портативном ассемблере типа GNU Lightning, разработка займет еще больше времени.


      1. VlK Автор
        07.11.2018 21:31
        #19336310

        Но вот если честно, все это несложно, правда. У libjit неплохая документация и хорошие примеры, можно еще по интернету туториалы хорошие найти. Где-то тут на хабре даже был перевод одного из них.


  1. kaleman
    08.11.2018 10:09
    #19337922

    К сожалению не описана работа виртуальной машины с вещественными числами, строками, структурами. А все это очень интересно.
    Еще нет бинарного формата файла байткода, чтобы понять как хранить скомпилированные опкоды, целые и вещественные константы, строки, ресуры и т.д.


    1. VlK Автор
      08.11.2018 10:51
      #19338122

      Согласен, все это очень интересно.

      Но надо же на чем-то концентрироваться, а виртуальные машины бывают очень разные. Здесь я выбрал именно главный цикл виртуальной машины, так как это то, что встречается в любой реализации. То есть оптимизация именно этого цикла даст выигрыш в любом случае.

      Если интересно, могу на пальцах вот прямо в комментариях изложить, как, например, константы, строки и структуры хранятся.


      1. kaleman
        08.11.2018 12:42
        #19338748

        Да изложите. Интересно как происходят операции со строками, структурами и вещественными числами на стеке.


        1. VlK Автор
          08.11.2018 12:59
          #19338856
          +2

          Давайте начну с вещественных чисел, для случая низкоурвневых машинок языков, а ля JVM, то есть с типами значений, известными на этапе компиляции.

          1. Вещественные числа.

          Вводится второй комплект инструкций для арифметических операции с вещественными чисел + конвертирующие между ними и целочисленными значениями инструкции.

          Вещественные числа представляются приличным числом байт, в непосредственные аргументы пихаются хуже, поэтому обычно оказываются в таблице констант. Соответственно, для добавляются операции извлечения чисел из таблицы констант на стект.

          Таблица констант со всем содержимым вкладывается в байт-код, т.е. тут не просто поток байт, как в «ПоросенокВМ», у набор структур данных (сам байт-код + таблица констант).

          2. Строки (и структуры, для них оно похожим образом работает).

          Тут возможны варианты, но обычно вводится специальный тип обобщенных объектов. Это, в сущности, маркер типа объекта («здесь строка» или «здесь структура») + сам объект Байт-код или стек не оперирует самими значениями объектов (было бы странно хранить длиннющие строки в стеке ограниченного размера), а указателями на них. Указатели на эти объекты-строки или объекты-структуры помещают в ту же таблицу констант, если значение известно заранее, либо уж в динамическую память (англ. heap).

          Соответственно, появляются специальные инструкции для помещения указателей на объекты из таблицы констант на стек + инструкции для работы с этими указателями.

          Раз уж мы заговорили про динамическую память, то, конечно, появляется необходимость в сборщике мусора и инструкциях аллокации/деаллокации объектов…

          3. Вы про это не спрашивали. Функции и методы — тоже важная штука.

          Байт-код и таблица констант тоже не в одной пачке хранится в файле. Они сгруппированы по функциями, если только это не таблица глобальных констант… Т.е. файл с байт-кодом это: таблица глобальных констант + методы. Каждый метод: таблица локальных констант + сам байт-код функции.

          Не стесняйтесь спрашивать, если что-то еще интересно.


          1. kaleman
            08.11.2018 14:17
            #19339394

            Первый раз слышу, что на уровне байткода есть функции. В них действительно есть смысл? Или достаточно делать JMP на подпрограмму.


            1. VlK Автор
              08.11.2018 14:23
              #19339432
              +1

              На уровне байт-кода виртуальных машин для языков программирования функции есть почти всегда, это я вам точно говорю. И целая машинерия для их обслуживания. И рядовой jit компилирует именно в терминах этих самых функций.

              Делаются они по-разному, но есть всегда. Да чего уж!.. Бывают и классы даже.

              В машинном коде и микрокоде эмуляторов железных процессоров их, конечно, нет.


  1. segment
    08.11.2018 12:44
    #19338754

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


    1. VlK Автор
      08.11.2018 13:10
      #19338916

      Это вы точно заметили :-)

      Можно было бы один раз на старте транслировать программу в машинный код — и не париться.

      Но! Машинный код еще скомпилировать и прилинковать к программе надо. Для быстрого запуска маленьких программок это не подходит, что бы там не говорили поклонники JVM. Тот же Питон запускается и приступает к работе намного быстрей.

      Опять же, программы здорово распухают в памяти с таким подходом, что, конечно, в наши дни уже не так страшно, но все же…

      Да и… Для быстрой компиляции нужен какой-то ассемблер, типа GNU Lightning, это не так просто, как может показаться (но и не суперсложно, да).

      Практические виртуалки обычно выбирают какой-то отдельный «горячий» участок программы для компиляции. Особенно с этим стараются не переборщить реализации Javascript: пользователи не любят ждать загрузку страниц.


      1. segment
        08.11.2018 14:33
        #19339506

        Я подразумевал не полную компиляцию всего и вся в единую бинарную программу. А компилировать только тела функций, набрасывая ассемблерные команды по шаблону на каждую из них. Пуская с nop выравниванием и оригинальными вызовами функций. В одном теле не так много переходов, чтобы оно «распухало» при переводе в ассемблерный вид. Хотя конечно не спорю, в больших программах потребуется время на подготовку.


        1. VlK Автор
          08.11.2018 14:40
          #19339560

          Это, кажется, называется «шаблонной динамической компиляцией» (или англ. template jit), и она действительно довольно быстро работает. В GNU Guile недавно именно такой jit добавили на базе GNU Lightning.

          Я ж не против :-) Думаю, в случае «ПоросенокВМ» такой подход отлично сработает, особенно если не кешировать скомпилированные функции между запусками программ. Тип тут один, инструкции простенькие… Да, должно быть несложно.

          Вы что-нибудь такое пробовали делать?


          1. segment
            08.11.2018 15:06
            #19339678

            Пробовал, частично, в виде тестов. Этот подход неплохой как компромисс, но проблема у меня в методе отладки при таком подходе. Если с обычным байткодом отладка реализуема и понятна, то при переводе в машинные коды пока не увидел адекватного решения.


            1. VlK Автор
              08.11.2018 15:11
              #19339702

              Добро пожаловать в дивный мир деоптимизации :-) Это типа целая наука, особенно в случая продвинутых оптимизирующих jit-ов.

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

              Вы что-нибудь сделали в итоге или сдались?


              1. segment
                08.11.2018 15:28
                #19339792

                Это сейчас одно и моих направлений, нужно выбирать за основу какой-то вариант реализации. При этом скорость исполнения на первом месте, именно поэтому читаю и смотрю варианты с пред-компиляцией.
                Разве, если делать такие вставки, то не придется ли слишком много прыгать?


                1. VlK Автор
                  08.11.2018 16:06
                  #19340018

                  не знаю, обсуждаем ли мы одно и то же, но раз уж на то пошло…

                  В случае обычного шаблонного jit-а, думаю, можно сделать что-то вроде двух режимов: отладочный и обычный, и в отладочном добавлять какой-то дополнительный код или дополнительные данные. Либо вообще всегда включать в машинный хранить дополнительные отладочные символы, но трогать их только при необходимости.

                  В любом случае начать можно с байт-кода, а там при необходимости и наличии времени можно сбоку прикруть компилятор-ускорялку.


                  1. segment
                    08.11.2018 16:12
                    #19340058

                    Два режима понятно, но накладно. То есть переключаясь в режим отладки, мы получаем другой машинный код, что уже может повлечь за собой какие-то различия в исполнении. Вопрос у меня скорее в другом. Как будут работать эти отладочные символы, про которые Вы говорите? На стороне IDE есть только инструкции байткода, и их соответствие с языком верхнего уровня. В runtime уже появляется две сущности, одна это оригинальный байткод, другая это исполняемый код. Как Вы предполагаете осуществлять работу, для начала, точек останова?


                    1. VlK Автор
                      08.11.2018 16:18
                      #19340098

                      А вот тут я вам не помогу, признаться. Все зависит от IDE и того, как она отладочные символы понимает.

                      Я бы для начала обошелся жирным комлпектом тестов, без привязки к конкретной IDE, который бы и гонял как на простом байт-коде, так и jit-компилированном коде.

                      IDE и отладочными символами заниматься имеет смысл, если только это какой-то более долгосрочный проект. Но это мой подход.


                      1. segment
                        08.11.2018 16:24
                        #19340134

                        Так я скорее про сам возможный принцип работы точек останова в таком виде. Речь не идет о какой-то конкретной IDE. В моем случае это долгосрочный проект, поэтому этот момент пытаюсь у Вас расспросить. Мне показалось, что у Вас есть представление о том, как это может быть реализовано.


                        1. VlK Автор
                          08.11.2018 16:38
                          #19340210

                          Ну в каком-то ограниченном смысле я могу вам что-то подсказать, но, честно говоря, слишком много темой внешних дебаггеров не занимался.

                          Кроме того, весь мой опыт это Линукс, а на каждой платформе свой подход к этим вещам. Под Линуксом есть специальный syscall для этого — ptrace, и все дебаггеры его используют.

                          Вот неплохое введение по тому, как работает gdb:

                          sourceware.org/gdb/wiki/Internals/Breakpoint%20Handling

                          А вот хороший туториал от знающего специалиста:

                          eli.thegreenplace.net/2011/01/23/how-debuggers-work-part-1

                          Для остального потребуется знание уже конкретного проекта и конкретной платформы.


  1. VaalKIA
    08.11.2018 13:34
    #19339044

    Если программа будет осуществлять самомодифицируемый код: сместить блок кода или проставить значение jp, что бы без ифов, эти оптимизации будут применимы?


    1. VlK Автор
      08.11.2018 13:40
      #19339100

      С самомодифицируемым кодом, как и в железных машинах, все сложней, но ничего непреодолимого.

      1. Суперинструкции будут работать как работали.
      2. Оптимизация проверки интервала значений байт-кода будет работать как работала.
      3. Трассы придется на каждую модификацию инвалидировать и пересобирать.

      НО! Опять же, как и в обычном машинном коде будут проблемы с адресами и метками. Если мы смещаем блок кода, то надо будет исправлять адреса всех меток во всех условных и безусловных переходах.

      А почему вы спрашиваете? Есть какой-то живой пример?


      1. VaalKIA
        08.11.2018 14:21
        #19339424

        Спрашиваю, потому что оптимизации компилятора не должны ломать уровень железа. Почему суперинструкции будут работать: если первая её часть модифицирует вторую?


        1. VlK Автор
          08.11.2018 14:29
          #19339476

          Потому что статические суперинструкции это просто рядовые инструкции, куда вложена логика сразу двух инструкций. У них свой конкретный адрес есть, и их нельзя модифицировать по кускам. Использует их сразу компилятор, сама же виртуалка видит их как неделимое целое.

          Динамические — другой вопрос, но я не слышал, чтобы кто-то вообще разрешал двигать куда-то байт-код в виртуалках для языков. Даже самые динамические из интерпретаторов байт-кода обычно просто подменяют байт-код функции целиком.


          1. VaalKIA
            09.11.2018 14:19
            #19344634

            Например, в проекте есть много циклов где используется подряд две инструкции xor [addr], value; setbit7 reg1. Вы объединяете это в суперинструкцию, а в другом проекте xor [addr], value изменяет не данные в графическом буфере, а бит инструкции setbit7 reg1 (и так же они идут подряд), превращая её в setbit3 reg1, соответственно, при выполнении суперинструкции код изменится, но инструкция будет выполнена старая.


            1. VlK Автор
              09.11.2018 14:46
              #19344786

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

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

              Грубо говоря, если в новой версии JVM появится новая сложная (супер)инструкция «взять со стека, прибавить число, умножить на число», то она будет одинаковой для всех.


          1. VaalKIA
            09.11.2018 14:41
            #19344766

            А ещё, меня интересует, можно ли на автомате перейти от стековой к регистровой модели, то есть, создать такие суперинструкции, которые не гоняют память через стек, а вообще используют какую-то внутреннюю переменную (регистр), это может быть сильно эффективней. Просто ISA современных процессоров, что RISC, что CISC создавалась людьми и по наитию или из каких-то идейных соображений, но теперь-то можно взять программы на ЯВУ и получить низкоуровневые суперинструкции из который создать оптимальную ISA статистическими методами.


            1. VlK Автор
              09.11.2018 14:48
              #19344802

              Можно. Более того, главные исследования, сравнивавшие производительность регистровых и стековых машиных, так и делали: разработали процедуру прямого портирования стекового кода в регистровый, а потом сравнивали производительность работы одной и той же программы в разных архитектурах кода.


      1. 0x9d8e
        09.11.2018 15:07
        #19344918

        Однажды сделал для специфических нужд (хотя больше поиграться) машину с весьма ограниченным объёмом памяти (восьмибитная шина на всё про всё). Машину написать было просто, а вот научиться что-то вменяемое в неё уместить не совсем. В частности код постоянно самомодифицировался таким образом, чтобы экономить на его объёме, например весь ввод-вывод шел через чтение/запись по 0x01 в цикле по одному байту. И сам код цикла и обслуживания буфера занимал столько места, что его пришлось переиспользовать. Так как условные переходы потребовали бы много инструкций, пришлось реализовать это динамической заменой безусловных переходов. В принципе можно было это обойти суперинструкциями, но это религия не позволила. Ибо байт-код должен был быть прост и минимален как пробка: два с половиной регистра, двадцать элементарных команд без всяких аргументов. Например что-то в роде a = 1; b = 2; c = a + b; выполняемое в рантайме занимало 19 байт из которых 13 инструкции. С некоторыми плясками можно уместить в 17.
        В таких условиях приходилось иногда использовать команды в качестве констант и константы в качестве команд. И использовать константы в роли переменных с таким расчётом, чтобы к моменту, когда понадобится первоначальное значение там оказалось бы именно оно. Само-собой такие программы любили внезапно превращаться в ГПСЧ, а их отладка в ад адовый. Но это работало и кушать не просило. И в «конвееры» потоковой обработки чего-либо стакалось.
        Собственно суперинструкции тут конечно много чего позволили бы. Замену свича на арифметику с указателями пробовал, толку очень мало дало почему-то. Трассы точно не сработают. Правда можно сделать как-бы кеш, длиной в машинное слово хоста, чтобы не по байту читать, но сохранить полную совместимость с «честными» восьмью битами.
        А с адресами меток в таких случаях проблем нет т.к. это остаётся на совести программиста.


        1. VlK Автор
          09.11.2018 15:36
          #19345072

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

          Собственно, физические процессоры, поддерживающие модификацию кода, так и делают: сбрасывают весь кеш декодированных инструкций.


          1. 0x9d8e
            09.11.2018 17:33
            #19345710

            Хм, а что если распознавать модифицированный код как ещё один набор инструкций, а момент этой модификации как переход между ними? Правда это потребует как минимум дополнительной памяти. Зато в итоге имеем программу которая относительно эффективно работает и на очень ограниченном железе и на машине с кучей памяти, где эти оптимизации по памяти фактически будут развёрнуты обратно в оптимизации по времени. Тот факт что написание такого кода обойдётся дороже любого железа опустим


  1. true-grue
    09.11.2018 16:48
    #19345502
    +1

    Большое спасибо за популяризацию техник создания интерпретаторов/языковых ВМ!

    «Писать программы для виртуальной машины прямо в C — моветон, но и создавать язык программирования — долго, поэтому мы с поросёнком решили ограничиться свинским языком ассемблера»


    А вот эта фраза меня раззадорила. Дело в том, что у меня как раз, совершенно случайно, завалялся набор инструментов для быстрого создания компиляторов. В результате полдня ушло вот на такой миниатюрный компилятор PigletC, написанный с нуля: github.com/true-grue/PigletC

    Пример.

    int r;
int n;

void main() {
  n = 5;
  r = 1;
  while (n > 1) {
    r = r * n;
    n = n - 1;
  }
  print(r);
}


    Результат компиляции.

    PUSHI 1
    PUSHI 5
    STORE
    PUSHI 0
    PUSHI 1
    STORE
    L0:
    PUSHI 1
    LOAD
    PUSHI 1
    GREATER
    JUMP_IF_FALSE L1
    PUSHI 0
    PUSHI 0
    LOAD
    PUSHI 1
    LOAD
    MUL
    STORE
    PUSHI 1
    PUSHI 1
    LOAD
    PUSHI 1
    SUB
    STORE
    JUMP L0
    L1:
    PUSHI 0
    LOAD
    PRINT
    DONE


    Запускаем.

    pigletvm-exec asm fact.c.pvm fact.c.b
    pigletvm-exec run fact.c.b
    120
    Result value: 0
    PROFILE: switch code finished took 0ms
    120
    Result value: 0
    PROFILE: switch code (no range check) finished took 1ms
    120
    Result value: 0
    PROFILE: threaded code finished took 0ms
    120
    Result value: 0
    PROFILE: trace code finished took 1ms


    Надеюсь, PigletVM и PigletC сумеют кого-то заинтересовать тематикой создания инструментального ПО.