34

作为一个帮助我了解解释器和优化的练习,我对此一无所知,我用 C 编写了一个笨拙的解释器。到目前为止,它似乎工作得完美无缺,尽管与其他快速相比,它在执行速度上的竞争并不好口译员。

我可以通过哪些方式更改此解释器以提高性能(或以其他方式)?

我的解释器的一个有趣的方面(尽管大多数其他人可能也这样做)是我运行一个循环来读取源输入并将每条指令转换为

struct { long instruction; long loop; }

loop值是匹配]指令的索引,如果指令是 a [,匹配指令的索引[,如果指令是 a ],允许快速跳转。我想这个“解析”过程(不需要很长时间)比每次需要时都进行冗余重新解析以找到匹配的方括号来提高执行时间。

一个有趣的对brainfuck解释器速度的测试是这个程序:

++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
  1. 解释器的第一个版本
  2. 实现Jerry Coffin 的答案后的解释器,它通过使instruction结构instruction成为指向操作函数的直接指针来删除运行时循环中的巨大开关 -这比以前的版本运行得慢(函数调用开销?)
  3. 反转先前更改并添加优化以“折叠”多个连续的非循环操作后的解释器,减少循环周期 -这原来的运行速度略快
4

7 回答 7

21

好吧,这不是 C。它也不是一个解释器。所以,是的,这个问题完全不合适。

但它是一个使用 C++0x 可变参数模板的完美可移植的 Brainfuck 编译器。您必须#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;
}
于 2011-08-02T05:48:11.080 回答
19

我可以看到几种可能性。我想我会走的路是将它变成一个产生直接线程代码的编译器。即,当您读取输入时,我不会或多或少地将大部分“指令”复制到内存中,而是编写代码以将每条指令实现为函数,并将指向每个函数的指针复制到内存中。然后执行代码将包括按顺序调用这些函数。我可能会让该函数返回要执行的下一条指令的索引(或者可能是地址),所以你最终会得到类似的结果:

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;
}
于 2011-07-28T03:20:52.257 回答
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文章作为代码生成的明显灵感]。

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 命令在第一个输入请求之前做了什么;这必须是一个“常量”初始内存配置,并使用该常量生成一个 CELLSPACE 初始化程序,并按照我展示的方式为程序的其余部分生成代码。如果你这样做了,OP 的示例程序将消失在一个 CELLSPACE 初始化程序和几个 putc 调用中。

于 2011-08-02T04:01:33.760 回答
7

由于该项目的重点是学习,因此使用工具或替代解决方案显然不能回答问题。

首先,免责声明:我不是 x86 程序员——我在嵌入式环境和现在(使用手机)ARM 芯片方面做了很多工作。到好东西...

有两种基本方法可以让你的解释器更快:让它优化 BF 代码本身,以及让解释器本身优化。我将在下面的一步中推荐两者。

据我所知,x86 花费了大量的染料空间来提供相对令人印象深刻的快速分支特性。可能正因为如此,我已经看到几个编译器(包括 gcc)生成嵌套分支以支持 x86 的实际跳转表。跳转表在理论上听起来很有吸引力,但实际上 x86 对遗留技术的优化非常好,以至于传统的大 O 思维在大多数实践中并不适用。这就是为什么长期的 x86 开发人员会告诉您,如果您想计算代码有多快,那么您需要编写、运行并计时。

尽管在 x86 上发生分支的速度非常快,但仍然可能值得在不分支上花费一些开销。由于 BF 指令无论如何都非常简单,因此可以采取“一次执行大部分指令,因为它比另一个分支更快”的形式。其中一些甚至可以由无法进行分支的处理器并行完成。(x86 在单个内核中有足够的解码和执行单元,因此这很可能是可行的)

另一件会影响性能的事情是错误检查(例如换行)。将其保留在那里会导致性能问题(目前不是主要问题),但更重要的是会阻止您进行优化。

此外,您的程序非常通用。它将允许您使用任何最大值进行包装。如果它是 2 的幂,您只需执行按位与(非常快,因为它在几乎所有现代平台上都是一个 CPU 周期)相当于包装而不是比较和分支。编写真正快速的解释器的细节是魔鬼——你添加的每一点都会让它变得更加复杂。

为此,我建议简化您的 BF 解释器的工作(例如,使其以 2 的幂为值进行包装)。单独的按位与技巧和强制换行是选项(就像大多数现代编程语言中溢出/下溢的情况一样)已经删除了至少两个分支。

一旦处理好这些,这将实现一个有趣的优化:丢弃 BF 指令,而是让您的机器执行更适合解释器的不同指令。

考虑 Java:Java 不解释。它 JIT 转换成一种完全不同的语言。

我建议应用相同的逻辑。你已经通过给你的指令一个与它们相关的值来做到这一点。

