C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: Mamut Швеция http://dmitriid.com
Дата: 07.07.09 08:30
Оценка:
http://thedeemon.livejournal.com/1569.html

Несколько дней назад закончилось соревнование ICFP Contest 2009... Там в задании была описана несложная виртуальная машина, на которой запускались данные организаторами программы для моделирования орбитальной механики. Тут я расскажу, как, используя возможности функционального языка программирования, можно сделать интерпретатор быстрее, чем на С++.

...

[C++] реализация на моей рабочей машинке 2,33 ГГц выполняет первую программу из 266 команд 377 000 раз в секунду. Но при участии в ICPFC я все писал на OCaml'e. [OCaml] работал несколько медленнее: только 263 000 итераций в секунду. Захотелось его ускорить, и были сделаны две оптимизации.

...

Оптимизированная программа подвергается описанной выше псевдокомпиляции, и скорость возрастает до 650 000 итераций в секунду, что в 1,7 раза быстрее варианта на С++ и в 2,5 раза быстрее исходного интепретатора на Окамле.


Код — по ссылке

via http://lionet.livejournal.com/36771.html


dmitriid.comGitHubLinkedIn
Re: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: WolfHound  
Дата: 07.07.09 10:08
Оценка:
Здравствуйте, Mamut, Вы писали:

M>http://thedeemon.livejournal.com/1569.html

О том что тоже самое можно проделать с программой на С++ автор умалчивает...
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: Аноним  
Дата: 07.07.09 10:37
Оценка:
Здравствуйте, WolfHound, Вы писали:

M>>http://thedeemon.livejournal.com/1569.html

WH>О том что тоже самое можно проделать с программой на С++ автор умалчивает...

Какой ценой? В C++ даже замыканий нет, я уж не говорю про продолжения.

Можно то оно и на ассемблере можно. Но во временных рамках ICFPC точно нельзя. Да и в любом реальном проекте не рекомендуется, такой код поддерживать будет просто нереально.
Re[2]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: Mamut Швеция http://dmitriid.com
Дата: 07.07.09 10:44
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Mamut, Вы писали:


M>>http://thedeemon.livejournal.com/1569.html

WH>О том что тоже самое можно проделать с программой на С++ автор умалчивает...

Я для этого отдельную ветку в КСВ сделал http://rsdn.ru/forum/flame.comp/3458672.aspx


dmitriid.comGitHubLinkedIn
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: WolfHound  
Дата: 07.07.09 11:04
Оценка: +1
Здравствуйте, Аноним, Вы писали:

А> Какой ценой?

В данном случае весьма не большой.

А>В C++ даже замыканий нет, я уж не говорю про продолжения.

Но есть указатели на функции и виртуальные функции на выбор.

А> Можно то оно и на ассемблере можно. Но во временных рамках ICFPC точно нельзя. Да и в любом реальном проекте не рекомендуется, такой код поддерживать будет просто нереально.

Писать лень(да и компилятора С++ под рукой нет). Но кода там будет не многим больше.
Короче не надо ужасов там где их нет.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: WolfHound  
Дата: 07.07.09 11:06
Оценка:
Здравствуйте, Mamut, Вы писали:

M>Я для этого отдельную ветку в КСВ сделал http://rsdn.ru/forum/flame.comp/3458672.aspx

Не надо кросспостить.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 07.07.09 11:17
Оценка:
Здравствуйте, Mamut, Вы писали:

M>http://thedeemon.livejournal.com/1569.html

M>via http://lionet.livejournal.com/36771.html

В этом разделе rsdn уже была ссылка — в теме про ICFPC. Не стоит столько постов плодить.
Re[4]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 07.07.09 11:20
Оценка:
Здравствуйте, WolfHound, Вы писали:

А>>В C++ даже замыканий нет, я уж не говорю про продолжения.

WH>Но есть указатели на функции и виртуальные функции на выбор.

На Окамле там создается цепочка из замыканий, причем все вызовы хвостовые и превращаются в jmp.
Интересно было бы увидеть, как это можно сделать на С++. Но даже если можно, не уверен, что получится хорошая скорость.
Re[4]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: Qbit86 Кипр
Дата: 07.07.09 11:24
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Писать лень(да и компилятора С++ под рукой нет). Но кода там будет не многим больше.

WH>Короче не надо ужасов там где их нет.

