Optimisation pour un interprète en panne de cerveau

Question

Comme exercice pour m'aider à apprendre les interpréteurs et l'optimisation, dont je ne connais rien, j'ai écrit un interpréteur brainfuck en C. Il semble fonctionner parfaitement jusqu'à présent, bien qu'il ne rivalise pas en vitesse d'exécution par rapport à d'autres interpréteurs rapides.

Comment puis-je modifier cet interpréteur pour améliorer les performances (ou autres) ?

Un aspect intéressant de mon interpréteur (même si la plupart des autres font probablement de même) est que j'exécute une boucle qui lit l'entrée source et convertit chaque instruction en un fichier

struct { long instruction; long loop; }

El loop est l'indice de l'élément correspondant ] si l'instruction est une [ et l'indice de la correspondance [ si l'instruction est une ] ce qui permet de sauter rapidement. J'imagine que ce processus de "parsing" (qui ne prend pas beaucoup de temps) améliore les temps d'exécution par rapport à un reparsing redondant pour trouver les crochets correspondants chaque fois qu'ils sont nécessaires.

Un test intéressant de la vitesse de l'interprète de brainfuck est ce programme :

++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>

1. la première version de l'interpréteur
2. l'interprète après avoir mis en œuvre La réponse de Jerry Coffin qui supprime l'interrupteur géant dans la boucle d'exécution, en faisant de l'élément instruction de la structure instruction un pointeur direct vers une fonction d'opération - cela fonctionne plus lentement que la version précédente (surcharge d'appels de fonction ?)
3. l'interprète après inverser le changement précédent et l'ajout d'une optimisation permettant de "regrouper" plusieurs opérations consécutives sans boucle, ce qui réduit les cycles de boucle. cette version est légèrement plus rapide que la version originale

Answer 1

Eh bien, ce n'est pas C. Et ce n'est pas un interpeter. Donc, oui, c'est totalement inapproprié pour cette question.

Mais ce qu'il est, c'est un compilateur parfaitement portable qui utilise les templates variadiques C++0x. Vous devez #define PROGRAM comme une séquence de caractères de syntaxe C séparés par des virgules, car je n'ai pas pu les extraire de la chaîne au moment de la compilation. Mais sinon, c'est légitime. Je pense.

Testé avec g++ 4.5.2, en utilisant 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;
}

Answer 2

