Optimización para un intérprete de brainfuck
optimization interpreter (7)
Aquí hay un ejemplo de cómo puede hacer un intérprete de BF rápido:
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++;
}
}
Muy bien, los aspectos más destacados de mi código que deberían hacerlo más rápido que tu solución:
No estoy comprobando cada bucle, es probable que el compilador genere un bucle incondicional en bruto aquí (o eso me dicen los asistentes de C). Y como estoy usando los datos brutos de la cadena en lugar de las estructuras, solo tengo que poner ''/ 0'' al final del interruptor! Esto significa que la única vez que mi intérprete verifica si necesita finalizar el programa es cuando nada más coincide con el interruptor.
Estoy usando punteros simples para todo, y solo manipulando esos, no hago aritmáticos en enteros y luego accedo a la memoria apuntada con los operadores [], simplemente estoy manipulando los punteros y su memoria apuntada directamente.
Estoy usando una simple ''pila'' para mantener los bucles, esto limita la profundidad máxima de bucles que puede tener, pero 32 es suficiente para la mayoría de los programas de brainfuck, y es ajustable en origen.
He ordenado la caja del interruptor para ver la frecuencia con la que aparecen las cosas, ya que + y - son los personajes de brainfuck más comunes, y luego> y <y luego [y] y finalmente los caracteres de entrada. No estoy al 100% en esto, pero estoy muy seguro de que el orden del cambio sí importa SI TIENE UN POCO.
No estoy verificando ningún error, supongo que la entrada del usuario es perfecta. Si bien esto puede no dar errores agradables, como quedarse sin límites y eso, EXACTAMENTE qué idiomas hacen en tiempo de ejecución, un programa C puede generar un segfault fácilmente, probablemente -no deberíamos- verificar esto. (Una nota rápida, la mía generó MUCHOS segfaults al escribir esto: P)
Y finalmente, una posible optimización que pensé:
Ejecutar codificación de longitud, como se usa en compresión. Puede ejecutar la longitud de codificación de la brainfuck en un formato simple, de modo que: +++ se convierta en 3+ y el intérprete la "obtenga" y en lugar de agregar una tres veces, agrega tres una vez. La ganancia de rendimiento aquí podría ser INCREÍBLE en algunos lugares
Y ahí tienes, eso es todo lo que tengo. No conozco C sorprendentemente bien, así que podría haber cometido algunos errores, pero intenté hacerlo lo mejor posible, no dude en comparar el código provisto, no tengo ni idea exactamente qué tan rápido se ejecuta. Acepta la entrada como un argumento de línea de comando.
Como un ejercicio para ayudarme a aprender sobre los intérpretes y la optimización, ninguno de los cuales conozco, escribí un intérprete de brainfuck en C. Parece que funciona perfectamente hasta el momento, aunque no compite bien en velocidad de ejecución en comparación con otros rápidos intérpretes.
¿De qué maneras puedo cambiar este intérprete para mejorar el rendimiento (o no)?
Un aspecto interesante de mi intérprete (aunque la mayoría de los otros probablemente también lo hagan) es que ejecuto un ciclo que lee la fuente de entrada y convierte cada instrucción en una
struct { long instruction; long loop; }
El valor del loop es el índice de la instrucción matching ] , si la instrucción es un [ , y el índice de la instrucción [ matching, si la instrucción es a ] , lo que permite saltos rápidos. Me imagino que este proceso de "análisis sintáctico" (que no lleva mucho tiempo) mejora los tiempos de ejecución en lugar de realizar un repaso redundante para encontrar corchetes coincidentes cada vez que se necesiten.
Una prueba interesante de la velocidad del intérprete brainfuck es este programa:
++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
- la primera versión del intérprete
- el intérprete después de implementar la respuesta de Jerry Coffin , que elimina el interruptor gigante en el bucle de tiempo de ejecución, haciendo que la
instructionstruct deinstructionun puntero directo a una función de operación; esto funciona más lento que la versión anterior (¿sobrecarga de llamada de función?) - el intérprete después de revertir el cambio anterior y agregar una optimización para ''colapsar'' múltiples operaciones consecutivas sin bucle, reduciendo los ciclos de bucle - esto funciona un poco más rápido que el original
Brainfuck debería ser bastante fácil de compilar en código C, que luego compila y ejecuta. Eso probablemente sería un "intérprete" BF muy rápido.
Fundamentalmente, todo lo que tienes que hacer es generar un código bastante trivial para cada operador brainfuck de izquierda a derecha en el programa. Uno puede optimizar fácilmente las secuencias de + y -; de manera similar, uno puede optimizar secuencias de <y>, almacenando en caché los recuentos de cada uno encontrado recientemente. Este es un tipo de optimización de mirilla.
Aquí hay un borrador del compilador, que acepta código BF en la línea de comando e imprime el programa compilado en la consola:
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;
}
}
}
Esto está en la parte superior de mi cabeza, inspirado por el código de Matthew Blanchard (gracias a Matthew!), Pero no probado. Lo dejo a otra alma; no dude en parchear el código si encuentra un problema. Obviamente, mejoraría si escribiera su código en un archivo: -}
[Utilicé el artículo http://en.wikipedia.org/wiki/Brainfuck como la inspiración obvia para el código para generar].
El programa BF de OP:
++++++++ [-> - [-> - [-> - [-] <] <] <]> ++++++++ [<++++++++++ > -] <[> +> + << -]> -.> -----.>
debería compilar a (sangría agregada):
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;
}
Esto probablemente promedia bastante cerca de una instrucción de máquina por BF op.
Alguien que fuera realmente ambicioso calcularía los valores posibles para ptr en cada punto del programa; Supongo que en muchos casos se refiere a una celda constante. Entonces uno podría evitar los accesos indirectos.
Si realmente quieres volverse loco, puedes averiguar qué hacen los comandos BF hasta la primera solicitud de entrada; debe ser una configuración de memoria inicial "constante", y generar un inicializador CELLSPACE con esa constante, y generar código para el resto del programa de la manera que he mostrado. Si lo hicieras, el programa de ejemplo de OP se desvanecería en un único inicializador CELLSPACE y algunas llamadas putc.
Bueno, esto no es C. Y no es un interperador. Entonces, sí, bastante totalmente inapropiado para esta pregunta.
Pero lo que es, es un compilador de brainfuck perfectamente portátil que usa plantillas varicas de C ++ 0x. Tienes que #define PROGRAM como una secuencia de caracteres C-sintaxis separados por comas, porque no pude extraerlos de la cadena en tiempo de compilación. Pero de lo contrario es de fiar. Creo.
Probado con g ++ 4.5.2, usando 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;
}
Dado que el objetivo de este proyecto es aprender, usar una herramienta o una solución de reemplazo claramente no responde la pregunta.
En primer lugar, un descargo de responsabilidad: no soy un programador de x86. He hecho una buena cantidad de trabajo en entornos integrados y ahora (con teléfonos móviles) chips ARM. En lo bueno ...
Hay dos formas básicas de hacer que su intérprete sea más rápido: haga que optimice el código BF en sí mismo y optimice el intérprete. Recomendaré un poco de ambos en un paso más abajo.
Hasta donde yo sé, x86 gasta mucho espacio de tinte para proporcionar propiedades de ramificación rápidas relativamente impresionantes. Probablemente debido a esto, he visto varios compiladores (incluido gcc) producir ramas anidadas a favor de tablas de salto reales para x86. Las tablas de salto suenan atractivas en teoría, pero realmente x86 se optimiza tan bien para las técnicas heredadas que el pensamiento convencional de la gran O simplemente no se aplica en la mayoría de las prácticas. Es por eso que los desarrolladores de x86 a largo plazo le dirán si desea calcular qué tan rápido es el código, entonces necesita escribirlo, ejecutarlo y cronometrarlo.
A pesar de la velocidad a la que las ramas pueden ocurrir en x86, es probable que valga la pena gastar un poco de sobrecarga en no ramificar. Ya que las instrucciones BF son tan simples de todos modos, eso puede tomar la forma de "hacer la mayoría de las instrucciones de una vez, ya que es más rápido que otra rama". Algo de esto incluso puede ser hecho en paralelo por el procesador donde no puede haber ramificaciones. (x86 tiene suficientes unidades de decodificación y ejecución en un solo núcleo, de modo que esto es factible)
Otra cosa que va a matar su rendimiento es la comprobación de errores (como el ajuste). Mantenerlo allí le está causando problemas de rendimiento (no importante en este momento) pero lo que es más importante, le impide optimizar.
Además, tu programa es muy genérico. Le permitirá usar cualquier valor máximo para envolver. Si fuera una potencia de dos, simplemente realizaría un Y a nivel de bit (muy rápido ya que es un ciclo de CPU en prácticamente todas las plataformas modernas) equivalente a envolver en lugar de comparar y ramificar. El diablo está en los detalles para escribir intérpretes verdaderamente rápidos: cada pequeño detalle que agregas lo hace mucho más complejo.
Con ese fin, recomiendo simplificar lo que hace su intérprete de BF (por ejemplo, envuélvalo a una potencia de dos para los valores). El truco AND bit a bit y el forzado wrap es la opción (como es el caso en la mayoría de los lenguajes de programación modernos para desbordamientos / subdesbordamientos) ya elimina al menos dos ramas.
Una vez que se cuiden de ellos, esto permite una optimización interesante: deseche las instrucciones de BF y en su lugar haga que su máquina realice las diferentes instrucciones que sean más adecuadas para un intérprete.
Considera Java: Java no interpreta. JIT en un lenguaje completamente diferente.
Recomiendo aplicar la misma lógica. Ya ha hecho esto un poco dando a sus instrucciones un valor asociado a ellos.
Recomiendo crear una instrucción con la siguiente información:
- la cantidad para agregar al valor en el puntero de datos (o restar - resta es solo agregar un número negativo)
- la cantidad para agregar al valor del puntero de datos (nuevamente, o restar)
- un puntero a la siguiente instrucción para ejecutar
- un valor que se compara con el valor en el puntero de datos antes de cambiarlo
El bucle del intérprete cambia a la lógica de la siguiente manera: agregue el valor de datos en la instrucción al valor en el puntero de datos agregue el valor de dirección de datos en la instrucción al puntero de datos si el valor en el puntero de datos coincide con nuestro valor de comparación establecido el puntero de instrucción al nuevo puntero de instrucción continúa (al siguiente ciclo de intérprete) si el valor de comparación es un valor especial (p. ej., puede elegir 0x80000000) manejar elementos de entrada / salida aumentar la dirección de instrucción en uno
La interpretación inicial ahora se vuelve más complicada: las instrucciones ahora pueden combinar +, -, <,> y algunas veces incluso [, y por lo general] en la misma instrucción. La primera rama en el bucle se puede representar sin ramificación si es inteligente al respecto (y aún más eficiente con algún ensamblaje atascado o algunos intrínsecos del compilador). Es posible que desee informar al compilador que es poco probable que la segunda ramificación golpee (la entrada / salida es el cuello de botella en ese caso, no la velocidad de interpretación, por lo que incluso si está haciendo una gran cantidad de entrada / salida, una pequeña rama no optimizada no hará la diferencia).
Se debe tener cuidado para la condición de fin de carrera. La última instrucción en su programa BF interpretado ahora SIEMPRE debe hacer que el puntero de instrucción sea NULO para que el bucle salga.
El orden en el que ocurre la interpretación es importante porque - / + se realiza antes de que se realice <> antes de que [se haya realizado antes] antes de la E / S. Entonces,> + es dos instrucciones interpretadas mientras que +> es uno.
Más allá de diseñar un intérprete rápido de bucle cerrado como este, está buscando un análisis de código más complejo, en cuyo caso obtendrá el diseño del compilador y se alejará de un intérprete directo. Esto no es algo que hago todos los días, pero el libro "Construcción de compiladores" de Louden fue una lectura muy buena para mí, pero de esa manera no terminará siendo un proyecto pequeño. A menos que piense seriamente en hacer que esto sea ridículamente rápido y, al final, probablemente código compilado, me mantendré alejado de arrojar las grandes y contundentes optimizaciones.
Espero haberle dado una idea para probar y probar que lo lleve a más pasos de optimización. No he probado nada de esto yo mismo, así que sigue siendo una conjetura basada en la experiencia pasada. Sin embargo, incluso si no termina siendo más rápido, habrá adquirido cierta experiencia en la reescritura del código BF en una arquitectura relativamente diferente de un intérprete vainilla BF.
PD: ¡ gran pregunta!
Puedo ver un par de posibilidades. Creo que la forma en que iría sería convertirlo en un compilador que produjera código de subproceso directo. Es decir, a medida que lee la entrada, en lugar de copiar la mayoría de las "instrucciones" en la memoria más o menos como está, en su lugar escribiría el código para implementar cada instrucción como una función y copiaría un puntero a cada función en la memoria. Luego, ejecutar el código consistiría en llamar esas funciones en orden. Probablemente tendré esa función devolviendo el índice (o tal vez la dirección) de la siguiente instrucción para ejecutar, por lo que terminaría con algo como:
typedef int return_type;
typedef return_type (*f)(void);
f *im = malloc(sizeof(f) * ia);
ci = (*(im[ci]))();
También tendría tres funciones separadas para cada instrucción, una para cada modo BF_END_ *, por lo que solo tendrías que lidiar con eso durante la fase de "compilación". Cuando ejecutas el código, tienes un puntero directamente a la función correcta.
Editar:
He estado jugando un poco con el código. He separado las direcciones de los bucles en una matriz separada, y he fusionado la mayoría del análisis sintáctico, por lo que se ve así:
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;
}
}
Eso no hace una diferencia real en la velocidad, pero hace que el código sea mucho más corto y (al menos en mi opinión) más fácil de entender.
Edit2:
De acuerdo, he tenido la oportunidad de jugar con esto un poco más, y encontré una optimización (bastante extraña) que parece ayudar al menos un poco. Los compiladores a menudo producen un código marginalmente mejor para las sentencias switch con valores de casos densos, así que traté de convertir a eso, y obtuve una mejora de alrededor del 9-10% (dependiendo un poco del compilador).
#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;
}
Usa la infraestructura LLVM JIT y haz que optimice el código para ti ...
editar: en realidad ya se ha hecho varias veces; compilador: http://www.remcobloemen.nl/2010/02/brainfuck-using-llvm/ JIT: https://github.com/resistor/BrainFTracing (observe cómo el "compilador" tiene 230 líneas de longitud, contando también en blanco líneas, comentarios y #includes)
edit2: para el que menosprecia: dado que pareces haberlo perdido, el significado de mi respuesta fue "no reinventar la rueda"
Vería varias cosas.
Su switch es bastante complicado debido al manejo de errores. Intente reorganizar eso, que solo tenga la ruta rápida dentro del interruptor y llame a una o varias funciones para detectar errores. En general, cuanto más corto se obtenga el código dentro del switch y menos variables utilices, mejor será el que tu optimizador pueda switch .
Tienes demasiados indirectos. Por ejemplo, su índice ci no sirve mucho. Tener un puntero que apunta a la celda real. Esto le permite guardar un registro. Podrías hacer algo similar con ii . En lugar de mantener el número de instrucciones, solo tiene un puntero en la posición en cm .
En cualquier caso, verifique el ensamblador que se genera. Verá rápidamente dónde su compilador produce demasiado desbordamiento de registros o cosas por el estilo.