LINUX.ORG.RU

Как оптимизировали программу на Ocaml

 , , ,


2

0

По ссылке приведены примеры программ с соревнований на ICFPC'09 (кстати, самим по себе интересными тем, что участники соревновались в управлении космическими аппаратами) которые демонстрируют как оптимизационные возможности, свойственные функциональным языкам (в частности хвостовая рекурсия), позволяют написанной на нём программе-интерпретатору некоего языка управления двигателем космического аппарата обогнать по скорости работы аналогичную на C/C++.

>>> Подробности

Re: Как Ocaml обогнал по скорости C++

Ладно, старый тролль Karapuz написал бы такой заголовок, но модер... %)

tailgunner ★★★★★ ()

Re: Как Ocaml обогнал по скорости C++

баян, насчет "обогнал" - бред, взяли два варианта( с++ был быстрее ), после чего начали оптимизировать только второй( Ocaml ), такие "обгоны" можно для любых языков написать

lester ★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от lester

Re: Как Ocaml обогнал по скорости C++

Там фишка в том, что C++-ный вариант так просто не пооптимизируешь. То есть на такой коротком примере и можно, конечно, но на маломальски сложном проекте код превратится во что-то слишком сложное, в то время как для Ocaml'а оптимизация оказывается более естественной.

anonymous_incognito ★★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от anonymous_incognito

Re: Как Ocaml обогнал по скорости C++

> То есть на такой коротком примере и можно, конечно, но на маломальски сложном проекте код превратится во что-то слишком сложное

начали одним, а теперь утверждаем второе - не менее безосновательное

lester ★★★★ ()

Re: Как Ocaml обогнал по скорости C++

в толксы.

volh ★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от anonymous_incognito

Re: Как Ocaml обогнал по скорости C++

> C++-ный вариант

Ну пеар ч0рный же, нет там никакого Си++. Голый Си.

> так просто не пооптимизируешь

Ну как минимум надо было бы сообщить версию компилятора, и попробовать (непереносимые) computed goto.

> То есть на такой коротком примере и можно, конечно, но на маломальски сложном проекте код превратится во что-то слишком сложное

А для Окамля это типа не справедливо? %) И судя по описанию, 3-й вариант Окамля вообще ничего общего не имел с 1-м. А Си-интерпретатор вообще не пытались ускорить.

tailgunner ★★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от lester

Re: Как Ocaml обогнал по скорости C++

> начали одним, а теперь утверждаем второе - не менее безосновательное

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

anonymous_incognito ★★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от anonymous_incognito

Re: Как Ocaml обогнал по скорости C++

> Начал вообще-то автор заметки и смысл в том, что первоначально отстававший вариант на Ocaml легко сделали более быстрым.

разве это тоже самое, что и "Ocaml обогнал по скорости C++"?

> На мой вкус эта заметка иллюстрирует не столько конкретный случай, сколько подход, а этот подход у Ocaml выглядит весьма интересным в данном случае.


у С/C++ тоже масса вариантов для оптимизации - не менее интересных

> То есть у Ocaml оптимизация выглядит более что-ли высокоуровневой, чем возможная у C++.


уже писали - где там С++?

lester ★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от tailgunner

Re: Как Ocaml обогнал по скорости C++

> Ну пеар ч0рный же, нет там никакого Си++. Голый Си.

Кстати да. Просто автор назвал C++, а я как-то механически повёлся, тот код действительно Си-шный.

P.S. Первоначально я хотел это поместить в Talks. Потом в Development, потом мне показалось, что подобной темы давненько не было в новостях, а обсуждения Mono как-то подзапарили.

Но оставлю пока на усмотрение других модераторов куда это девать. Если ещё кому-то покажется, что можно в новости, давайте в новости.

anonymous_incognito ★★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от anonymous_incognito

Re: Как Ocaml обогнал по скорости C++

> Если ещё кому-то покажется, что можно в новости, давайте в новости.

