LINUX.ORG.RU

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

 , , ,


2

0

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

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

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

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

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

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

С массивом указателей на функции было бы конечно красивее, но тогда мы имели бы вызов процедуры на каждую VM-инструкцию. А так log2(количество инструкций) джампов на каждую итерацию.

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

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

Вариант оптимизации Си там уже упоминался: созданием "декомпилированного" чистого Си-кода под каждую входную программу. Это уж точно на максимуме быстродействия - окамл там рядом не стоял.

Но мне окамл больше нравится, т.к. не скоростью единой...

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

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

> Но мне окамл больше нравится, т.к. не скоростью единой...

по ссылке автор средствами Ocaml решал недостатки Ocaml же( что из этого получилось - по ссылке ), что же вам такого понравилось в Ocaml?

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

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

>> Но мне окамл больше нравится, т.к. не скоростью единой...

>по ссылке автор средствами Ocaml решал недостатки Ocaml же( что из этого получилось - по ссылке ),

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

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

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

> Нету там такого, он организовал программу иначе используя примитивы которых в С++ нет

потому что тот вариант, который изначально на С работает c максимальной скоростью( "расшифровка" ), а также очень прост и читабелен, на Ocaml не эффективен, потому и приходится использовать "примитивы которых в С++ нет", которые позволяют частично устранить недостаток эффективности и окончательно запутать и усложнить код, ну и где тут хоть один плюс от этих супер фишек, которых нет в С и С++?

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

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

>> С массивом указателей на функции было бы конечно красивее

>значит сможете, я в вас верил

Там есть два варианта диспатчинга - O(1) с большим констатнтным множителем и O(Log(N)) с маленьким констатнтным множителем. Первое делается через массив указателей на функции, второе через switch. Так что не трахай мне мозг - пример на Си написан хорошо. И вообще, умный программист тупым кодом решает сложные проблемы а не наоборот.

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

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

> Так что не трахай мне мозг - пример на Си написан хорошо

а я об чем, это вы начинаете выдумывать странные неэффективные решения

> умный программист тупым кодом решает сложные проблемы


там где надо скорость такое не катит

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

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

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

С++ слишком флудливый и неудобный язык, фич в нём крайне мало. Если не верите, почитайте какой-нибудь brief overview of Common Lisp, Haskell, да того же OCaml.

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


Для задач (кроме legacy), к которым плюсы ещё подходят - OCaml почти всегда будет заменой. Для задач, к которым плюсы никогда и не подходили - OCaml может быть заменой, а может и не быть.

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


Выход всегда есть :)

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

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

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

Скажем так, я его люблю умеренно (и обязательно с бустом). Например, пишу сетевые сервера на asio, но чисто потому, что не знаю Эрланга :)

mv ★★★★★ ()

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

> Скажем так, я его люблю умеренно

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

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

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

> кстати вы явно не смотрели финальный вариант( напоминаю - он не полный )

Я вообще не люблю сравнения A толще B. Иногда, конечно, приходится защищаться от толстых и зелёных, но, в целом, всё равно не люблю. Обычно оказывается, что факты притянуты за уши, что голый Си всегда быстрее, пока не вылезет знаток ассемблера и ненавистник компиляторов. Зато когда начинаешь писать большую программу, да ещё и подходящую под парадигму языка, то оказывается, что чем больше абстракций предоставляет язык, тем лучше.

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

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

> вы просто не умеете его готовить

Я *не хочу* уметь готовить плюсы. В жизни есть более насущные проблемы, чем оттачивание мастерства делать всё через жопу.

mv ★★★★★ ()

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

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

чего вам жизненно не хватает в С++? и приведите плз пример реального практического применения этих фишек

lester ★★★★ ()

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

> В жизни есть более насущные проблемы, чем оттачивание мастерства делать всё через жопу.

и это говорит лиспер? :)

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

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

>чего вам жизненно не хватает в С++?

Ну к примеру в оптимизированном примере на OcaML были использованы континуации. Я конечно знаю как это можно сделать на ++, например через Loki::Functor, Loki::BindFirst и Loki::Chain, но не факт что это будет быстрее родных континуаций.

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

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

> Ну к примеру в оптимизированном примере на OcaML были использованы континуации. Я конечно знаю как это можно сделать на ++, например через Loki::Functor, Loki::BindFirst и Loki::Chain, но не факт что это будет быстрее родных континуаций.

я спросил чего не хватает ;)

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

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

> чего вам жизненно не хватает в С++? и приведите плз пример реального практического применения этих фишек

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

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

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

Много ещё чего.

mv ★★★★★ ()

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

> Поддержка bignum и натуральных дробей. Поддержка языком, а не анально каким-нибудь libgmp

маразм - все в язык вместить нельзя, а то что вы хотите - рядовая задача, которая просто обязана реализоваться отдельной библиотекой, вы еще скажите, что вам средств создания gui встроенных не хватает

