34

インタープリターと最適化について学ぶのに役立つ演習として、私はどちらも何も知りませんが、C でブレイン インタープリターを作成しました。通訳者。

このインタープリターを変更してパフォーマンスを向上させる (またはその他の方法で) には、どのような方法がありますか?

私のインタープリターの興味深い点の 1 つは (おそらく他のほとんどの人もこれを行っているでしょうが)、ソース入力を読み取り、各命令を

struct { long instruction; long loop; }

loop値は、命令が a の場合は一致する]命令のインデックスであり、命令が a の場合は一致する命令[のインデックスであり、迅速なジャンプが可能です。この「解析」プロセス (時間はかかりません) は、必要なたびに一致する角かっこを見つけるために冗長な再解析を行うよりも実行時間を改善すると思います。[]

ブレインファック インタープリターの速度の興味深いテストは、次のプログラムです。

++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
  1. インタプリタの最初のバージョン
  2. Jerry Coffin's answerを実装した後のインタープリターinstructionは、構造体instructionを操作関数への直接ポインターにすることで、ランタイム ループの巨大なスイッチを削除します。これは、以前のバージョンよりも遅く実行されます (関数呼び出しのオーバーヘッド?)
  3. 前の変更を元に戻し、複数の連続する非ループ操作を「折りたたむ」ための最適化を追加して、ループ サイクルを減らした後のインタプリタ-これは元のインタプリタよりもわずかに高速に実行されます
4

7 に答える 7

21

これは 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;
}
于 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]))();

また、命令ごとに 3 つの個別の関数 (BF_END_* モードごとに 1 つ) を用意するので、「コンパイル」フェーズでのみ処理する必要があります。コードを実行すると、正しい関数への直接のポインターが得られます。

編集:

少しコードをいじってみました。ループ アドレスを別の配列に分割し、ほとんどの解析をマージしたので、次のようになります。

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

これは、マシュー ブランチャードのコード (マシューに感謝します!) に触発されて、頭のてっぺんからキー入力されていますが、テストされていません。私はそれを他の魂に任せます。問題が見つかった場合は、気軽にコードにパッチを当ててください。コードをファイルに書き込めば明らかに改善されます:-}

[コードを生成するための明らかなインスピレーションとして、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 op ごとに 1 つのマシン命令にかなり近くなります。

本当に野心的な人は、プログラムの各ポイントで ptr の可能な値を計算します。多くの場合、定数セルを指していると思います。そうすれば、間接アクセスを避けることができます。

本当に頭がおかしくなりたい場合は、最初の入力要求までに BF コマンドが何をするかを理解することができます。それは「一定の」初期メモリ構成でなければならず、その定数でCELLSPACE初期化子を生成し、私が示した方法でプログラムの残りのコードを生成します。これを行うと、OP のサンプル プログラムは、単一の CELLSPACE 初期化子といくつかの putc 呼び出しに消えてしまいます。

于 2011-08-02T04:01:33.760 に答える
7

このプロジェクトの要点はすべて学習であるため、ツールや代替ソリューションを使用しても、明らかに質問への回答にはなりません。

まず、免責事項: 私は x86 プログラマーではありません。組み込み環境でかなりの量の作業を行ってきましたが、現在は (携帯電話で) ARM チップを使用しています。良いものに...

インタープリターを高速化する基本的な方法は 2 つあります。BF コード自体を最適化する方法と、インタープリター自体を最適化する方法です。以下の 1 つの手順で、両方を少しお勧めします。

私の知る限り、x86 は、比較的印象的な高速分岐特性を提供するために、多くの Dye スペースを費やしています。おそらくこれが原因で、いくつかのコンパイラ (gcc を含む) が、x86 の実際のジャンプ テーブルを優先してネストされたブランチを生成するのを見てきました。ジャンプ テーブルは理論的には魅力的に聞こえますが、実際には x86 はレガシー テクニックに対して非常にうまく最適化されているため、従来のビッグ オーの考え方はほとんどの場合適用されません。そのため、x86 の長年の開発者は、コードの速度を計算するには、コードを記述し、実行し、時間を計る必要があると教えてくれます。

x86 では分岐が発生する速度が速いにもかかわらず、分岐しないことに多少のオーバーヘッドを費やす価値はあります。とにかくBF命令は非常に単純なので、「他の分岐よりも速いので、ほとんどの命令を一度に実行する」という形を取ることができます。これの一部は、分岐できないプロセッサによって並列に実行されることさえあります。(x86 では、単一のコアに十分なデコードおよび実行ユニットがあり、これが実現可能である可能性があります)

パフォーマンスを低下させるもう 1 つのことは、エラー チェック (ラッピングなど) です。そこに保持すると、パフォーマンスの問題が発生しますが (現時点では重大ではありません)、さらに重要なことに、最適化が妨げられます。

さらに、プログラムは非常に汎用的です。ラッピングに任意の最大値を使用できます。2 のべき乗の場合は、比較と分岐の代わりに、ラップと同等のビット単位の AND (事実上すべての最新のプラットフォームで 1 CPU サイクルであるため非常に高速) を実行するだけです。真に高速なインタープリターを作成するには、細部に注意が必要です。少しずつ追加すると、さらに複雑になります。

そのためには、BF インタープリターが行うことを合理化することをお勧めします (たとえば、値を 2 のべき乗でラップするようにします)。ビットごとの AND トリックだけで、ラップをオプションにすることを強制する (オーバーフロー/アンダーフローのほとんどの最新のプログラミング言語の場合と同様に) 少なくとも 2 つの分岐が既に削除されています。

それらが処理されると、興味深い最適化が可能になります。つまり、BF 命令を破棄し、代わりにインタプリタにより適した別の命令をマシンに実行させます。

Java を考慮してください。Java は解釈しません。まったく別の言語に JIT します。

同じロジックを適用することをお勧めします。命令に関連付けられた値を与えることで、これはすでに少し行っています。

次の情報を使用して指示を作成することをお勧めします。

  • データ ポインタの値に加算する量(または減算 -- 減算は単に負の数を加算することです)
  • データポインタの値に加算する量(再度、または減算)
  • 次に実行する命令へのポインタ
  • 変更のデータポインタの値と比較される値

次に、インタプリタ ループは次のようなロジックに変更されます。 命令内のデータ値をデータ ポインタの値に追加する データ ポインタの値が比較値セットと一致する場合、命令内のデータアドレス値をデータ ポインタ自体に追加する新しい命令ポインタへの命令ポインタ 比較値が特別な値 (たとえば、0x80000000 を選択できます) の場合、(次のインタプリタ ループへ) 続行します 入出力スタッフの処理 命令アドレスを 1 ずつ増やします

最初の解釈はよりトリッキーになりました: 命令は、+、-、<、>、場合によっては [、通常は ] を同じ単一の命令に結合できるようになりました。ループ内の最初の分岐は、賢明であれば分岐せずに表すことができます (さらに、いくつかのアセンブリがスタックしている場合やコンパイラの組み込み関数がある場合はさらに効率的です)。2 番目の分岐がヒットする可能性が低いことをコンパイラに通知することもできます (その場合、入力/出力がボトルネックであり、解釈の速度ではありません。したがって、大量の入力/出力を行っている場合でも、最適化されていない小さな分岐が 1 つあります)。違いはありません)。

