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

[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

[gabaidulin.livejournal.com]

А что за класс VM?

[thedeemon.livejournal.com]

Там данные ВМ, загрузчик и исходный интерпретатор. В приведенном выше коде оттуда только данные используются.

class VM {
public:
DWORD prg[16384];
int prglen;
double mem[16384];
bool status;
int time;

double inp[16384];
double out[16384];

VM() : status(false), time(0), prglen(0) {
for(int i=0; i<16384;i++) {
inp[i] = out[i] = mem[i] = 0.0;
prg[i] = 0;
}
}
...

[dmzlj.livejournal.com]

Есть вариант интерпретации такого кода с вычислимыми метками - вроде бы это близко к предельной скорость интерпретации для подобного кода.

Тут все таки много лишнего делается - какие-то выделения памяти, виртуальные вызовы и т.п.

void vm_run(char *pcode)
{
    unsigned int lit    = 0;
    unsigned int regs[] = { 0, 0, 0, 0 };
    unsigned int regi   = 0;

	void *opcodes[] = {
        &&op_nop, &&op_lit, &&op_add, &&op_sub
	}

    goto opcodes[*pcode++];

	op_nop:
		goto opcodes[*pcode++];

    op_load:
        // decode register
        // decode register
        // decode register
        regs[r_dst] = regs[r_src1] + regs[r_scr2];
		goto opcodes[*pcode++];

    op_add:
        // decode register
        // decode register
        // decode register
        regs[r_dst] = regs[r_src1] - regs[r_scr2];
		goto opcodes[*pcode++];

    // ...

}

[dmzlj.livejournal.com]

недоисправил метки, но суть я думаю, понятна

[thedeemon.livejournal.com]

Но это gcc-only, так?
Я в MSVC все компилю.

[dmzlj.livejournal.com]

Наверное, да. хотя MS моглаи поддержать, или у них есть какие-то аналоги. Все таки и switch, и вызов на опкод дают оверхед - в первом случае неэффективное сравнение, во втором затраты на пролог - эпилог вызываемой функции. По идее, если есть способ сгенерировать функцию без пролога - эпилога, то может тоже получится неплохо.

Где-то была статья, сравнивающая способы интерпретации такого байткода, можно попытаться ее найти, если надо.

[thedeemon.livejournal.com]

>Наверное, да. хотя MS моглаи поддержать, или у них есть какие-то аналоги.

Видимо, не поддержали и не предоставили аналогов. Именно поэтому исполнитель окамловского байткода, собранный в MSVC, медленнее собранного GCC.

[thedeemon.livejournal.com]

Выделения памяти только один раз - при "компиляции". Во время выполнения их нет.
Виртуальный вызов по стоимости должен быть сравним с
goto opcodes[*pcode++], возможно даже быстрее (т.к. индекс - константа).

[dmzlj.livejournal.com]

То есть другими словами, это решение рассчитывает на вариант, когда мы сравнительно небольшой код один раз "компилируем", а затем многократно исполняем?

Т.е. в случае однократного прогона, в режиме обычной vm - особой прибыли не будет? Тогда, в общем, понятно.

[lazyreader.livejournal.com]

Я вот никак не пойму, чем это лучше, чем простой switch?

[dmzlj.livejournal.com]

ну скомпилируйте "простой свитч" и приведите то, во что он скомпилируется. думаю, комментарии будут излишни.

[lazyreader.livejournal.com]

run():
.LFB17:
	pushl	%esi
.LCFI0:
	pushl	%ebx
.LCFI1:
	xorl	%ebx, %ebx
	subl	$20, %esp
.LCFI2:
	.p2align 4,,7
	.p2align 3
.L32:
	movl	prg(,%ebx,4), %eax
	movl	%eax, %edx
	movl	%eax, %ecx
	shrl	$14, %ecx
	movl	%eax, %esi
	shrl	$28, %edx
	andl	$16383, %ecx
	andl	$16383, %esi
	cmpl	$6, %edx
	jbe	.L42
	movl	%ebx, 8(%esp)
	movl	%edx, 4(%esp)
	movl	$.LC3, (%esp)
	call	printf
.L33:
	addl	$20, %esp
	popl	%ebx
	popl	%esi
	ret
	.p2align 4,,7
	.p2align 3

Вот, собственно, и он, простой switch:

.L42:
	jmp	*.L10(,%edx,4)
	.section	.rodata
	.align 4
	.align 4
.L10:
	.long	.L3
	.long	.L4
	.long	.L5
	.long	.L6
	.long	.L7
	.long	.L8
	.long	.L9

[dmzlj.livejournal.com]

ok, я как раз собирался развить эту тему у себя несколько позже. сравнить скорость интерпретации разных реализаций. нюанс не только в раскрытии свичта, но есть и другие бенефиты, правда менее заметные.

если приведете компилятор, опции и исходник, который собирался - тоже будет полезно. возможно, со времен gcc 3.X компиляторы продвинулись, но в моей специфике приходится полагаться в лучшем случае на gcc 3.X, так как embedded компиляторы делаются на его базе. там все намного более печально.

[lazyreader.livejournal.com]

g++ (Debian 4.3.2-1.1) 4.3.2

А исходник - тот самый, что в http://thedeemon.livejournal.com/1569.html.

[dmzlj.livejournal.com]

http://dmzlj.livejournal.com/45288.html

[lazyreader.livejournal.com]

Да, опции - -O3 -fomit-frame-pointer

[dmzlj.livejournal.com]

Вот тут у меня возникает непонимание - по идее, самой проблемной операцией является сравнение опкодов и определение кода, который будет тот или иной опкод исполнять.

Т.е. до меня никак не может дойти, что где мы выигрываем, сначала пройдясь и построив всю цепочку, применив теже самые сравнения, а потом просто эту цепочку пробежав.

Кроме того, под вопросом как оно себя поведет, например, если байткодов много. Т.е. под 300 - 500 инструкций навыделять кусочков памяти не вопрос, а вот под 5'000'000 ?

Я свою попытку сделать vm на окамле тестировал на примерно таком количестве.

[thedeemon.livejournal.com]

Данная ВМ была для ICFPC'09, там программа исполняется миллионы раз. Поэтому да, подход именно один раз скомпилять и много раз выполнить. У меня это активно использовалось в решении - многократно просчитывалось движение спутников на 1000 секунд вперед.

Ускорение исполнения в 1,3 раза не покрывает расходов на "компиляцию" при однократном запуске.

С сильно большой программой получится менее cache friendly и выигрыш может сойти на нет.

Размер кода можно уменьшить.

[andrew-falaleev.livejournal.com]

В C++ есть шаблоны и наследие C - макросы.
У вас куча однотипного кода написано - это все замечательно сокращается до небольшой портяночки.

Оно конечно хорошо, что вы все таки проверили, что он и правда быстрее, но то что объем кода будет очень большой - несовсем верно.

Re: Размер кода можно уменьшить.

[thedeemon.livejournal.com]

Можно пример кода?
Запихивать целый класс в макрос как-то не привык..

Re: Размер кода можно уменьшить.

[andrew-falaleev.livejournal.com]

Например самый простой вариант. Вы же используете MSVC, там в том же MFC часто встречаются макросы.

#define CLASS_BEGIN(NAME) \
class NAME : public Command { \
public: \
NAME(int _ip, int _r1, int _r2, Command *k, VM& _vm) :\
Command(_ip, _r1, _r2, k, _vm) {} \
virtual void Execute() {

#define CLASS_END next->Execute(); } };


Тогда ваши портянки сведутся к:

CLASS_BEGIN(Add) vm.mem[ip] = vm.mem[r1] + vm.mem[r2]; CLASS_END
CLASS_BEGIN(Sub) vm.mem[ip] = vm.mem[r1] - vm.mem[r2]; CLASS_END
...

Там у вас ниже CmpLEZ - оно маленько отличается. Если грубо, то можно в лоб:

CLASS_BEGIN(CmpLEZ) vm.mem[k->ip] = vm.mem[r1] <= 0 ? vm.mem[k->pr1] : vm.mem[k->pr2]; k-> CLASS_END

Это как самый простой вариант уменьшения объема кода. Возможны другие подходы.

Re: Размер кода можно уменьшить.

[thedeemon.livejournal.com]

Спасибо! Действительно, можно сделать так. Но чтобы придти к такому сжатому варианту и понять как именно его получить, надо сначала написать несжатый (хотя бы часть). Итоговое число строк сократится, а время и усилия на разработку не очень.

[lesterzx.livejournal.com]

Ну нельзя настолько специально подтасовывать, а также вводить в заблуждение относительно читабельности кода, просто сделай вариант на С c "расшифровкой" и последующим кодом в виде:

for( size_t i = 0 ; i < progLen ; ++i )
{
switch( cm[ i ] )
{
case ADD: mem[ i ] = arg1[ i ] + arg2[ i ]; break;
case MIN: mem[ i ] = arg1[ i ] - arg2[ i ]; break;
...
}
}

( то что ты "забыл" сделать в первом варианте ) и удивись полученному приросту от отсутствия трех switch и шести строк на расшифовку комманд

[thedeemon.livejournal.com]

Верно. Еще избавиться от case и break, и получится почти Окамл. :)

[lesterzx.livejournal.com]

mem[ arg1[ i ] ] и mem[ arg2[ i ] ] конечно, кстати интересно услышать про компилятор и параметры оптимизации

[thedeemon.livejournal.com]

MSVC 6.0, Release.

[lesterzx.livejournal.com]

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

[lazyreader.livejournal.com]

Извините, но вы пишете странные вещи. Как может программа, набитая new и вызовами виртуальных функций, быть быстрее программы с одним простым циклом со счётчиком, внутри которого switch с инлайновым кодом, оптимизирующийся компилятором почти идеально? (Во всяком случае, мой эксперимент показывает, что она и не быстрее, а медленнее примерно в полтора раза.)

Если бы вы выложили компилируемый пример для обоих случаев, то это был бы аргумент. Пока же и умозрительно, и экспериментально я вижу, что вторая программа медленнее первой.

[lazyreader.livejournal.com]

Если компилировать один раз, а потом много раз исполнять, то, признаю, получится сильно быстрее.

[http://users.livejournal.com/_kleptos_/]

> оптимизатор в Окамле почти никакой
это чуть более, чем полностью не соответствует действительности.

[thedeemon.livejournal.com]

Рад, что Вы так думаете.
Из чтения окамловской рассылки, тестов и статей о том, как оптимизировать код на нем, у меня сложилось другое мнение.