Оптимизация для интерпретатора умопомрачения

Question

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

Какими способами я могу изменить этого переводчика для повышения производительности (или иным образом)?

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

struct { long instruction; long loop; }

. Значение loop является индексом соответствующей инструкции ], если инструкция [, и индекс соответствующей инструкции [, если инструкция ], позволяющая быстрый переход.Я полагаю, что этот процесс «синтаксического анализа» (который не занимает много времени) сокращает время выполнения по сравнению с избыточным повторным анализом, чтобы находить совпадающие квадратные скобки каждый раз, когда они необходимы.

Интересный тест скорости интерпретатора brainfuck -эта программа:

++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>

1. первая версия интерпретатора
2. интерпретатор после реализации ответа Джерри Коффина , который удаляет гигантский переключатель в цикле выполнения, делая instruction struct instruction прямым указателем на функцию операции - это работает медленнее, чем в предыдущей версии (издержки вызова функции?)
3. интерпретатор после отмены предыдущего изменения и добавления оптимизации для «свертывания» нескольких последовательных операций без цикла, сокращая циклы цикла - это выполняется незначительнобыстрее оригинала

Answer 1

Ну, это не C. И это не интерпретатор. Так что, да, этот вопрос совершенно неуместен.

Но что это такое? Это совершенно портативный компилятор мозгового штурма, использующий вариационные шаблоны C ++ 0x. Вы должны #define PROGRAM как последовательность символов синтаксиса C, разделенных запятыми, потому что я не мог извлечь их из строки во время компиляции. Но в остальном это законно. Я думаю.

Протестировано с g ++ 4.5.2, с использованием g++ -std=c++0x -O2 -Wall.

#include <cstdio>
#include <vector>

#define PROGRAM '+', '+', '+', '+', '+', '+', '+', '+', '[', '-', '>',  \
        '-', '[', '-', '>', '-', '[', '-', '>', '-', '[', '-', ']', '<', \
        ']', '<', ']', '<', ']', '>', '+', '+', '+', '+', '+', '+', '+', \
        '+', '[', '<', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', \
        '>', '-', ']', '<', '[', '>', '+', '>', '+', '<', '<', '-', ']', \
        '>', '-', '.', '>', '-', '-', '-', '-', '-', '.', '>'

template<char... all>
struct C;

template<char... rest>
struct C<'>', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder remainder;
    static char *body(char *p) {
        return rest_t::body(p+1);
    }
};

template<char... rest>
struct C<'<', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder remainder;
    static char *body(char *p) {
        return rest_t::body(p-1);
    }
};

template<char... rest>
struct C<'+', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder remainder;
    static char *body(char *p) {
        ++*p;
        return rest_t::body(p);
    }
};


template<char... rest>
struct C<'-', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder remainder;
    static char *body(char *p) {
        --*p;
        return rest_t::body(p);
    }
};

template<char... rest>
struct C<'.', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder remainder;
    static char *body(char *p) {
        putchar(*p);
        return rest_t::body(p);
    }
};

template<char... rest>
struct C<',', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder remainder;
    static char *body(char *p) {
        *p = getchar();
        return rest_t::body(p);
    }
};

template<char... rest>
struct C<'[', rest...> {
    typedef C<rest...> rest_t;
    typedef typename rest_t::remainder::remainder remainder;
    static char *body(char *p) {
        while (*p) {
            p = rest_t::body(p);
        }
        return rest_t::remainder::body(p);
    }
};


template<char... rest>
struct C<']', rest...> {
    typedef C<rest...> rest_t;
    struct remainder_hack {
        typedef typename rest_t::remainder remainder;
        static char *body(char *p) {
            return rest_t::body(p);
        }
    };
    typedef remainder_hack remainder;
    static char *body(char *p) {
        return p;
    }
};

template<>
struct C<> {
    static char *body(char *p) {
        return p;
    }
    struct remainder {
        static char *body(char *p) {
            return p;
        }
    };
};

int
main(int argc, char *argv[])
{
    std::vector<char> v(30000, 0);
    C<PROGRAM> thing;

    thing.body(&v[0]);
    return 0;
}

Answer 2

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

typedef int return_type;
typedef return_type (*f)(void);

