Ускорение интерпретатора на С++

[thedeemon]

В предыдущем посте изначально проигрывавший сиплюсплюсу Окамл после одной оптимизации интерпретатора стал С++ немного обгонять, а после второй - еще сильнее. Как справедливо заметили читатели, те же оптимизации можно сделать и в С++. Вторая делается элементарно, а вот первая требует наличия замыканий и оптимизации хвостовой рекурсии. Только что попробовал сделать закат солнца вручную - первый прием с замыканиями реализовал на С++ в лоб, представив замыкания объектами.

Update: это НЕ попытка предложить оптимальный способ интерпретации. Это только попытка напрямую перенести на С++ прием из предыдущего поста.

Кода получилось намного больше:

enum cmp_op {
    LTZ=0, LEZ=1, EQZ=2, GEZ=3, GTZ=4
};

enum instr_d {
    SOP=0, ADD=1, SUB=2, MUL=3, DIV=4, OUTPUT=5, PHI=6
};

enum instr_s {
    NOP=0, CMP=1, SQRT=2, COPY=3, INPUT=4
};

class Command {
public:
    int ip, r1, r2;
    Command *next;
    VM &vm;
    Command(int _ip, int _r1, int _r2, Command *k, VM& _vm) : ip(_ip), r1(_r1), r2(_r2), next(k), vm(_vm) {}
    virtual void Execute()=0;
};

class Add : public Command {
public:
    Add(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] = vm.mem[r1] + vm.mem[r2]; next->Execute(); } 
};

class Sub : public Command {
public:
    Sub(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] = vm.mem[r1] - vm.mem[r2]; next->Execute(); } 
};

class Mul : public Command {
public:
    Mul(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] = vm.mem[r1] * vm.mem[r2]; next->Execute(); } 
};

class Div : public Command {
public:
    Div(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] = vm.mem[r2]==0.0 ? 0.0 : vm.mem[r1] / vm.mem[r2]; next->Execute(); } 
};

class Out : public Command {
public:
    Out(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.out[r1] = vm.mem[r2]; next->Execute(); } 
};

class Inp : public Command {
public:
    Inp(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] =  vm.inp[r1]; next->Execute(); } 
};

class Sqrt : public Command {
public:
    Sqrt(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] = sqrt(vm.mem[r1]); next->Execute(); } 
};

