Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 16.09.09 17:20
Оценка: 67 (7)
Запостил в раздел C/C++ описание своей реализации задачи chameneos-redux на С для The Computer Language Benchmarks Game:
http://www.rsdn.ru/forum/cpp/3539197.1.aspx
Автор: remark
Дата: 16.09.09

Т.к. форума, посвященного многопоточности, на RSDN нет, а материал может быть интересен и разработчикам на Java, C# и др., то делаю анонс тут.

Дабы немного разжечь интерес:

На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды. Так же можно отметить: самая быстрая реализация на Java – 7 сек.; Scala – 15 сек.; Erlang – 111 сек.; Ruby — 131 сек.; Python — 221 сек.
Результат моей реализации — 0.72 секунды.



1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[15]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 13:46
Оценка: +7
Здравствуйте, thesz, Вы писали:

T>>>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.

CC>>Это вторая стандартная отмазка.

CC>>Да и в целом, не пристало сеньёру сказав "А" замять тему и таки не говорить "Б".

CC>>Тем более делов то: ткнуть носом нубов в те самые примитивы, которых недостаёт хаскель программе чтоб таки догнать сишный код remark-а.

T>Фиксирование зелёных нитей на процессорах есть. Во что я "ткнул носом нубов" в том сообщении FR.


Этого не достаточно. Все 4 аспекта, который я описал критичны. Если убрать хотя бы 1, то время выполнения увеличивается в разы.
Я думаю, что для Haskell просто не разумно гнаться "один-в-один" за С/С++, и показывать на наличие конкретных аналогичных возможностей. На Haskell это будет реализовывать просто до-другому, поэтому наличие аналогичной возможности не релевантно. Соотв. вопрос — какой производительности может достичь программа на Haskell реализованная "по-другому", по его законам, так сказать?


CC>>Ну или признать что их на самом деле попросту нет.


T>Да мне на это наплевать. Есть они, нет их. Для работы это неважно.

T>Это важно для раздутия чьей-то (моей, чьей-то ещё, неважно) пиписьки прямо здесь и прямо сейчас, и совершенно не имеет смысла в длительной перспективе.

Ну так об этом как раз и есть этот топик. Можно назвать это "переньем пиписьками", можно назвать соревнованием в реализации конкретной задачи.
Если тебе на это наплевать, то зачем и о чём ты тут вообще пишешь? Проходи мимо. Или говори по теме.



1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 11:09
Оценка: 1 (1) +4
Здравствуйте, thesz, Вы писали:

T>>>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.

CC>>Подтверди на практике.

T>Уже неоднократно, поэтому обратись к кому ещё.


T>Конкретно этот эксперимент мне неинтересен, поскольку у меня своих покрупней и повыгодней есть штуки три.


Не вопрос, тогда мы просто подождём с тем, что бы верить тебе на слово, до того момента, когда у тебя появится время.
А то так утверждение достаточно не очевидно по крайней мере для меня и для значительного числа Haskell программистов, которые на протяжении нескольких лет пытались максимально ускорить эту реализацию:
http://www.haskell.org/pipermail/haskell-cafe/2006-January/013745.html


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[13]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 12:47
Оценка: 1 (1) +4
Здравствуйте, thesz, Вы писали:

T>>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.

FR>>Угу вполне стандартная отмазка

T>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.


Не вопрос, никто и не говорит, что тебе делать. Просто пока всё, что ты сказал несёт практически нулевую информацию, и складывается впечатление, что интересно тебе переливание из пустого в порожнее. Я тоже могу сказать, что у меня есть программа, которая в 1000 раз быстрее всех ваших, но больше ничего говорить и показывать не буду. Смысл? Это уже попахивает троллингом в техническом форуме. Да, полезное общение в форуме требует времени, это надо понимать, и ИМО сообщать либо хоть какую-то информацию, либо не говорить ничего. Уже мог бы за это время лучше набросать программу (благо там всего-то 65 строчек в программе на Haskell, некоторую часть можно прям оттуда и скопи-пастить), и запостить здесь, а я могу её туда засабмитить (с твоим именем естественно). Делов-то? Тем более, я так понимаю, что для тебя это достаточно тривиальная задача.


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[17]: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 15:53
Оценка: 1 (1) +4
Здравствуйте, thesz, Вы писали:

R>>Если ты говоришь, о том, что можно сделать эффективную реализацию на Haskell, образно выражаясь, "скопировав" реализацию на С, то привязки потоков к ядрам не достаточно. Очень сильно не достаточно. Необходимы все 4 момента, которые я описал, включая определение топологии системы. Отсутствие любого из них увеличит время выполнения в разы.


T>У тебя четыре пункта, отставание у Хаскеля в пять раз. Если каждый пункт обеспечивает ускорение в разы (в два раза), то твоя программа должна опережать Хаскельную в 16 раз. Чего мы не наблюдаем.


T>Поэтому я думаю, что из твоих четырёх пунктов только один или два являются значимыми, а остальные только на подхвате.


А что тут думать то? Все выкладки он разжевал. Тебе остается только изучить его код и его описание и реализовать с их учетом оптимизировать хаскелевскую программу. Результат будет говорить сам за себя.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Хамелеоны быстрые и очень быстрые
От: FR  
Дата: 17.09.09 14:50
Оценка: :))) :))
Здравствуйте, remark, Вы писали:

R>Дабы немного разжечь интерес:

R>

R>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды. Так же можно отметить: самая быстрая реализация на Java – 7 сек.; Scala – 15 сек.; Erlang – 111 сек.; Ruby — 131 сек.; Python — 221 сек.
R>Результат моей реализации — 0.72 секунды.


Ну нельзя же так, взял и всю малину Хаскелистам обломал
Re[2]: Хамелеоны быстрые и очень быстрые
От: hexamino http://hexamino.blogspot.com/
Дата: 17.09.09 15:10
Оценка: :)))
Здравствуйте, FR, Вы писали:

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


R>>Дабы немного разжечь интерес:

R>>

R>>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды.


FR>Ну нельзя же так, взял и всю малину Хаскелистам обломал


Небось, в хасекле ленивые хамелеоны никуда не ходят, а сразу вычисляют цвет, который они будут иметь в конце.
Re: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 14:48
Оценка: +3
Здравствуйте, remark, Вы писали:

R>Дабы немного разжечь интерес:...

R>