f *im = malloc(sizeof(f) * ia);

ci = (*(im[ci]))();

У меня также было бы три отдельные функции длякаждая инструкция, одна для каждого режима BF_END_ *, так что вам придется иметь дело только с этим на этапе «компиляции».Когда вы выполняете код, у вас будет указатель на правильную функцию.

Редактировать:

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

for (ii = 0; (i = getc(fp)) != EOF; ++ii) {
    if (++in > ia) {
        ia *= 2;
        im = realloc(im, sizeof(*im) * ia);
        loops = realloc(loops, sizeof(*loops) * ia);
    }
    im[in-1] = i;
    switch (i) {
        case BF_OP_LSTART:
            if (ln >= la)
                ls = realloc(ls, sizeof(*ls) * (la *= 2));
            ls[ln++] = ii;
            break;
        case BF_OP_LEND:
            loops[in-1] = ls[--ln];
            loops[ls[ln]] = ii;
            break;
    }
}

Это не имеет никакого реального значения для скорости, но делаеткод намного короче, и (по крайней мере, на мой взгляд) легче понять.

Edit2:

Хорошо, у меня была возможность поиграть с этим немного больше, и я нашелодна (довольно странная) оптимизация, которая, кажется, помогает хотя бы немного.Компиляторы часто генерируют немного лучший код для операторов switch с плотными значениями регистра, поэтому я попытался преобразовать его в него и получил улучшение примерно на 9-10% (в зависимости от компилятора).

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#define BF_END_ERROR    'e'
#define BF_END_IGNORE   'i'
#define BF_END_WRAP     'w'
#define BF_OP_VINC      '+'
#define BF_OP_VDEC      '-'
#define BF_OP_PINC      '>'
#define BF_OP_PDEC      '<'
#define BF_OP_LSTART    '['
#define BF_OP_LEND      ']'
#define BF_OP_IN        ','
#define BF_OP_OUT       '.'

enum { 
    C_OP_VINC, 
    C_OP_VDEC, 
    C_OP_PINC, 
    C_OP_PDEC, 
    C_OP_LSTART, 
    C_OP_LEND, 
    C_OP_IN, 
    C_OP_OUT 
};