走行終了状態には注意が必要です。解釈された BF プログラムの最後の命令は、ループが終了するように命令ポインターを常に NULL にする必要があります。

-/+ は <> が実行される前に実行され、[ は I/O の前に実行されます。したがって、>+ は 2 つの解釈された命令であり、+> は 1 つです。

このような高速でタイトループのインタープリターを設計するだけでなく、より複雑なコード分析を検討している場合、コンパイラーの設計に取り掛かり、ストレートアップのインタープリターから離れることは少なくなります。これは私が毎日行うことではありませんが、Louden の「Compiler Construction」の本は私にとって非常に良い読み物でしたが、そのように小さなプロジェクトに終わることはありません。このことをとてつもなく速くし、最終的におそらくコンパイルされたコードにすることに真剣に取り組んでいない限り、私は大規模で強力な最適化をそれに投入することは避けます。

より多くの最適化ステップにつながる試行とテストのアイデアを提供できたことを願っています. 私はこれを自分で試したことはありませんので、過去の経験に基づいたすべての推測です。ただし、最終的に高速化されなくても、通常の 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 行で、空白もカウントされることに注意してください行、コメント、#include)

編集2:反対票を投じた人のために:あなたはそれを見逃しているようですので、私の答えの意味は「車輪を再発明しないでください」でした

于 2011-07-28T08:17:03.487 に答える
2

私はいくつかのことを見るでしょう。

エラーswitch処理のため、非常に複雑です。スイッチ内に高速パスしかないことを再編成し、エラーに対して1つまたは複数の関数を呼び出してみてください。一般に、内部のコードを短く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' を入れてください! これは、インタープリターがプログラムを終了する必要があるかどうかを確認するのは、スイッチに一致するものがない場合のみであることを意味します。

私はすべてに単純なポインターを使用しており、それらを操作するだけです。整数に対して算術演算を行っていないため、[] 演算子を使用してポイント先のメモリにアクセスしています。単にポインターとそのポイント先のメモリを直接操作しています。

私はループを保持するために単純な「スタック」を使用しています。これにより、使用できるループの最大深度が制限されますが、ほとんどのブレインファック プログラムでは 32 で十分であり、ソースで調整できます。

+ と - が最も一般的なブレインファック文字であり、次に > と < 、次に [ と ] 、最後に入力文字であることを確認して、スイッチケースを注文しました。私はこれについて 100% ではありませんが、スイッチの順序が少しだけ重要であると確信しています!

エラーチェックは行っていません。ユーザーの入力が完璧であると想定しています。これは、実行時に言語が行うこととまったく同じように、境界外の実行などの適切なエラーを発生させない可能性がありますが、C プログラムはセグメンテーション違反を簡単に生成できます。おそらく、これらをチェックする必要はありません。(簡単なメモ、私のものはこれを書いているときに多くのセグメンテーション違反を生成しました:P)

最後に、私が考えた 1 つの可能な最適化:

圧縮で使用されるようなランレングス エンコーディング。+++ は 3+ に変わり、インタープリターはそれを「取得」し、1 を 3 回追加する代わりに、3 を 1 回追加します。ここでのパフォーマンスの向上は、場所によっては驚くべきものになる可能性があります

そして、ほら、それが本当に私が持っているすべてです。私は C を驚くほどよく知らないので、間違いを犯した可能性がありますが、最善を尽くしました。コマンドライン引数として入力を受け入れます。

于 2011-07-30T17:43:51.050 に答える