> Метаобъектного протокола и интроспекции не хватает. Хочу вот отладить бажный код и вставить до и после вызова каждого метода у определённого класса вывод отладочной информации. Для этого нужно обойти в рантайме все эти методы и перехватить их диспетчеризацию.


для этого давно придумали профайлеры - мне смешно, что вы руками это делаете

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


посмотрите в сторону VC и будем вам счастье

lester ★★★★ ()

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

> Поддержка bignum и натуральных дробей. Поддержка языком, а не анально каким-нибудь libgmp

Ну и чем класс отличался бы от "встроенной поддержки"? Да ничем.

> Нет инкрементальной компиляции.

Это недостаток gcc, а не Си++.

tailgunner ★★★★★ ()

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

> Для задач (кроме legacy), к которым плюсы ещё подходят - OCaml почти всегда будет заменой.

Это если задача игрушечная и ее решение должно работать только на одном конкретном Unix-е.

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

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

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


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

и вообще не понятно, причем тут плюсы.

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

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

> Это если задача игрушечная

Не-а. Смотри какой-нибудь CCured или Ivy - вполне настоящие задачи.

> и ее решение должно работать только на одном конкретном Unix-е.

Да на любом распространенном.

tailgunner ★★★★★ ()

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

> Поддержка bignum и натуральных дробей. Поддержка языком, а не анально каким-нибудь libgmp.

чем тебе перегрузка операторов не "поддержка языком"? (конкретно)

> Метаобъектного протокола и интроспекции не хватает. Хочу вот отладить бажный код и вставить до и после вызова каждого метода у определённого класса вывод отладочной информации.

рефлексия: копать в сторону gccxml (он шаблоны разворачивает как надо) и либ на его основе, либо dwarf

отладка:

Generate instrumentation calls for entry and exit to functions. Just after function entry and just before function exit, the following profiling functions will be called with the address of the current function and its call site. (On some platforms, `__builtin_return_address' does not work beyond the current function, so the call site information may not be available to the profiling functions otherwise.)

void __cyg_profile_func_enter (void *this_fn, void *call_site);

void __cyg_profile_func_exit (void *this_fn, void *call_site);

The first argument is the address of the start of the current function, which may be looked up exactly in the symbol table.

This instrumentation is also done for functions expanded inline in other functions.

Полноценный МОП во время компиляции безусловно нужен.

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

Я привык жить без этого, но не сказал бы, что это не нужно.

> Много ещё чего.

подробнее

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

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

> Ну и чем класс отличался бы от "встроенной поддержки"? Да ничем.

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

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

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

> Не-а. Смотри какой-нибудь CCured или Ivy - вполне настоящие задачи.

CCured (http://caml.inria.fr/cgi-bin/hump.fr.cgi?contrib=88) -- врядли задача парсинга и анализа исходников изначально хорошо подходит для C++.

Ivy -- если это http://ant.apache.org/ivy/index.html , то он, кажись, на Java.

>> и ее решение должно работать только на одном конкретном Unix-е.

> Да на любом распространенном.

Ну т.е. дальше Linux/FreeBSD/Solaris и не уедешь.

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

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

> CCured (http://caml.inria.fr/cgi-bin/hump.fr.cgi?contrib=88) -- врядли задача парсинга и анализа исходников изначально хорошо подходит для C++.

Это ты согласился, что для некоторых реальных задач Си++ не подходит? ;)

> Ivy -- если это http://ant.apache.org/ivy/index.html , то он, кажись, на Java.

Нет, это http://ivy.cs.berkeley.edu/ivywiki/index.php/Main/HomePage

> Ну т.е. дальше Linux/FreeBSD/Solaris и не уедешь.

Ну это уже не "один конкретный Unix" (думаю, на макакос тоже есть Окамль). Но таки да, Си++ больше распространен.

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

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

> чем тебе перегрузка операторов не "поддержка языком"? (конкретно)

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

> рефлексия: копать в сторону gccxml (он шаблоны разворачивает как надо) и либ на его основе, либо dwarf


gccxml не шевелится. И это не язык. И профайлер не замена MOP, как в это свято lester верит (он просто про MOP ничего не знает :)

> void __cyg_profile_func_enter (void *this_fn, void *call_site);


И чего делать с плюсовыми методами, с разным mangling в разных компиляторах?

> Я привык жить без этого, но не сказал бы, что это не нужно.


Но, тем не менее, лучше быть здоровым и богатым, чем бедным и больным.

> подробнее


Гугль в помощь, всё повторяется в стотыщный раз.

mv ★★★★★ ()

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

> левый класс бигнум не знает, как, скажем, складываться с левым классом натуральной дроби.

Ну так напиши либу нормально. Желание, чтобы либу написали за тебя - разумное желание, но отсуствие нужной тебе либы не является недостатком языка.

tailgunner ★★★★★ ()

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

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

и как люди без этого живут :) реализация пишется на коленке( обычный "умный" контейнер ), если вы посмотрите набор библиотек для С/C++ - вам станет стыдно за lisp, что в нем столько всего нет

lester ★★★★ ()

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

> Гугль в помощь, всё повторяется в стотыщный раз.

да - лисперы в очередной раз убого сливают и доказывают, что их удел - писать прикладные программки для БД, и что, кроме как пыжится, доводов у них нет

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

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

> Ну так напиши либу нормально. Желание, чтобы либу написали за тебя - разумное желание, но отсуствие нужной тебе либы не является недостатком языка.

Если нужная мне фича входит в стандарт языка, реализована во всех имплементациях и интегрированна со всем остальным в языке, то это определённо killer feature по сравнению с другим языком, где этого ничего нет. Не зря же люди вообще ЯП изобретают? А то щёлкали бы себе тумблерами, не парились...

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

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

> И в чем проблема это написать?

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

mv ★★★★★ ()

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

> Если нужная мне фича входит в стандарт языка, реализована во всех имплементациях и интегрированна со всем остальным в языке, то это определённо killer feature по сравнению с другим языком, где этого ничего нет.

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

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

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

> если вы посмотрите набор библиотек для С/C++ - вам станет стыдно за lisp, что в нем столько всего нет

*краснеет*

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

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

> Это ты согласился, что для некоторых реальных задач Си++ не подходит? ;)

Я с этим уже лет 10, как минимум, не спорю. Тем не менее, оригинальное утверждение было о том, что почти для всего, для чего подходит C++, его может заменить OCaml. Что не есть правда.

CCured -- это задача, для которой C++ не сильно подходит вообще. Если только вопрос не станет о максимальном быстродействии под Windows ;)

> Нет, это http://ivy.cs.berkeley.edu/ivywiki/index.php/Main/HomePage

На первый взгляд это таки игрушечный проект just for fan.

> Ну это уже не "один конкретный Unix" (думаю, на макакос тоже есть Окамль). Но таки да, Си++ больше распространен.

О том и речь.

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

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

> да - лисперы в очередной раз убого сливают и доказывают, что их удел - писать прикладные программки для БД, и что, кроме как пыжится, доводов у них нет

Я не лиспер. Мой удел - Си и systemtap.

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

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

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

Вот ты сколько языков знаешь?

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

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

>> Нет, это http://ivy.cs.berkeley.edu/ivywiki/index.php/Main/HomePage

> На первый взгляд это таки игрушечный проект just for fan.

Это не ради вентилятора, это исследовательский проект :) http://ivy.cs.berkeley.edu/ivywiki/index.php/Main/Publications http://ivy.cs.berkeley.edu/ivywiki/index.php/Main/Projects http://sourceforge.net/projects/jekyllc

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

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

>> Ну к примеру в оптимизированном примере на OcaML были использованы континуации. Я конечно знаю как это можно сделать на ++, например через Loki::Functor, Loki::BindFirst и Loki::Chain, но не факт что это будет быстрее родных континуаций.

>я спросил чего не хватает ;)

Я и привел пример - континуации. Аналогом оптимизированного кода на Окамле для С++ было бы собрать цепочку из Loki::Chain.

Absurd ★★★ ()

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

> И чего делать с плюсовыми методами, с разным mangling в разных компиляторах? толсто

> Гугль в помощь, всё повторяется в стотыщный раз.

Давай определеннее.

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

www_linux_org_ru ★★★★★ ()

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

> Вот ты сколько языков знаешь?

много, причем очень разные - до С++ я много перепробовал( причем не просто смотрел - а использовал ), от asm( Z80 и x86 ) до С, basic, prolog, pascal, java, python etc., даже на FoxPro писал( в школе сначала был только он, а своего компьютера еще не было ) - т.к. интересно было

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

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

> Я и привел пример - континуации. Аналогом оптимизированного кода на Окамле для С++ было бы собрать цепочку из Loki::Chain.

то что в Ocaml надо такая оптимизация( только из-за скорости ), не значит, что в С++ это даст прирост скорости, более вероятно, что наоборот

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

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

> Это не ради вентилятора, это исследовательский проект :)

Ага, эксперименты для дилетантов должны проводиться в лабораториях для дилетантов ;)

Это я к тому, что исследователи могут писать свой проект на чем хотят и как хотят. А потом в любой момент выбросить. Но если бы им пришлось передать свой код на сопровождение в течении лет 10-15 обычным программистам, то спрос был бы другой.

Хоть у C++ читабельность далеко не самая лучшая, но все же (на мой взгляд) лучше, чем у OCaml. Поэтому за сопровождение чужого C++ного кода я бы еще взялся. А вот OCaml-овского -- только за очень большие деньги.

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