typedef struct {
    long instruction;       /* instruction type */
    long loop;              /* 'other' instruction index in a loop */
} instruction;
void die(const char *s, ...) {
    va_list a;
    va_start(a, s);
    fprintf(stderr, "brief: error: ");
    vfprintf(stderr, s, a);
    putchar(10);
    va_end(a);
    exit(1);
}
int main(int argc, char **argv) {
    unsigned instruction_count = 0;
    long
        ci = 0,             /* current cell index */
        cn = 4096,          /* number of cells to allocate */
        cw = BF_END_WRAP,   /* cell wrap behaviour */
        ia = 4096,          /* number of allocated instructions */
        ii = 0,             /* current instruction index */
        in = 0,             /* number of used instructions */
        la = 4096,          /* loop stack allocation */
        ln = 0,             /* loop stack used */
        va = 0,             /* minimum value */
        vb = 255,           /* maximum value */
        vw = BF_END_WRAP    /* value wrap behaviour */
    ;
    instruction *im = malloc(sizeof(instruction) * ia); /* instruction memory */
    long *cm = NULL;        /* cell memory */
    long *ls = malloc(sizeof(long) * la);               /* loop stack */
    FILE *fp = NULL;
    int i;
    while ((i = getopt(argc, argv, "a:b:c:f:hv:w:")) != -1) {
        switch (i) {
            case 'a': va = atol(optarg); break;
            case 'b': vb = atol(optarg); break;
            case 'c': cn = atol(optarg); break;
            case 'f':
                fp = fopen(optarg, "r");
                if (!fp)
                    die("%s: %s", optarg, strerror(errno));
                break;
            case 'h':
                fputs(
                    "brief: a flexible brainfuck interpreter\n"
                    "usage: brief [options]\n\n"
                    "options:\n"
                    "   -a  set minimum cell value (default 0)\n"
                    "   -b  set maximum cell value (default 255)\n"
                    "   -c  set cells to allocate (default 4096)\n"
                    "   -f  source file name (required)\n"
                    "   -h  this help output\n"
                    "   -v  value over/underflow behaviour\n"
                    "   -w  cell pointer over/underflow behaviour\n\n"
                , stderr);
                fputs(
                    "cells are 'long int' values, so do not use -a with a "
                    "value less than -2^31 or -2^63, and do not use -b with a "
                    "value more than 2^31-1 or 2^63-1, depending on your "
                    "architecture's 'long int' size.\n\n"
                    "over/underflow behaviours can be one of:\n"
                    "   e   throw an error and quit upon over/underflow\n"
                    "   i   do nothing when attempting to over/underflow\n"
                    "   w   wrap-around to other end upon over/underflow\n"
                , stderr);
                exit(1);
                break;
            case 'v': vw = optarg[0]; break;
            case 'w': cw = optarg[0]; break;
            default: break;
        }
    }
    if (!fp)
        die("no source file specified; use -f");
    for (ii = 0; (i = getc(fp)) != EOF; ++ii) {
        if (++in > ia) {
            ia *= 2;
            im = realloc(im, sizeof(*im) * ia);
        }
        switch (i) {
            case BF_OP_LSTART:
                if (ln >= la)
                    ls = realloc(ls, sizeof(*ls) * (la *= 2));
                ls[ln++] = ii;
                im[in-1].instruction = C_OP_LSTART;
                break;
            case BF_OP_LEND:
                im[in-1].loop = ls[--ln];
                im[ls[ln]].loop = ii;
                im[in-1].instruction = C_OP_LEND;
                break;
            case BF_OP_VINC:
                im[in-1].instruction = C_OP_VINC;
                break;
            case BF_OP_VDEC:
                im[in-1].instruction = C_OP_VDEC;
                break;
            case BF_OP_PINC:
                im[in-1].instruction = C_OP_PINC;
                break;
            case BF_OP_PDEC:
                im[in-1].instruction = C_OP_PDEC;
                break;
            case BF_OP_IN:
                im[in-1].instruction = C_OP_IN;
                break;
            case BF_OP_OUT:
                im[in-1].instruction = C_OP_OUT;
                break;
        }
    }
    cm = memset(malloc(cn * sizeof(long)), 0, cn * sizeof(long));
    for (ii = 0; ii < in; ii++) {
        ++instruction_count;
        switch (im[ii].instruction) {
            case C_OP_VINC:
                if (cm[ci] == vb)
                    switch (vw) {
                        case BF_END_ERROR:
                            die("value overflow");
                            break;
                        case BF_END_IGNORE: break;
                        case BF_END_WRAP: cm[ci] = 0; break;
                    }
                else ++cm[ci];
                break;
            case C_OP_VDEC:
                if (cm[ci] == 0)
                    switch (vw) {
                        case BF_END_ERROR:
                            die("value underflow");
                            break;
                        case BF_END_IGNORE: break;
                        case BF_END_WRAP: cm[ci] = vb; break;
                    }
                else --cm[ci];
                break;
            case C_OP_PINC:
                if (ci == cn - 1)
                    switch (cw) {
                        case BF_END_ERROR:
                            die("cell index overflow");
                            break;
                        case BF_END_IGNORE: break;
                        case BF_END_WRAP: ci = 0; break;
                    }
                else ++ci;
                break;
            case C_OP_PDEC:
                if (ci == 0)
                    switch (cw) {
                        case BF_END_ERROR:
                            die("cell index underflow");
                            break;
                        case BF_END_IGNORE: break;
                        case BF_END_WRAP: ci = cn - 1; break;
                    }
                else --ci;
                break;
            case C_OP_IN:
                cm[ci] = getchar();
                break;
            case C_OP_OUT:
                putchar(cm[ci]);
                break;
            case C_OP_LSTART:
                if (!cm[ci])
                    ii = im[ii].loop;
                break;
            case C_OP_LEND:
                if (cm[ci])
                    ii = im[ii].loop;
                break;
            default: break;
        }
    }
    fprintf(stderr, "Executed %d instructions\n", instruction_count);
    free(cm);
    return 0;
}

Answer 3

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