тогда хоть заголовок исправьте, например "Как оптимизировать код на Ocaml, чтоб он обогнал по скорости неоптимизированный код на C для специфической задачи" ( ну или сокращенно как-то )

lester ★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от lester

Re: Как Ocaml обогнал по скорости C++

> у С/C++ тоже масса вариантов для оптимизации - не менее интересных

Я так понял там хвостовую рекурсию использовали за счёт представления тела цикла в виде последовательного вызова функций - это разве C/C++ может? А уж второй тип описанной оптимизации с генерацией кода в зависимости от исходных данных вообще за гранью. Хотя тоже можно завести таблицу, прописать всё ручками и сгенерировать массив указателей на функции, через который их и вызывать потом. Проблема в том, что поддерживать такой код сложно.

anonymous_incognito ★★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от anonymous_incognito

Re: Как Ocaml обогнал по скорости C++

предкомпиляцию то кто мешает сделать? уже тройной вложенности switch'и и битовые сдвиги уйдут

lester ★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от anonymous_incognito

Re: Как Ocaml обогнал по скорости C++

> и сгенерировать массив указателей на функции, через который их и вызывать потом

только у фанатов Ocaml при решении примитивной задачи рождаются такие сложные решения ;)

lester ★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от lester

Re: Как Ocaml обогнал по скорости C++

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

anonymous_incognito ★★★★★ ()

Re: Как оптимизировали программу на Ocaml

Автор сделал-таки закат солнца вручную и аналогичным образом оптимизировал плюсовый вариант. По скорости OCaml обогнали. Объём написанного - существенно больше:

http://thedeemon.livejournal.com/1859.html

Miguel ★★★★★ ()

Re: Как оптимизировали программу на Ocaml

> космического аппарата

Супер! Обязательно проверю сей код на своем iPhone.

Проверю, будет ли это работать быстрее чем arm darwin gcc 4.2.1.

Bioreactor ★★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от Miguel

Re: Как оптимизировали программу на Ocaml

> Автор сделал-таки закат солнца вручную и аналогичным образом оптимизировал плюсовый вариант. По скорости OCaml обогнали. Объём написанного - существенно больше:

очередной бред - обычная "расшифровка" как назвал это аффтар, позволяет вместо трех прыжков по switch и от 4 до 7 строк на итерацию оставить только один прыжок по switch и одну строку на итерацию, думаю очевидно какой это даст прирост, потому своим добавлением классов и "закатом солнца" он просто затормозил вариант на С( наверное, чтоб всем показать, что это таки С++, а также показать как можно неэффективно на нем писать )

lester ★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от Miguel

Re: Как оптимизировали программу на Ocaml

Я посмотрел вариант оптимизации, применённый для Ocaml и вариант, применённый для C++ и понял, что автор сознательно опускает плюсы. Сравнение субъективное настолько, насколько это возможно.

name_no ★★ ()

Re: Как оптимизировали программу на Ocaml

Чо за глупость

PETER ★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от lester

Re: Как Ocaml обогнал по скорости C++

> только у фанатов Ocaml при решении примитивной задачи рождаются такие сложные решения ;)

Нет, не только. Давеча видел такое на C++. :)

AlexM ★★★★★ ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от lester

Re: Как Ocaml обогнал по скорости C++

>баян, насчет "обогнал" - бред, взяли два варианта( с++ был быстрее ), после чего начали оптимизировать только второй( Ocaml ), такие "обгоны" можно для любых языков написать

Ну этот как в том анекдоте: "У него аж шланг заправочный из рук выпал". :)

Davidov ★★★★ ()

Re: Как оптимизировали программу на Ocaml

Назвал бы сразу "C/С++ говно, Ocaml решает, а теперь попробуйте опровергнуть, мудаки". К чему эти прелюдии.

mannaz ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от tailgunner

Re: Как Ocaml обогнал по скорости C++

> Ну как минимум надо было бы ...... попробовать (непереносимые) computed goto.

+1.

computed goto ИМХО классика для интерпретатора. И главное, выглядело бы все очень понятно.

