Glasgow Haskell Compiler 6.10.1

>>Реализаций нитей M:N довольно много.

>Не уводите в сторону:)

Да ни разу :) В конце концов, Эрланговые процессы - это еще одна реализация M:N (или даже 1:N, если учитывать, что SMP поддерживается относительно недавно).

> Как бы то ни было "ПИСАТЬ на C, так же, как на Эрланге" - получится:)

Вот и мне так кажется (если ты не оговорился :)). А с тем, что на Эрланге будет удобнее, я и не спорю.

>Вот и мне так кажется (если ты не оговорился :))

Оговорился:)

>А с тем, что на Эрланге будет удобнее, я и не спорю.

Удобнее, потому что чтобы "ПИСАТЬ на C, как на Эрланге", нужно сначала на C реализовать "полЭрланга":)

А ещё - рассчитывать на то, что C-компилятор оптимизирует хвостовую рекурсию (gcc с какого-то моента это делает, но не в -O0, а другие компиляторы - не факт)

>> ...на монадах или прямее ...

> ну ни фига ж себе прямее

берем словарь и выясняем значение слова "или"

> вообще задачи не понял. можно то же самое, но по-человечески?

Упрощенно совсем: есть у тебя char videomemory[1600*1200*4] -- это двумерная память прямо видеодаптера; ее надо из хаскеля напрямую адресовать, дабы там линии чертить хотя бы и квадратики-кружочки рисовать. А еще перед тем, как адресовать и рисовать, ее надо залочить, а порисовав -- отдать лок.

"на монадах или прямее" означает, что программист на с++ может юзать монады когда захочет, но плюс к этому избавлен от *необходимости* юзать монады, когда нужно менять состояние какого-то внешнего от программы объекта, и это состояние можно менять более прямым и ясным способом, чем монады.

>> ...на монадах или прямее ...

> ну ни фига ж себе прямее

Если тебя синтаксис плюсовый испугал -- то в общем я согласен, он ужасный, но у хаскеля не сказал бы что намного лучше.

В смысле у хаскеля синтаксис поприятнее чем у с++, но не намного.

2 sv75
 случайно пробовал. сделай пакет, если тебе его нехватает

2 www_linux_org_ru ктото там писал про гланды через жопу. это чтото вроде функционального программирования на C++ и массивов на haskell, да?

> Как я понимаю, распараллеливание в функциональных языках основывается на иммутабельности данных и естественном параллелизме операций над ними (типа map). И основная фишка именно в том, что распараллеливание именно _незаметно_.

о чём я и спрашивал. Мне сказали что речь тут не об этом, так что я в недоумении какие такие возможности даёт мне именно среда и язык.

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

[s]А программист на ассемблере[/s]

Вот-вот, это значит, что компилятор C++ ничего за программиста не проверит.

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

> и это состояние можно менять более прямым и ясным способом, чем монады.

WTF?

modify (здесь функция состояние -> состояние) - это сложно?

> Как я понимаю, распараллеливание в функциональных языках основывается на иммутабельности данных и естественном параллелизме операций над ними (типа map). И основная фишка именно в том, что распараллеливание именно _незаметно_.

Я тоже на это было купился, но оказалось, неявно распараллелить программу ни один хаскельный компилятор не может. Что смешно, фортрановские компиляторы делают это с незапамятных пор. Если начать распараллеливать в хаскеле вообще все операции типа map и все аргументы функций вычислять параллельно, пользуясь чистотой, то этого параллелизма станет слишком много, накладные расходы напрочь убьют весь выигрыш. А решить, что надо параллелить, а что нет, у компилятора ума не хватит, это AI-полная задача. Поэтому приходится указывать вручную, в Data Parallel Haskell, например, просто добавили параллельные версии некоторых функций и специальные массивы для них, прям как в жабских библиотеках, и то оно нифига не работает на самом деле. А в Glasgow Parallel Haskell так и вовсе не стали ломать голову, а тупо прикрутили par и seq из Оккама. В итоге непонятно, столько разговоров про чистоту и параллелизм, а на практике никакого профита пока не видно.

