LINUX.ORG.RU

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

 , , ,


2

0

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

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

Ответ на: комментарий от lester

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

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

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

Absurd ★★★
()
Ответ на: комментарий от anonymous_incognito

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

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

matumba ★★★★★
()
Ответ на: комментарий от matumba

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

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

lester ★★★★
()
Ответ на: комментарий от lester

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

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

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

Absurd ★★★
()
Ответ на: комментарий от Absurd

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

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

lester ★★★★
()
Ответ на: комментарий от lester

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

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

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

Absurd ★★★
()
Ответ на: комментарий от Absurd

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

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

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


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

lester ★★★★
()
Ответ на: комментарий от constRS

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

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

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


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

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


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

mv ★★★★★
()
Ответ на: комментарий от mv

> фич в нём крайне мало

и чем эти фичи помогли в данном случае?

lester ★★★★
()
Ответ на: комментарий от lester

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

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

mv ★★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от lester

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

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

mv ★★★★★
()
Ответ на: комментарий от anonymous_incognito

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

Читать мыщьха до посинения.

devl547 ★★★★★
()
Ответ на: комментарий от lester

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

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

mv ★★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от lester

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

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

Absurd ★★★
()
Ответ на: комментарий от Absurd

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

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

lester ★★★★
()
Ответ на: комментарий от lester

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

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

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

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

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

mv ★★★★★
()
Ответ на: комментарий от mv

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

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

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


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

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


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

lester ★★★★
()
Ответ на: комментарий от mv

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

очень интересно - чего же? предыдущие пункты однозначно сливают

lester ★★★★
()
Ответ на: комментарий от mv

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

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

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от mv

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

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

eao197 ★★★★★
()
Ответ на: комментарий от anonymous_incognito

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


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

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

yeolahim
()
Ответ на: комментарий от eao197

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

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

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от mv

> Поддержка 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 ★★★★★
()
Ответ на: комментарий от tailgunner

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

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

mv ★★★★★
()
Ответ на: комментарий от tailgunner

> Не-а. Смотри какой-нибудь 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 ★★★★★
()
Ответ на: комментарий от eao197

> 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 ★★★★★
()
Ответ на: комментарий от www_linux_org_ru

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

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

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


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

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


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

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


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

> подробнее


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

mv ★★★★★
()
Ответ на: комментарий от mv

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от mv

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

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

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от mv

> gccxml не шевелится. И это не язык.

И не должен. Там уже все есть что надо для рефлексии.

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от tailgunner

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

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

mv ★★★★★
()
Ответ на: комментарий от www_linux_org_ru

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

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

mv ★★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от lester

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

*краснеет*

mv ★★★★★
()
Ответ на: комментарий от tailgunner

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

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

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

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

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

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

О том и речь.

eao197 ★★★★★
()
Ответ на: комментарий от lester

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

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

mv ★★★★★
()
Ответ на: комментарий от lester

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

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

mv ★★★★★
()
Ответ на: комментарий от eao197

>> Нет, это 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 ★★★★★
()
Ответ на: комментарий от lester

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

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

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

Absurd ★★★
()
Ответ на: комментарий от mv

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

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

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

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

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от mv

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

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

lester ★★★★
()
Ответ на: комментарий от Absurd

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

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

lester ★★★★
()
Ответ на: комментарий от tailgunner

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

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

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

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

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