Ты не хочешь все это дело оформить соответствующим образом, доработать чтобы материал был более развернутым и понятным, добавить туда результаты и т.п. и прислать нам для размещения в качестве статьи?

А то ведь через некоторое время тема уйдет вниз и все про нее забудут.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 15:36
Оценка: -3
Здравствуйте, remark, Вы писали:

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


T>>>>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.

CC>>>Это вторая стандартная отмазка.

CC>>>Да и в целом, не пристало сеньёру сказав "А" замять тему и таки не говорить "Б".

CC>>>Тем более делов то: ткнуть носом нубов в те самые примитивы, которых недостаёт хаскель программе чтоб таки догнать сишный код remark-а.

T>>Фиксирование зелёных нитей на процессорах есть. Во что я "ткнул носом нубов" в том сообщении FR.

R>Этого не достаточно. Все 4 аспекта, который я описал критичны. Если убрать хотя бы 1, то время выполнения увеличивается в разы.

Понятно.

Но неинтересно.

R>Я думаю, что для Haskell просто не разумно гнаться "один-в-один" за С/С++, и показывать на наличие конкретных аналогичных возможностей. На Haskell это будет реализовывать просто до-другому, поэтому наличие аналогичной возможности не релевантно. Соотв. вопрос — какой производительности может достичь программа на Haskell реализованная "по-другому", по его законам, так сказать?


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

CC>>>Ну или признать что их на самом деле попросту нет.

T>>Да мне на это наплевать. Есть они, нет их. Для работы это неважно.
T>>Это важно для раздутия чьей-то (моей, чьей-то ещё, неважно) пиписьки прямо здесь и прямо сейчас, и совершенно не имеет смысла в длительной перспективе.
R>Ну так об этом как раз и есть этот топик. Можно назвать это "переньем пиписьками", можно назвать соревнованием в реализации конкретной задачи.
R>Если тебе на это наплевать, то зачем и о чём ты тут вообще пишешь? Проходи мимо. Или говори по теме.

И вот зачем ты это сказал?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[5]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 22.09.09 13:44
Оценка: +2
Здравствуйте, thesz, Вы писали:

FR>>>>Ну нельзя же так, взял и всю малину Хаскелистам обломал


T>>>http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#8


T>>>Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.


FR>>Это совсем другое, там просто нет примитивов необходимых чтобы догнать си.


T>Да что ты говоришь!


Было бы интересно увидеть практическое подкрепление этим словам.


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[10]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 10:43
Оценка: :))
Здравствуйте, FR, Вы писали:

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


T>>Параллелизм в этой задаче всё же есть (время выполнения миллиард тактов, не меньше), но он очень мелкий, поэтому избавившись от расходов на межпроцессный обмен мы получаем ускорение.


T>>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.

FR>Так давай делай раз все что нужно есть.
FR>Если империя нанесет ответный удар будет хорошая реклама для Хаскеля.

Я бы предпочёл, чтобы этим занялся ты.

Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[16]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 15:49
Оценка: -1 :)
Здравствуйте, remark, Вы писали:

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


T>>>>>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.

FR>>>>>Угу вполне стандартная отмазка

T>>>>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.


R>>>Не вопрос, никто и не говорит, что тебе делать.


T>>И завершил тираду, сказав, что мне надо делать.

R>Ну хорошо, да, я говорю/призываю людей высказываться по существу и аргументированно. Мне кажется, это вполне разумно.

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

Это нормально.

R>>>Просто пока всё, что ты сказал несёт практически нулевую информацию, и складывается впечатление, что интересно тебе переливание из пустого в порожнее. Я тоже могу сказать, что у меня есть программа, которая в 1000 раз быстрее всех ваших, но больше ничего говорить и показывать не буду. Смысл? Это уже попахивает троллингом в техническом форуме. Да, полезное общение в форуме требует времени, это надо понимать, и ИМО сообщать либо хоть какую-то информацию, либо не говорить ничего. Уже мог бы за это время лучше набросать программу (благо там всего-то 65 строчек в программе на Haskell, некоторую часть можно прям оттуда и скопи-пастить), и запостить здесь, а я могу её туда засабмитить (с твоим именем естественно). Делов-то? Тем более, я так понимаю, что для тебя это достаточно тривиальная задача.


T>>Э, нет.

T>>Я FR показал, что есть примитивы фиксации нитей на процессорах, пусть он теперь ваяет, если захочет.
T>>Или пусть это дело ваяешь ты.
T>>Иными словами, те люди, которым интересна производительность языков программирования.
T>>Если нет желания, то я не против.
R>Если ты говоришь, о том, что можно сделать эффективную реализацию на Haskell, образно выражаясь, "скопировав" реализацию на С, то привязки потоков к ядрам не достаточно. Очень сильно не достаточно. Необходимы все 4 момента, которые я описал, включая определение топологии системы. Отсутствие любого из них увеличит время выполнения в разы.

У тебя четыре пункта, отставание у Хаскеля в пять раз. Если каждый пункт обеспечивает ускорение в разы (в два раза), то твоя программа должна опережать Хаскельную в 16 раз. Чего мы не наблюдаем.

Поэтому я думаю, что из твоих четырёх пунктов только один или два являются значимыми, а остальные только на подхвате.

Какие из них какие, меня мало волнует. В любом случае я смогу обеспечить выполнение любого пункта из перечисленных тобой.

А в реальной жизни так я вообще возьму C. Или сгенерю его.

R>Так что пока что мы ничего не имеем с твоей стороны.

R>А то, что есть возможность привязки потоком в процессорам, это и так было ясно, потому что бывшая самая быстрая реализация на Haskell как раз и использует forkOnIO, и за счёт этого и была относительно быстрой.
R>Так что вот эти 4.5 секунд как раз и есть предел с использованием forkOnIO.

Ура!
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 15:57
Оценка: +2
Здравствуйте, thesz, Вы писали:

T>Последний из них http://thesz.mskhug.ru/svn/hhdl и он же самый интересный. Это не шутаут, это много прикольней. Это то, чего C++ никогда не сможет.


Что он не сможет то?

С++ не может только одного. Позволить написать большой объем кода без ошибок. Все остальное он позволяет. Всегда можно скатиться на уровень Си и писать практически на высокоуровневом ассемблере используя все преимущества железа.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[18]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 24.09.09 09:16
Оценка: -2
Здравствуйте, remark, Вы писали:

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


