Оптимизация для интерпретатора мозгового укуса

Ответ 1

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

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

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

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

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

Edit:

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

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 с плотными значениями case, поэтому я попытался преобразовать их в это и получил улучшение около 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 '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;
}

Ответ 2

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

Но что это такое, является совершенно переносимым компилятором brainfuck, использующим вариативные шаблоны С++ 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;
}

Ответ 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P.S. Большой вопрос!

Ответ 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 как явное вдохновение для генерации кода].

Программа OP BF:

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

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

 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 до первого запроса на вход; которая должна быть "постоянной" начальной конфигурацией памяти, и сгенерируйте intializer CELLSPACE с этой константой и сгенерируйте код для остальной части программы, как я показал. Если вы это сделали, пример OP программа исчезнет в один инициализатор CELLSPACE и несколько вызовов putc.

Ответ 5

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

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

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

Ответ 6

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

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

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

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

Ответ 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++;
    }
}

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

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

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

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

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

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

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

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

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