> Да ни разу :) В конце концов, Эрланговые процессы - это еще одна реализация M:N (или даже 1:N, если учитывать, что SMP поддерживается относительно недавно).

С той разницей, что переключение стоит СИЛЬНО дешевле, чем в случае настоящих процессов.

>С той разницей, что переключение стоит СИЛЬНО дешевле, чем в случае настоящих процессов.

И "весят" они СИЛЬНО меньше, чем в случае настоящих процессов.

> [s]А программист на ассемблере[/s]

А что может программист на ассемблере, чего не может программист на С++?

> Вот-вот, это значит, что компилятор C++ ничего за программиста не проверит. Серьёзно, попробуй сделать STM на языке, который не видит разницы между чистыми и нечистыми функциями. Получится говно.

STM = software transactional memory ?

Компилятор С++ видит разницу между константными методами (=функциями класса) и неконстантными, но достаточный ли это аналог чистых функций -- не скажу сходу -- надо смотреть задачи.

> Вот-вот, это значит, что компилятор C++ ничего за программиста не проверит. Серьёзно, попробуй сделать STM на языке, который не видит разницы между чистыми и нечистыми функциями. Получится говно.

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

> 2 www_linux_org_ru ктото там писал про гланды через жопу. это чтото вроде функционального программирования на C++ и массивов на haskell, да?

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

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

s/называет/называется/

> Я тоже на это было купился, но оказалось, неявно распараллелить программу ни один хаскельный компилятор не может. Что смешно, фортрановские компиляторы делают это с незапамятных пор. Если начать распараллеливать в хаскеле вообще все операции типа map и все аргументы функций вычислять параллельно, пользуясь чистотой, то этого параллелизма станет слишком много, накладные расходы напрочь убьют весь выигрыш. А решить, что надо параллелить, а что нет, у компилятора ума не хватит, это AI-полная задача. Поэтому приходится указывать вручную, в Data Parallel Haskell, например, просто добавили параллельные версии некоторых функций и специальные массивы для них, прям как в жабских библиотеках, и то оно нифига не работает на самом деле. А в Glasgow Parallel Haskell так и вовсе не стали ломать голову, а тупо прикрутили par и seq из Оккама. В итоге непонятно, столько разговоров про чистоту и параллелизм, а на практике никакого профита пока не видно.

Чтобы понять, что нужно (не "можно", а именно "нужно") компилятор должен найти участки кода, накладные расходы на выполнение которых выше, чем на создание потоков под них. А это выявить можно только многократным прогоном программы. Это первая сложность. Вторая сложность - ленивость. В общем, велкам в Haskell mailing list, там сейчас как раз тема обсуждается по автоматическому распараллеливанию. Не стоит, кстати, забывать, что автоматически можно было бы распараллелить, но кто сказал, что компилятор распараллелит именно так, как мне/задаче выгодно? Хинты для компилера не такая уж плохая идея.

> В итоге непонятно, столько разговоров про чистоту и параллелизм, а на практике никакого профита пока не видно.

А есть ли эффективный механизм, как раскидать "лёгкие нити" по различным процессорам? Если есть, тогда профит в чистоте виден.

>> С той разницей, что переключение стоит СИЛЬНО дешевле, чем в случае настоящих процессов.

> И "весят" они СИЛЬНО меньше, чем в случае настоящих процессов.

Причем здесь вообще "настоящие" процессы? В Эрланге "процессом" называется то, что обычно называют "нитью". И с чего бы процессу Эрланга весить меньше, чем нить в реализации M:N? Стек и набор регистров есть в обоих случаях, а больше ничего особенного M:N реализация для нити и не хранит.

>В Эрланге "процессом" называется то, что обычно называют "нитью".