R>>>Если ты говоришь, о том, что можно сделать эффективную реализацию на Haskell, образно выражаясь, "скопировав" реализацию на С, то привязки потоков к ядрам не достаточно. Очень сильно не достаточно. Необходимы все 4 момента, которые я описал, включая определение топологии системы. Отсутствие любого из них увеличит время выполнения в разы.


T>>У тебя четыре пункта, отставание у Хаскеля в пять раз. Если каждый пункт обеспечивает ускорение в разы (в два раза), то твоя программа должна опережать Хаскельную в 16 раз. Чего мы не наблюдаем.


R>Зависимость не линейная.


Иными словами, ты сам толком не знаешь, что же в твоём подходе самое важное.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[17]: Хамелеоны быстрые и очень быстрые
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 24.09.09 13:16
Оценка: +2
Здравствуйте, WolfHound, Вы писали:

WH>Пожалуйста перелови все переполнения буфера в линуксе.

WH>Да и мне нужно строгое доказательство что их там не осталось.
WH>И это весьма примитивные ошибки...

Гы. Аргументы пошли сильные.
Пожалуйста, перепиши Линукс на языке, который не допустит ни одного переполнения буфера.
Флейм это всё, флейм.
Re[3]: Легковесные потоки
От: Mr.Cat  
Дата: 23.09.09 22:47
Оценка: 12 (1)
Здравствуйте, Roman Odaisky, Вы писали:
RO>И можно ссылку на место, где запрещается кооперативное планирование?
http://shootout.alioth.debian.org/u32q/benchmark.php?test=chameneosredux&lang=all

Programs may use kernel threads, lightweight threads; but coroutines, cooperative threads and other programs with custom schedulers will be listed as interesting alternative implementations. Briefly say what concurrency technique is used in the program header comment.

Re[16]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 17:24
Оценка: 2 (1)
Здравствуйте, VladD2, Вы писали:

VD>Это огромное заблуждение. Есть множество вещей которые нельзя качественно реализовать в библиотеках.

VD>Тот же ЖЦ отличный пример. Просто ЖЦ реализовать можно. Хороший — никогда. Основание элементарно. Хороший ЖЦ должен заниматься оптимизацией хипа. Это поразумевает перемещение блоков памяти. А это подразумевает исправление всех ссылко на них. Если язык не предоставляет возмонсти следить за ссылками. А С и С++ это принципиально сделать не позволяют, то и реализация универсального ЖЦ тоже невозможно.
VD>Эта тема обсуждалась уже сто раз и мне она не интересна.
VD>Я говорил о другом. Об оптимизации. Ежу понятно, что для конкретных условий языки вроде С++ позволяют создать решение максимально близкое к оптимальному. Вопрос только в том — чего это стоит?
VD>Когда кода становится много, то оптимизировать его весь становится просто не реально, а стоимость ручной оптимизации становится слишком дорогой. Посему в реальных приложениях оптимизируются только критические места.
VD>Когда кто-то пишет большое приложение на С++, то он старается применять набор практик позволяющих избежать ошибок и упростить разработку. Именно такие практики встраиваются в более высокоуровневые языки. Так что ординарный С++-код обычно мало отличается по скорости от ординарного кода на более высокоуровенвом языке.
VD>С другой стороны в С++ больше простора для оптимизаций. Еще больше простора в ассемблере. Но тут разница в уровне языка и зависимость от конкретной аппаратуры становится настолько очевидной, что не многие решатся на использования ассемблера. Хотя уверен, что ту же задачу хамелеонов решить на ассемблере можно и эффективнее если делать это со знанием дела и провести много времени за тестированием.
VD>В прочем, С тем и хорош, что позволяет оптимизировать не только программы на С.


Реализовать некоторые вещи на 100% в библиотеке не получится. Согласен. Но я думаю, что можно их реализовать так скажем хотя бы на 80%, т.е. получить основную суть фичи, получить основные преимущества.
ГЦ наверное одна из самых сложных вещей в этом плане, а вот если взять например что-нибудь типа персистентных структур данных и операций над списками в стиле Лисп, то вообще никаких проблем не видится. Конечно если у человека в голове "я хочу программировать на необычном математическом языке", то тут это не поможет; а если задача просто получить преимущества персистентных структур данных, то тут никакой принципиальной разницы между встроенной поддержкой и С++ библиотекой я не вижу.
Вещь посложнее — агентно-ориентированное программирование в стиле Эрланг. Практически всё можно реализовать не хуже, чем в Эрланг. Единственная проблема — очень долго выполняющиеся обработчики сообщений, т.к. они едят стек. В целом это решается, возможно с какими дополнительными практически выполнимыми ограничениями.
Что касается ГЦ. Ну Boehm GC обеспечивает основную гарантию — безопасность (объект не будет удалён пока используется). В качестве оптимизации, например, можно указывать при аллокации блока памяти, что в этом блоке нет указателей (строки, мыссивы чисел). Сложно ли это указывать в некоторых местах на практике? Не особо. Это даже можно встроить в библиотечные классы строк и массивов.
Другой момент — в ГЦ языке просто нет выбора как использовать ГЦ для всех объектов. В программе на С/С++ это может быть совсем не необходимо. ГЦ может быть целесообразно использовать только для каких-то объектов, для которых проблемно управлять временем жизни другими средствами. В такой ситуации можно использовать умные указатели, которые будут говорить ГЦ библиотеке, где управляемые объекты, и где в них сидят ссылки на другие управляемые объекты.
Другой пример — я сейчас делаю библиотеку по управлению временем жизни, она использует поколения для оптимизации. Автоматическое определение и продвижение объектов по поколениям реализуемо, но достаточно проблематично. Поэтому пользователь при создании объекта просто указывает поколение для объекты (обычный, долго живущий, совсем долго живущий). Сложно ли это задавать на практике? По-моему, не особо. В конце-концов пользователь должен понимать, что за объект он создаёт. Ну и опять же это исключительно оптимизация.
Или вот взять например SQL. В чём проблема его реализовать? Разве что синтаксис будет немного другой. Тем более скорее всего не нужно будет его реализовывать в полном объёме, плюс можно реализовать что-то чего нет в SQL.