Во-первых, отказ от ответственности: я не программист x86 - у меня естьпроделал приличный объем работы во встроенных средах и теперь (с мобильными телефонами) чипы ARM.Что касается хороших вещей ...

Есть два основных способа сделать ваш интерпретатор быстрее: заставить его оптимизировать сам код BF и оптимизировать сам интерпретатор.Я рекомендую немного и того, и другого на шаге ниже.

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

Несмотря на скорость, с которой ветки могут происходить на x86, этовсе еще вероятно стоит потратить немного накладных расходов на не ветвление.Так как инструкции BF в любом случае настолько просты, что они могут принять форму «выполняйте большинство инструкций одновременно, так как это быстрее, чем в другой ветви».Часть этого может даже выполняться параллельно процессором, где не может быть ветвления.(x86 имеет достаточно модулей декодирования и выполнения в одном ядре, так что это возможно)

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

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

С этой целью я рекомендую упростить то, что делает ваш BF-интерпретатор (сделайте так, чтобы он был силениз двух для значений, например).Один только побитовый трюк AND и принудительное использование переноса (как это имеет место в большинстве современных языков программирования для переполнения / недополнения) уже удаляют как минимум две ветви.

После того, как об этом позаботятся, это позволяетИнтересная оптимизация: отбросьте инструкции BF и вместо этого заставьте ваш компьютер выполнять другие инструкции, которые больше подходят для интерпретатора.

Рассмотрим Java: Java не интерпретирует.Это JIT на совершенно другой язык.

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

Я рекомендую создать инструкцию со следующей информацией:

• сумма, добавляемая к значению в указатель данных (или вычитание - вычитание просто добавляет отрицательное число)
• сумма, добавляемая к значению из указатель данных (снова иливычесть)
• указатель на следующую инструкцию для выполнения
• значение, которое сравнивается со значением в указателе данных до , оно изменяется

Затем цикл интерпретатора изменяется на логику следующим образом: добавьте значение данных в инструкции к значению в указателе данных, добавьте значение данных address в инструкции к самому указателю данных, если значениеесли указатель данных совпадает с нашим значением сравнения, установите указатель инструкции на новый указатель инструкции продолжения (до следующего цикла интерпретатора), если значение сравнения является специальнымзначение l (например, вы можете выбрать 0x80000000)обрабатывать ввод / вывод материала увеличить адрес инструкции на один

Первоначальная интерпретация теперь становится сложнее: Теперь инструкции могут объединять +, -, <,>, а иногда даже [и обычно] в одну и ту же инструкцию. Первая ветвь в цикле может быть представлена ​​без ветвления, если вы разбираетесь в этом (и даже более эффективно, если какая-то застрявшая сборка или некоторые встроенные функции компилятора). Возможно, вы захотите сообщить компилятору, что вторая ветвь вряд ли ударит (в этом случае узким местом является узкая область ввода / вывода, а не скорость интерпретации, поэтому, даже если вы делаете много ввода / вывода, одну маленькую неоптимизированную ветвь не будет иметь значения).

Необходимо соблюдать осторожность в условиях окончания работы. Последняя инструкция в вашей интерпретируемой BF-программе теперь ВСЕГДА должна указывать на инструкцию NULL, чтобы цикл завершился.

Порядок, в котором происходит интерпретация, важен, потому что - / + выполняется до <> до [выполняется до] перед I / O. Итак,> + - это две интерпретированные инструкции, а +> - одна.

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

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

P.S. Отлично вопрос!

Answer 4

Brainfuck должно быть довольно легко скомпилировано в C-код, который вы затем компилируете и выполняете. Это, вероятно, был бы очень быстрый BF "переводчик".

По сути, все, что вам нужно сделать, это сгенерировать довольно тривиальный код для каждого оператора brainfuck слева направо в программе. Можно легко оптимизировать последовательности + и -; Точно так же можно оптимизировать последовательности <и>, кэшируя счетчики каждого из последних встречается. Это своего рода оптимизация глазка.

Вот черновой компилятор, принимающий код BF в командной строке и вывод скомпилированной программы на консоль:

int increments;  // holds pending increment operations

void flush_increments(){
   if (increments==0) return;
   printf("  *ptr+=%d;\n",increments);
   increments=0;
}