Ты в этом уверен? абсолютно?

>> В Эрланге "процессом" называется то, что обычно называют "нитью".

> Ты в этом уверен?

Да.

> абсолютно?

Нет ничего абсолютного. Если я не прав - скажи, в чем именно.

> Хинты для компилера не такая уж плохая идея.

А в пределе получаем Occam, который может чуть менее чем полностью состоять из хинтов компилятору :) И возникает вопрос - а так ли нужно ФП и чистота именно для распараллеливания? Не отрицая другие выигрыши от них.

>Нет ничего абсолютного. Если я не прав - скажи, в чем именно.

http://en.wikipedia.org/wiki/Erlang_(programming_language)

Читай "Concurrency and distribution oriented language" про то, как реализованы "нити" в Erlang

http://ru.wikipedia.org/wiki/Erlang

Но это всё очень упрощённое описание, естественно:)

> Читай "Concurrency and distribution oriented language" про то, как реализованы "нити" в Erlang

Вообще-то я читал документацию OTP, но вики так вики... "Erlang processes are neither operating system procehttp://en.wikipedia.org/wiki/Erlang_(programming_language) sses nor operating system threads, but lightweight processes somewhat similar to Java's original “green threads” (the Java Virtual Machine now uses native threads). Like operating system processes (and unlike green threads and operating system threads) they have no shared state between them."

Итого, единственное отличие процессов Эрланга от банальных green threads - это отсуствие "shared state". Причем это "shared state" отсуствует на уровне Эрланга (надеюсь, то очевидно), а не ОС. В общем, совершенно обычные userspace threads, разве выполняют байткод BEAM, и стеки небольшие.

Поэтому и вопрос был - какое отношение ко всему этому имеют "обычные" процессы.

> Но это всё очень упрощённое описание, естественно:)

Это называется "несколько скупых слов" http://en.wikipedia.org/wiki/Erlang_(programming_language)#Concurrency_and_di...

Erlang processes are neither operating system processes nor operating system threads, but lightweight processes somewhat similar to Java's original “green threads” (the Java Virtual Machine now uses native threads). Like operating system processes (and unlike green threads and operating system threads) they have no shared state between them. The estimated minimal overhead for each is 300 words <...>

Я еще копнул тут: http://en.wikipedia.org/wiki/Green_threads

The Erlang virtual machine has what might be called 'green processes' - they are like operating system processes (they do not share state like threads do) but are implemented within the Erlang Run Time System (erts). These are sometimes (erroneously) cited as 'green threads'.

Ты лучше прямо скажи:

1. Как они в Ерланге решили вопрос с блокировкой зеленого процесса на ВВ?

2. Их зеленые процессы кооперативно многозадачны?

tailgunner, вот что я не понимаю:

Benchmarks on computers running the Linux kernel have shown that:

- green threads outperform Linux native threads on thread activation and synchronization.

- Linux native threads have much better performance on I/O and context switching operations.

Что мешает сделать в ядре такие нити, чтобы никто больше не пытался их делать сам, "на коленке" ?

>- green threads outperform Linux native threads on thread activation and synchronization.

Во-первых, не указано, какую именно реализацию и насколько они outperform; во-вторых, часто (не всегда) green threads используют модель 1:N, так что синхронизация у них простая, вообще без входа в ядро, а активация - обычный jump (зато 1:N не может использовать SMP, как Эрланг до недавнего времени).

> - Linux native threads have much better performance on I/O and context switching operations.

С I/O более-менее понятно (оно лучше параллелится, если нити полноценные), но про context switching - O_O

> Что мешает сделать в ядре такие нити, чтобы никто больше не пытался их делать сам, "на коленке" ?

То, что для планирования по-любому придется делать вход/выход из ядра. И то, что планировщик ядра ничего не знает о специфике пользовательского приложения (например, очередях сообщений Эрланга), которая может учитываться при планировании userspace-планировшиком.