www_linux_org_ru ★★★★★ ()

Re: Как оптимизировали программу на Ocaml

Да...

virtual void Execute() { vm.mem[ip] = vm.mem[r1]; next->Execute(); }

return new Sqrt(ip, sr1, dr2, nxt, vm);

Вообще-то на C++ писать нужно уметь. Это, кстати, основная беда языка C++ - высокий порог вхождения.

Первая программа была написана на С, вторая на С с классами. Крайне удивительно, что даже в таком диком виде вторая программа рвёт OCaml.

Во-первых, зачем-то используются виртуальные функции - т.е. вызов по указателю. Во-вторых, new, т.е. куча, которая в C++ "отсасывает у кого угодно" :-) - http://lj.rossia.org/users/kouzdra/664091.html?nc=66 (собственно говоря, это настолько известная штука, что её даже нигде явно не описывают).

К сведению, нормальный С++ для расчётов, это шаблоны.

constRS ()
Ответ на: Re: Как Ocaml обогнал по скорости C++ от www_linux_org_ru

Re: Как Ocaml обогнал по скорости C++

> computed goto ИМХО классика для интерпретатора. И главное, выглядело бы все очень понятно. 

просто использование той же оптимизации, что и для ocaml в первой "неоптимизированной" версии уже понятно и быстрее, и если б аффтар не поленился написать сразу два варианта одинаково - все последующие попытки( даже с вырезанием неиспользуемых блоков ) не смогли бы помочь обогнать С:

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

lester ★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от Miguel

Re: Как оптимизировали программу на Ocaml

> Автор сделал-таки закат солнца вручную и аналогичным образом оптимизировал плюсовый вариант. По скорости OCaml обогнали. Объём написанного - существенно больше

Тут смеяться или плакать?

1. идея записывать goto как функции с (обрезанной компилятором) хвостовой рекурсией вполне себе разумна

2. на с/с++ такие goto записываются как goto или switch, то что автор там понаписал ни в какие ворота не лезет

3. автор даже не попытался уменьшить объем кода в 2-3 раза через хотя бы #define

www_linux_org_ru ★★★★★ ()

Re: Как оптимизировали программу на Ocaml

Ха - он компилировал VC6 с дефолтными параметрами оптимизации

lester ★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от constRS

Re: Как оптимизировали программу на Ocaml

> Вообще-то на C++ писать нужно уметь. Это, кстати, основная беда языка C++ - высокий порог вхождения.

Вообще-то, на одной ноге нужно уметь ходить. Это, кстати, основная беда хождения на одной ноге - высокий порог вхождения (нужно отрубить одну ногу).

> Первая программа была написана на С, вторая на С с классами. Крайне удивительно, что даже в таком диком виде вторая программа рвёт OCaml.


Я Окамл особо не знаю и не люблю (Лисп - наше всё), C++ знаю достаточно хорошо, но вот при чтении референса на Окамл, практически, первое, что пришло в голову - Окамл хорошая замена ужасным плюсам.

Первой мыслью было, конечно: "таки Коммон Лисп побогаче будет...".

> К сведению, нормальный С++ для расчётов, это шаблоны.


Упасибохх на плюсах что-то считать.

mv ★★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от lester

Re: Как оптимизировали программу на Ocaml

> Ха - он компилировал VC6 с дефолтными параметрами оптимизации

Ссылку можно? А вообще, можно было ещё на интерпретаторе CINT запустить :-).

constRS ()

Re: Как оптимизировали программу на Ocaml

Автор наверное хотел показать, что он знает Ocaml но плавает в C (его творение на C++ просто пример того как ненадо писать программы). Получилось очень убедительно.

A-234 ★★★★★ ()

Re: Как оптимизировали программу на Ocaml

Сходил по ссылке, сразу споткнулся на

> программу не большей длины


это нынче так технари на русская языка пишут?

xintrea ()

Re: Как оптимизировали программу на Ocaml

> Вообще-то, на одной ноге нужно уметь ходить.

