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

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

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

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

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

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

в толксы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> тогда хоть заголовок исправьте

Исправил.

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

причем я 100% уверен, что этого хватит, чтоб уделать Ocaml

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

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

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

тут выложил аргументацию:
http://www.linux.org.ru/view-message.jsp?msgid=3853085&nocache=-1559135412

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

+1.

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

Да...

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 (собственно говоря, это настолько известная штука, что её даже нигде явно не описывают).

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

> 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;
        ...
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://thedeemon.livejournal.com/1859.html?view=13891#t13891

внизу

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

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

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

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

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

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

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

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

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

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

Действительно: MSVC 6.0, Release. Печально.

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

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

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

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

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

> Почетал

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

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

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

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

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

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

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

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

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

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

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

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

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

И как же тогда называется чудовище о 2-х ногах? :-)

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

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

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

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

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

reserve же

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

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

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

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