Je vois plusieurs possibilités. Je pense que la voie que j'emprunterais serait de le transformer en un compilateur qui produirait du code direct-threaded. C'est-à-dire qu'en lisant l'entrée, au lieu de copier la plupart des "instructions" en mémoire plus ou moins telles quelles, j'écrirais le code pour implémenter chaque instruction comme une fonction, et copierais un pointeur vers chaque fonction en mémoire. Ensuite, l'exécution du code consisterait à appeler ces fonctions dans l'ordre. Je ferais probablement en sorte que cette fonction renvoie l'index (ou peut-être l'adresse) de la prochaine instruction à exécuter, ce qui donnerait quelque chose comme.. :

typedef int return_type;
typedef return_type (*f)(void);

f *im = malloc(sizeof(f) * ia);

ci = (*(im[ci]))();

J'aurais également trois fonctions distinctes pour chaque instruction, une pour chaque mode BF_END_*, de sorte que vous n'auriez à vous en occuper que pendant la phase de "compilation". Lorsque vous exécutez le code, vous avez un pointeur directement sur la bonne fonction.

Editar:

J'ai joué un peu avec le code. J'ai séparé les adresses des boucles dans un tableau séparé, et j'ai fusionné la plupart des analyses, donc ça ressemble à ça :

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

Cela ne fait pas de réelle différence en termes de vitesse, mais rend le code beaucoup plus court et (du moins à mon avis) plus facile à comprendre.

Edit2 :

J'ai eu l'occasion de jouer avec un peu plus et j'ai trouvé une optimisation (plutôt étrange) qui semble aider au moins un peu. Les compilateurs produisent souvent un code légèrement meilleur pour les instructions switch avec des valeurs de cas denses, j'ai donc essayé de convertir en cela, et j'ai obtenu une amélioration d'environ 9-10% (dépendant un peu du compilateur).

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

Answer 3

Puisque le but de ce projet est d'apprendre, l'utilisation d'un outil ou d'une solution de remplacement ne répond clairement pas à la question.

Tout d'abord, un avertissement : je ne suis pas un programmeur x86 - j'ai fait une quantité décente de travail dans les environnements embarqués et maintenant (avec les téléphones mobiles) les puces ARM. Passons aux choses sérieuses...

Il y a deux façons de rendre votre interpréteur plus rapide : Faire en sorte qu'il optimise le code BF lui-même, et faire en sorte que l'interpréteur lui-même soit optimisé. Je recommanderai un peu des deux en une seule étape ci-dessous.

Pour autant que je sache, x86 consacre beaucoup d'espace de teinture à fournir des propriétés de branchement rapide relativement impressionnantes. Probablement à cause de cela, j'ai vu plusieurs compilateurs (y compris gcc) produire des branches imbriquées en faveur de véritables tables de saut pour x86. Les tables de saut semblent attrayantes en théorie, mais en réalité, x86 optimise si bien les techniques traditionnelles que la pensée conventionnelle big-O ne s'applique pas dans la plupart des cas. C'est pourquoi les développeurs x86 de longue date vous diront que si vous voulez calculer la rapidité d'un code, vous devez l'écrire, l'exécuter et le chronométrer.

Malgré la vitesse à laquelle les branchements peuvent se produire sur x86, il vaut toujours la peine de dépenser un peu d'overhead pour ne pas brancher. Les instructions BF étant de toute façon très simples, cela peut prendre la forme de "faire la plupart des instructions en une seule fois puisque c'est plus rapide qu'un autre branchement". Certaines de ces opérations peuvent même être effectuées en parallèle par le processeur là où le branchement ne peut pas l'être. (x86 a suffisamment d'unités de décodage et d'exécution dans un seul noyau pour que cela soit probablement réalisable).

Le contrôle des erreurs (comme le wrapping) est un autre élément qui va réduire vos performances. Le fait de le conserver vous cause des problèmes de performance (pas majeurs pour l'instant) mais surtout vous empêche d'optimiser.

De plus, votre programme est très générique. Il vous permettra d'utiliser n'importe quelle valeur maximale pour l'enveloppement. S'il s'agissait d'une puissance de deux, il suffirait d'effectuer un ET par bit (très rapide puisqu'il représente un cycle CPU sur pratiquement toutes les plates-formes modernes) équivalent au wrapping au lieu de comparer et de bifurquer. Le diable se cache dans les détails de l'écriture d'interprètes vraiment rapides - chaque petit détail que vous ajoutez rend le tout beaucoup plus complexe.

À cette fin, je recommande de rationaliser ce que fait votre interpréteur BF (faire en sorte qu'il s'enroule à une puissance de deux pour les valeurs, par exemple). L'astuce du AND binaire seul et le fait de forcer le wrap à être l'option (comme c'est le cas dans la plupart des langages de programmation modernes pour les overflows/underflows) supprime déjà au moins deux branches.

Une fois qu'on s'en est occupé, cela permet une optimisation intéressante : on peut se débarrasser des instructions BF et faire en sorte que la machine exécute des instructions différentes qui conviennent mieux à un interprète.

Considérez Java : Java n'interprète pas. Il effectue un JIT dans un langage entièrement différent.

Je recommande d'appliquer la même logique. Vous l'avez déjà fait un peu en donnant à vos instructions une valeur qui leur est associée.

Je recommande de créer une instruction contenant les informations suivantes :

• le montant à ajouter à la valeur sur le pointeur de données (ou soustraire -- la soustraction consiste simplement à ajouter un nombre négatif)
• le montant à ajouter à la valeur de le pointeur de données (à nouveau, ou soustraire)
• un pointeur vers l'instruction suivante à exécuter
• une valeur qui est comparée à la valeur du pointeur de données avant il est changé

La boucle de l'interpréteur se transforme alors en la logique suivante : ajouter la valeur des données dans l'instruction à la valeur du pointeur de données ajouter les données adresse la valeur dans l'instruction au pointeur de données lui-même si la valeur du pointeur de données correspond à notre valeur de comparaison place le pointeur d'instruction sur le nouveau pointeur d'instruction continuer (vers la boucle d'interprétation suivante) si la valeur de comparaison est une valeur spéciale (par exemple, vous pourriez choisir 0x80000000) gérer les trucs d'entrée/sortie augmenter l'adresse de l'instruction d'une unité

L'interprétation initiale devient maintenant plus délicate : Les instructions peuvent maintenant combiner +, -, <, > et parfois même [, et généralement ] dans la même instruction unique. La première branche de la boucle peut être représentée sans branchement si vous êtes malin à ce sujet (et encore plus efficacement avec un peu d'assembleur coincé ou quelques intrinsèques du compilateur). Vous pouvez informer le compilateur qu'il est peu probable que la deuxième branche soit atteinte (l'entrée/sortie est le goulot d'étranglement dans ce cas, pas la vitesse d'interprétation, donc même si vous faites beaucoup d'entrée/sortie, une petite branche non optimisée ne fera pas la différence).