int steps; // holds pending pointer steps

void flush_steps(){
   if (steps==0) return;
   printf("  ptr+=%d;\n",steps);
   steps=0;
}

int main(int argc, char **argv){
    // Brainfuck compiler
    if( !(argc > 1) )
        return 1;
    unsigned char *code = argv[1];
    int nesting=0;
    printf("int main(){\n");
    printf("  #define CELLSPACE 1000\n");
    printf("  unsigned char *ptr = malloc(sizeof(char)*CELLSPACE);\n");
    printf("  if(ptr == NULL) return 1;\n")
    printf("  for(int i=0;i<CELLSPACED;i++) ptr[i]=0; // reset cell space to zeros");
    increments=0;
    steps=0;
    for(;;) {
        switch(*code++) {
            case '+':
                flush_steps();
                ++increments;
                break;
            case '-':
                flush_steps();
                --increments;
                break;
            case '>':
                flush_increments();
                ++steps;
                break;
            case '<':
                flush_increments();
                --steps;
                break;
            case '[':
                flush_increments();
                flush_steps();
                printf("while(*ptr){");
                ++nesting;
                break;
            case ']': 
                flush_increments();
                flush_steps();
                if (--nesting<0)
                   { printf("Unmatched ']'\n");
                     return 1;
                   }
                printf("}\n";);
                break;
            case '.':
                flush_increments();
                flush_steps();
                printf(" putc(*ptr, stdout);\n");
                break;
            case ',':
                increments=0;
                flush_steps();
                printf("*ptr = getc(stdin);");
                break;
            case '\0':
                 printf("}");
                 if (nesting>0)
                   { printf("Unmatched '['\n");
                     return 1;
                   }
                return 0;
        }
    }
}

Это написано на макушке моей головы, вдохновлено кодом Мэтью Бланшара (спасибо Мэтью!), но не проверено. Я оставлю это другой душе; не стесняйтесь исправлять код если вы найдете проблему. Очевидно, это было бы улучшено, если бы он записал свой код в файл: -}