А еще ядерная нить обладает некоторым фиксированным оверхэдом, который может быть неприемлем.

> С I/O более-менее понятно (оно лучше параллелится, если нити полноценные), но про context switching - O_O

Подумав, я тоже удивился насчет context switching. Но возможно причина в том, что это -- Ява. Вот та ссылка:

http://cselab.snu.ac.kr/member/naehyuck/papers/[J14]Comparative performance evaluation of Java threads for embedded applications.pdf

>> Что мешает сделать в ядре такие нити, чтобы никто больше не пытался их делать сам, "на коленке" ? > То, что для планирования по-любому придется делать вход/выход из ядра. И то, что планировщик ядра ничего не знает о специфике пользовательского приложения (например, очередях сообщений Эрланга), которая может учитываться при планировании userspace-планировшиком.

(мечта) А хорошо бы в планировщик ядра грузить кусочки своего кода... написанные на каком-нить тупом язычке, который не позволяет buffer overflow и качественно компилиться в асм...

... а еще язычок д.б. вообще без циклов -- чтобы еще он и гарантированно не зацикливался и заканчивался за заранее известное время.

> хорошо бы в планировщик ядра грузить кусочки своего кода...

IIRC, в Соляре дитсциплины планирования можно подгружать модулями.

> написанные на каком-нить тупом язычке, который не позволяет buffer overflow и качественно компилиться в асм...

Был такой проект на Cyclon.

> А еще ядерная нить обладает некоторым фиксированным оверхэдом, который может быть неприемлем.

А *почему* у зеленой нити без него можно обойтись, а в ядре -- нет?

> IIRC, в Соляре дитсциплины планирования можно подгружать модулями.

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

> Был такой проект на Cyclon.

Я несколько другое предложил -- *тупой* язык, т.е. даже не полный по тьюрингу, зато гарантированно заканчивающийся вовремя.

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

Та же STM - вполне маленькая. Вот тебе чуть-чуть упрощённый вариант:

Есть набор переменных в памяти. Для простоты будем считать, что все они - типа int.

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

Конкретнее, нужны следующие примитивы:

а) Прочитать данную переменную - на входе - какой-то идентификатор переменной, на выходе - значение.

б) Записать значение в данную переменную - на входе - идентификатор переменной и значение, на выходе - ничего.

в) Выполнить некое вычисление АТОМАРНО. То есть, внутри этого вычисления мы можем забыть о существовании других потоков, и ничего не сломается.

Ну, например (псевдокод):

atomically {c := read counter; write counter (c+1)}

При этом, если несколько потоков выполняют этот код одновременно, то счётчик будет увеличен на 1 столько раз, сколько раз код будет выполнен. Информация не должна теряться. Кроме того, не должны возникать взаимоблокировки.

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

STM эту задачу решает. Однако при этом возникает следующая вещь: вычисление внутри atomically может быть произведено несколько раз. Грубо говоря, STM перезапускает вычисление, если, производя запись в переменную, выясняет, что в эту переменную писал кто-то ещё. Если при этом сайд-эффектом вычисления является запуск ракет, то я не уверен, что повторение этого несколько раз - тот эффект, который нам нужен.

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

Типизированное лямбда-исчисление. Без игрек-комбинатора.

>> А еще ядерная нить обладает некоторым фиксированным оверхэдом, который может быть неприемлем.

> А *почему* у зеленой нити без него можно обойтись, а в ядре -- нет?

Ядро такое, какое оно есть. Если Линус сказал "мы создаем ядреный несвопабельный стек размером 1 страница", значит ядро буде его создавать. Если тебя это не устраивает - добро пожаловать в чудный зеленый мир %)

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

Я лично не вижу никаких препятствий. Кроме здравого смысла, конечно - зачем помещать такое в ядро? Ну а если уж очень надо, то для этого придуманы scheduler activations и прочие богомерзкие бздизвращения :)

