Несколько дней назад закончилось соревнование ICFP Contest 2009... Там в задании была описана несложная виртуальная машина, на которой запускались данные организаторами программы для моделирования орбитальной механики. Тут я расскажу, как, используя возможности функционального языка программирования, можно сделать интерпретатор быстрее, чем на С++.
...
[C++] реализация на моей рабочей машинке 2,33 ГГц выполняет первую программу из 266 команд 377 000 раз в секунду. Но при участии в ICPFC я все писал на OCaml'e. [OCaml] работал несколько медленнее: только 263 000 итераций в секунду. Захотелось его ускорить, и были сделаны две оптимизации.
...
Оптимизированная программа подвергается описанной выше псевдокомпиляции, и скорость возрастает до 650 000 итераций в секунду, что в 1,7 раза быстрее варианта на С++ и в 2,5 раза быстрее исходного интепретатора на Окамле.
Какой ценой? В C++ даже замыканий нет, я уж не говорю про продолжения.
Можно то оно и на ассемблере можно. Но во временных рамках ICFPC точно нельзя. Да и в любом реальном проекте не рекомендуется, такой код поддерживать будет просто нереально.
Re[2]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Mamut, Вы писали:
M>>http://thedeemon.livejournal.com/1569.html WH>О том что тоже самое можно проделать с программой на С++ автор умалчивает...
Здравствуйте, Аноним, Вы писали:
А> Какой ценой?
В данном случае весьма не большой.
А>В C++ даже замыканий нет, я уж не говорю про продолжения.
Но есть указатели на функции и виртуальные функции на выбор.
А> Можно то оно и на ассемблере можно. Но во временных рамках ICFPC точно нельзя. Да и в любом реальном проекте не рекомендуется, такой код поддерживать будет просто нереально.
Писать лень(да и компилятора С++ под рукой нет). Но кода там будет не многим больше.
Короче не надо ужасов там где их нет.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, WolfHound, Вы писали:
А>>В C++ даже замыканий нет, я уж не говорю про продолжения. WH>Но есть указатели на функции и виртуальные функции на выбор.
На Окамле там создается цепочка из замыканий, причем все вызовы хвостовые и превращаются в jmp.
Интересно было бы увидеть, как это можно сделать на С++. Но даже если можно, не уверен, что получится хорошая скорость.
Re[4]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, WolfHound, Вы писали:
WH>Писать лень(да и компилятора С++ под рукой нет). Но кода там будет не многим больше. WH>Короче не надо ужасов там где их нет.
Написать свой аллокатор взамен malloc/new — «немногим больше»? Если я не перепутал блогпост, то там в обсуждении говорилось, что сливает именно стандартный плюсовый менеджер памяти. А в OCaml'е там GC, выделения памяти очень быстрые.
Глаза у меня добрые, но рубашка — смирительная!
Re[5]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, Qbit86, Вы писали:
Q> Если я не перепутал блогпост
перепутал
Re[4]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От:
Аноним
Дата:
07.07.09 11:28
Оценка:
Здравствуйте, WolfHound, Вы писали:
А>> Какой ценой? WH>В данном случае весьма не большой.
А для интерпретатора размерами побольше? А для кода, в котором этих интерпретаторов десятки?
А>>В C++ даже замыканий нет, я уж не говорю про продолжения. WH>Но есть указатели на функции и виртуальные функции на выбор.
Что?!? Тоже мне, равнозначная замена. Код в разы раздувается, если окружение в замыкания вручную засовывать.
WH>Писать лень(да и компилятора С++ под рукой нет). Но кода там будет не многим больше.
Нет, там будет намного больше кода. Уж больно язык уродский. Глупо даже сравнивать с языком, где есть замыкания и continuations.
WH>Короче не надо ужасов там где их нет.
Их там таки есть.
Re[2]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, eao197, Вы писали:
E>А доступен ли где-нибудь C++ный бенчмарк и тестовая программка для этой ВМ? Чтобы можно было скачать и поэкспериментировать
Здравствуйте, WolfHound, Вы писали:
WH>О том что тоже самое можно проделать с программой на С++ автор умалчивает...
Уже не умалчивает: http://thedeemon.livejournal.com/1859.html
В общем, закат солнца вручную возможен и приносит свои плоды, но приходится написать много нудного кода. На одинаковых алгоритмах С++ все же быстрее, у него оптимизатор лучше.
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, WolfHound, Вы писали:
WH>>О том что тоже самое можно проделать с программой на С++ автор умалчивает...
DM>Уже не умалчивает: DM>http://thedeemon.livejournal.com/1859.html DM>В общем, закат солнца вручную возможен и приносит свои плоды, но приходится написать много нудного кода. На одинаковых алгоритмах С++ все же быстрее, у него оптимизатор лучше.
Что если заменить все эти мелкие классы c виртуальными Execute на простые функции в классе VM ? Должно быть проще.
class VM;
class params;
typedef void (VM::*)(const params&) continuat_t;
class params
{
public:
params() // для op_end
{ }
params(int ip, int r1, int r2, continuat_t next, params *npar)
// тут инициализация
{ }
// getter's for ip, r1, r2void next(VM *vm) const
{
(vm->*next_)(*npar_);
}
private:
int ip_, r1_, r2_;
continuat_t next_;
const params *npar_;
};
class VM
{
...
public:
void op_add(const params &ps)
{
// действие операции
ps.next(this); // продолжение
}
...
void op_end(const params&)
{
}
...
};
// использование:typedef std::deque<params> vec_ps;
continuat_t comp_prog(vec_ps &prog)
{
// последняя операция - op_end
continuat_t next = VM::op_end;
prog.push_back(params());
// с конца - к началуfor (...)
{
switch (dop)
{
#define OP(TAG, IP, R1, R2, COP) case OP: prog.push_back(params(IP, R1, R2, next, &prog.back())); next = &VM::COP; break;
...
// case ADD: prog.push_back(params(ip, dr1, dr2, next, &prog.back())); next = &VM::op_add; break;
OP(ADD, ip, dr1, dr2, op_add)
...
#undef OP
}
}
return next;
}
int main()
{
VM vm(...);
vec_ps prog;
continuat_t start = comp_prog(prog);
vm.*start(prog.back());
}
Код не проверял.
You aren't expected to absorb this
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
M>>>http://thedeemon.livejournal.com/1569.html WH>>О том что тоже самое можно проделать с программой на С++ автор умалчивает...
А> Какой ценой? В C++ даже замыканий нет, я уж не говорю про продолжения.
А> Можно то оно и на ассемблере можно. Но во временных рамках ICFPC точно нельзя. Да и в любом реальном проекте не рекомендуется, такой код поддерживать будет просто нереально.
Ну вообще говоря, это преувеличения. Для реализации подобной задачи замыкания особенно и ни к чему, да и классы
с виртуальными функциями тоже. Код VM — примитивен, никаких проблем с поддержкой в принципе быть не может.
Наиболее ресурсоемкая операция — вовсе не переход, а декодирование опкода. Соответственно, если выполнить декодирование один раз,
заменив опкоды на указатели на функции или метки, то можно даже не заморачиваться с оптимизацией перехода от инструкции
к инструкции — это всего лишь лишнее продвижение указателя.
Но, в общем, смысл мерять окамл и вообще высокоуровневые языки на задачах, которые должны работать как можно ближе к железу?
Ценность окамла для данной задачи в том, что vm делается за пять минут, и работает сразу, без затрат времени на вылавливание
ошибок. Потому что мало кода и программа заведомо корректна с точки зрения типов, и ничего никуда не упадет.
Если же захотелось быстрой интерпретации, то незначительно подкрутив код на окамле, можно сделать транслятор байткодов в си
с последующей компиляцией последнего.
А вот когда дело доходит до сложных вещей, начинает упираться в управление памятью и когда декомпозиция задачи начинает играть роль,
вот тут уже меряться имеет смысл.
Вот тут я померял разные способы интерпретации на си. Реализация аналогичной машины на окамле тоже есть, уступает по производительности минимум в пять раз.
И, кстати, могу заметить, что C++ для данной задачи только помеха — все вот эти реализации паттерна Command с виртуальной функцией и кучей классов — только раздувают код, не принося ничего полезного по сути.
Re[4]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
Здравствуйте, dmz, Вы писали:
dmz>Наиболее ресурсоемкая операция — вовсе не переход, а декодирование опкода. Соответственно, если выполнить декодирование один раз, dmz>заменив опкоды на указатели на функции или метки, то можно даже не заморачиваться с оптимизацией перехода от инструкции dmz>к инструкции — это всего лишь лишнее продвижение указателя.
это называется шитый код. а если его ещё синлайнить — то получится быстрее чем вручную написанная асмовская программа
Люди, я люблю вас! Будьте бдительны!!!
Re[5]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
BZ>это называется шитый код. а если его ещё синлайнить — то получится быстрее чем вручную написанная асмовская программа
Их там целое семейство шитых кодов. Этот у наc token-threaded. Под инлайнингом понимается замена опкода непосредственно на код, его выполняющий (приведение к direct threaded code) ? Это соответственно и плохо скажется на плотности кода, а один из смыслов использования интерпретаторов — это получение более плотного кода, нежели нативный, что бы впихнуть больше функций в устройства с сильно ограниченной памятью.
Есть еще всякие полумеры, например, вычисление адресов и замена номеров "регистров" непосредственно указателями на "регистр". Тогда размер растет предсказуемо, в каких-то случаях может оказаться выгоднее.
http://rsdn.ru/forum/flame.comp/3458672.aspx
