company_banner

Интерпретаторы байт-кодов своими руками


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


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


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


    Предыстория


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


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


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


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


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


    Популярность виртуальных наборов инструкций в качестве промежуточного представления кода объясняется тремя причинами:


    1. Программы в виде байт-кодов легко переносятся на новые платформы.
    2. Интерпретаторы байт-кодов работают быстрее интерпретаторов синтаксического дерева кода.
    3. Разработать простейшую виртуальную машину можно буквально за пару часов.

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


    Полные коды примеров выложены на GitHub. Примеры можно собрать любым относительно свежим GCC:


    gcc interpreter-basic-switch.c -o interpreter
    ./interpreter

    Все примеры имеют одинаковую структуру: сначала идёт код самой виртуальной машины, после — главная функция с assert-ами, проверяющими работу кода. Я старался внятно комментировать опкоды и ключевые места интерпретаторов. Надеюсь, статья будет понятна даже людям, ежедневно не пишущим на C.


    Самый простой в мире интерпретатор байт-кода


    Как я уже говорил, простейший интерпретатор сделать очень легко. Комментарии — сразу за листингом, а начнём непосредственно с кода:


    struct {
        uint8_t *ip;
        uint64_t accumulator;
    } vm;
    
    typedef enum {
        /* increment the register */
        OP_INC,
        /* decrement the register */
        OP_DEC,
        /* stop execution */
        OP_DONE
    } opcode;
    
    typedef enum interpret_result {
        SUCCESS,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    
    void vm_reset(void)
    {
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
    }
    
    interpret_result vm_interpret(uint8_t *bytecode)
    {
        vm_reset();
    
        puts("Start interpreting");
        vm.ip = bytecode;
        for (;;) {
            uint8_t instruction = *vm.ip++;
            switch (instruction) {
            case OP_INC: {
                vm.accumulator++;
                break;
            }
            case OP_DEC: {
                vm.accumulator--;
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
    
        return SUCCESS;
    }
    

    Здесь меньше ста строк, но все характерные атрибуты виртуальной машины представлены. У машины единственный регистр (vm.accumulator), три операции (инкремент регистра, декремент регистра и завершение исполнения программы) и указатель на текущую инструкцию (vm.ip).


    Каждая операция (англ. operation code, или opcode) кодируется одним байтом, а диспетчеризация осуществляется при помощи обычного switch в функции vm_interpret. Ветки в switch содержат логику операций, то есть меняют состояние регистра либо завершают исполнение программы.


    Операции передаются в функцию vm_interpret в виде массива байтов — байт-кода (англ. bytecode) — и последовательно выполняются до тех пор, пока в байт-коде не встретится операция завершения работы виртуальной машины (OP_DONE).


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


    Некоторые исследователи (Virtual-machine Abstraction and Optimization Techniques, 2009) предлагают разделять виртуальные машины на высокоуровневые и низкоуровневые по близости семантики виртуальной машины к семантике физической машины, на которой будет выполняться байт-код.


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


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


    Промежуточное положение занимают интерпретаторы языков программирования общего назначения, имеющие элементы как высокого, так и низкого уровней. В популярнейшей Java Virtual Machine есть как низкоуровневые инструкции для работы со стеком, так и встроенная поддержка объектно-ориентированного программирования с автоматическим выделением памяти.


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


    Аргументы инструкций в байт-коде


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


    Расширим пример, внеся инструкции (OP_ADDI, OP_SUBI), принимающие аргумент в виде байта, следующего непосредственно за опкодом:


    struct {
        uint8_t *ip;
        uint64_t accumulator;
    } vm;
    
    typedef enum {
        /* increment the register */
        OP_INC,
        /* decrement the register */
        OP_DEC,
        /* add the immediate argument to the register */
        OP_ADDI,
        /* subtract the immediate argument from the register */
        OP_SUBI,
        /* stop execution */
        OP_DONE
    } opcode;
    
    typedef enum interpret_result {
        SUCCESS,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    
    void vm_reset(void)
    {
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
    }
    
    interpret_result vm_interpret(uint8_t *bytecode)
    {
        vm_reset();
    
        puts("Start interpreting");
        vm.ip = bytecode;
        for (;;) {
            uint8_t instruction = *vm.ip++;
            switch (instruction) {
            case OP_INC: {
                vm.accumulator++;
                break;
            }
            case OP_DEC: {
                vm.accumulator--;
                break;
            }
            case OP_ADDI: {
                /* get the argument */
                uint8_t arg = *vm.ip++;
                vm.accumulator += arg;
                break;
            }
            case OP_SUBI: {
                /* get the argument */
                uint8_t arg = *vm.ip++;
                vm.accumulator -= arg;
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
    
        return SUCCESS;
    }
    

    Новые инструкции (см. функцию vm_interpret) читают из байт-кода свой аргумент и прибавляют его к регистру / вычитают его из регистра.


    Такой аргумент называется непосредственным аргументом (англ. immediate argument), поскольку он располагается прямо в массиве опкодов. Главное ограничение в нашей реализации заключается в том, что аргумент представляет собой один-единственный байт и может принимать только 256 значений.


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


    Стековая машина


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


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


    #define STACK_MAX 256
    
    struct {
        uint8_t *ip;
    
        /* Fixed-size stack */
        uint64_t stack[STACK_MAX];
        uint64_t *stack_top;
    
        /* A single register containing the result */
        uint64_t result;
    } vm;
    
    typedef enum {
        /* push the immediate argument onto the stack */
        OP_PUSHI,
        /* pop 2 values from the stack, add and push the result onto the stack */
        OP_ADD,
        /* pop 2 values from the stack, subtract and push the result onto the stack */
        OP_SUB,
        /* pop 2 values from the stack, divide and push the result onto the stack */
        OP_DIV,
        /* pop 2 values from the stack, multiply and push the result onto the stack */
        OP_MUL,
        /* pop the top of the stack and set it as execution result */
        OP_POP_RES,
        /* stop execution */
        OP_DONE,
    } opcode;
    
    typedef enum interpret_result {
        SUCCESS,
        ERROR_DIVISION_BY_ZERO,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    
    void vm_reset(void)
    {
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
        vm.stack_top = vm.stack;
    }
    
    void vm_stack_push(uint64_t value)
    {
        *vm.stack_top = value;
        vm.stack_top++;
    }
    
    uint64_t vm_stack_pop(void)
    {
        vm.stack_top--;
        return *vm.stack_top;
    }
    
    interpret_result vm_interpret(uint8_t *bytecode)
    {
        vm_reset();
    
        puts("Start interpreting");
        vm.ip = bytecode;
        for (;;) {
            uint8_t instruction = *vm.ip++;
            switch (instruction) {
            case OP_PUSHI: {
                /* get the argument, push it onto stack */
                uint8_t arg = *vm.ip++;
                vm_stack_push(arg);
                break;
            }
            case OP_ADD: {
                /* Pop 2 values, add 'em, push the result back to the stack */
                uint64_t arg_right = vm_stack_pop();
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left + arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_SUB: {
                /* Pop 2 values, subtract 'em, push the result back to the stack */
                uint64_t arg_right = vm_stack_pop();
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left - arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_DIV: {
                /* Pop 2 values, divide 'em, push the result back to the stack */
                uint64_t arg_right = vm_stack_pop();
                /* Don't forget to handle the div by zero error */
                if (arg_right == 0)
                    return ERROR_DIVISION_BY_ZERO;
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left / arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_MUL: {
                /* Pop 2 values, multiply 'em, push the result back to the stack */
                uint64_t arg_right = vm_stack_pop();
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left * arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_POP_RES: {
                /* Pop the top of the stack, set it as a result value */
                uint64_t res = vm_stack_pop();
                vm.result = res;
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
    
        return SUCCESS;
    }
    

    В этом примере операций уже больше, и почти все они работают только со стеком. OP_PUSHI помещает на стек свой непосредственный аргумент. Инструкции OP_ADD, OP_SUB, OP_DIV, OP_MUL извлекают по паре значений из стека, вычисляют результат и помещают его обратно на стек. OP_POP_RES снимает значение со стека и помещает его в регистр result, предназначенный для результатов работы виртуальной машины.


    Для операции деления (OP_DIV) отлавливается ошибка деления на ноль, что останавливает работу виртуальной машины.


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


    Регистровая машина


    Благодаря своей простоте стековые виртуальные машины получили самое широкое распространение среди разработчиков языков программирования; те же JVM и Python VM используют именно их.


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


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


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


    #define REGISTER_NUM 16
    
    struct {
        uint16_t *ip;
    
        /* Register array */
        uint64_t reg[REGISTER_NUM];
    
        /* A single register containing the result */
        uint64_t result;
    } vm;
    
    typedef enum {
        /* Load an immediate value into r0  */
        OP_LOADI,
        /* Add values in r0,r1 registers and put them into r2 */
        OP_ADD,
        /* Subtract values in r0,r1 registers and put them into r2 */
        OP_SUB,
        /* Divide values in r0,r1 registers and put them into r2 */
        OP_DIV,
        /* Multiply values in r0,r1 registers and put them into r2 */
        OP_MUL,
        /* Move a value from r0 register into the result register */
        OP_MOV_RES,
        /* stop execution */
        OP_DONE,
    } opcode;
    
    typedef enum interpret_result {
        SUCCESS,
        ERROR_DIVISION_BY_ZERO,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    
    void vm_reset(void)
    {
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
    }
    
    void decode(uint16_t instruction,
                uint8_t *op,
                uint8_t *reg0, uint8_t *reg1, uint8_t *reg2,
                uint8_t *imm)
    {
        *op = (instruction & 0xF000) >> 12;
        *reg0 = (instruction & 0x0F00) >> 8;
        *reg1 = (instruction & 0x00F0) >> 4;
        *reg2 = (instruction & 0x000F);
        *imm = (instruction & 0x00FF);
    }
    
    interpret_result vm_interpret(uint16_t *bytecode)
    {
        vm_reset();
        puts("Start interpreting");
        vm.ip = bytecode;
    
        uint8_t op, r0, r1, r2, immediate;
        for (;;) {
            /* fetch the instruction */
            uint16_t instruction = *vm.ip++;
            /* decode it */
            decode(instruction, &op, &r0, &r1, &r2, &immediate);
            /* dispatch */
            switch (op) {
            case OP_LOADI: {
                vm.reg[r0] = immediate;
                break;
            }
            case OP_ADD: {
                vm.reg[r2] = vm.reg[r0] + vm.reg[r1];
                break;
            }
            case OP_SUB: {
                vm.reg[r2] = vm.reg[r0] - vm.reg[r1];
                break;
            }
            case OP_DIV: {
                /* Don't forget to handle the div by zero error */
                if (vm.reg[r1] == 0)
                    return ERROR_DIVISION_BY_ZERO;
                vm.reg[r2] = vm.reg[r0] / vm.reg[r1];
                break;
            }
            case OP_MUL: {
                vm.reg[r2] = vm.reg[r0] * vm.reg[r1];
                break;
            }
            case OP_MOV_RES: {
                vm.result = vm.reg[r0];
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
    
        return SUCCESS;
    }
    

    В примере показана регистровая машина на 16 регистров. Инструкции занимают по 16 бит каждая и кодируются тремя способами:


    1. 4 бита на код операции + 4 бита на имя регистра + 8 бит на аргумент.
    2. 4 бита на код операции + трижды по 4 бита на имена регистров.
    3. 4 бита на код операции + 4 бита на единственное имя регистра + 8 неиспользованных бит.

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


    Первый вид кодирования (4 + 4 + 8) нужен для загрузки данных в регистры операцией OP_LOADI. Второй вид (4 + 4 + 4 + 4) используется для арифметических операций, которые должны знать, где брать пару аргументов и куда складывать результат вычисления. И, наконец, последний вид (4 + 4 + 8 ненужных бит) используется для инструкций с единственным регистром в качестве аргумента, в нашем случае это OP_MOV_RES.


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


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


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


    Стековые и регистровые машины, сравнение


    Есть интересное исследование (Virtual machine showdown: Stack versus registers, 2008), оказавшее большое влияние на все последующие разработки в области виртуальных машин для языков программирования. Его авторы предложили способ прямой трансляции из стекового кода стандартной JVM в регистровый код и сравнили производительность.


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


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


    Спор о том, какая же архитектура лучше, всё ещё не закончен. Если говорить о компиляторах Java, то байт-код Dalvik VM, до недавних пор работавший в каждом Android-устройстве, был регистровым; но титульная JVM сохранила стековый набор инструкций. Виртуальная машина Lua использует регистровую машину, но Python VM — по-прежнему стековая. И так далее.


    Байт-код в интерпретаторах регулярных выражений


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


    
    typedef enum {
        /* match a single char to an immediate argument from the string and advance ip and cp, or
         * abort*/
        OP_CHAR,
        /* jump to and match either left expression or the right one, abort if nothing matches*/
        OP_OR,
        /* do an absolute jump to an offset in the immediate argument */
        OP_JUMP,
        /* stop execution and report a successful match */
        OP_MATCH,
    } opcode;
    
    typedef enum match_result {
        MATCH_OK,
        MATCH_FAIL,
        MATCH_ERROR,
    } match_result;
    
    match_result vm_match_recur(uint8_t *bytecode, uint8_t *ip, char *sp)
    {
        for (;;) {
            uint8_t instruction = *ip++;
            switch (instruction) {
            case OP_CHAR:{
                char cur_c = *sp;
                char arg_c = (char)*ip ;
                /* no match? FAILed to match */
                if (arg_c != cur_c)
                    return MATCH_FAIL;
                /* advance both current instruction and character pointers */
                ip++;
                sp++;
                continue;
            }
            case OP_JUMP:{
                /* read the offset and jump to the instruction */
                uint8_t offset = *ip;
                ip = bytecode + offset;
                continue;
            }
            case OP_OR:{
                /* get both branch offsets */
                uint8_t left_offset = *ip++;
                uint8_t right_offset = *ip;
                /* check if following the first offset get a match */
                uint8_t *left_ip = bytecode + left_offset;
                if (vm_match_recur(bytecode, left_ip, sp) == MATCH_OK)
                    return MATCH_OK;
                /* no match? Check the second branch */
                ip = bytecode + right_offset;
                continue;
            }
            case OP_MATCH:{
                /* success */
                return MATCH_OK;
            }
            }
            return MATCH_ERROR;
        }
    }
    
    match_result vm_match(uint8_t *bytecode, char *str)
    {
        printf("Start matching a string: %s\n", str);
        return vm_match_recur(bytecode, bytecode, str);
    }
    

    Главная инструкция — OP_CHAR. Она берёт свой непосредственный аргумент и сравнивает его с текущим символом в строке (char *sp). В случае совпадения ожидаемого и текущего символов в строке происходит переход к следующей инструкции и следующему символу.


    Машина также понимает операцию перехода (OP_JUMP), принимающую единственный непосредственный аргумент. Аргумент означает абсолютное смещение в байт-коде, откуда следует продолжать вычисление.


    Последняя важная операция — OP_OR. Она принимает два смещения, пробуя применить сначала код по первому из них, потом, в случае ошибки, второму. Делает она это при помощи рекурсивного вызова, то есть инструкция делает обход в глубину дерева всех возможных вариантов регулярного выражения.


    Удивительно, но четырёх опкодов и семидесяти строк кода достаточно, чтобы выразить регулярные выражения вида "abc", "a?bc", "(ab|bc)d", "a*bc". В этой виртуальной машине даже нет явного состояния, так как всё необходимое — указатели на начало потока инструкций, текущую инструкцию и текущий символ — передаётся аргументами рекурсивной функции.


    Если вам интересны детали работы движков регулярных выражений, для начала можете ознакомиться с серией статей Расса Кокса (англ. Russ Cox), автора движка для работы с регулярными выражениями от Google RE2.


    Итоги


    Давайте подведём итоги.


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


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


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


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


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


    Практические рекомендации:


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

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

    Badoo

    305,00

    Big Dating

    Поделиться публикацией

    Похожие публикации

    Комментарии 107
      +1

      Спасибо за статью! Можете рассказать почему решили делать свой байткод а не интерпритатор без компиляции?

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

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

        Ну и… Работает значительно быстрее.
          +1

          Виртуальную машину будете свою реализовывать? Если да, то смотрели ли в сторону готовых GraalVM либо LLVM ?

            0
            Подождите-подождите…

            При чем здесь GraalVM или LLVM? У нас относительно небольшой движок регулярных выражений, а не новый язык программирования, упаси боже. Использоваться он будет использоваться в контексте, о котором я расскажу, вероятно, в другой статье.

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

              У LLVM низкий порог вхождения, есть оптимизатор, интерпретатор и JIT. Это лучше велосипедов даже для не очень больших проектов, мне кажется.
              От статьи больше вреда, чем пользы.

                +4
                Вы предлагаете включать LLVM в проект ради десятка-двух операций над строкой интов..?

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

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

                Обратите внимание, статья о том, как виртуальные машины устроены, а не о том, какой just-in-time компилятор стоит использовать.
                0

                Я могу переформулировать свой вопрос.
                Было интересно почему вы решили писать свою виртуальную машину а не взять готовую, поэтому и вспомнил LLVM и GraalVM которые должны, в моем представлении, помогать в таких случаях.

                  +2
                  В nginx тоже своя легкая вм для реврайтов. Насколько я понял, здесь требуется высокая скорость создания контекста и низкое потребление памяти вкупе с приемлемой производительностью. Разве LLVM/GraalVM здесь подойдет?
                    +4
                    Мне нужно просто выполнять легкие и простенькие запросы. Маленькая виртуальная машинка в таких случаях — практически стандартное решение. Такие машинки есть в ядре Линукса, SQLite и т.д.

                    LLVM это вообще не виртуальная машина в традиционном смысле слова, а фреймворк — и очень хороший фреймворк! — для компиляции промежуточного представления кода в нативный код. В сравнении с бэкэндом GCC сам фреймворк действительно проще. Но объективно это огромный проект в сотни тысяч строк, использовать который не так уж и дешево в смысле времени и нервов.

                    GraalVM это дальнейшая эволюция JVM. Мне даже страшно думать о том, чтобы мои 500-1000 строк кода заменять на JVM-подобную махину.

                    Приведенные же в статье примеры — маленькие машинки.
                      0
                      Такие машинки есть в ядре Линукса,

                      Можете поделиться ссылкой? очень интересно почитать.
                        0
                        Например, вот эта. И еще одна с недавних пор появилась, не помню, как называется.
                          +1
                          Еще спецификация ACPI содержит язык ACPI Machine Language, который тоже должен интерпретироваться ядром. Так что ядро поддерживает минимум две виртуальные машины.
                        0

                        Спасибо, ради этого ответа я вас и мучал вопросами, не знал просто как лучше спросить.

                          +1
                          Думаю, такие вопросы могут появиться хотя бы даже потому, что сам термин «виртуальная машина» сильно перегружен. Это и Parallels, и Bochs, и KVM, и QEMU, и SQLite VM, и многие другие совершенно разные проекты.

                          LLVM сюда, кстати, не относится :-) Это не виртуальная машина, название сильно путает.
              0
              А не знаете случаем легковесного компилятора си в байткод с интерпретатором. Именно легковесного, чтобы интерпретатор влез на микроконтроллер (компилятор не обязательно).
                0
                Кое-что в голову приходит.

                Прежде чем я почешу голову и залезу в старые заметки, можно вопрос? А почему именно интерпретатор, а не просто какой-нибудь маленький компилятор в бинарный код для микроконтроллера?
                  0
                  Уже использую picoc как просто интерпретатор. Проблема в том, что если встроить его, скажем, в плеер некого формата, то развитие и фиксы багов приведут к несовместимости версий плееров. Отладить 1 раз байткод-интерпретатор, встраивать в формат именно байт-код, а потом спокойно доводить компилятор видится проще.
                    0
                    github.com/jnz/q3vm

                    У них был вроде еще один, проще. Компилятор основан на LCC.

                    Собственно, LCC можно переделать под любую виртуальную машину. Бэкэнды там делаются легко, виртуальную машину тоже возможно наклепать.

                    Но я бы взял готовую, ту, что выше.
                      +1
                      Спасибо, выглядит как именно то что надо. И вм простая, можно отдельно реализовать самостоятельно. У меня оказывается звезда на этот проект уже стояла, видимо отложил на посмотреть потом :)
                      0
                      Кстати, ваш picoc тоже, думаю, должно быть очень легко портировать на вашу же гипотетическую виртуальную машинку. Кода там мало, и он хороший.
                        0
                        Да, код хороший. С ним больше проблема что он далеко не полный стандарт си понимает, потому и хотел посмотреть что еще есть. Да и не нужен строковый парсер в самом плеере, вм достаточно.
                          0
                          Надо будет мне глянуть этот picoc, интересно, как они так лаконично все сделали.
                            +2

                            tcc смотрели?

                              0
                              Да, изначально именно его и использовал, привлекает то что у него есть JIT. Но у него нашлись баги, mob бранч сломан, там фактически нет того, кто принимает и проверяет патчи. Я даже находил коммит который сломал, но починить самостоятельно за обозримое время не смог, код уже довольно запутанный. Есть еще про проблемы — он не виртуализирует #include, мне пришлось переделывать/вырезать всю работу с FILE и код разошелся с апстримом. Кроме того опять же нет возможности сделать JIT готового откомпилированного байт-кода (или просто его исполнить, для платформ где JIT не поддерживается).
                      +1
                      Присмотритесь к pawn. Си подобный. Есть отладка через последовательный порт. Сам использую на микроконтроллерах и очень доволен.
                      –2
                      Байт-код, это виртуальная машина. Виртуальная машина, это виртуальная архитектура. Архитектура должна по меньшей мере отвечать каким-то потребностям. Просто «перегонять» программу в байт-код, занятие… так себе. С таким же успехом можно просто взять за байткод команды процессора, ну например, х86, и исполнять их собственным двиглом, добавив блекджек и… Собственно как-то так работают эмуляторы. При этом хотя бы архитектура будет внятной и документированной. Не говоря уже о компиляторах. Можно будет использовать даже C/С++.

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

                      В общем, все здорово, но не ясно зачем это, если не ответить на ключевой вопрос — какие задачи будет решать виртуальная машина и какую архитектуру при этом будет иметь.
                        +3

                        Сводят. Все современные интерпретируемым языки типа Python, Java — сводят, и ещё как! Есть лексер-парсер-транслятор в байт-код, и есть собственно какой-нибудь CPython, который этот байт-код выполняет.
                        У функций в питоне можно в runtime посмотреть (а на самом деле даже и создать функцию из байт-кода) байт-код функции через объект func.code

                          0

                          Забрала съел разметку, конечно же func.__code__

                          +2
                          Вы все правильно сказали: просто так делать байт-код не надо.

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

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

                          «Обратимость». Характерный байт-код языков программирования сильно теряет по сравнению с самим языком, и именно поэтому его легче выполнять интерпретатору, т.к. в нем меньше всяких деталей. Машинный код по сравнению с языком Си, например, очень сильно теряет в выразительности и подробностях. Что вы имеете в виду, когда говорите, что «оно чаще всего обратимо»?
                            0

                            p-код, кстати, как раз таки и является байт-кодом. Непонятно, чем так не угодили вм товарищу rpiontik )

                              +1
                              ok. С терминологией, да, мегостранно. Моя школа разделяла понятие бат-кода и P-кода, теперь, это оказывается синонимы. Последую совету, но все же, думаю неспроста они по разному пишутся. Суть же такова:
                              — при трансляции в байт-код, происходит фактически компиляция, что с одной стороны позволяет использовать механизмы оптимизации, но с другой, устраняет саму суть языка из которого сгенерирован этот самый байт-код;
                              — при трансляции в P-код (в моем понимании), происходит кодирование синтаксиса языка. Ну к примеру, функция заменяется ее уникальным кодом, параметры кодируются в бинарное представление, а строковые константы оформляются ссылками в оптимизированную область памяти. При этом, обратная трансляция может восстановить исходный код. В этом случае синтаксис языка сохраняется даже на уровне интерпретации.

                              И если вариант 2 мне в целом понятен как «быстрое решение для простых задач». То вариант 1 мне кажется чрезмерным, т.к. требует больше телодвижений и должен быть оправдан уникальными свойствами виртуальной машины.

                              Надеюсь так яснее.
                                0
                                В золотые времена Паскаля, когда использовался p-code (или portable code), терминология еще не устоялась, если судить по публикациям того времени. В понимании авторов термина p-код это код для абстрактной машины, который легко и выполнять, и компилировать в машинный код.

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

                                Байт-код в современном понимании потому и используется, что его легко и генерировать, и интерпретировать. Вариант 1 на практике делается очень несложно. В примерах статьи я за часа три-четыре сделал 5(!) виртуальных машинок. Уверяю вас, компиляторы в коды для этих машин из несложных языков я сделаю каждый за те же полдня.

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

                                Конкретный пример из личного опыта.

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

                                Условия эти формируются гейм-дизайнерами в виде XML-описаний, или, если условия хитрые, пишутся программистами. Сначала мы компилировали XML в язык программирования (Питон), и вкладывали в проект. Но потом выяснилось, что дизы хотят другой формат, и хотят легко код подменять чуть ли не лету.

                                Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…

                                Профит со всех сторон.
                                  0

                                  Ну я все же пока радикально не утвердился в верности "новой" терминологии. Потрачу время на поиск "истины".


                                  Со слов "это сделать просто", на моей памяти, начиналось оч много великов.


                                  В остальном, посмотрим, по следующим статьям, чем же плохи остальные реализации и почему нужно ваять что-то свое.

                                    0
                                    Истины нет, истина если не в вине, то в том, что хорошо работает в Вашем проекте. :-)
                                    0
                                    Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…

                                    А в чем плюс по сравнению с иcпользованием, например, lua? А то месяц работы программиста — не очень много, но ощутимо.
                                      0
                                      Там ж большая система, а не сайтик для дяденьки :-) Месяц — нормальная единица планирования.

                                      В общем-то, никто против Луа, или любого другого такого же языка программирования, ничего не имел. Дело было не том, что нужен был еще один язык, а в том, что была плюс минус-понятная абстрактная машина, в термины которогой надо было разные языки переводить.
                                        0
                                        Ну, я к тому, что луа легковесный и легко встраивается. Я не агитирую, а просто интересно, в чем выигрыш использования своего байт-кода по сравнению с использованием распространенного языка.
                                          0
                                          Будь это большой проект на плюсах или простом Си, где надо было бы местами быстренько логику менять, то да, имело бы смысл встроить что-нибудь легковесное.

                                          Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.
                                            0
                                            Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.

                                            Знаете все равно не понятно, зачем следовало создавать виртуальную машину, когда можно было бы все в тот же питон перегонять.
                                            Возможно какой-нибудь наглядный кейс из той задачи, дал бы некое прояснение)
                                              0
                                              1. С питоном надо было перезагружать кластер, со своим же байт-кодом можно делать что угодно.
                                              2. В питон трудно компилировать.
                                              3. Питон — и его программы — слишком много чего умеет, а в собственной виртуалке можно строго ограничить возможности програамы.

                                              По схожим причинам опен-сорсная игра Battle for Wesnoth в свое время убрала возможность скриптовать расширения на питоне в пользу собственного декларативного языка.
                                                +1
                                                В GameDev использование VM — это очень древняя практика. Достаточно вспомнить ту же Sierra On-Line c их SGI еще в 1988 году.
                                0
                                С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее.

                                В 90-х это была новинка, в 2000-х настоящее а сейчас это уже прошлое. Настоящее — jit-компиляторы.

                                  +1
                                  Я вас удивлю, возможно, но интерпретаторы байт-кодов ортогональны just-in-time компиляции. С выполнением исключительно jit-компилированного кода (в динамических языках так точно) закончили к концу девяностых по целому ряду причин. Могу углубиться в детали, если интересно.

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

                                  Если уж на то пошло, то последнее веяние — мета-трейсинг в стиле того, что делает проект PyPy в своем RPython. Вот здесь обзорный пост гляньте.
                                    0

                                    Есть ещё такая интересная штука, как специализация языков, и с помощью нее из интерпретатора и специализированные можно комплилятор получить)

                                      0
                                      Да, вы же про частичное вычисление (partial evaluation)? По моей ссылке про это тоже есть, это с определенными оговорками фреймворк Truffle именно так и работает.
                                      0
                                      > С выполнением исключительно jit-компилированного кода (в динамических языках так точно) закончили к концу девяностых по целому ряду причин.

                                      Насколько я в курсе, дотнет сделан именно так: «основной интерпретатор» вообще не существует, любая функция (метод) переводится в JIT по первому использованию, но может быть обновлена потом. Во всяком случае, в книгах пишется именно так. А он только начинался в девяностых.
                                      Прошу уточнить: это книги врут, или вы имеете в виду что-то немного другое?

                                      > Могу углубиться в детали, если интересно.

                                      Да, интересно.
                                        0
                                        Признаться, конкретно про .NET я мало что знаю. Но про Smalltalk/SELF, JVM, luajit, PyPy, разные реализации JS читал ключевые работы авторов.

                                        История выглядит так, насколько помню сходу:

                                        1. Сначала (8о-е, 90-е, начало нулевых) получили распространение интерпретаторы с jit-ом, предварительно компилировавшим весь код (Smalltalk/SELF, JVM) метод за методом по мере работы программы.

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

                                        2. Стали (JVM, ранние jit в Джаваскрипте, т.е. середина нулевых) делать так: код интерпретируется, но помечаются «горячие» методы, которые потом и компилируются тяжелым комплилятором.

                                        3. Появились (поздние нулевые, Firefox, luajit, PyPy) трассирующие jit-компиляторы, которые ищут «горячие» циклы и компилируют именно их, сначала же все работает с простого интерпретатора.

                                        4. Наши дни. Самые развитые виртуальные (Firefox, V8) машины имеют несколько уровней компиляции. Базовый — байткод, потом «легкий» компилятор и для самых «горячих» методов/трасс — тяжелый компилятор. Код подменяется на лету, по мере сбора статистики.

                                        5. Совсем последние новости: трассирующие jit-компиляторы выходят из моды.

                                        Конечно, в менее крупных проектах такое зверство — каскад компиляторов — малополезно и очень трудоемко, и используется метод, указанный вами: предкомпиляция всех вызываемых методов.

                                        Надеюсь, утолил ваше любопытство :-) Опять же, деталей не знаю, но могу предполжить, что .NET прошел схожие этапы в развитии.
                                      0
                                      Как в микроконтроллер воткнуть jit-компилятор?
                                    0
                                    Дальше было бы интересно почитать про JIT и про трансляцию байт-кода в машинный :)
                                      +4
                                      Ох, про jit рассказать можно, но там много кода, или библиотек, а мне хотелось бы делать что-то с конкретными примерами без внешних зависимостей и легко портируемое.

                                      Думаю, следующий пост будет про те вещи, которые можно сделать в рамках простого Си и трех сотен строк. Уверяю вас, кой-какие приемы неплохо работают и по старинке, без непосредственно руками вбитого машинного кода :-)
                                        0
                                        Да, я понимаю, что в JIT очень много кода. Мои эксперименты с JIT с ипользованием библиотек показали, что овчинка выделки не стоит. Если вы занимались этой темой, было бы интересно почитать про ваш опыт, без погружения в код…

                                        Неплохо — это хорошо, но не великолепно ;)
                                          +2
                                          Скажем так, jit игрушечный я делал, и некоторые из ключевых исследований читал. В бою не пригодилось. Причины:

                                          1. Красиво и эффективно сделать jit-компиляцию сложно.

                                          Я тут где-то писал, что, например, для Емакса уже было несколько попыток, но выхлоп был очень слабый. Разработчики PostgreSQL, недавно внедрившие llvm-jit, хвастаются, что скорость увеличилась на 10-15% в подходящих случаях. Для них это много, но я могу убиться об стену, но начальству не смогу продать два-три месяца разработки ради такой разницы.

                                          2. Применимость в бытовом программировании маленькая.

                                          Задачи такие встречаются редко, и они далеко всегда критичны.

                                          Другое дело, что если не уметь делать, то и не пригодится никогда. По себе и своим коллегам знаю :-) Бывало и так: «Нормально, что мы в кластере молотим данные десять минут», когда я на одной машине за секунды делаю.

                                          А вот простенький интерпретатор действительно раза три был очень нужен.
                                            0
                                            Понял, спасибо, мои выводы совпадают с вашими.
                                      +3
                                      «С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее»

                                      Словно бы мы говорим не о 90-х, а о 60-х годах! В 60-е годы языковые ВМ только развивались и за их использование еще нужно было кого-то агитировать. К середине 70-х такие решения уже окончательно стали частью арсенала рядовых разработчиков. Можно вспомнить, например, статью J. Bell «Threaded Code» (1973) или учебник Вирта «Алгоритмы + структуры данных = программы» (1976), где был описан интерпретатор ВМ PL/0.

                                      Вспомните также многочисленные игры конца 70-х и начала 80-х со встроенным интерпретатором байткода. Вспомните опередившую свое время систему Visi On. А уже в 80-х использованием языковой ВМ уже никого нельзя было удивить.

                                      Исторический контекст важно учитывать и если у этой заметки будет продолжение на тему JIT, то нелишне будет и ознакомиться со статьей «A Brief History of Just-In-Time»: eecs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/JustInTimeCompilation.pdf
                                        +2
                                        Не только ее читал, но и изрядную долю статей в библиографии :-) Это лучший обзор на тему. Плюс вам в карму за упоминание.

                                        И совершенно согласен с вами насчет того, что и виртуальные машины, и компиляция на лету (aka jit) — технологии старые.

                                        Помнится, известнейшая игра Another World была со встроенной виртуальной машиной; многие — почти все? — квесты от LucasGames использовали виртуальную машину. Infocom для своих текстовых игр тоже держали специальный движок с виртуальной машиной.

                                        Однако же, средний потребитель софта до Джавы кушал именно программы, собранные из Си или Паскаля, компилировавшихся в машинный код.
                                          +1
                                          А знакомы ли Вы с системой META II (1964)? Такие известные личности, как Д. Кнут, А. Кэй или Д. Армстронг (автор Erlang) отзывались о META II очень положительно.

                                          META II это генератор компиляторов, который написан на себе самом и порождает код для стековой VM. Оригинальная статья о META II в числе моих самых любимых: www.ibm-1401.info/Meta-II-schorre.pdf

                                          P.S. Когда-то у меня была идея написать краткий вводный курс по компиляторам-интерпретаторам с разбором всего двух систем: META II и Forth.
                                            +1
                                            Гм. Нет, не знаком. Я за последние месяцы множество статей перепахал, в том числе и Форту, но сознательно раньше конца семидесятых уже не копал — надо ж где-то заканчивать. Я ж не преподаватель :-) Но внесту в очередь на прочтение, пока драйв и интерес есть.

                                            Про Форт же, да, конечно. Я так понимаю, что по поводу быстрых интерпретаторов именно байт-кода все было сделано еще в 70-е. Почти все интересные работы 2000-х ссылаются на идею «шитого» кода именно на примере Форта.
                                              0
                                              Да, причем некоторые из этих древних техник до сих пор недоступны в рамках стандартного Си. В частности, в рамках интерпретатора шитого кода можно было бы избавиться от конструкции switch с применением вычислимого goto. Но такой вариант является использованием нестандартного gcc-расширения.

                                              Поделюсь еще одной малоизвестной статьей. На сей раз достаточно свежей. Ее автор, В. Макаров (известный разработчик в gcc-сообществе) сравнивает регистровые и стековые ВМ, пишет о шитом коде и т.д. уже с современных позиций: arxiv.org/pdf/1604.01290.pdf
                                                0
                                                О, очень интересно, спасибо большое, сейчас прям и распечатаю. Эту прочитаю срочно!
                                                  0
                                                  Я как раз бился над вычисляемым goto в си, для того чтобы прыгнуть в нужное место раскрученного цикла и сравниться с ручным асмом. Оказалось это можно, примерно вот так:
                                                      int p = (n/8) & 7;
                                                      switch(p)
                                                      {
                                                      case 0: do { do_some_part_job;
                                                      case 7:      do_some_part_job;
                                                      case 6:      do_some_part_job;
                                                      case 5:      do_some_part_job;
                                                      case 4:      do_some_part_job;
                                                      case 3:      do_some_part_job;
                                                      case 2:      do_some_part_job;
                                                      case 1:      do_some_part_job;
                                                          } while(--n > 0);
                                                          break;
                                                      }
                                                  

                                                  Но от компилятора сильно зависит, нужны нестандартные расширения или нет. MSVC, например, нужно было default: __assume(0);, чтобы он понял что остальные варианты switch недоступны и range проверка не нужна.
                                                    0
                                                    Это ж устройство Даффа, да? :-)

                                                    Ходите по грани непортируемости решения. :-)
                                                      0
                                                      Ну да :) Не замечал, чтобы были проблемы с портируемостью. Да и куда деваться, выигрыш был слишком существенен чтобы игнорировать, а вызов асм функции сбивает оптимизирующий компилятор еще больше + он не может переделать ей ABI, перемапить регистры итд. Так что хорошо еще что не на асме =)
                                                      Я пробовал rust еще, но на нем так же не получается догнать асм + у него пока нет alloca и другие проблемы.
                                                    +1
                                                    Прочитал Макарова о его языке программировании и всяких техниках интерпретации.

                                                    Ну что ж. Джентельмен серьезный :-)

                                                    Выжимка для самого себя по поводу статьи:
                                                    1. Уже не так важно, как именно оформлен главный цикл интерпретатора.
                                                    2. Правильная регистровая машина может быть в разы быстрее стековой.
                                                    3. Возможно быстро и легко сделать портативный jit-компилятор.
                                                    4. Чем меньше работает диспетчер — тем лучше; «склеивать» инструкции хорошо.
                                                    5. Дальнейшие улучшения идут за счет техник, специфичных для динамических языков.

                                                    Вообще, у него там совсем маньячный подход, т.е. он действительно много приемов использует.
                                                    0
                                                    В работах Чарльза Мура(создателя Forth-а) где-то в конце 2000-х был интересный быстрый компилятор стекового языка colorForth, там были и исходники.

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

                                                    Я переработал идеи, но за несколько редких подходов законченной реализации нет. Сейчас думаю сделать очередной подход…

                                                    +1
                                                    Вот тут о Мете еще интереснее: www.bayfronttechnologies.com/mc_tutorial.html

                                                    Исполнение прямо в браузере плюс подробное руководство, как расширить метакомпилятор
                                                      0
                                                      Да, это хорошее руководство. Кстати, для любого интересующегося программиста посоветую полезное упражнение: реализовать META II на вашем любимом языке. Так, чтобы код системой порождался для вашего же языка.

                                                      А вот еще замечательная статья, которую Вы, возможно, не видели: www.vpri.org/pdf/tr2010003_PEG.pdf

                                                      Ian Piumarta — один из разработчиков, участвовавших в проекте STEPS Алана Кэя. И его система из статьи мне нравится своим изяществом значительно больше, чем известная oMeta.

                                                      Кстати, один из вариантов META II использовался для создания знаменитой «The Mother of All Demos» (1968). И примечателен сам подход: создание сложной системы в нотациях множества DSL. Только в те времена их называли SPL — special purpose languages. Воистину, новое — хорошо забытое старое.
                                                0

                                                А


                                                главная функция с assert-ами

                                                где?

                                                  0
                                                  В коде на Гитхабе, там в самом начале ссылка есть. Полные листинги с тестами очень длинные выходили.

                                                  Возможно, не стоило их здесь упоминать. :-)
                                                    0

                                                    Может под спойлер бы...

                                                      0
                                                      Да, пожалуй, нужен какой-то гибридный вариант.

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

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

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

                                                    Всякие там дополнительные приемы могут эти затраты снизить с 10-20 инструкций на один байт-код в среднем до 5-10 в самых быстрых из языков с виртуальной машиной. Это я так, не считая.
                                                      0
                                                      Если важна скорость, то я думаю легко сделать простенький компилятор байткода в машинный код. Особенно если сразу сделать байткод виртуальной машины максимально близким к целевому ассемблеру.
                                                        +1
                                                        Ну… Можно и так, но это, в сущности, и есть aot- или jit-компиляция. Компиляцию наперед сделать можно, но в языках высокого уровня профита будет мало, т.к. они и так время по большей части в телах инструкций проводят.

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

                                                        Опять же, серьезный оптимизирующий компилятор — штука сложная.

                                                        Словом, в общем случае я голосую за простенькие специализированные виртуалочки.
                                                      0
                                                      Вот немного устаревший бенчмарк разных встраиваемых языков:
                                                      github.com/r-lyeh-archived/scriptorium
                                                      0

                                                      Ещё хотелось бы понять, чем байткод отличается от шитого кода? Что из них быстрее работает?

                                                        0
                                                        «Шитый» код — способ прохода по программе. Подвидов «шитого» кода — масса.

                                                        Стандартный подход к интерпретатору — здоровенный «switch» от байта.

                                                        Но в «шитом» коде можно, например, превратить массив байт в массив указателей на функции, которые потом последовательно вызывать. Другой вариант — массив меток, к которым переходить при помощи goto.

                                                        Где-то до начала последнего десятилетия это очень даже имело смысл, но есть исследования, показывающие, что сейчас процессоры научились хорошо предсказывать ветвления через switch. Основная проблема метода — может понадобиться ассемблер, т.е. это плохо портируется.
                                                        0
                                                        Всегда интересовало, какой с какой целью в виртуальные машины добавляют опкод NOP?
                                                          +2
                                                          Что бы выровнять функции по границе слова, например. Или что бы заменить их потом на какой-нибуть DBG_STOP и проконтолировать переход на неправильный адрес.
                                                            +2
                                                            Да по-разному, это типа такой костыль.

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

                                                            Пример второй, реалистичный. У вас байт-код, где есть безусловные переходы по каким-либо адресам, то есть в нем можно найти: JUMP. Вы хотите убрать какие-то инструкции до указанного адреса, но тогда надо менять адреса у JUMP-ов. Заменяете инстркции на NOP — и все хорошо.

                                                            Пример третий, хитрый. В некоторых архитектурах чтение байтов по адресами, не выровненным по длине машинного слова, либо запрещено, либо работает неэффективно. NOP-ами можно сделать выравнивание.
                                                            –1
                                                            Cпасибо за статью!
                                                            Функцию vm_stack_pop можно сократить
                                                            uint64_t vm_stack_pop(void)
                                                            {
                                                                vm.stack_top--;
                                                                return *vm.stack_top;
                                                            }
                                                            

                                                            До
                                                            uint64_t vm_stack_pop(void)
                                                            {
                                                                return --*vm.stack_top;
                                                            }
                                                            

                                                              0
                                                              Еще вопрос есть. Существуют мультистековые машины, в чем их преимущества и недостатки?
                                                                0
                                                                А какие именно мультистековые машины вы имеете в виду? Те, что разделяют стеки функций и вычислений?
                                                                  0
                                                                  Я увидел, что в регистровых машинах используется набор регистров, а в стековых машинах только один стек. Вот я и подумал, а есть ли машины с несколькими стеками? Набрал в поисковике оказывается есть, в книге «Введение в теорию автоматов, языков и вычислений. 2-е издание».
                                                                  Интересно, как повлияет на вид байт-кода использование нескольких стеков и будет ли это эффективно в каких-то случаях?
                                                                    0
                                                                    Вы говорите про математические модели, я, признаться, в них не очень разбираюсь, так как универ давно уже не посещал. :-)

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

                                                                    С практической стороны могу сказать следующее:

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

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

                                                                    3. Байт-код от регистровости зависит сильно. Это и есть самая большая разница. Одно дело, когда надо делать PUSH 1,PUSH 2,ADD, другое — ADD r1,r2,r3.

                                                                    4. Вычислительная способность регистровых и стековых машин не особо отличаются.

                                                                    Два стека действительно часто используются. Но у нас ж в наличии и так есть условно бесконечная лента памяти, поэтому разницы в вычислительных возможностях это не делает.
                                                                      0
                                                                      Я тоже давным-давно не студент.) Математические модели иногда переходят в практические.
                                                                      А про два стека вы говорите, это стек вызовов функций и стек вычислений?
                                                                      Если он разделен на таковые(в некоторых процессорах… хотя в виртуальных машинах можно эмулировать все что угодно), то это позволяет избежать проблему перезаписи адреса возврата в случае переполнения стека.
                                                                        0
                                                                        В реальных процессорах я про два стека не слышал. В x86 стек один точно.

                                                                        Насчет переполнения стека… Тут сильно от языка зависит. В приличных языках это вообще невозможно :-) кадр каждой функции аллоцируется один раз и не меняется во время работы функции.

                                                                        Да, второй стек в виртуальных машинах обычно делают для кадров функций и удобства работы с ними: прохода вверх по всему стеку и т.д…
                                                                          0
                                                                          Про x86 я тоже знаю, что нет 2 стеков. Также знаю, что в других процессорах есть разделение памяти данных и кода. В виртуальных машинах это тоже реализуется?

                                                                          Про переполнение стека — ну если процессор позволяет, почему бы он не мог бы переполнится :) (Закон Мерфи). Приличные языки — это не С? =)

                                                                          Уверен, что способы построения виртуальных машин влияют на архитектуру реальных процессоров.
                                                                            0
                                                                            Нашел по теме следующее softwareengineering.stackexchange.com/a/251942/293202
                                                                            Вы знаете, что-нибудь о SECD machine?
                                                                              0
                                                                              Ага, SECD и его потомков… Немало.

                                                                              Есть еще WAM, раз уж на то пошло, и многие другие.

                                                                              Надо будет как-нибудь провести исследование самых влиятельных из популярных абстрактных машин и написать сюда статеечку.
                                                                                0
                                                                                Да, было бы интересно почитать .)
                                                                              0
                                                                              Опять же, это вотчина Форта. Есть форт-процессоры с двумя аппаратными стеками (возвратов и вычислений). Для каждого типа данных можно заводить свой стек. Собственно, даже на x86 есть еще и FPU-стек.
                                                                                0
                                                                                Я не изучал форт-процессоры, посмотрю.
                                                                                А если рассматривать мультиядерные процессоры, то там и еще пару стеков найдется.)
                                                                                Есть также java-процессоры.
                                                                                Кстати, я даже не удивлюсь если есть какой-нибудь MSIL-processor.
                                                                                По сути, получается, можно построить виртуальную машину(если существующие процессоры не позволяют реализовать свои задумки), а потом построить на основе этого свой процессор(hardware) и байт-код будет обычным машинным кодом.
                                                                                  0
                                                                                  Ага, так многие разработчики архитектур или расширений к наборам инструкций и проверяют свои идеи: берут какой-нибудь эмулятор подходящий, приписывают к нему обработчики новых инструкций и смотрят, что на выходе.

                                                                                  Эмулятор это зачастую, собственно, банальный интерпретатор байт-кода, только байт-код повторяет код машинный.
                                                                                  0
                                                                                  Да, кстати, вы правы, про FPU я как-то забыл. Сто лет эти инструкции в ассемблере не видел :-)
                                                                                  0
                                                                                  Думаю, влияние взаимное.

                                                                                  Разработчики процессоров подстраиваются под популярные виртуальные машины, типа JVM или Python VM, и наоборот, разработчики виртуальных машин стремятся оптимально «железный» процессор использовать.

                                                                                  Ну… Я очень люблю Си, но это не значит, что я не знаю, про его фундаментальные проблемы :-)
                                                                            0
                                                                            Если весь код выполняется императивно, то нужды в нескольких стеках (именно стеках операндов) кмк, нет. Это имеет смысл если мы вводим параллельные вычисления.
                                                                        +1
                                                                        Извеняюсь, ошибка в коде.) Удалил бы, да не могу.
                                                                          +1
                                                                          Ага, ошибка. В любом случае, разницы особой нет, если глянуть ассемблер на выходе, а мой вариант читается проще людям, не пишущим регулярно на Си.
                                                                            0
                                                                            Да, на выходе *(--vm.stack_top); тоже самое.
                                                                              0
                                                                              Кто бы сомневался.
                                                                              Было тут на хабре где-то упоминание книги, автор которой считал, что чем короче исходник — тем быстрее работает код. Но название книги там, к сожалению, не упомянули, чтобы не выглядело моральной атакой на её автора.
                                                                                0
                                                                                ))) Это уточнение для тех кто не понял(новичков). Не знаю, мне просто на вид проще, в данном случае, в одну строку, а не в две.

                                                                                А так, ну компилируется быстрее, совсеееееем чуть-чуть))) пробелы просто убрать и то лучше будет. А если интерпретатор, то тоже такая же несущественная разница.

                                                                                Ну автор книги, конечно заблуждается, если он существует.
                                                                                Интересно было бы узнать о чем книга =))

                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                      Самое читаемое