针对Brainfuck解释器的优化

34
作为一个练习,帮助我了解解释器和优化,这两个方面我都不太了解,我用C语言编写了一个Brainfuck解释器。目前看来,它似乎运行得非常完美,尽管与其他快速解释器相比,它的执行速度并不理想。
有哪些方法可以改变这个解释器以提高性能(或其他方面)?
我的解释器有一个有趣的方面(尽管大多数其他解释器可能也这样做),即我运行一个循环,读取源输入并将每个指令转换为
struct { long instruction; long loop; }
loop值是匹配的]指令的索引,如果指令是[,并且是匹配的[指令的索引,如果指令是],允许快速跳转。我想这个“解析”过程(不需要很长时间)可以提高执行时间,避免了每次需要查找匹配方括号时进行冗余的重新解析。
一个有趣的测试brainfuck解释器速度的程序是:
++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
  1. 解释器的第一个版本
  2. Jerry Coffin的答案实现后的解释器,通过使instruction结构体的instruction直接指向操作函数来移除运行时循环中的巨大开关 - 这比先前的版本运行速度较慢(函数调用开销?)
  3. 撤销上次更改并添加了一种优化方法来“折叠”多个连续的非循环操作,减少循环周期 - 这比原始版本略快

顺便提一下,你的代码(我认为所有版本)存在一个错误。在“case BF_OP_LSTART:”的代码中,你写了:“ls = realloc(im, sizeof(long) * (la *= 2));”,我相信你本意是:“ls = realloc(ls, sizeof(long) * (la *= 2));”。 - Jerry Coffin
谢谢你注意到了这个问题!解析器应该将分配加倍并返回到循环堆栈,而不是指令内存。 - Delan Azabani
2
使用realloc的方式会导致内存泄漏。在将新返回值赋值给原始指针之前,您需要检查返回值。 - R.. GitHub STOP HELPING ICE
它是如何导致内存泄漏的? - Delan Azabani
FYI:你的“版本3”(折叠多个指令)不再正确处理BF_END_WRAP情况,因为增量/减量可能超过1。 - Nemo
谢谢!我会尽快修复这个漏洞。 - Delan Azabani
7个回答

22

好的,这不是C语言,也不是一个解释器。所以,对于这个问题而言,它完全不合适。

但它是一个使用C++0x可变参数模板的完全可移植的Brainfuck编译器。你必须将#define PROGRAM定义为逗号分隔的C语法字符序列,因为我无法在编译时从字符串中提取它们。但除此之外,它是合法的。我想。

在使用g++ -std=c++0x -O2 -Wall测试过,使用g++ 4.5.2编译。

#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;
}

12
必须要承认,你将深奥和亵渎的元素融合在一起,让我们大家痛苦不已……所有这一切都是徒劳的。 - Ira Baxter

20

我可以看到几个可能性。我认为我会将其转换为一个生成直接线程代码的编译器。也就是说,当你读取输入时,我不会将大部分“指令”按照原样复制到内存中,而是将实现每条指令的代码编写为一个函数,并将每个函数的指针复制到内存中。然后执行代码将包括按顺序调用这些函数。我可能会让该函数返回要执行的下一条指令的索引(或地址),这样你最终会得到类似于:

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;
    }
}

这对速度并没有真正的影响,但可以使代码变得更加简短,并且(至少在我看来)更易于理解。

编辑2:

好的,我有机会再次尝试了一下,并发现了一个(相当奇怪的)优化,似乎可以稍微提高一点性能。编译器通常会针对具有密集case值的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;
}