Написать свой аллокатор взамен malloc/new — «немногим больше»? Если я не перепутал блогпост, то там в обсуждении говорилось, что сливает именно стандартный плюсовый менеджер памяти. А в OCaml'е там GC, выделения памяти очень быстрые.
Глаза у меня добрые, но рубашка — смирительная!
Re[5]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 07.07.09 11:25
Оценка:
Здравствуйте, 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 Беларусь http://eao197.blogspot.com
Дата: 07.07.09 12:04
Оценка:
Здравствуйте, D. Mon, Вы писали:

M>>http://thedeemon.livejournal.com/1569.html

M>>via http://lionet.livejournal.com/36771.html

DM>В этом разделе rsdn уже была ссылка — в теме про ICFPC. Не стоит столько постов плодить.


А доступен ли где-нибудь C++ный бенчмарк и тестовая программка для этой ВМ? Чтобы можно было скачать и поэкспериментировать


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 07.07.09 12:55
Оценка:
Здравствуйте, eao197, Вы писали:

E>А доступен ли где-нибудь C++ный бенчмарк и тестовая программка для этой ВМ? Чтобы можно было скачать и поэкспериментировать


http://thedeemon.livejournal.com/1569.html?thread=2849#t2849
Re[2]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 07.07.09 14:31
Оценка: +1
Здравствуйте, WolfHound, Вы писали:

WH>О том что тоже самое можно проделать с программой на С++ автор умалчивает...


Уже не умалчивает:
http://thedeemon.livejournal.com/1859.html
В общем, закат солнца вручную возможен и приносит свои плоды, но приходится написать много нудного кода. На одинаковых алгоритмах С++ все же быстрее, у него оптимизатор лучше.
Re[3]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: R.K. Украина  
Дата: 08.07.09 12:28
Оценка:
Здравствуйте, 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, r2

  void 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 и ускорение интерпретатора
От: dmz Россия  
Дата: 09.07.09 05:25
Оценка: 6 (2) +2
M>>>http://thedeemon.livejournal.com/1569.html
WH>>О том что тоже самое можно проделать с программой на С++ автор умалчивает...

А> Какой ценой? В C++ даже замыканий нет, я уж не говорю про продолжения.


А> Можно то оно и на ассемблере можно. Но во временных рамках ICFPC точно нельзя. Да и в любом реальном проекте не рекомендуется, такой код поддерживать будет просто нереально.


Ну вообще говоря, это преувеличения. Для реализации подобной задачи замыкания особенно и ни к чему, да и классы
с виртуальными функциями тоже. Код VM — примитивен, никаких проблем с поддержкой в принципе быть не может.

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

Но, в общем, смысл мерять окамл и вообще высокоуровневые языки на задачах, которые должны работать как можно ближе к железу?
Ценность окамла для данной задачи в том, что vm делается за пять минут, и работает сразу, без затрат времени на вылавливание
ошибок. Потому что мало кода и программа заведомо корректна с точки зрения типов, и ничего никуда не упадет.

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

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

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

И, кстати, могу заметить, что C++ для данной задачи только помеха — все вот эти реализации паттерна Command с виртуальной функцией и кучей классов — только раздувают код, не принося ничего полезного по сути.
Re[4]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: BulatZiganshin  
Дата: 09.07.09 19:37
Оценка:
Здравствуйте, dmz, Вы писали:

dmz>Наиболее ресурсоемкая операция — вовсе не переход, а декодирование опкода. Соответственно, если выполнить декодирование один раз,

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

это называется шитый код. а если его ещё синлайнить — то получится быстрее чем вручную написанная асмовская программа
Люди, я люблю вас! Будьте бдительны!!!
Re[5]: C++ vs Ocaml. ICFPC'09 и ускорение интерпретатора
От: dmz Россия  
Дата: 10.07.09 01:54
Оценка:
BZ>это называется шитый код. а если его ещё синлайнить — то получится быстрее чем вручную написанная асмовская программа

Их там целое семейство шитых кодов. Этот у наc token-threaded. Под инлайнингом понимается замена опкода непосредственно на код, его выполняющий (приведение к direct threaded code) ? Это соответственно и плохо скажется на плотности кода, а один из смыслов использования интерпретаторов — это получение более плотного кода, нежели нативный, что бы впихнуть больше функций в устройства с сильно ограниченной памятью.

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