В общем, мой тезис такой, что получить полную копию фичи, включая синтаксис, в некоторых случаях не получится. Но всегда можно получить основную суть фичи, основные её преимущества. Поэтому говорить, что что-то *принципиально* не доступно в языке общего назначения, я считаю, не правильно. Что касается принципиальной недоступности, так это как раз и относится к специальным языкам. Я думаю, что примеры для таких языков как Erlang, SQL, Lisp каждый может придумать сам. А в языке общего назначения никакие фичи не недоступны, вопрос только в цене реализации, синтаксисе, несколько меньшем контроле со стороны компилятора и т.д. Это я и считаю одним из основных преимуществ языков общего назначения.

Кстати, такие вещи не обязательно реализовывать в библиотеках. Пара примеров.
Intel реализовал в своём компиляторе С++ поддержку STM (Software Transactional Memory). Фича, не уступающая по сложности ГЦ.
Cilk Arts реализовала в компиляторе GCC, поддержку пары новых ключевых слов для своей системы параллельного программирования Cilk++. Они сводятся в основном к созданию замыканий.
С++/CLI практически С++ со сборкой мусора.
Собственно "чистым С++" никто никогда особо и не пользовался, все пользуются "реализациями с расширениями". А что там может быть — да что угодно, если это нужно и важно и в библиотеке не реализовать.

з.ы. Ты написал "Есть множество вещей которые нельзя качественно реализовать в библиотеках", что ещё кроме ГЦ?


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[6]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 22.09.09 18:22
Оценка: 1 (1)
Здравствуйте, FR, Вы писали:

FR>Ну привяжем все потоки к одному ядру и максимум добъемся того же результата что на одноядернике http://shootout.alioth.debian.org/u32/benchmark.php?test=chameneosredux&lang=all&box=1 а чтобы догнать вариант от remark надо еще в неколько раз ускорится что нереально без ручного управления памятью



Кстати, я вот задумался над следующим моментом. Вопрос к Haskell сообществу.
Вот эта программа на Haskell:
http://shootout.alioth.debian.org/u32q/benchmark.php?test=chameneosredux&lang=ghc&id=2
показывает 4.59 сек когда доступны все 4 ядра (реально она использует только 2), и 5.19 сек когда доступно только 1 ядро.

Насколько я понял из кода, она проводит сразу 2 встречи параллельно, при этом первая встреча привязывается к процессору 0, а вторая — к процессору 1. Соотв. я бы ожидал, что время выполнения на 1 ядре должно быть в 2 раза больше, чем на 4(2), т.к. встречи полностью независимы. Т.е. должно быть идеальное линейное ускорение. Но этого не происходит. Почему?



1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[7]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 22.09.09 17:10
Оценка: :)
Здравствуйте, thesz, Вы писали:

FR>>>>>>Ну нельзя же так, взял и всю малину Хаскелистам обломал


T>>>>>http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#8


T>>>>>Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.


FR>>>>Это совсем другое, там просто нет примитивов необходимых чтобы догнать си.


T>>>Да что ты говоришь!


R>>Было бы интересно увидеть практическое подкрепление этим словам.


T>Я тоже.


T>Дело за малым под псевдонимом FR. Это было его высказывание насчёт отсутствия примитивов.


А, понятно. Тогда наверное я неправильно трактовал твою фразу (по-моему уже не в первый раз). Просто фразе "Да что ты говоришь!" можно придать 2 совершенно разных смысла — "Конечно это так, этим ты америку не открыл" или "Это — полная чушь".


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: Хамелеоны быстрые и очень быстрые
От: FR  
Дата: 23.09.09 09:00
Оценка: +1
Здравствуйте, thesz, Вы писали:

T>Не надо тиражировать глупости.


Не тиражируй

T>Параллелизм в этой задаче всё же есть (время выполнения миллиард тактов, не меньше), но он очень мелкий, поэтому избавившись от расходов на межпроцессный обмен мы получаем ускорение.


T>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.


Так давай делай раз все что нужно есть.
Если империя нанесет ответный удар будет хорошая реклама для Хаскеля.
Re[10]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 10:44
Оценка: :)
Здравствуйте, CreatorCray, Вы писали:

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


T>>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.

CC>Подтверди на практике.

Уже неоднократно, поэтому обратись к кому ещё.

Конкретно этот эксперимент мне неинтересен, поскольку у меня своих покрупней и повыгодней есть штуки три.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[15]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 13:55
Оценка: +1
Здравствуйте, thesz, Вы писали:

T>>>>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.

FR>>>>Угу вполне стандартная отмазка

T>>>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.


R>>Не вопрос, никто и не говорит, что тебе делать.


T>И завершил тираду, сказав, что мне надо делать.


Ну хорошо, да, я говорю/призываю людей высказываться по существу и аргументированно. Мне кажется, это вполне разумно.


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


R>>Просто пока всё, что ты сказал несёт практически нулевую информацию, и складывается впечатление, что интересно тебе переливание из пустого в порожнее. Я тоже могу сказать, что у меня есть программа, которая в 1000 раз быстрее всех ваших, но больше ничего говорить и показывать не буду. Смысл? Это уже попахивает троллингом в техническом форуме. Да, полезное общение в форуме требует времени, это надо понимать, и ИМО сообщать либо хоть какую-то информацию, либо не говорить ничего. Уже мог бы за это время лучше набросать программу (благо там всего-то 65 строчек в программе на Haskell, некоторую часть можно прям оттуда и скопи-пастить), и запостить здесь, а я могу её туда засабмитить (с твоим именем естественно). Делов-то? Тем более, я так понимаю, что для тебя это достаточно тривиальная задача.


T>Э, нет.

T>Я FR показал, что есть примитивы фиксации нитей на процессорах, пусть он теперь ваяет, если захочет.
T>Или пусть это дело ваяешь ты.
T>Иными словами, те люди, которым интересна производительность языков программирования.
T>Если нет желания, то я не против.

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

А то, что есть возможность привязки потоком в процессорам, это и так было ясно, потому что бывшая самая быстрая реализация на Haskell как раз и использует forkOnIO, и за счёт этого и была относительно быстрой.
Так что вот эти 4.5 секунд как раз и есть предел с использованием forkOnIO.



1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 20.09.09 13:26
Оценка:
Здравствуйте, FR, Вы писали:

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


R>>Дабы немного разжечь интерес:

R>>

R>>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды. Так же можно отметить: самая быстрая реализация на Java – 7 сек.; Scala – 15 сек.; Erlang – 111 сек.; Ruby — 131 сек.; Python — 221 сек.
R>>Результат моей реализации — 0.72 секунды.


FR>Ну нельзя же так, взял и всю малину Хаскелистам обломал


