브레인포크 인터프리터 최적화
통역사와 최적화에 대해 배우는 데 도움이 되는 연습으로, 저는 C에서 브레인포크 통역사를 썼습니다.아직까지는 완벽하게 작동하는 것처럼 보이지만, 다른 빠른 인터프리터에 비해 실행 속도에서 경쟁이 잘 되지 않습니다.
이 인터프리터를 변경하여 성능을 향상시킬 수 있는 방법은 무엇입니까?
제 인터프리터의 한 가지 흥미로운 측면은 (대부분의 다른 사람들도 아마 이것을 할 것이지만) 소스 입력을 읽고 각 명령을 하나의 루프로 변환하는 것입니다.
struct { long instruction; long loop; }
그loopvalue는 일치하는 항목의 인덱스입니다.]명령어, 명령어가 a인 경우[, 그리고 일치하는 색인.[명령어, 명령어가 a인 경우], 재빠르게 점프할 수 있는이 '파싱' 프로세스는 필요할 때마다 일치하는 사각형을 찾기 위해 중복 리파싱을 하는 것보다 실행 시간을 향상시킬 수 있다고 생각합니다.
브레인포크 인터프리터 속도에 대한 흥미로운 테스트는 이 프로그램입니다.
++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
- 통역의 제1판
- Runtime loop의 거대 스위치를 제거하는 Jerry Copin의 답변을 실행한 후 통역사는 다음과 같이 합니다.
instruction구조의instruction연산 함수에 대한 직접 포인터 - 이전 버전보다 느리게 실행됩니다(함수 호출 오버헤드?). - 이전 변경 사항을 반대로 변경하고 'collapse' 다중 연속 비루프 작동에 최적화를 추가하여 루프 주기를 줄인 후 인터프리터 - 원래보다 약간 빠르게 실행됩니다.
음, 이건 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;
}
몇 가지 가능성을 볼 수 있습니다.제가 가고 싶은 길은 직접 스레드 코드를 생성하는 컴파일러로 바꾸는 것입니다.즉, 입력을 읽을 때, 대부분의 "명령어"를 그대로 메모리에 복사하는 대신, 저는 대신 각 명령어를 함수로 구현하기 위한 코드를 작성하고, 각 함수에 대한 포인터를 메모리에 복사합니다.그런 다음 코드를 실행하는 것은 순서대로 함수를 호출하는 것으로 구성됩니다.이 함수를 실행할 다음 명령의 인덱스(또는 주소)를 반환하도록 하면 다음과 같은 결과를 얻을 수 있습니다.
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:
좋아요, 저는 이것을 좀 더 가지고 놀 기회가 있었는데, 적어도 조금은 도움이 될 것 같은 (다소 이상한) 최적화를 발견했습니다.컴파일러는 대소문자 값이 밀도가 높은 스위치 문에 대해 약간 더 나은 코드를 생성하는 경우가 많기 때문에 이를 변환해 보았는데 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;
}
브레인포크는 C 코드로 컴파일하기가 꽤 쉬워야 하고, 그런 다음 컴파일하고 실행합니다.그것은 아마도 매우 빠른 BF "통역사"가 될 것입니다.
기본적으로 당신이 해야 할 일은 프로그램에서 왼쪽에서 오른쪽으로 각각의 뇌사자에 대한 아주 사소한 코드를 생성하는 것입니다.+와 -의 시퀀스를 쉽게 최적화할 수 있습니다. 마찬가지로 최근에 접한 각각의 카운트를 캐싱하여 <과 >의 시퀀스를 최적화할 수 있습니다.이것은 일종의 엿보는 구멍 최적화입니다.
다음은 컴파일러 초안으로, 명령줄에서 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 프로그램:
++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
다음으로 컴파일해야 합니다(indent 추가).
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 당 하나의 기계 명령에 상당히 가까운 평균일 것입니다.
정말 야심이 많은 사람이라면 프로그램의 각 지점에서 ptr에 대한 가능한 값을 계산할 것입니다. 많은 경우 일정한 셀을 의미한다고 생각합니다.그러면 간접적인 접근을 피할 수 있습니다.
정말로 미쳐가고 싶다면, 첫 번째 입력 요청까지 BF 명령이 무엇을 하는지 알아낼 수 있습니다. 그것은 "상수" 초기 메모리 구성이어야 하고, 그 상수를 가진 CELLSPACE intitializer를 생성하고, 제가 보여준 것처럼 나머지 프로그램에 대한 코드를 생성할 수 있습니다.그렇게 하면 OP의 예제 프로그램은 한 번의 CELLSPACE 이니셜저와 몇 번의 퍼치콜로 사라집니다.
이 프로젝트의 핵심은 학습이기 때문에 도구나 대체 솔루션을 사용하는 것은 질문에 대한 답이 아닙니다.
첫째, 면책 사항:저는 x86 프로그래머가 아닙니다. 저는 임베디드 환경에서 상당한 작업을 해왔고 이제는 (휴대폰으로) ARM 칩을 사용했습니다.좋은 일에 대해서는...
통역사를 빠르게 만드는 두 가지 기본적인 방법이 있습니다. BF 코드 자체를 최적화하는 것과 통역사 자체를 최적화하는 것입니다.아래 단계에서 두 가지를 조금 추천해 드리겠습니다.
x86은 비교적 인상적인 빠른 분기 특성을 제공하는 데 많은 염료 공간을 사용하는 것으로 알고 있습니다.아마도 이것 때문에 여러 컴파일러(gcc 포함)가 x86용 실제 점프 테이블을 선호하여 중첩 분기를 생성하는 것을 본 적이 있습니다.점프 테이블은 이론적으로 매력적으로 들리지만, 실제로 x86은 레거시 기술에 매우 잘 최적화되어 기존의 big-O 사고 방식은 대부분의 경우 적용되지 않습니다.그렇기 때문에 코드가 얼마나 빠른지 계산하려면 코드를 작성하고 실행하고 시간을 정해야 한다고 장기 x86 개발자들이 알려줄 것입니다.
x86에서 분기가 발생할 수 있는 속도에도 불구하고 분기하지 않는 것은 여전히 약간의 오버헤드를 들일 가치가 있습니다.어차피 BF 지시는 너무 간단하기 때문에, 그것은 "다른 지점보다 빠르니까 대부분의 지시를 한꺼번에 한다"는 형태를 취할 수 있습니다.이 중 일부는 분기가 불가능한 프로세서에 의해 병렬로 수행될 수도 있습니다. (x86은 단일 코어에 충분한 디코딩 및 실행 유닛을 가지고 있으므로 이것이 가능할 가능성이 높습니다.)
성능을 저하시키는 또 다른 문제는 오류 검사(랩핑 등)입니다.성능 문제를 야기할 뿐만 아니라 최적화를 방해할 수도 있습니다.
게다가 당신의 프로그램은 매우 일반적입니다.포장에 사용할 수 있는 최대값을 사용할 수 있습니다.2의 거듭제곱이라면 비교 및 분기 대신 래핑(wrapping)과 동등한 수준의 AND(거의 모든 최신 플랫폼에서 CPU 사이클 하나이므로 매우 빠름)를 수행할 수 있습니다.악마는 정말 빠른 통역사를 쓰기 위한 세부사항에 있습니다. 여러분이 덧붙이는 작은 것 하나하나가 그것을 훨씬 더 복잡하게 만듭니다.
이를 위해 BF 인터프리터가 수행하는 작업을 간소화할 것을 권장합니다(예를 들어 값에 대해 2의 거듭제곱으로 래핑합니다).비트 와이즈 AND 트릭 단독 및 강제 랩 옵션(오버플로/언더플로의 현대 프로그래밍 언어의 경우 대부분)은 이미 최소한 두 개의 분기를 제거합니다.
BF 명령을 처리하면 흥미로운 최적화가 가능합니다. BF 명령을 버리고 대신 기계가 통역사에게 적합한 다양한 명령을 수행하도록 합니다.
Java를 고려합니다. Java는 해석하지 않습니다.그것은 완전히 다른 언어로 JIT를 만듭니다.
저는 같은 논리를 적용하는 것을 추천합니다.이 작업은 지침과 관련된 값을 제공함으로써 이미 어느 정도 완료되었습니다.
다음 정보를 사용하여 명령어를 만드는 것이 좋습니다.
- 데이터 포인터의 값에 추가할 양(또는 뺄셈 -- 뺄셈은 음수만 추가하는 것입니다)
- 데이터 포인터의 값에 추가할 양(다시 또는 빼기)
- 실행할 다음 지시를 가리키는 지시자.
- 데이터 포인터가 변경되기 전의 값과 비교되는 값
인터프리터 루프는 다음과 같이 로직으로 바뀝니다. 명령어의 데이터 값을 데이터 포인터의 값에 추가하고 만약 데이터 포인터의 값이 우리의 비교 값과 일치한다면 명령어의 데이터 주소 값을 데이터 포인터 자체에 추가합니다. 명령어 포인터를 새 명령어 포인터로 계속 설정합니다(다음 int까지).rpreter loop) 비교값이 특별한 값일 경우(예: 0x80000000을 선택할 수 있음) 핸들 입력/출력 항목은 명령어 주소를 1씩 증가시킵니다.
이제 초기 해석이 더 까다로워졌습니다.이제 명령어는 +, -, <, > 그리고 때로는 [, 그리고 보통은 ]까지도 동일한 단일 명령어로 결합할 수 있습니다.만약 당신이 그것에 대해 영리하다면, 루프의 첫 번째 분기는 분기 없이 표현될 수 있습니다. (그리고 일부 어셈블리가 끼어 있거나 컴파일러 고유성이 있는 상태에서 훨씬 더 효율적으로 표현될 수 있습니다.컴파일러에게 두 번째 분기가 적중할 가능성이 낮다고 알리는 것이 좋을 수도 있습니다(입력/출력은 해석 속도가 아니라 병목 현상이므로 많은 입력/출력을 수행하더라도 최적화되지 않은 분기 하나로는 차이가 나지 않습니다).
주행 종료 상태에 주의해야 합니다.이제 해석된 BF 프로그램의 마지막 명령은 루프가 종료되도록 명령 포인터를 항상 NULL로 만들어야 합니다.
해석이 수행되는 순서는 중요한데, 이는 I/O가 수행되기 전에 <<>>이 수행되기 전에 수행되기 때문입니다.따라서 >+는 두 개의 해석 명령어이고 +>는 하나입니다.
이와 같이 빠른 속도로 순환하는 인터프리터를 설계하는 것을 넘어, 보다 복잡한 코드 분석을 검토하게 될 것이며, 이 경우 컴파일러 설계에 참여하게 될 것이며, 직관적인 인터프리터에서 벗어나게 될 것입니다.이것은 제가 매일 하는 일은 아니지만, Louden의 "Compiler Construction" 책은 제게 아주 잘 읽혔지만, 그렇게 해서 작은 프로젝트가 되지는 않을 것입니다.당신이 이 일을 말도 안되게 빨리 만들고 결국에는 코드가 컴파일되지 않는 한, 저는 그것에 큰 타격을 주는 최적화 작업을 하지 않을 것입니다.
더 많은 최적화 단계로 이어질 수 있도록 시도하고 테스트할 수 있는 아이디어를 제안해 드렸기를 바랍니다.제가 직접 해본 적이 없어서 아직도 다 과거 경험에 의한 추측입니다.그러나 속도가 빨라지지 않더라도 바닐라 BF 인터프리터와는 비교적 다른 아키텍처로 BF 코드를 다시 작성하는 경험을 쌓을 수 있을 것입니다.
추신: 좋은 질문입니다!
LLVM JIT 인프라스트럭처를 사용하여 코드를 최적화하고...
edit: 실제로 그것은 이미 여러 번 행해졌습니다; 컴파일러: http://www.remcobloemen.nl/2010/02/brainfuck-using-llvm/ JIT: https://github.com/resistor/BrainFTracing ("compiler"의 길이가 230줄이고 공백 줄, 댓글, #includes 등을 세는 방법 참조)
edit2: 다운보터의 경우: 놓친 것 같으니 내 대답의 의미는 "바퀴를 재창조하지 말라"였습니다.
여러 가지를 볼 수 있을 겁니다.
당신의.switch오류 처리 때문에 상당히 복잡합니다.스위치 내부에 빠른 경로만 있다고 재구성하고 오류가 발생하면 하나 또는 여러 개의 함수를 호출합니다.일반적으로 조금만 더 짧게 하면 내부에 코드가 들어옵니다.switch변수를 적게 사용할수록 옵티마이저가 더 효과적으로 작동할 수 있습니다.
당신은 방향이 너무 많습니다.예를 들어 색인ci별로 도움이 되지 않습니다.실제 셀을 가리키는 포인터가 있습니다.그러면 레지스터를 저장할 수 있습니다.당신은 당신과 비슷한 일을 할 수 있습니다.ii. 명령어의 숫자를 유지하는 대신에 위치에 포인터만 있으면 됩니다.cm.
어떠한 경우에도 생성된 Assembler를 확인합니다.컴파일러가 레지스터를 너무 많이 흘리거나 그런 것들을 생성하는 곳을 금방 알 수 있을 것입니다.
다음은 빠른 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를 쉽게 생성할 수 있지만, 아마도 이러한 오류를 확인해서는 안 될 것입니다. (간단한 말씀이지만, 제가 이 글을 쓰면서 segfault를 많이 생성했습니다 :P)
마지막으로 제가 생각한 최적화 방법은 다음과 같습니다.
압축에 사용되는 것처럼 실행 길이 인코딩.브레인포크를 간단한 형식으로 길이 부호화할 수 있습니다. +++가 3+로 바뀌면 인터프리터가 3개를 더하는 대신 3개를 한 번 더 추가합니다.여기서의 성능 향상은 어떤 곳에서는 놀라운 것입니다.
그리고 여기 있네요, 정말로 제가 가진 것은 이것뿐입니다.저는 C를 놀라울 정도로 잘 몰라서 실수를 좀 했을 수도 있지만 최선을 다했습니다. 제공된 코드를 자유롭게 벤치마킹해보세요. 얼마나 빨리 실행되는지 정확하게 알지 못합니다.입력을 명령줄 인수로 허용합니다.
언급URL : https://stackoverflow.com/questions/6853548/optimisation-for-a-brainfuck-interpreter
'sourcecode' 카테고리의 다른 글
| 최대 MySQL 사용자 암호 길이 (0) | 2023.11.05 |
|---|---|
| 실패 - EPLus.dll에서 만든 Excel 파일을 다운로드할 때 네트워크 오류 발생 (0) | 2023.11.05 |
| 로보카피가 파일을 덮어쓰도록 하려면 어떻게 해야 합니까? (0) | 2023.11.05 |
| 사용되지 않는 명령줄 인수 오류를 비활성화하지 않고 clang으로 침묵시키는 방법은 무엇입니까? (0) | 2023.11.05 |
| javascript로 XML을 예쁘게 인쇄 (0) | 2023.11.05 |