class Copy : public Command {
public:
    Copy(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { vm.mem[ip] = vm.mem[r1]; next->Execute(); } 
};

class Phi : public Command {
public:
    Phi(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm) {}
    virtual void Execute() { printf("Error: phi gets executed!\n"); } 
};

class CmpLTZ : public Command {
    int pip, pr1, pr2;
public:
    CmpLTZ(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm), 
        pip(k->ip), pr1(k->r1), pr2(k->r2) { next = k->next; }
    virtual void Execute() { vm.mem[pip] = vm.mem[r1] < 0 ? vm.mem[pr1] : vm.mem[pr2];  next->Execute(); }
};

class CmpLEZ : public Command {
    int pip, pr1, pr2;
public:
    CmpLEZ(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm), 
        pip(k->ip), pr1(k->r1), pr2(k->r2) { next = k->next; }
    virtual void Execute() { vm.mem[pip] = vm.mem[r1] <= 0 ? vm.mem[pr1] : vm.mem[pr2];  next->Execute(); }
};

class CmpEQZ : public Command {
    int pip, pr1, pr2;
public:
    CmpEQZ(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm), 
        pip(k->ip), pr1(k->r1), pr2(k->r2) { next = k->next; }
    virtual void Execute() { vm.mem[pip] = vm.mem[r1] == 0.0 ? vm.mem[pr1] : vm.mem[pr2];  next->Execute(); }
};

class CmpGEZ : public Command {
    int pip, pr1, pr2;
public:
    CmpGEZ(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm), 
        pip(k->ip), pr1(k->r1), pr2(k->r2) { next = k->next; }
    virtual void Execute() { vm.mem[pip] = vm.mem[r1] >= 0 ? vm.mem[pr1] : vm.mem[pr2];  next->Execute(); }
};

class CmpGTZ : public Command {
    int pip, pr1, pr2;
public:
    CmpGTZ(int _ip, int _r1, int _r2, Command *k, VM& _vm) : Command(_ip, _r1, _r2, k, _vm), 
        pip(k->ip), pr1(k->r1), pr2(k->r2) { next = k->next; }
    virtual void Execute() { vm.mem[pip] = vm.mem[r1] > 0 ? vm.mem[pr1] : vm.mem[pr2];  next->Execute(); }
};

class End : public Command {
public:
    End(VM& _vm) : Command(0,0,0, NULL,_vm) {}
    virtual void Execute() { vm.time++; }
};

Command* comp_instr(int ip, DWORD ins, Command *nxt, VM& vm)
{
    const int dop = ins>>28;
    const int dr1 = (ins >> 14) & 0x3FFF; 
    const int dr2 = ins & 0x3FFF;
    switch(dop) {
        case ADD: return new Add(ip, dr1, dr2, nxt, vm); break;
        case SUB: return new Sub(ip, dr1, dr2, nxt, vm); break;
        case MUL: return new Mul(ip, dr1, dr2, nxt, vm); break;
        case DIV: return new Div(ip, dr1, dr2, nxt, vm); break;
        case OUTPUT: return new Out(ip, dr1, dr2, nxt, vm); break;
        case PHI: return new Phi(ip, dr1, dr2, nxt, vm); break;
        case SOP:    { 
                const int sop = ins >> 24;
                const int imm = (ins >> 21) & 7;
                const int sr1 = dr2;
                switch(sop) {                    
                    case NOP: return nxt; break;
                    case CMP: switch(imm) {
                                case LTZ: return new CmpLTZ(ip, sr1, dr2, nxt, vm); break;
                                case LEZ: return new CmpLEZ(ip, sr1, dr2, nxt, vm); break;
                                case EQZ: return new CmpEQZ(ip, sr1, dr2, nxt, vm); break; 
                                case GEZ: return new CmpGEZ(ip, sr1, dr2, nxt, vm); break; 
                                case GTZ: return new CmpGTZ(ip, sr1, dr2, nxt, vm); break; 
                                default: printf("bad imm=%d ip=%d\n", imm, ip); return NULL;
                            } break;
                    case SQRT: return new Sqrt(ip, sr1, dr2, nxt, vm); break;
                    case COPY: return new Copy(ip, sr1, dr2, nxt, vm); break;
                    case INPUT: return new Inp(ip, sr1, dr2, nxt, vm); break;
                    default: printf("bad sop=%d ip=%d\n", sop, ip); return NULL;
                }
                }
                break;
        default: printf("bad dop=%d ip=%d\n", dop, ip); return NULL;
    } 
    return NULL;
}

Command* comp_prg(DWORD *prg, int prglen, VM& vm)
{
    Command *cmd = new End(vm);
    for(int i=prglen-1; i>=0; i--) 
        cmd = comp_instr(i, prg[i], cmd, vm);
    return cmd;
}

Зато скорость возросла в 1,3 раза. Результат быстрее, чем аналогичный вариант на Окамле после первой оптимизации. Что и понятно - т.к. С++ есть кроссплатформенный ассемблер с рюшками, на нем можно повторить почти все, просто нередко, как в данном случае, это потребует кропотливого мартышкиного труда, который в случае более высокоуровневых языков берет на себя компилятор. А т.к. оптимизатор в Окамле почти никакой, аналог на С++ получается быстрее.

Comments

[thedeemon.livejournal.com]

MSVC 6.0, Release.

[lesterzx.livejournal.com]

а теперь попробуйте VC2008 + оптимизация O2( я молчу про подбор остальных параметров ), и даже на вашем варианте почувствуйте разницу