[Я использовал статью http://en.wikipedia.org/wiki/Brainfuck как очевидное вдохновение для создания кода].

Программа БФ ОП:

++++++++ [-> - [-> - [-> - [-] <] <] <]> ++++++++ [<+++++++ +++> -] <[> +> + << -]> -..> ----->

должен компилироваться в (отступ добавлен):

 int main(){
 #define CELLSPACE 1000
   unsigned char *ptr = malloc(sizeof(char)*CELLSPACE);
   if(ptr == NULL) return 1;
   for(int i=0;i<CELLSPACED;i++) ptr[i]=0; // reset cell space to zeros
   *ptr+=8;
   while(*ptr) {
      *ptr+=-1;
      ptr+=1;
      *ptr+=-1;
     while(*ptr) {
       *ptr+=-1;
       ptr+=1;
       *ptr+=-1;
       while(*ptr) {
         *ptr+=-1;
         ptr+=1;
         *ptr+=-1;
         while(*ptr) {
            *ptr+=-1;
         }
         ptr+=-1;
       }
       ptr+=-1;
     }
     ptr+=1;
     *ptr+=8;
     while (*ptr) {
        ptr+=-1;
        *ptr+=10;
        ptr+=1;
        *ptr+=-1;
     }
     ptr+=-1;
     while (*ptr) {
        ptr+=1;
        *ptr+=1;
        ptr+=1;
        *ptr+=1;
        ptr+=-2;
        *ptr+=-1;
     }
     ptr+=1;
     *ptr+=-1;
     putc(*ptr,stdout);
     ptr+=1;
     *ptr+=-5;
     putc(*ptr,stdout);
     ptr+=1;
 }

Это, вероятно, в среднем довольно близко к одной машинной инструкции на одну операцию BF.

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

Если вы действительно хотите сходить с ума, вы можете выяснить, что делают команды BF до первого входного запроса; это должна быть «постоянная» начальная конфигурация памяти, и сгенерировать инициализатор CELLSPACE с этой константой, и сгенерировать код для остальной части программы, как я показал. Если вы сделали это, пример OP программа исчезнет в одном инициализаторе CELLSPACE и нескольких вызовах putc.

Answer 5

Используйте инфраструктуру LLVM JIT, чтобы оптимизировать код для вас ...

редактировать: на самом деле это уже было сделано несколько раз; компилятор: http://www.remcobloemen.nl/2010/02/brainfuck-using-llvm/ JIT: https://github.com/resistor/BrainFTracing (обратите внимание, что длина «компилятора» составляет 230 строк, считая также пустые строки, комментарии и #include)

edit2: для downvoter: так как вы, кажется, пропустили его, смысл моего ответа был "не изобретать велосипед"

Answer 6

Я бы увидел несколько вещей.

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

У тебя слишком много косвенных указаний. Например, ваш индекс ci мало что дает. Есть указатель, который указывает на фактическую ячейку. Это позволяет сохранить регистр. Вы можете сделать то же самое с ii. Вместо того, чтобы хранить номер инструкции, просто поместите указатель на позицию в cm.

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

Answer 7

Вот пример того, как вы можете сделать быстрый BF-интерпретатор:

int main(int argc, char **argv)
{
    if( !(argc > 1) )
        return 1;
    unsigned char *progmem = argv[1];
    unsigned char *cellmem = malloc(sizeof(char)*CELLSPACE);
    if(cellmem == NULL)
        return 1; 
    unsigned char **loopdepth = malloc(sizeof(char*)*MAXLOOPDEPTH);
    if(loopdepth == NULL)
        return 1;

    unsigned char *origcellmem = cellmem;
    unsigned char **origloopdepth = loopdepth;

    for(;;)
    {
        switch(*progmem)
        {
            case '+':
                ++*cellmem;
                break;
            case '-':
                --*cellmem;
                break;
            case '>':
                cellmem++;
                break;
            case '<':
                cellmem--;
                break;
            case '[':
                *loopdepth = progmem-1;
                loopdepth++;
                break;
            case ']':
                loopdepth--;
                if(*cellmem)
                {
                    progmem = *loopdepth;
                }
                break;
            case '.':
                putc(*cellmem, stdout);
                break;
            case ',':
                *cellmem = getc(stdin);
                break;
            case '\0':
                free(origcellmem);
                free(origloopdepth);
                return 0;
        }
        progmem++;
    }
}

Хорошо, основные моменты моего кода, которые должны сделать его быстрее, чем ваше решение:

I 'Я не проверяю каждый цикл, компилятор, скорее всего, сгенерирует здесь необработанный безусловный цикл (или так говорят мастера C). И так как я использую необработанные данные из строки вместо структур, я просто должен поместить '\ 0 'в конце переключателя!Это означает, что единственный раз, когда мой интерпретатор проверяет, нужно ли завершить программу, - это когда ничто больше не соответствует переключателю.

Я использую простые указатели для всего, и только манипулирую ими, я не делаю арифметическиецелые числа, а затем доступ к указанным на память с помощью операторов [], я просто манипулирую указателями и их указателями на память напрямую.

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

Я заказал корпус переключателя для того, как часто появляются вещи, видя как + и - наиболеераспространенные символы брейкфук, а затем> и <, а затем [и] и, наконец, вводимые символы.Я не на 100% в этом, но я - очень уверен - порядок переключения имеет значение, ЕСЛИ ТОЛЬКО НЕМНОГО БИТА! </p>

Я не делаю никакой проверки ошибок, я предполагаю, что ввод пользователяидеально.Хотя это может не дать хороших ошибок, таких как исчерпание границ и т. Д., Это ТОЧНО, что делают языки во время выполнения, программа на C может легко генерировать segfault, мы, вероятно, не должны их проверять.(Небольшое примечание, мое сгенерировало МНОГО ошибок при написании этого: P)

И, наконец, одна из возможных оптимизаций, о которых я подумал:

Выполнение кодирования длины, как при сжатии.Вы можете запустить кодировку brainfuck длины в простом формате, так что: +++ превращается в 3+, и интерпретатор «получает» его, и вместо добавления одного три раза, он добавляет три один раз.Увеличение производительности в некоторых местах может быть УДИВИТЕЛЬНЫМ

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