> Типизированное лямбда-исчисление. Без игрек-комбинатора.

О типизации можно *ядру* не заботиться (нафиг эти сложности -- это дело программера и компилятора), и вообще на вход принимать чистый асм и *его* проверять на отсутствие джампов назад, коллов и т.п. -- что тривиально.

Коллы можно некоторые разрешить, например, "пройти по всему списку нитей и к каждому применить вот это: value=f(value,thread)"

> Ядро такое, какое оно есть. Если Линус сказал "мы создаем ядреный несвопабельный стек размером 1 страница", значит ядро буде его создавать. Если тебя это не устраивает - добро пожаловать в чудный зеленый мир %)

А может "добро пожаловать в мир написания ядерного модуля"? Что мне мешает *там* сделать нити с маленьким оверхедом?

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

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

> Я лично не вижу никаких препятствий. Кроме здравого смысла, конечно - зачем помещать такое в ядро?

Только что писали о том, что эрлангу это может пригодиться -- смотреть на длину очереди...

> Ну а если уж очень надо, то для этого придуманы scheduler activations и прочие богомерзкие бздизвращения :)

А в линуксе их нет, хотя бы модулями?

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

1. Время его завершения м.б. оценено константой (определяемой по коду)?

2. Его придется компилить чтобы верифицировать (или можно верифицировать сделаный из него асм + немного метаинфы)?

3. Есть ли готовые компиляторы?

> зачем помещать такое в ядро?

> Только что писали о том, что эрлангу это может пригодиться -- смотреть на длину очереди...

Зачем помещать это _в ядро_? Какой бенефит, кроме чудовищно раздувающихся очередей планировщика (оставим в стороне вопрос о ядерном стеке)? IIUC, в Эрланге процесс - главный (или единственный?) способ хранить состояние, поэтому ему нужно огромное количество процессов. Это не то, как предполагается использовать ядерные нити.

>> Ну а если уж очень надо, то для этого придуманы scheduler activations и прочие богомерзкие бздизвращения :)

> А в линуксе их нет, хотя бы модулями?

AFAIK, нет. Реализовать такое модулем довольно трудно - придется врезать вызовы userspace в код планировщика... исходя из того, что я читал, это очень трудно в случае линуксового планировщика. Кроме того, это против идеологии линуксового ядра - максимально заоптимизировать понятные вещи и не искать приключений на свою задницу.

> Время его завершения м.б. оценено константой (определяемой по коду)?

Естественно. Запустили код, померили время - вот тебе и константа.

> Его придется компилить чтобы верифицировать (или можно верифицировать сделаный из него асм + немного метаинфы)?

Запихиваем код в метаинфу...

> Есть ли готовые компиляторы?

Хэзе.

> Естественно. Запустили код, померили время - вот тебе и константа.

Нет, я спрашивал "а можно ли его время выполнения оценить константой, зависящей от кода, но не зависящей от исходных данных" ?

> STM эту задачу решает. Однако при этом возникает следующая вещь: вычисление внутри atomically может быть произведено несколько раз. Грубо говоря, STM перезапускает вычисление, если, производя запись в переменную, выясняет, что в эту переменную писал кто-то ещё. Если при этом сайд-эффектом вычисления является запуск ракет, то я не уверен, что повторение этого несколько раз - тот эффект, который нам нужен.

Я понял задачу. Посмотрю, можно ли на плюсах написать что-то похожее. Хотя есть замечания:

А если наш побочный эффект -- это не запуск ракет, а сбор статистики или отладка? (Как с этим в хаскеле?)

> Зачем помещать это _в ядро_? Какой бенефит, кроме чудовищно раздувающихся очередей планировщика (оставим в стороне вопрос о ядерном стеке)? IIUC, в Эрланге процесс - главный (или единственный?) способ хранить состояние, поэтому ему нужно огромное количество процессов.

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