Il faut faire attention à l'état de fin de course. La dernière instruction de votre programme BF interprété doit maintenant TOUJOURS rendre le pointeur d'instruction NULL pour que la boucle se termine.

L'ordre dans lequel l'interprétation a lieu est important car -/+ est fait avant <> est fait avant [ est fait avant ] est fait avant I/O. Donc, >+ est deux instructions interprétées alors que +> est une seule.

Au-delà de l'ingénierie d'un interpréteur rapide à boucles serrées comme celui-ci, vous vous intéressez à l'analyse de code plus complexe, auquel cas vous vous orientez vers la conception d'un compilateur et vous vous éloignez moins d'un simple interpréteur. Ce n'est pas quelque chose que je fais tous les jours, mais le livre "Compiler Construction" de Louden a été une très bonne lecture pour moi, mais ce ne sera pas un petit projet de cette façon. A moins que vous ne vouliez sérieusement rendre cette chose ridiculement rapide et au final probablement compiler du code, je resterais à l'écart des grosses optimisations percutantes.

J'espère vous avoir donné une idée à essayer et à tester qui vous conduira à d'autres étapes d'optimisation. Je n'ai pas essayé tout cela moi-même, donc ce ne sont que des conjectures basées sur l'expérience passée. Cependant, même si cela ne s'avère pas plus rapide, vous aurez acquis une certaine expérience dans la réécriture de code BF sur une architecture relativement différente de celle d'un interpréteur BF classique.

P.S. Superbe question !

Answer 4

Brainfuck devrait être assez facile à compiler en code C, que vous compilez et exécutez ensuite. Ce serait probablement un "interpréteur" de BF très rapide.

Fondamentalement, tout ce que vous avez à faire, c'est de générer un code assez trivial pour chaque opérateur d'imbécile. de gauche à droite dans le programme. On peut facilement optimiser des séquences de + et - ; De même, on peut optimiser les séquences de < et >, en mettant en cache les comptes de chaque opérateur récemment rencontré. rencontrés. Il s'agit d'une sorte d'optimisation de type "peephole".

Voici un projet de compilateur, acceptant le code BF sur la ligne de commande et imprimant le programme compilé sur la console :

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

C'est un code composé à partir de ma tête, inspiré par le code de Matthew Blanchard (merci Matthew !), mais pas testé. Je laisse cela à une autre âme ; n'hésitez pas à corriger le code si vous trouvez un problème. Évidemment, il serait amélioré s'il écrivait son code dans un fichier :-}

[J'ai utilisé le http://en.wikipedia.org/wiki/Brainfuck article comme l'inspiration évidente pour le code à générer].

Le programme BF de l'OP :

++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>

devrait se compiler en (indentation ajoutée) :

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

La moyenne est probablement assez proche d'une instruction machine par opération BF.

Quelqu'un de vraiment ambitieux calculerait les valeurs possibles de ptr à chaque point du programme ; je suppose que dans de nombreux cas, il se réfère à une cellule constante. On pourrait alors éviter les accès indirects.

Si vous vouliez vraiment devenir fou, vous pourriez comprendre ce que font les commandes BF jusqu'à la première demande d'entrée ; cela doit être une configuration initiale "constante" de la mémoire, et générer un initialisateur CELLSPACE avec cette constante, et générer du code pour le reste du programme comme je l'ai montré. Si vous faites cela, l'exemple de programme d'OP disparaîtrait en un seul initialisateur CELLSPACE et quelques appels putc.

Answer 5

Utilisez l'infrastructure LLVM JIT et laissez-la optimiser le code pour vous...

edit : en fait, cela a déjà été fait plusieurs fois ; compilateur : http://www.remcobloemen.nl/2010/02/brainfuck-using-llvm/ JIT : https://github.com/resistor/BrainFTracing (notez comment le "compilateur" fait 230 lignes, en comptant aussi les lignes vides, les commentaires et les #includes)

edit2 : pour le downvoter : puisque vous semblez l'avoir manqué, le sens de ma réponse était "ne réinventez pas la roue".