http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#8

Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[3]: Хамелеоны быстрые и очень быстрые
От: FR  
Дата: 21.09.09 05:09
Оценка:
Здравствуйте, thesz, Вы писали:


FR>>Ну нельзя же так, взял и всю малину Хаскелистам обломал


T>http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#8


T>Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.


Это совсем другое, там просто нет примитивов необходимых чтобы догнать си.
Re[4]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 21.09.09 09:35
Оценка:
Здравствуйте, FR, Вы писали:

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



FR>>>Ну нельзя же так, взял и всю малину Хаскелистам обломал


T>>http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#8


T>>Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.


FR>Это совсем другое, там просто нет примитивов необходимых чтобы догнать си.


Да что ты говоришь!
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[5]: Хамелеоны быстрые и очень быстрые
От: FR  
Дата: 21.09.09 09:55
Оценка:
Здравствуйте, thesz, Вы писали:

T>>>Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.


FR>>Это совсем другое, там просто нет примитивов необходимых чтобы догнать си.


T>Да что ты говоришь!


Ну привяжем все потоки к одному ядру и максимум добъемся того же результата что на одноядернике http://shootout.alioth.debian.org/u32/benchmark.php?test=chameneosredux&lang=all&box=1 а чтобы догнать вариант от remark надо еще в неколько раз ускорится что нереально без ручного управления памятью
Re[6]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 22.09.09 16:49
Оценка:
Здравствуйте, remark, Вы писали:

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


FR>>>>>Ну нельзя же так, взял и всю малину Хаскелистам обломал


T>>>>http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#8


T>>>>Поскольку я не могу проверить работу на нескольких ядрах (оба мои компа одноядерные), я помещу только ссылку, поскольку sapienti sat.


FR>>>Это совсем другое, там просто нет примитивов необходимых чтобы догнать си.


T>>Да что ты говоришь!


R>Было бы интересно увидеть практическое подкрепление этим словам.


Я тоже.

Дело за малым под псевдонимом FR. Это было его высказывание насчёт отсутствия примитивов.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[7]: Хамелеоны быстрые и очень быстрые
От: FR  
Дата: 22.09.09 18:02
Оценка:
Здравствуйте, thesz, Вы писали:


T>Я тоже.


T>Дело за малым под псевдонимом FR. Это было его высказывание насчёт отсутствия примитивов.


http://www.rsdn.ru/forum/philosophy/3543472.1.aspx
Автор: FR
Дата: 21.09.09
Re[8]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 08:50
Оценка:
Здравствуйте, FR, Вы писали:

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



T>>Я тоже.


T>>Дело за малым под псевдонимом FR. Это было его высказывание насчёт отсутствия примитивов.


FR>http://www.rsdn.ru/forum/philosophy/3543472.1.aspx
Автор: FR
Дата: 21.09.09


Не надо тиражировать глупости.

Параллелизм в этой задаче всё же есть (время выполнения миллиард тактов, не меньше), но он очень мелкий, поэтому избавившись от расходов на межпроцессный обмен мы получаем ускорение.

Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Хамелеоны быстрые и очень быстрые
От: CreatorCray  
Дата: 23.09.09 09:15
Оценка:
Здравствуйте, thesz, Вы писали:

T>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.

Подтверди на практике.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[11]: Хамелеоны быстрые и очень быстрые
От: FR  
Дата: 23.09.09 11:07
Оценка:
Здравствуйте, thesz, Вы писали:

T>Я бы предпочёл, чтобы этим занялся ты.


Да я не думал что ленивый язык настолько сильно воздействует на мозг
Ты лучше Влада попроси думаю он с удовольствием сделает.

T>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.


Угу вполне стандартная отмазка
Re[11]: Хамелеоны быстрые и очень быстрые
От: CreatorCray  
Дата: 23.09.09 11:30
Оценка:
Здравствуйте, thesz, Вы писали:

T>>>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.

CC>>Подтверди на практике.
T>Уже неоднократно, поэтому обратись к кому ещё.
Где можно наглядно ознакомиться с результатами, сравнить?

T>Конкретно этот эксперимент мне неинтересен, поскольку у меня своих покрупней и повыгодней есть штуки три.

О да!
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[12]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 12:08
Оценка:
T>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.
FR>Угу вполне стандартная отмазка

Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[12]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 12:12
Оценка:
Здравствуйте, CreatorCray, Вы писали:

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


T>>>>Надо достичь баланса в этом самом межпроцессном обмене, а для этого средства есть.

CC>>>Подтверди на практике.
T>>Уже неоднократно, поэтому обратись к кому ещё.
CC>Где можно наглядно ознакомиться с результатами, сравнить?

В разных местах.

T>>Конкретно этот эксперимент мне неинтересен, поскольку у меня своих покрупней и повыгодней есть штуки три.

CC>О да!

Да.

http://thesz.mskhug.ru/svn

Последний из них http://thesz.mskhug.ru/svn/hhdl и он же самый интересный. Это не шутаут, это много прикольней. Это то, чего C++ никогда не сможет.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: Хамелеоны быстрые и очень быстрые
От: CreatorCray  
Дата: 23.09.09 12:20
Оценка:
Здравствуйте, thesz, Вы писали:

T>>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.

FR>>Угу вполне стандартная отмазка

T>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.

Это вторая стандартная отмазка.

Да и в целом, не пристало сеньёру сказав "А" замять тему и таки не говорить "Б".
Тем более делов то: ткнуть носом нубов в те самые примитивы, которых недостаёт хаскель программе чтоб таки догнать сишный код remark-а.
Ну или признать что их на самом деле попросту нет.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[14]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 12:41
Оценка:
Здравствуйте, CreatorCray, Вы писали:

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


T>>>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.

FR>>>Угу вполне стандартная отмазка

T>>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.

CC>Это вторая стандартная отмазка.

CC>Да и в целом, не пристало сеньёру сказав "А" замять тему и таки не говорить "Б".

CC>Тем более делов то: ткнуть носом нубов в те самые примитивы, которых недостаёт хаскель программе чтоб таки догнать сишный код remark-а.

Фиксирование зелёных нитей на процессорах есть. Во что я "ткнул носом нубов" в том сообщении FR.

CC>Ну или признать что их на самом деле попросту нет.


Да мне на это наплевать. Есть они, нет их. Для работы это неважно.