7
由于这个项目的整个目的是学习,使用工具或替代解决方案显然不能回答问题。
首先,免责声明:我不是x86程序员 - 我在嵌入式环境中做了相当多的工作,现在(随着手机)是ARM芯片。进入正题...
使你的解释器更快有两种基本方法: 使它优化BF代码本身,并使解释器本身优化。我会在下面的一步中建议两者都做一些。
据我所知,x86在提供相对较快的分支属性方面花费了很多染料空间。可能由于这个原因,我看到过几个编译器(包括gcc)为x86而不是实际跳转表生成嵌套分支。跳转表在理论上听起来很有吸引力,但实际上x86对传统技术进行了如此好的优化,以至于常规大O思维在大多数情况下都不适用。这就是为什么长期的x86开发人员会告诉你,如果你想计算代码的速度,那么你需要编写它,运行它并计时它。
尽管在x86上分支可以发生的速度很快,但花费一点额外的开销不分支仍然是值得的。由于BF指令非常简单,因此可以采用“一次执行大多数指令,因为这比另一个分支快”的形式。处理器甚至可以并行执行其中的一些操作,而无法进行分支。(x86在单个核中具有足够的解码和执行单元,以便实现这一点)
还有一件事会影响你的性能,那就是错误检查(例如包装)。保留它会导致性能问题(现在不是很严重),但更重要的是阻止你进行优化。
此外,你的程序非常通用。它将允许你使用任何最大值进行包装。如果是2的幂,则只需执行位AND(在几乎所有现代平台上都是一个CPU周期非常快),相当于包装,而不是比较和分支。编写真正快速的解释器的细节在于每添加一点东西,它就变得更加复杂。
为此,我建议简化你的BF解释器所做的事情(例如使其在值为2的幂时进行包装)。仅仅使用位AND技巧并强制使用包装选项(在大多数现代编程语言中用于溢出/下溢)就已经删除了至少两个分支。
一旦这些问题得到解决,这就启用了一个有趣的优化:抛弃BF指令,而是让你的机器执行更适合解释器的不同指令。
考虑Java:Java不进行解释。它JITs成一种完全不同的语言。
我建议应用相同的逻辑。通过为指令分配相关值,您已经做到了这一点。
我建议创建一个带有以下信息的指令:
  • 要添加到数据指针的值(或者减去--减法只是加上一个负数)
  • 要添加到数据指针的量(同样,或者减去)
  • 下一条要执行的指令的指针
  • 在更改之前与数据指针处的值进行比较的值

解释器循环然后按以下逻辑更改:

  • 将指令中的数据值添加到数据指针处的值中
  • 将指令中的数据地址值添加到数据指针本身中
  • 如果数据指针处的值与我们的比较值匹配
    • 将指令指针设置为新的指令指针
    • 继续(进入下一个解释器循环)
  • 如果比较值是特殊值(例如,您可以选择0x80000000)
    • 处理输入/输出操作
  • 增加指令地址一

初始解释现在变得更加棘手:

指令现在可以将+、-、<、>甚至[和]组合成相同的单个指令。如果聪明地使用它(并且通过一些汇编代码或者一些编译器内置函数更高效地使用),则循环中的第一个分支可以表示为不分支。您可能需要通知编译器第二个分支不太可能命中(在这种情况下,输入/输出是瓶颈,而不是解释速度,因此即使进行大量输入/输出,一个小的未优化分支也不会有所区别)。

必须注意运行结束条件。您解释的BF程序中的最后一个指令现在应始终使指令指针为NULL,以便循环退出。

解释发生的顺序很重要,因为-/+是在<>之前完成的,[是在]之前完成的,I/O是在最后完成的。因此,>+是两个解释指令,而+>是一个解释指令。

除了设计快速紧密循环的解释器之外,您还需要进行更复杂的代码分析,这样您将进入编译器设计并远离直接的解释器。这不是我每天做的事情,但Louden的《编译器构造》书对我来说是一本非常好的读物,但以这种方式结束最终可能不会成为一个小项目。除非您认真考虑让这件事变得非常快,并且最终可能是编译代码,否则我会远离将大而强大的优化投向它。

希望我给您提供了一个想法,尝试并测试,以便您可以进行更多的优化步骤。我自己没有尝试过这些,因此仍然是基于过去经验的推测。但是,即使它最终不会变得更快,您也将在将BF代码重写为相对不同的体系结构时获得一些经验,这与香草BF解释器有所不同。

P.S. 问题!


7

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;
        }
    }
}