К чему такой тупой сарказм? Я понимаю, сказал бы про 3-4 ноги (всё-таки С++ слишком большой, а не урезанный), было бы смешно.

> Окамл хорошая замена ужасным плюсам.

Для каких-то задач - да. Для каких-то нет. Если чуточку задуматься, это очевидно (конечно, если из школьного возраста вышел).

> Упасибохх на плюсах что-то считать.

Жизнь заставит, и не так раскорячишься. :-)

constRS ()

Re: Как оптимизировали программу на Ocaml

про то, что вы не любите С++, мы давно знаем, не стоит трудится и рассказывать об этом всем и везде( даже там где обсуждается пример на С )

lester ★★★★ ()

Re: Как оптимизировали программу на Ocaml

Почетал статью и не понял, что мешало сделать эти же две оптимизации в C-шной реализации??

xintrea ()
Ответ на: Re: Как оптимизировали программу на Ocaml от constRS

Re: Как оптимизировали программу на Ocaml

>> Вообще-то, на одной ноге нужно уметь ходить.

>Я понимаю, сказал бы про 3-4 ноги (всё-таки С++ слишком большой, а не урезанный), было бы смешно.

Скорее одна нога с двумя-тремя коленями. Честная одна нога это Си.

Absurd ★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от xintrea

Re: Как оптимизировали программу на Ocaml

> Почетал

это нынче так технари на русская языка пишут? (c) ;)

> что мешало сделать эти же две оптимизации в C-шной реализации??


я уже писал - самая ключевая оптимизация была уже в первом варианте на Ocaml, а в С ее нет, и автор признал это

lester ★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от lester

Re: Как оптимизировали программу на Ocaml

>про то, что вы не любите С++, мы давно знаем,

А мы знаем что вы его любитель.

>даже там где обсуждается пример на С

Пример на Си кстати неплох, если компилятор балансирует switch конечно.

Absurd ★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от Absurd

Re: Как оптимизировали программу на Ocaml

> А мы знаем что вы его любитель.

но я пишу по теме, в отличие от

> Пример на Си кстати неплох, если компилятор балансирует switch конечно.


вы сможете написать хуже?

lester ★★★★ ()

Re: Как оптимизировали программу на Ocaml

> при чтении референса на Окамл, практически, первое, что пришло в голову
- Окамл хорошая замена ужасным плюсам.

тогда прочитайте мнение автора - "Верно. Еще избавиться от case и break, и получится почти Окамл. :)", и подумайте - может не стоит искать замену? ;)

lester ★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от constRS

Re: Как оптимизировали программу на Ocaml

> Во-вторых, new, т.е. куча, которая в C++ "отсасывает у кого угодно" :-) - http://lj.rossia.org/users/kouzdra/664091.html?nc=66

Скорее, там приведен тест, в котором код записан неопимально, и JIT таки смог увидеть эту неоптимальность и оптимизировать, в то время как компилятор плюсов не будет такое делать.

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

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

www_linux_org_ru ★★★★★ ()
Ответ на: Re: Как оптимизировали программу на Ocaml от www_linux_org_ru

Re: Как оптимизировали программу на Ocaml

Там, если вы посмотрите, умный человек заранее говорит, что тестирует new/delete. Т.е. этот тест синтетический.

В С++ вообще нельзя ставить new/delete во внутренние циклы. Что kouzdra и показывает. Поэтому переаллокации в std::vector и std::string ему до лампочки.

constRS ()
Ответ на: Re: Как оптимизировали программу на Ocaml от www_linux_org_ru

Re: Как оптимизировали программу на Ocaml

> Кучей в плюсах надо пользоваться через кастомные аллокаторы, типа "аллоцируем много, ничего не освобождаем, потом освобождаем весь пул". При этом компилятор нам не помощник в определении того, не ошиблись ли мы -- это уже явная недоработка языка.

это если не писать многопотоковое приложение, в противном случае никакого выигрыша не будет - мутексы все съедят

lester ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.