Это важно для раздутия чьей-то (моей, чьей-то ещё, неважно) пиписьки прямо здесь и прямо сейчас, и совершенно не имеет смысла в длительной перспективе.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re: Эрланг
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 13:08
Оценка:
Здравствуйте, minorlogic, Вы писали:

M>>>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ?

E>>Re[2]: Хамелеоны быстрые и очень быстрые
Автор: remark
Дата: 19.09.09
тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.


M>Так это и поражает, легковесные потоки в Эрланге не являются потоками системы, точнее не обязаны ими быть. Поэтому казалось бы что на подобных задачах Эрланг должен как минимум быть удовлетворительным.


Случай, когда легковесные потоки не являются ядерными, можно видеть здесь:
http://shootout.alioth.debian.org/u32/benchmark.php?test=chameneosredux&amp;lang=all
и тут Эрланг действительно показывает "удовлетворительный" результат в 8.3 секунды

А вот когда легковесные потоки становятся ядерными:
http://shootout.alioth.debian.org/u32q/benchmark.php?test=chameneosredux&amp;lang=all
время уже становится 111 секунд.

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

Кстати, по поводу "удовлетворительного" результата с легковесными потоками. Моя реализация показывает в такой ситуации 10.4 секунды, но каждое взаимодействие есть честное переключение ядерного потока ОС (при ожидании я всегда делаю sched_yield()). Т.е. "легковесные" Эрланг потоки легче честных ядерных потоков всего на 25%, вот и судите несколько они "легковесные", и насколько разница в 25% может порождать другой стиль программирования.

Интересно было бы сделать реализацию на С с использованием fibers. На Windows их переключение примерно раз в 40 быстрее переключения ядерных потоков, т.к. там всего пара десятков инструкций. Насколько я понимаю такую реализацию не примут, т.к. там запрещено использование кооперативного планирования (хотя не понятно, языки с легковесными потоками её используют; а фиберы предоставляет ОС, что практически тоже самое для С). Но будет интересно сравнить "легковесность" с процессами Эрланг.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Эрланг
От: FR  
Дата: 23.09.09 13:27
Оценка:
Здравствуйте, remark, Вы писали:

R>Кстати, по поводу "удовлетворительного" результата с легковесными потоками. Моя реализация показывает в такой ситуации 10.4 секунды, но каждое взаимодействие есть честное переключение ядерного потока ОС (при ожидании я всегда делаю sched_yield()). Т.е. "легковесные" Эрланг потоки легче честных ядерных потоков всего на 25%, вот и судите несколько они "легковесные", и насколько разница в 25% может порождать другой стиль программирования.


Ну учитывая насколько эрланг медленнее чем си, то очень даже легковесные.
Еще учти что на Эрланге можно без проблем создать десять тысяч потоков, системные же несколько тысяч потоков будут в основном тратить время на переключения друг на друга.
Re[14]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 23.09.09 13:30
Оценка:
Здравствуйте, remark, Вы писали:

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


T>>>>Мне неинтересен [b]конкретно этот[b] эксперимент. У меня своих висящих штуки три или больше, с потенциально гораздо большим выхлопом.

FR>>>Угу вполне стандартная отмазка

T>>Я уж столько надоказывал и тут и всюду, что имею право на занятия тем, что интересно мне лично.


R>Не вопрос, никто и не говорит, что тебе делать.


И завершил тираду, сказав, что мне надо делать.

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

R>Просто пока всё, что ты сказал несёт практически нулевую информацию, и складывается впечатление, что интересно тебе переливание из пустого в порожнее. Я тоже могу сказать, что у меня есть программа, которая в 1000 раз быстрее всех ваших, но больше ничего говорить и показывать не буду. Смысл? Это уже попахивает троллингом в техническом форуме. Да, полезное общение в форуме требует времени, это надо понимать, и ИМО сообщать либо хоть какую-то информацию, либо не говорить ничего. Уже мог бы за это время лучше набросать программу (благо там всего-то 65 строчек в программе на Haskell, некоторую часть можно прям оттуда и скопи-пастить), и запостить здесь, а я могу её туда засабмитить (с твоим именем естественно). Делов-то? Тем более, я так понимаю, что для тебя это достаточно тривиальная задача.


Э, нет.

Я FR показал, что есть примитивы фиксации нитей на процессорах, пусть он теперь ваяет, если захочет.

Или пусть это дело ваяешь ты.

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

Если нет желания, то я не против.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[3]: Эрланг
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 14:20
Оценка:
Здравствуйте, FR, Вы писали:

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


R>>Кстати, по поводу "удовлетворительного" результата с легковесными потоками. Моя реализация показывает в такой ситуации 10.4 секунды, но каждое взаимодействие есть честное переключение ядерного потока ОС (при ожидании я всегда делаю sched_yield()). Т.е. "легковесные" Эрланг потоки легче честных ядерных потоков всего на 25%, вот и судите несколько они "легковесные", и насколько разница в 25% может порождать другой стиль программирования.


FR>Ну учитывая насколько эрланг медленнее чем си, то очень даже легковесные.


Не понял мысль.
Я говорил о следующем.
Апологеты Эрланг говорят примерно следующее. Переключение ядерных потоков дорого, поэтому вы не можете их использовать в ряде задач, т.к. время переключения будет слишком большим. В Эрланге потоки легковесные и переключаются быстро, поэтому вы можете из использовать для некоторых из тех целей, для который вы не могли это делать с ядерными потоками.
А на практике получается что время переключения практически одинаковое, и если я пишу на С с использованием ядерных потоков, то я могу их использовать точно там же, где на Эрланге я бы использовал легковесные потоки.


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


Это бесспорно. В плане памяти они легковесные.
Ядерных потоков можно создать, ну там допустим, 32*Количество_процессоров, что бы всё нормально работало. Но O(N) (по размерности входных данных) потоков всё равно создавать нельзя. На Эрланге можно создавать O(N) процессов.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[4]: Эрланг
От: FR  
Дата: 23.09.09 14:30
Оценка:
Здравствуйте, remark, Вы писали:


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

R>А на практике получается что время переключения практически одинаковое, и если я пишу на С с использованием ядерных потоков, то я могу их использовать точно там же, где на Эрланге я бы использовал легковесные потоки.

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

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


R>Это бесспорно. В плане памяти они легковесные.

R>Ядерных потоков можно создать, ну там допустим, 32*Количество_процессоров, что бы всё нормально работало. Но O(N) (по размерности входных данных) потоков всё равно создавать нельзя. На Эрланге можно создавать O(N) процессов.