我建议使用以下信息创建指令:

  • 添加到数据指针的值的数量(或减去 - 减法只是添加一个负数)
  • 添加到数据指针值数量(再次或减去)
  • 指向下一条要执行的指令的指针
  • 与数据指针更改的值进行比较的值

然后解释器循环变为如下逻辑:将指令中的数据值添加到数据指针处的值如果数据指针处的值与我们的比较值集匹配,则将指令中的数据地址值添加到数据指针本身如果比较值是特殊值(例如,您可以选择 0x80000000),则指向新指令指针的指令指针继续(到下一个解释器循环) 处理输入/输出内容 将指令地址增加一

初始解释现在变得更加棘手:指令现在可以将 +、-、<、> 甚至有时甚至 [,通常是 ] 组合成同一条指令。如果你很聪明的话,循环中的第一个分支可以在没有分支的情况下表示(甚至更有效地使用一些卡住的程序集或一些编译器内在函数)。您可能想通知编译器第二个分支不太可能命中(在这种情况下,输入/输出是瓶颈,而不是解释的速度,因此即使您正在执行大量输入/输出,还有一个未优化的小分支不会有所作为)。

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

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

除了像这样设计一个快速紧密循环的解释器之外,您正在研究更复杂的代码分析,在这种情况下,您将进入编译器设计,而不是远离直接的解释器。这不是我每天都做的事情,但 Louden 的“编译器构建”一书对我来说是一本非常好的读物,但它最终不会成为一个小项目。除非你真的想把这个东西弄得快得离谱,而且最终可能会编译代码,否则我会远离对它进行大的、强硬的优化。

我希望我已经给了您一个尝试和测试的想法,从而引导您进行更多优化步骤。我自己没有尝试过任何这些,所以这仍然是基于过去经验的推测。然而,即使它最终没有变得更快,你也会获得一些将 BF 代码重写为与普通 BF 解释器相对不同的架构的经验。

PS问题!

于 2011-08-04T03:55:50.067 回答
3

使用 LLVM JIT 基础设施并让它为您优化代码......

编辑:实际上它已经完成了多次;编译器:http ://www.remcobloemen.nl/2010/02/brainfuck-using-llvm/ JIT:https ://github.com/resistor/BrainFTracing (注意“编译器”的长度是 230 行,也算空白行、注释和#includes)

编辑2:对于downvoter:既然你似乎错过了它,我回答的意思是“不要重新发明轮子”

于 2011-07-28T08:17:03.487 回答
2

我会看到几件事。

switch由于错误处理,您的操作非常复杂。尝试重新组织它,让您在交换机内只有快速路径,并调用一个或多个函数来解决错误。一般来说,你得到的代码越短,你在switch其中使用的变量越少,你的优化器就能越好地发挥作用。

你有太多的间接。例如,您的索引ci服务不多。有一个指向实际单元格的指针。这使您可以保存寄存器。你可以用ii. 无需保留指令的编号,只需将指针指向cm.

无论如何,请检查生成的汇编程序。你会很快看到你的编译器在哪里产生了过多的寄存器溢出或类似的东西。

于 2011-07-28T06:51:56.683 回答
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 向导告诉我。)因为我使用的是字符串中的原始数据而不是结构,所以我只需要把'\0'放在开关的末尾!这意味着我的解释器检查它是否需要结束程序的唯一时间是当没有其他东西与开关匹配时。

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

我正在使用一个简单的“堆栈”来保存循环,这限制了您可以拥有的最大循环深度,但是对于大多数 Brainfuck 程序来说,32 就足够了,而且它在源代码中是可调节的。

我已经订购了开关盒以了解事物出现的频率,因为 + 和 - 是最常见的脑残字符,然后是 > 和 <,然后是 [ 和 ],最后是输入字符。我不是 100% 对此,但我 - 非常确定 - 如果只是一点点,开关的顺序很重要!

我没有做任何错误检查,我假设用户的输入是完美的。虽然这可能不会产生很好的错误,比如越界等,这正是语言在运行时所做的,C 程序可以轻松生成段错误,我们可能 - 不应该 - 检查这些。(快速说明,我在写这篇文章时产生了很多段错误:P)

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

运行长度编码,就像在压缩中使用的一样。你可以用一种简单的格式对大脑进行长度编码,这样: +++ 变成 3+ 并且解释器“得到”它,而不是三次加一,而是一次加三。这里的性能提升在某些地方可能是惊人的

你去了,这就是我所拥有的。我不太了解 C,所以我可能犯了一些错误,但我尽了最大努力,随意对提供的代码进行基准测试,我不知道它运行的速度到底有多快。它接受输入作为命令行参数。

于 2011-07-30T17:43:51.050 回答