这是我凭记忆编写的,灵感来自Matthew Blanchard的代码(感谢Matthew!),但未经测试。我会留给其他人去测试;如果你发现问题,请随意修补代码。显然,如果它将其代码写入文件中,它将得到改进:-}
[我使用http://en.wikipedia.org/wiki/Brainfuck文章作为生成代码的明显灵感来源。]
原帖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命令在第一个输入请求之前做了什么;那一定是一个“常数”初始内存配置,并生成一个CELLSPACE初始化器,以及为程序的其余部分生成代码,就像我展示的那样。如果你这样做,OP的示例程序将消失为一个CELLSPACE初始化器和几个putc调用。


所有生成未使用值的表达式是用来做什么的? - R.. GitHub STOP HELPING ICE
你提供的编译后的代码示例中充满了 *ptr-1;。这是一个无操作指令。 - R.. GitHub STOP HELPING ICE
@R:哎呀,你说得对。这就是手动模拟编译器的后果,而且还是在晚上。这些语句大多数应该是 *ptr+=-1; 或者其他类似的语句。我已经回去调整了它们。本来应该只是编译并运行这个程序就好了。无论如何,在生成的代码中,不应该有任何未使用的值;每个语句都是为了完成特定的工作而生成的。 - Ira Baxter
你可以将它们全部写成 ++*ptr;, --*ptr;, ++ptr;--ptr;。这样可能更清晰明了。(使用预增/减以避免哪个运算符绑定更紧密的问题。) - R.. GitHub STOP HELPING ICE
好的,现在它有意义了。当然,你可以始终生成增量/减量为1。C编译器会为您进行优化。 :-) - R.. GitHub STOP HELPING ICE
显示剩余2条评论

3

2

我看到了几件事情。

你的switch语句因为错误处理而变得非常复杂。尝试重新组织代码,使得在switch内部只有快速路径,并针对错误调用一个或多个函数。一般来说,你让switch内部的代码越短,使用的变量越少,优化器就能做得越好。

你有太多的间接寻址。例如,你的索引ci没有什么作用。使用指向实际单元格的指针来代替它。这可以让你节省一个寄存器。你也可以对ii进行类似的操作。不要保留指令的编号,而是直接在cm中指向相应位置。

无论如何,检查生成的汇编代码。你很快就会发现你的编译器产生了过多的寄存器溢出等问题。


1

这是一个快速的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专家告诉我是这样)。由于我使用字符串的原始数据而不是结构体,所以我只需要在switch的末尾放置'\0'!这意味着我的解释器仅在没有其他匹配项时才检查是否需要结束程序。

我对所有内容都使用简单指针,并且仅操作那些指针,我没有对整数进行算术运算,然后使用[]运算符访问指向的内存,我只是直接操作指针及其指向的内存。

我使用一个简单的“堆栈”来保存循环,这限制了您可以拥有的循环的最大深度,但32足以满足大多数brainfuck程序的要求,并且可以在源代码中进行调整。

我按出现频率对switch case进行了排序,因为“+”和“-”是最常见的brainfuck字符,然后是“>”和“<”,然后是“[”和“]”,最后是输入字符。我不能100%确定,但我非常确定switch的顺序很重要,即使只有一点点!

我没有进行任何错误检查,我假设用户的输入是完美的。虽然这可能不会给出很好的错误提示,比如越界等,但这正是语言在运行时所做的,C程序很容易生成段错误,我们可能不应该检查这些错误。(一个快速的注意事项,我的写作中生成了很多段错误:P)

最后,我想到了一种可能的优化:

运行长度编码,就像在压缩中使用的那样。您可以在简单格式中对brainfuck进行运行长度编码,例如:+++变成3+,解释器“获取”它,而不是将其添加三次,它只添加一次三个。在某些地方,这里的性能提升可能是惊人的。

这就是我所拥有的全部内容。我不是非常了解C,所以可能犯了一些错误,但我尽力了。请随意对提供的代码进行基准测试,我不知道它的运行速度有多快。它接受命令行参数作为输入。


一个好的C编译器会将switch语句转换为跳转表。你不需要特殊的排序,因为case语句不是按顺序检查的。唯一可能有帮助的是将字符转换为连续的整数值 - 一些编译器可能不喜欢稀疏的值列表。 - phkahler
2
“[`” 命令应该跳到匹配的“]”,如果当前单元格为零,但是你的代码没有实现这个功能。 - user3710044

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接