Ну так это тоже компонент цены.
Re[5]: Эрланг
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 14:35
Оценка:
Здравствуйте, FR, Вы писали:

FR>Наверно на хамелеонах можешь, а там где потоков больше и логика другая может быть совсем по другому.

FR>Да и по скорости переключений надо мерять, мне кажется оценивать по одной задаче будет неправильно.

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


R>>Это бесспорно. В плане памяти они легковесные.

R>>Ядерных потоков можно создать, ну там допустим, 32*Количество_процессоров, что бы всё нормально работало. Но O(N) (по размерности входных данных) потоков всё равно создавать нельзя. На Эрланге можно создавать O(N) процессов.

FR>Ну так это тоже компонент цены.


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



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 15:01
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ты не хочешь все это дело оформить соответствующим образом, доработать чтобы материал был более развернутым и понятным, добавить туда результаты и т.п. и прислать нам для размещения в качестве статьи?


VD>А то ведь через некоторое время тема уйдет вниз и все про нее забудут.


Очень хочу... но, блин, время, сами понимаете.
Написать работающую программу под Windows заняло пару часов от силы. Казалось бы вот и все трудозатраты. Ан нет, портировать, причесать, протестировать, засабмитить, исправить, засабмитить заняло наверное где-то день. Засабмитил, думаю, как-то глупо получается, всё, что получилось в результате 1 циферка в таблице. Написание описания заняло наверное ещё день. Для статьи нужны таблицы, картинки, подробные описания, редакторская правка и т.д. в итоге дня 3 как минимум.
Тем более, что всё остаётся в моих блогах:
http://software.intel.com/ru-ru/blogs/author/dmitriy-vyukov/
http://software.intel.com/en-us/blogs/author/dmitriy-vyukov/


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 15:49
Оценка:
Здравствуйте, remark, Вы писали:

VD>>А то ведь через некоторое время тема уйдет вниз и все про нее забудут.


R>Очень хочу... но, блин, время, сами понимаете.


Это понятно. Но и результат более ценный будет.

R>Написать работающую программу под Windows заняло пару часов от силы. Казалось бы вот и все трудозатраты. Ан нет, портировать, причесать, протестировать, засабмитить, исправить, засабмитить заняло наверное где-то день.


Для статьи все это не так нужно. В прочем все равно уже все сделано.

R> Засабмитил, думаю, как-то глупо получается, всё, что получилось в результате 1 циферка в таблице. Написание описания заняло наверное ещё день.


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

R>Для статьи нужны таблицы, картинки, подробные описания, редакторская правка и т.д. в итоге дня 3 как минимум.

R>Тем более, что всё остаётся в моих блогах:
R>http://software.intel.com/ru-ru/blogs/author/dmitriy-vyukov/
R>http://software.intel.com/en-us/blogs/author/dmitriy-vyukov/

Ну, так потрать эти 3 дня на пользу человечества .
Тем более, что можно делать это потихоничку. Выкрить эти 3 дня в течении месяца.

Что до картинок, то тут мы можем тебе помочь. У нас на то есть редакторы. Сделай макет картинок в том формате в котором тебе будет удобнее, а мы переделаем их в красивом виде и в том формате в котором их буде удобнее размещать на вебе.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[17]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 15:54
Оценка:
Здравствуйте, thesz, Вы писали:

R>>Если ты говоришь, о том, что можно сделать эффективную реализацию на Haskell, образно выражаясь, "скопировав" реализацию на С, то привязки потоков к ядрам не достаточно. Очень сильно не достаточно. Необходимы все 4 момента, которые я описал, включая определение топологии системы. Отсутствие любого из них увеличит время выполнения в разы.


T>У тебя четыре пункта, отставание у Хаскеля в пять раз. Если каждый пункт обеспечивает ускорение в разы (в два раза), то твоя программа должна опережать Хаскельную в 16 раз. Чего мы не наблюдаем.


Зависимость не линейная.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[14]: Хамелеоны быстрые и очень быстрые
От: remark Россия http://www.1024cores.net/
Дата: 23.09.09 16:08
Оценка:
Здравствуйте, VladD2, Вы писали:

T>>Последний из них http://thesz.mskhug.ru/svn/hhdl и он же самый интересный. Это не шутаут, это много прикольней. Это то, чего C++ никогда не сможет.


VD>Что он не сможет то?


VD>С++ не может только одного. Позволить написать большой объем кода без ошибок. Все остальное он позволяет. Всегда можно скатиться на уровень Си и писать практически на высокоуровневом ассемблере используя все преимущества железа.


Как сказал, по-моему, Страуструп (к сожалению никак не могу найти эту цитату):

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


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



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[14]: Хамелеоны быстрые и очень быстрые
От: WolfHound  
Дата: 23.09.09 16:15
Оценка:
Здравствуйте, VladD2, Вы писали:

T>>Последний из них http://thesz.mskhug.ru/svn/hhdl и он же самый интересный. Это не шутаут, это много прикольней. Это то, чего C++ никогда не сможет.


VD>Что он не сможет то?

VD>С++ не может только одного. Позволить написать большой объем кода без ошибок.

Так там оно и есть.
Большой объем хитрого кода.
На С++ без ошибок хрен напишешь.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[15]: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 16:25
Оценка:
Здравствуйте, remark, Вы писали:

R>Вопрос, конечно, в том, что её надо реализовывать. Но с другой стороны всё действительно полезное и нужное уже реализовано в каких-то библиотеках. А дальше какая разница — будь то дядя реализовал это в каком-то языке или в какой-то библиотеке. Вот даже сборщик мусора промышленный для С/С++ есть, чего уж там говорить о персистентных структурах и агентно-ориентированном программировании.


Это огромное заблуждение. Есть множество вещей которые нельзя качественно реализовать в библиотеках.
Тот же ЖЦ отличный пример. Просто ЖЦ реализовать можно. Хороший — никогда. Основание элементарно. Хороший ЖЦ должен заниматься оптимизацией хипа. Это поразумевает перемещение блоков памяти. А это подразумевает исправление всех ссылко на них. Если язык не предоставляет возмонсти следить за ссылками. А С и С++ это принципиально сделать не позволяют, то и реализация универсального ЖЦ тоже невозможно.
Эта тема обсуждалась уже сто раз и мне она не интересна.
Я говорил о другом. Об оптимизации. Ежу понятно, что для конкретных условий языки вроде С++ позволяют создать решение максимально близкое к оптимальному. Вопрос только в том — чего это стоит?
Когда кода становится много, то оптимизировать его весь становится просто не реально, а стоимость ручной оптимизации становится слишком дорогой. Посему в реальных приложениях оптимизируются только критические места.
Когда кто-то пишет большое приложение на С++, то он старается применять набор практик позволяющих избежать ошибок и упростить разработку. Именно такие практики встраиваются в более высокоуровневые языки. Так что ординарный С++-код обычно мало отличается по скорости от ординарного кода на более высокоуровенвом языке.
С другой стороны в С++ больше простора для оптимизаций. Еще больше простора в ассемблере. Но тут разница в уровне языка и зависимость от конкретной аппаратуры становится настолько очевидной, что не многие решатся на использования ассемблера. Хотя уверен, что ту же задачу хамелеонов решить на ассемблере можно и эффективнее если делать это со знанием дела и провести много времени за тестированием.
В прочем, С тем и хорош, что позволяет оптимизировать не только программы на С.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 16:26
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Так там оно и есть.

WH>Большой объем хитрого кода.
WH>На С++ без ошибок хрен напишешь.

В Хамелионах то? Акстись. Это приципиально мелкая задачка со своими подводными камнями (неплохо описанными автором темы).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Хамелеоны быстрые и очень быстрые
От: WolfHound  
Дата: 23.09.09 17:00
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>В Хамелионах то? Акстись. Это приципиально мелкая задачка со своими подводными камнями (неплохо описанными автором темы).

А давай ты еще раз посмотришь на что ты отвечал.
Процитирую чтобы далеко не ходить

T>>Конкретно этот эксперимент мне неинтересен, поскольку у меня своих покрупней и повыгодней есть штуки три.
CC>О да!

Да.

http://thesz.mskhug.ru/svn

Последний из них http://thesz.mskhug.ru/svn/hhdl и он же самый интересный. Это не шутаут, это много прикольней. Это то, чего C++ никогда не сможет.

(С) http://rsdn.ru/forum/philosophy/3545864.1.aspx
Автор: thesz
Дата: 23.09.09

Выделенное это про хамелеонов.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[17]: Хамелеоны быстрые и очень быстрые
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.09.09 18:32
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>А давай ты еще раз посмотришь на что ты отвечал.


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

За одно не стоит от темы уходить так далеко .
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Легковесные потоки
От: Roman Odaisky Украина  
Дата: 23.09.09 20:22
Оценка:
Здравствуйте, remark, Вы писали:

R>Интересно было бы сделать реализацию на С с использованием fibers. На Windows их переключение примерно раз в 40 быстрее переключения ядерных потоков, т.к. там всего пара десятков инструкций. Насколько я понимаю такую реализацию не примут, т.к. там запрещено использование кооперативного планирования (хотя не понятно, языки с легковесными потоками её используют; а фиберы предоставляет ОС, что практически тоже самое для С). Но будет интересно сравнить "легковесность" с процессами Эрланг.


Насколько я знаю, fibers как раз не предоставляются ОС, а реализуются полностью в пространстве пользователя (наподобие setjmp/longjmp)? Там может не быть ни одного системного вызова (хотя glibc вызывает sigprocmask(2) внутри swapcontext(3)). В POSIX-системах есть <ucontext.h> с getcontext/setcontext/makecontext/swapcontext и обертка над ними GNU Pth, можно попробовать поиграться с ними.

И можно ссылку на место, где запрещается кооперативное планирование?
До последнего не верил в пирамиду Лебедева.
Re[15]: Хамелеоны быстрые и очень быстрые
От: CreatorCray  
Дата: 24.09.09 09:09
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>На С++ без ошибок хрен напишешь.

Ошибки ловятся и исправляются. Это не total show-stopper.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[14]: Хамелеоны быстрые и очень быстрые
От: thesz Россия http://thesz.livejournal.com
Дата: 24.09.09 09:21
Оценка:
Здравствуйте, VladD2, Вы писали:

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


T>>Последний из них http://thesz.mskhug.ru/svn/hhdl и он же самый интересный. Это не шутаут, это много прикольней. Это то, чего C++ никогда не сможет.


VD>Что он не сможет то?


VD>С++ не может только одного. Позволить написать большой объем кода без ошибок. Все остальное он позволяет. Всегда можно скатиться на уровень Си и писать практически на высокоуровневом ассемблере используя все преимущества железа.


Думая ответить на твой предыдущий ответ мне, я хотел попросить тебя читать сообщения перед тем, как на них отвечать.

Поскольку я решил не отвечать на тот твой ответ мне, прошу тебя в этом ответе: Влад, читай, пожалуйста, сообщения, на которые собираешься отвечать.

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

Вот алгебраические типы данных C++ не сможет внести в SystemC никогда.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[19]: Хамелеоны быстрые и очень быстрые
От: CreatorCray  
Дата: 24.09.09 10:39
Оценка:
Здравствуйте, thesz, Вы писали:

R>>Зависимость не линейная.

T>Иными словами, ты сам толком не знаешь, что же в твоём подходе самое важное.
Жжошь!
Иди, перечитай заметку еще раз. Потому как ты нифига не понял смысла того, что там написано.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[16]: Хамелеоны быстрые и очень быстрые
От: WolfHound  
Дата: 24.09.09 13:05
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Ошибки ловятся и исправляются. Это не total show-stopper.

Пожалуйста перелови все переполнения буфера в линуксе.
Да и мне нужно строгое доказательство что их там не осталось.
И это весьма примитивные ошибки...
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[18]: Хамелеоны быстрые и очень быстрые
От: WolfHound  
Дата: 24.09.09 13:37
Оценка:
Здравствуйте, Nuzhny, Вы писали:

WH>>Пожалуйста перелови все переполнения буфера в линуксе.

WH>>Да и мне нужно строгое доказательство что их там не осталось.
WH>>И это весьма примитивные ошибки...
N>Гы. Аргументы пошли сильные.
Я просто предельно наглядно показал что переловить даже примитивные ошибки в большой программе на С/С++ задача не решаемая.
Как следствие бравада что типа "мы тут ща все ошибки исправим" мягко говоря не уместна.

N>Пожалуйста, перепиши Линукс на языке, который не допустит ни одного переполнения буфера.

Если я и буду писать ОСь на правильном языке то она будет очень сильно отличаться от линукса.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.