It looks like the "FP languages' natural proficiency with multicores" is a new buzzphrase. hotgiraffe недавно постил ссылку на серию интервьюшек с создателями разных языков, где автор хаскеля честно признался, что это всё фигня, они пробовали и обнаружили предсказуемую проблему: fine grained parallelism sucks. Поэтому реально параллелится только эрланг, специально заточенный под это, да и то я на тесты не смотрел, например. А всё остальное -- химически чистое разведение руками.
Суха теория etc. Если в задаче связи тесные, то хрен чего напараллелишь. А если связи слабые, то параллелизуется лучше. От языка это зависит не так сильно, как от задачи.
Фишка не в том, что ФП параллелится автоматически, а в том, что оно параллелится ЛЕГЧЕ. И, скажем, для Хаскеля это так. Скажем, Control.Parallel.Strategies позволяет вообще написать алгоритм вычисления структуры отдельно, а порядок вычисления её - включая параллельное вычисление разных кусков - отдельно.
Подождите. С параллельными вычислениями есть две проблемы: они глючат и тормозят. Pure FP решает первую - глючить больше нечему.
Но разве это не получается ценой ещё более жутких тормозов? Если я пишу какой-нибудь Parallel.Foreach (из PLINQ, на который я глядел краем глаза когда-то), я могу оценить объём вычислений, который я пытаюсь распараллелить и объём каждого куска. А если оно всё ленивое, тогда как?
Плюс, там же ведь ещё дикие проблемы есть: вот возьмём например такое простое выражение list(i + 1 for i in range(10000) if not i % 1000) и запишем его функционально (как оно транслировалось бы из соответствующего LINQ в сишарпе, потому что в питоне не так): list(imap(ifilter(xrange(10000), lambda x: not x % 1000), lambda x: x + 1)) Как его параллелить? Легко видеть, что делать параллельный imap совершенно бессмысленно, равно как и параллельный ifilter, и тем более оба. По ходу следует трансформировать код: вместо pull из конвеера итераторов надо делать push в конвеер обработчиков (с проверкой того, что если результаты перестали быть нужны, надо прекращать, дискардя лишнее вычисленное) - и вот его-то параллелить. Я не знаю, как такая трансформация называется, кстати. Собственно, питон транслирует генератор как раз в что-то подобное - тупо в цикл, так что если б можно было распараллелить сам цикл, то получилось бы что надо. Если бы не то, что зачастую мы получаем итератор извне, а не используем свой range - тогда надо как-то более глобально трансформацию делать.
Итак, удивительное рядом: традиционный функциональный стиль с ленивыми итераторами оказывается вообще совершенно неприспособленным для параллелизма. По крайней мере в подобных часто встречающихся случаях. Одно это уже порождает дикие сомнения в обоснованности восторженности фанатов ФП.
Ну и ещё одно: я что-то дико сомневаюсь, что кроме увеличения числа ядер никаких других существенных изменений в архитектуре происходить не будет. Вот память, например - она же тормозит. Вычисление произведения больших матриц упирается в память уже на одноядернике даже без SSE, точнее, насколько я понимаю, там как раз очень милое совпадение импедансов. Надо бы ещё раз проверить как-нибудь. Условные переходы в более обычном коде тормозят проц, конечно - но и в память он залезает намного более причудливым образом. Очевидно, с этим тоже придётся что-то делать, причём тупо выдавать каждому ядру по большому личному кэшу нельзя - синхронизация всё сожрёт, если ядер много. Результаты-то и функциональному коду нужно куда-то записывать.
Короче говоря, я бы поставил на сравнительно крупные объекты, живущие в отдельных адресных пространствах (возможно виртуальных в смысле как это сделано в Сингулярити) и обменивающиеся мессагами.
> Если я пишу какой-нибудь Parallel.Foreach (из PLINQ, на который я глядел краем глаза когда-то), я могу оценить объём вычислений, который я пытаюсь распараллелить и объём каждого куска. А если оно всё ленивое, тогда как?
Э-э-э... Не въехал. Оценка сложности - это несколько другой коленкор, не связанный непосредственно с параллельностью.
> вот возьмём например такое простое выражение list(i + 1 for i in range(10000) if not i % 1000) и запишем его функционально
Опять не понял, это выражение вполне в функциональном стиле. Если я правильно понимаю питон (это ведь питон?), то это значит [i+1 | i <- [1..10000], i `mod` 1000 == 0]. Последнее - это чистый Хаскель. Что тут ещё переписывать?
> традиционный функциональный стиль с ленивыми итераторами
Я свой пример не продумал до конца, поэтому он показывает не совсем то, что мне хотелось. Попробую ещё раз, чётче.
Во-первых, я не знаю хаскеля =) Поэтому спорю с утверждением о том, что функциональность сама по себе позволяет легче параллелить программы - потому что от распараллеленной программы нам в первую очередь нужна повышенная эффективность, если повышения эффективности не будет, то наличие полученного "бесплатно" отсутствия race conditions не имеет никакого значения.
А с повышением эффективности есть проблемы:
Ленивые списки (они же итераторы - почему вы их концепцию не считаете функциональной?) самостоятельно не параллелятся. Чтобы перейти к следующему элементу нужно получить текущий. Чтобы распараллелить ленивый список нужно залезть ему внутрь или наоборот написать обёртку, где во время вычисления текущего элемента заранее вычислять и запоминать где-то следующие, причём не слишком увлекаясь - он же ленивым всё-таки должен оставаться.
Reduce (ака foldl) не параллелится (и я читал ту статью, далеко не все фолды можно превратить в ассоциативные операции). Ленивый filter не параллелится, потому что ленивый. Вообще ленивые структуры данных как правило самостоятельно не параллелятся, чтобы их распараллелить нужна реализованная внутри частичная неленивость.
Map может распараллелиться ровно настолько, к скольки элементам мы собираемся применять нашу функцию, глубже параллелизм сам по себе не пойдёт. То есть, о чём, я, собственно, и думал, когда писал пример: parallel_map(somefilteredlist, lambda x: x + 1) не даёт никакого выигрыша, если в списке после фильтрации осталось мало элементов, - более того, даёт жуткие затраты на порождение тредов и сбор результатов. Причём чем больше ядер, тем больше затраты! Независимо параллелить мап и фильтр вообще глупо, значит, нужно параллелить фильтр, вызывая мап из него, что в общем довольно непривычно выглядит - у нас же map(filter(...)).
Вообще попытка распараллелить любое что-нибудь, у чего мало элементов, приводит к затратам. Я дико сомневаюсь, что в какое-нибудь ближайшее время появится искуственный интеллект, который сможет сам предсказывать, где будет много элементов и где на вычисление одного элемента будет уходить много ресурсов - в случае ленивых структур нужно именно предсказывать, правда ведь? Поэтому нужен человек, который будет указывать компилятору, где и что следует параллелить - а если всё вокруг ленивое и вычисляется в самые неожиданные моменты, человеку это сделать весьма нелегко, и эта проблема имеет непосредственное отношение к распараллеливанию: повторюсь, если в результате распараллеливания программа начала работать медленнее, следует запускать её на одном ядре и не выпендриваться.
Вот как-то так. Я бы не говорил этого всего, если бы не то, что Саймон Пейтон-Джонс здесь после долгих рассуждений о безопасности чистых ФП прямо признаёт, что им как бы не удалось пока всё-таки сделать что-нибудь работающее на практике, подтвердив таким образом мои подозрения. Правда, он дальше говорит, что они сейчас изучают нечто под названием "nested data parallelism", но и оно пока далеко от реальности.
А я что сказал? Автоматически параллельность не достигается, да.
А что значит "списки параллелятся"? До сих пор я считал, что параллелится функция.
> жуткие затраты на порождение тредов и сбор результатов.
Не такие уж жуткие, кстати. Вон, эрланг нормально сотни тысяч тредов генерит, и работает шустро.
> нужен человек, который будет указывать компилятору, где и что следует параллелить
Так и работает, да.
> всё вокруг ленивое и вычисляется в самые неожиданные моменты
Второе из первого не следует, вообще-то.
> им как бы не удалось пока всё-таки сделать что-нибудь работающее на практике
И почему, спрашивается, вещи типа par и Control.Parallel.Strategies вполне себе работают. Он говорит, то же, что и я: автоматического параллелизма пока нет, но параллелить руками легче на порядок.
public static IEnumerable<int> Range(int count)
{
for (int i = 0; i < count; i++) yield return i;
}
public static IEnumerable<int> FilterOdd(this IEnumerable<int> lst)
{
foreach (var item in lst) if (item % 2 == 1) yield return i;
}
Я вот это имел в виду.
> А что значит "списки параллелятся"? До сих пор я считал, что параллелится функция. Ленивый список как бы является функцией, неправда ли? Ну, там, можно по-разному определять и всё такое, типа функция, возвращающая элемент и функцию, порождающую остаток списка, например. Поэтому элементы приходится получать последовательно, разве нет?
> Второе из первого не следует, вообще-то. > но параллелить руками легче на порядок. А можете показать решение такой задачи: вычисляется sha1 хэш от текущего времени, затем эн хэшей от стейта предыдущего и эн небольших строк. Распараллелить процесс так, чтобы первый хэш вычислился ровно один раз, затем остальные следующих параллельно. Я подозреваю что вам придётся совершать весьма нетривиальные телодвижения, чтобы не утянуть случайно первое вычисление за собой в треды.
Это вообще чего? Фразу "ленивые списки - это итераторы" я ещё могу как-то понять и выцепить из неё кусочек правды (только кусочек). Что этот кусок кода означает, в контексте нашей беседы, я совсем не рублю.
> Ленивый список как бы является функцией, неправда ли?
Ну вообще-то нет.
> эн хэшей от стейта предыдущего
От чего?
> и эн небольших строк.
Каких строк?
Похоже, что задача как раз на применение par, но я не до конца понял формулировку.
> Это вообще чего? Это итераторы. Или энумераторы, не знаю, есть ли разница. Первая функция возвращает объект, у которого есть метод MoveNext() и проперти Current. В результате последовательных вызовов MoveNext() (пока та возвращает true) проперти принимает значения последовательных натуральных чисел. То есть это типа ленивый список натуральных чисел - ленивый потому, что занимает константный объём памяти, независимо от значения count. Этот список можно скормить функции FilterOdd и она вернёт другой ленивый список, в котором лежат нечётные натуральные числа от 1 до count исключительно. Если б MoveNext возвращал итератор остатка списка, а не мутировал текущий, то был бы совсем настоящий ленивый список.
>> Ленивый список как бы является функцией, неправда ли? > Ну вообще-то нет. Почему же?
> я не до конца понял формулировку. ну как бы если sha1(string) возвращает иммутабельный объект-хэшер, умеющий в свою очередь возвращать новый хэшер при скармливании ему строки, или текущий дайджест, то я хочу увидеть распараллеливание следующего псевдокода:
let salt = sha1(currentTime) let d1 = salt("abc").digest let d2 = salt("cde").digest let d3 = salt("fgh").digest
> То есть это типа ленивый список натуральных чисел
Нет, это итератор по ним. Или энумератор, я тем более не в курсе.
> занимает константный объём памяти
Ленивый список НЕ ОБЯЗАТЕЛЬНО занимает константный объём памяти. МОЖЕТ занимать константный, а МОЖЕТ - и нет.
Простейший пример, на котором многие спотыкаются:
average xs = sum xs / length xs
Если сначала, например, вычислить сумму, то список - весь список - останется в памяти до начала вычисления длины.
В целом, итераторы - средство существенно более слабое, чем ленивые списки. На ленивых списках, например, вычисление чисел Хэмминга (тех, которые не делятся ни на какие простые, кроме 2, 3 или 5 - 1,2,3,4,5,6,8,9,10,12,15,...) делается в одну строчку, работает за линейное время и занимает линейный объём:
hammings = 1 : unfoldr (\xss -> let x = minimum (map head xss) in Just (x, map (dropWhile (x ==)) xss)) (map (\n -> map (n *) hammings) [2,3,5])
Как сделать что-то подобное на итераторах - не имею понятия.
> Почему же?
Потому что. Потому что, например, в вышеприведённом примере, если мы заменим везде списки на функции - время выполнения немедленно станет... хорошо если квадратичным, как бы там экспонента не нарисовалась.
> let salt = sha1(currentTime)...
Ну дык. Хаскель:
let salt = sha1 currentTime
d1 = salt "abc"
d2 = salt "cde"
d3 = salt "fgh"
in d1 `par` d2 `par` d3 `par` [d1,d2,d3]
Можно, подключив Control.Parallel.Strategies, сделать так:
let salt = sha1 currentTime
d1 = salt "abc"
d2 = salt "cde"
d3 = salt "fgh"
in [d1,d2,d3] `using` parList rwhnf
Про списки - ок, понял, был неправ. Впрочем, параллелиться их генерация от этого не начинает.
Про параллельное вычисление: насколько я понимаю, вы самое интересное-то не реализовали. Как сделать так, чтобы вычисление salt не произошло в тредах? Если, допустим, sha1 от строчки нашей длины вычисляется секунду (by design, чтобы затруднить брутфорс), я бы хотел, чтобы первую секунду работало одно ядро, потом ещё секунду - три.
> Как сделать так, чтобы вычисление salt не произошло в тредах?
В смысле, как сделать, чтобы оно не вычислялось несколько раз? Так и будет, здесь нечего реализовывать. При вычислении d[1-3] соответствующий тред увидит, что salt ещё недовычислено, что его вычисление уже идёт - и приостановится, поскольку без salt продолжать не может.
Это, конечно, если оптимизатор не сработает как надо и не отложит сам момент создания тредов.
Кстати, в последнем пункте я, конечно, хотел написать
let salt = sha1 currentTime in map salt ["abc", "cde", "fgh"] `using` parList rwhnf
> соответствующий тред увидит, что salt ещё недовычислено Это как? Включение этой библиотеки добавляет вообще к каждому стабу поле "вычисляется" и мьютекс для синхронизации? Если это так, то спасибо, такая многопоточность народу не нужна. Впрочем, вы смотрели в спецификацию или из общих соображений говорите?
> если оптимизатор не сработает как надо А откуда он вообще может знать, кому что нужно? А если эти треды из одного и того же ленивого списка данные берут? Вот правда, если у меня есть ленивый список этих самых чисел хоффмана и восемь тредов, в которых я считаю их суммы - в первом - просто, во втором - квадратов, в третьем - кубов и так далее, от первых элементов (с условием прекращения - пока сумма не станет больше миллиарда, чтобы компилятору точно пришлось задачу останова решать в общем случае. Как тогда? После вычисления очередного числа все треды просыпаются, обрабатывают одну итерацию и опять засыпают, пока один из них не посчитает следующее число и не разбудит оставшихся?
> Включение этой библиотеки добавляет вообще к каждому стабу поле "вычисляется"
Нет, конечно. Многопоточность - не та вещь, чтобы относить её реализацию в библиотеку. Она в компилятор встроена, а библиотеки содержат лишь несколько функций для использования этих возможностей компилятора.
> мьютекс для синхронизации
А зачем? Ситуация настолько проста, что мьютекс не нужен. Жизненный цикл любого значения - "не вычисляется" -> "вычисляется" -> "вычислено". Только в одну сторону. Зачем тут мьютекс?
> Впрочем, вы смотрели в спецификацию или из общих соображений говорите?
Читал статьи авторов GHC.
> А откуда он вообще может знать, кому что нужно?
Ну, в данном случае зависимость по данным довольно очевидна.
> После вычисления очередного числа все треды просыпаются, обрабатывают одну итерацию и опять засыпают, пока один из них не посчитает следующее число и не разбудит оставшихся?
Очень похоже на то. Простецкая параллелизация не срабатывает. Есть идея лучше?
> Она в компилятор встроена Вот у интерпретатора питона есть глобал интерпретер лок, который когда-то пытались убрать, но обнаружили, что в результате интерпретатор замедляется более чем в два раза на однопроцессорной машине, и решили пока не убирать. Например.
Не, я не хочу, не желаю верить в то, что у каждого thunk есть признак вычисленности специально для мультитредовости, который при каждом доступе специально обрабатывается нефиговой логикой, со спинлоком+syncronized xchg и прочими радостями. Работает же всё на фон-неймановской архитектуре, как бы любители ФП ни стремились забыть об этом.
Там же, кстати, дедлоки могут быть! Первый тред вычисляет один thunk, второй - другой, вдруг им обоим нужно поиспользовать друг-друга и привет! Следовательно, нужна вообще жуткая (и жутко тормозная) логика.
> Ну, в данном случае зависимость по данным довольно очевидна. А в общем случае сводится к решению проблемы останова.
> Есть идея лучше? Ну, я вижу три возможности.
Если всё так, как вы говорите, то функциональный язык Хаскель не предназначен для написания многопоточных программ.
Или мультитредовая библиотека использует замечательное свойство чисто-функционального языка и ничтоже сумняшеся перевычисляет те thunks, которые на момент обращения были невычислеными, результат-то не изменится.
Тогда где-то может быть специальная читерская монада, позволяющая зафорсить thunk (в лиспотерминах) (это не обычная монада - нам не просто порядок вычислений надо гарантировать, нам надо гарантировать, что вычисления _полностью_ случаться до того, как нам захочется посмотреть на результат из разных тредов), и правильные пацаны мучаясь и страдая применяют её ко всем параметрам той функции, которую они хотят распараллелить, фактически убивая ленивость. И изобретают совсем уж жуткие приспособления для мультитредовой обработки бесконечных ленивых списков. В таком случае функциональный язык хаскелль очень фигово приспособлен для написания многопоточных программ, почти совсем не приспособлен.
Либо же предлагается жрать что дают, то есть смириться с тем, что если удачно реализуется рейс-кондишен в сильно многопоточной программе, то она выполнится на восьми ядрах за то же время, что на одном, сожрав в процессе в восемь раз больше памяти и, кстати, дополнительно сколько-то времени на копирование этой памяти взад-вперёд. И функциональный язык Хаскель, таким образом, опять-таки не предназначен для написания многопоточных программ. QED.
PS: я не знаю, может быть они нашли какое-нибудь простое и красивое решение. Если да, хочу услышать, а нет -- ну, значит, нет.
> Не, я не хочу, не желаю верить в то, что у каждого thunk есть признак вычисленности специально для мультитредовости
Это, конечно, не так. Этот признак просто есть. Ну блин, надо же как-то отличать вычисленные значения от невычисленных, даже в однопоточной программе!
> который при каждом доступе специально обрабатывается нефиговой логикой
Да логика-то как раз очень простая! Такая вещь как вычисление некоторого значения ВООБЩЕ не попадёт в более чем один тред.
> Там же, кстати, дедлоки могут быть! Первый тред вычисляет один thunk, второй - другой, вдруг им обоим нужно поиспользовать друг-друга и привет! Следовательно, нужна вообще жуткая (и жутко тормозная) логика.
Да ни фига. Фишка в том, что если двум значениям надо использовать друг друга - то в программе циклическая зависимость, будь она мультитредной или однотредной! То есть, однотредная программа ЗАВИСНЕТ ТОЖЕ!
Разпараллелизация подобным образом СЕМАНТИКУ ПРОГРАММЫ НЕ МЕНЯЕТ!
> А в общем случае сводится к решению проблемы останова.
Да, конечно. А все вменяемые оптимизаторы занимаются частичным решением этой самой проблемы. В любом языке, не обязательно функциональном.
> Если всё так, как вы говорите, то функциональный язык Хаскель не предназначен для написания многопоточных программ.
Которые на нём отлично работают.
Контрольный пример:
fib 0 = 1 fib 1 = 1 fib n = let {a = fib (n-1); b = fib (n-2)} in a `par` b `par` (a+b)
Не обращайте внимание на глупость алгоритма, она намеренная, для демонстрации.
Так вот, разрешите такой программе использовать два проца - и скорость выполнения взлетает почти в два раза. Проверено.
> Или мультитредовая библиотека использует замечательное свойство чисто-функционального языка и ничтоже сумняшеся перевычисляет те thunks, которые на момент обращения были невычислеными, результат-то не изменится.
Это - вообще полный бред, перевычисление просто займёт лишнее время. А мультитредовость не в библиотеке сидит, а в компиляторе.
> если удачно реализуется рейс-кондишен в сильно многопоточной программе, то она выполнится на восьми ядрах за то же время, что на одном,
Естественно. А что, можно сделать иначе? Неважно, в функциональном языке или в императивном.
> дополнительно сколько-то времени на копирование этой памяти взад-вперёд.
> Да логика-то как раз очень простая! Если б логика была простая, написание многопоточных программ вообще не было бы проблемой. Вот считали мы из этого поля 0, "не вычислено", что дальше? Ведь в этот момент какой-то другой тред уже мог начать, а то и закончить вычисление. Поэтому на самом деле нужно доступиться к значению ещё раз, при помощи какой-нибудь инструкции вроде lock cmpxchg, которая сожрёт полтысячи тактов на прямой доступ к памяти, заблокировав на это время запись для всех остальных ядер, но присвоит туда единицу только если там по-прежнему ноль.
Это не то, чтобы ужас-ужас-ужас, нам ведь это только для невычисленных thunks делать надо, причём то же самое случится сразу после при выделении памяти из managed heap, но всё равно, затормаживать создание объектов ещё в два раза, особенно в языке с иммутабельностью, в котором оно случается часто, без надежды как-то хитроумно соптимизировать с выделением личного хипа каждому треду...
> однотредная программа ЗАВИСНЕТ ТОЖЕ Неа, однотредовая программа упадёт, а не зависнет, не правда ли?
> Не обращайте внимание на глупость алгоритма Не могу! Что он делает? Разве в хаскеле нет автоматической мемоизации? Если есть, то откуда ускорение? И почему для каждого значения заводятся _три_ параллельных потока (то есть два дополнительных)? Уж не потому ли, что reasoning о выполнении параллельных программ в ленивом языке настолько сложен, что даже в подобном тривиальном примере совершенно неочевидно, что одного дополнительного потока достаточно, и не понятно сразу, как сделать так, чтобы его действительно было достаточно?
> При помощи, например, комбинатора seq Ах, он всё-таки есть, значит, не всё потеряно.
Короче говоря, я ещё раз сформулирую мой поинт: если при написании программы придерживаться концепции о том, что она сама должна быть полностью понятна программисту, а не "тесты проходит - ну и отлично", то ленивость оказывается проблемой при распараллеливании. Потому что суть распараллеливания состоит в том, чтобы выделить какие-то приблизительно равные по сложности вычисления и запустить параллельно, а если сложность каждого конкретного вычисления оказывается секретной тайной, зависящей от миллиона нелокальных причин, то сделать это тяжело.
При том, что code-level parallelization вообще-то никому нафиг не нужен, особенно ручной, нужно параллелить высокоуровневые куски, причём сразу с рассчётом на то, что параллелиться они будут не на текущие четыре tightly coupled ядра, а практически на отдельные процессоры.
В таком случае во-первых никто не мешает убирать сайд-эффекты именно в этих высокоуровневых интерфейсах, как это вполне успешно делается уже лет десять в разнообразных ЭнтерпрайзЖаваБинах, во-вторых отсутствия сайд-эффектов оказывается _недостаточно_, потому как необходимо дополнительно контролировать объёмы и виды данных, передающихся между этими энтитями (что просто копируется, вместо чего передаётся прокси), в-третьих, ленивость (то есть практическая невозможность контролировать не только объёмы данных, но и объёмы вычислений) оказывается вообще злом.
> написание многопоточных программ вообще не было бы проблемой.
Мы вообще о чём говорим - о написании многопоточных программ, или о распараллеливании однопоточных? Это разные вещи.
> Неа, однотредовая программа упадёт, а не зависнет, не правда ли?
Может упасть, может зависнуть. Если бы она всегда падала, halting problem была бы решена давным-давно.
> Разве в хаскеле нет автоматической мемоизации?
Конечно, нет. Хотя бы потому, что а) хранить результаты всех предшествующих вычислений - глупо (далеко не факт, что они будут нужны), б) аргумент функции - не обязательно что-то столь же простое, как и число, и обнаружение того, что функция вызывается с тем же аргументом, что и раньше, равносильно решению той же halting problem.
Сделать свою мемоизацию, когда это нужно, в том варианте, который тебе нужен - практически тривиальная задача.
> И почему для каждого значения заводятся _три_ параллельных потока (то есть два дополнительных)?
Можно второй par заменить на seq, непринципиально. Потоки очень лёгкие, это вам не системные треды.
> Уж не потому ли
Нет. Скорее, потому, что заведение дополнительного потока - очень дешёвая операция.
> если сложность каждого конкретного вычисления оказывается секретной тайной
Не оказывается. Как правило, оценить сложность вычисления довольно просто.
> ленивость (то есть практическая невозможность контролировать не только объёмы данных, но и объёмы вычислений)
> Мы вообще о чём говорим - о написании многопоточных программ, или о распараллеливании однопоточных? Это разные вещи. О написании многопоточных, конечно!
> Может упасть, может зависнуть. Разве в однопоточной программе увидев на очередном необходимом танке тег "вычисляется" программа не должна тут же упасть со словами "я зациклилось"?
> нам надо гарантировать, что вычисления _полностью_ случаться до того, как нам захочется посмотреть на результат из разных тредов
А такого не бывает. И правильно не бывает, ленивость - она не зря ленивость, она по делу: некоторые значения вычислять не надо вообще, а часть из них (фишка ленивого языка!) в данных обстоятельствах вычислены быть не могут:
f x y z = if x then y else z -- определение функции f g x = f (x == 0) 0 (1/x) -- соответственно, определение g
В этом случае выражение "g 0" отлично отработает, несмотря на то, что по дороге возникнет выражение "1/0". Просто оно не будет вычислено.
Если же тебе вдруг кажется, что какие-то вещи надо вычислить до распараллеливания - нет проблем, напиши это явно. При помощи, например, комбинатора seq, или же соответствующей стратегией.
![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=91.7){kind=small}
ivan_gandhi's journal
Но разве это не получается ценой ещё более жутких тормозов? Если я пишу какой-нибудь Parallel.Foreach (из PLINQ, на который я глядел краем глаза когда-то), я могу оценить объём вычислений, который я пытаюсь распараллелить и объём каждого куска. А если оно всё ленивое, тогда как?
Плюс, там же ведь ещё дикие проблемы есть: вот возьмём например такое простое выражение list(i + 1 for i in range(10000) if not i % 1000) и запишем его функционально (как оно транслировалось бы из соответствующего LINQ в сишарпе, потому что в питоне не так): list(imap(ifilter(xrange(10000), lambda x: not x % 1000), lambda x: x + 1))
Как его параллелить? Легко видеть, что делать параллельный imap совершенно бессмысленно, равно как и параллельный ifilter, и тем более оба. По ходу следует трансформировать код: вместо pull из конвеера итераторов надо делать push в конвеер обработчиков (с проверкой того, что если результаты перестали быть нужны, надо прекращать, дискардя лишнее вычисленное) - и вот его-то параллелить. Я не знаю, как такая трансформация называется, кстати. Собственно, питон транслирует генератор как раз в что-то подобное - тупо в цикл, так что если б можно было распараллелить сам цикл, то получилось бы что надо. Если бы не то, что зачастую мы получаем итератор извне, а не используем свой range - тогда надо как-то более глобально трансформацию делать.
Итак, удивительное рядом: традиционный функциональный стиль с ленивыми итераторами оказывается вообще совершенно неприспособленным для параллелизма. По крайней мере в подобных часто встречающихся случаях. Одно это уже порождает дикие сомнения в обоснованности восторженности фанатов ФП.
Ну и ещё одно: я что-то дико сомневаюсь, что кроме увеличения числа ядер никаких других существенных изменений в архитектуре происходить не будет. Вот память, например - она же тормозит. Вычисление произведения больших матриц упирается в память уже на одноядернике даже без SSE, точнее, насколько я понимаю, там как раз очень милое совпадение импедансов. Надо бы ещё раз проверить как-нибудь. Условные переходы в более обычном коде тормозят проц, конечно - но и в память он залезает намного более причудливым образом. Очевидно, с этим тоже придётся что-то делать, причём тупо выдавать каждому ядру по большому личному кэшу нельзя - синхронизация всё сожрёт, если ядер много. Результаты-то и функциональному коду нужно куда-то записывать.
Короче говоря, я бы поставил на сравнительно крупные объекты, живущие в отдельных адресных пространствах (возможно виртуальных в смысле как это сделано в Сингулярити) и обменивающиеся мессагами.
Э-э-э... Не въехал. Оценка сложности - это несколько другой коленкор, не связанный непосредственно с параллельностью.
> вот возьмём например такое простое выражение list(i + 1 for i in range(10000) if not i % 1000) и запишем его функционально
Опять не понял, это выражение вполне в функциональном стиле. Если я правильно понимаю питон (это ведь питон?), то это значит [i+1 | i <- [1..10000], i `mod` 1000 == 0]. Последнее - это чистый Хаскель. Что тут ещё переписывать?
> традиционный функциональный стиль с ленивыми итераторами
А вот итератор - концепция не функциональная.
Я свой пример не продумал до конца, поэтому он показывает не совсем то, что мне хотелось. Попробую ещё раз, чётче.
Во-первых, я не знаю хаскеля =) Поэтому спорю с утверждением о том, что функциональность сама по себе позволяет легче параллелить программы - потому что от распараллеленной программы нам в первую очередь нужна повышенная эффективность, если повышения эффективности не будет, то наличие полученного "бесплатно" отсутствия race conditions не имеет никакого значения.
А с повышением эффективности есть проблемы:
Ленивые списки (они же итераторы - почему вы их концепцию не считаете функциональной?) самостоятельно не параллелятся. Чтобы перейти к следующему элементу нужно получить текущий. Чтобы распараллелить ленивый список нужно залезть ему внутрь или наоборот написать обёртку, где во время вычисления текущего элемента заранее вычислять и запоминать где-то следующие, причём не слишком увлекаясь - он же ленивым всё-таки должен оставаться.
Reduce (ака foldl) не параллелится (и я читал ту статью, далеко не все фолды можно превратить в ассоциативные операции). Ленивый filter не параллелится, потому что ленивый. Вообще ленивые структуры данных как правило самостоятельно не параллелятся, чтобы их распараллелить нужна реализованная внутри частичная неленивость.
Map может распараллелиться ровно настолько, к скольки элементам мы собираемся применять нашу функцию, глубже параллелизм сам по себе не пойдёт. То есть, о чём, я, собственно, и думал, когда писал пример: parallel_map(somefilteredlist, lambda x: x + 1) не даёт никакого выигрыша, если в списке после фильтрации осталось мало элементов, - более того, даёт жуткие затраты на порождение тредов и сбор результатов. Причём чем больше ядер, тем больше затраты! Независимо параллелить мап и фильтр вообще глупо, значит, нужно параллелить фильтр, вызывая мап из него, что в общем довольно непривычно выглядит - у нас же map(filter(...)).
Вообще попытка распараллелить любое что-нибудь, у чего мало элементов, приводит к затратам. Я дико сомневаюсь, что в какое-нибудь ближайшее время появится искуственный интеллект, который сможет сам предсказывать, где будет много элементов и где на вычисление одного элемента будет уходить много ресурсов - в случае ленивых структур нужно именно предсказывать, правда ведь? Поэтому нужен человек, который будет указывать компилятору, где и что следует параллелить - а если всё вокруг ленивое и вычисляется в самые неожиданные моменты, человеку это сделать весьма нелегко, и эта проблема имеет непосредственное отношение к распараллеливанию: повторюсь, если в результате распараллеливания программа начала работать медленнее, следует запускать её на одном ядре и не выпендриваться.
Вот как-то так. Я бы не говорил этого всего, если бы не то, что Саймон Пейтон-Джонс здесь после долгих рассуждений о безопасности чистых ФП прямо признаёт, что им как бы не удалось пока всё-таки сделать что-нибудь работающее на практике, подтвердив таким образом мои подозрения. Правда, он дальше говорит, что они сейчас изучают нечто под названием "nested data parallelism", но и оно пока далеко от реальности.
Э... Вот тут надо пояснить.
> самостоятельно не параллелятся.
А я что сказал? Автоматически параллельность не достигается, да.
А что значит "списки параллелятся"? До сих пор я считал, что параллелится функция.
> жуткие затраты на порождение тредов и сбор результатов.
Не такие уж жуткие, кстати. Вон, эрланг нормально сотни тысяч тредов генерит, и работает шустро.
> нужен человек, который будет указывать компилятору, где и что следует параллелить
Так и работает, да.
> всё вокруг ленивое и вычисляется в самые неожиданные моменты
Второе из первого не следует, вообще-то.
> им как бы не удалось пока всё-таки сделать что-нибудь работающее на практике
И почему, спрашивается, вещи типа par и Control.Parallel.Strategies вполне себе работают. Он говорит, то же, что и я: автоматического параллелизма пока нет, но параллелить руками легче на порядок.
Я вот это имел в виду.
> А что значит "списки параллелятся"? До сих пор я считал, что параллелится функция.
Ленивый список как бы является функцией, неправда ли? Ну, там, можно по-разному определять и всё такое, типа функция, возвращающая элемент и функцию, порождающую остаток списка, например. Поэтому элементы приходится получать последовательно, разве нет?
> Второе из первого не следует, вообще-то.
> но параллелить руками легче на порядок.
А можете показать решение такой задачи: вычисляется sha1 хэш от текущего времени, затем эн хэшей от стейта предыдущего и эн небольших строк. Распараллелить процесс так, чтобы первый хэш вычислился ровно один раз, затем остальные следующих параллельно. Я подозреваю что вам придётся совершать весьма нетривиальные телодвижения, чтобы не утянуть случайно первое вычисление за собой в треды.
Это вообще чего? Фразу "ленивые списки - это итераторы" я ещё могу как-то понять и выцепить из неё кусочек правды (только кусочек). Что этот кусок кода означает, в контексте нашей беседы, я совсем не рублю.
> Ленивый список как бы является функцией, неправда ли?
Ну вообще-то нет.
> эн хэшей от стейта предыдущего
От чего?
> и эн небольших строк.
Каких строк?
Похоже, что задача как раз на применение par, но я не до конца понял формулировку.
Это итераторы. Или энумераторы, не знаю, есть ли разница. Первая функция возвращает объект, у которого есть метод MoveNext() и проперти Current. В результате последовательных вызовов MoveNext() (пока та возвращает true) проперти принимает значения последовательных натуральных чисел. То есть это типа ленивый список натуральных чисел - ленивый потому, что занимает константный объём памяти, независимо от значения count. Этот список можно скормить функции FilterOdd и она вернёт другой ленивый список, в котором лежат нечётные натуральные числа от 1 до count исключительно. Если б MoveNext возвращал итератор остатка списка, а не мутировал текущий, то был бы совсем настоящий ленивый список.
>> Ленивый список как бы является функцией, неправда ли?
> Ну вообще-то нет.
Почему же?
> я не до конца понял формулировку.
ну как бы если sha1(string) возвращает иммутабельный объект-хэшер, умеющий в свою очередь возвращать новый хэшер при скармливании ему строки, или текущий дайджест, то я хочу увидеть распараллеливание следующего псевдокода:
let salt = sha1(currentTime)
let d1 = salt("abc").digest
let d2 = salt("cde").digest
let d3 = salt("fgh").digest
Нет, это итератор по ним. Или энумератор, я тем более не в курсе.
> занимает константный объём памяти
Ленивый список НЕ ОБЯЗАТЕЛЬНО занимает константный объём памяти. МОЖЕТ занимать константный, а МОЖЕТ - и нет.
Простейший пример, на котором многие спотыкаются:
average xs = sum xs / length xs
Если сначала, например, вычислить сумму, то список - весь список - останется в памяти до начала вычисления длины.
В целом, итераторы - средство существенно более слабое, чем ленивые списки. На ленивых списках, например, вычисление чисел Хэмминга (тех, которые не делятся ни на какие простые, кроме 2, 3 или 5 - 1,2,3,4,5,6,8,9,10,12,15,...) делается в одну строчку, работает за линейное время и занимает линейный объём:
Как сделать что-то подобное на итераторах - не имею понятия.
> Почему же?
Потому что. Потому что, например, в вышеприведённом примере, если мы заменим везде списки на функции - время выполнения немедленно станет... хорошо если квадратичным, как бы там экспонента не нарисовалась.
> let salt = sha1(currentTime)...
Ну дык. Хаскель:
let salt = sha1 currentTime d1 = salt "abc" d2 = salt "cde" d3 = salt "fgh" in d1 `par` d2 `par` d3 `par` [d1,d2,d3]Можно, подключив Control.Parallel.Strategies, сделать так:
let salt = sha1 currentTime d1 = salt "abc" d2 = salt "cde" d3 = salt "fgh" in [d1,d2,d3] `using` parList rwhnfПро параллельное вычисление: насколько я понимаю, вы самое интересное-то не реализовали. Как сделать так, чтобы вычисление salt не произошло в тредах? Если, допустим, sha1 от строчки нашей длины вычисляется секунду (by design, чтобы затруднить брутфорс), я бы хотел, чтобы первую секунду работало одно ядро, потом ещё секунду - три.
В смысле, как сделать, чтобы оно не вычислялось несколько раз? Так и будет, здесь нечего реализовывать. При вычислении d[1-3] соответствующий тред увидит, что salt ещё недовычислено, что его вычисление уже идёт - и приостановится, поскольку без salt продолжать не может.
Это, конечно, если оптимизатор не сработает как надо и не отложит сам момент создания тредов.
Кстати, в последнем пункте я, конечно, хотел написать
Это как? Включение этой библиотеки добавляет вообще к каждому стабу поле "вычисляется" и мьютекс для синхронизации? Если это так, то спасибо, такая многопоточность народу не нужна. Впрочем, вы смотрели в спецификацию или из общих соображений говорите?
> если оптимизатор не сработает как надо
А откуда он вообще может знать, кому что нужно? А если эти треды из одного и того же ленивого списка данные берут? Вот правда, если у меня есть ленивый список этих самых чисел хоффмана и восемь тредов, в которых я считаю их суммы - в первом - просто, во втором - квадратов, в третьем - кубов и так далее, от первых элементов (с условием прекращения - пока сумма не станет больше миллиарда, чтобы компилятору точно пришлось задачу останова решать в общем случае. Как тогда? После вычисления очередного числа все треды просыпаются, обрабатывают одну итерацию и опять засыпают, пока один из них не посчитает следующее число и не разбудит оставшихся?
Нет, конечно. Многопоточность - не та вещь, чтобы относить её реализацию в библиотеку. Она в компилятор встроена, а библиотеки содержат лишь несколько функций для использования этих возможностей компилятора.
> мьютекс для синхронизации
А зачем? Ситуация настолько проста, что мьютекс не нужен. Жизненный цикл любого значения - "не вычисляется" -> "вычисляется" -> "вычислено". Только в одну сторону. Зачем тут мьютекс?
> Впрочем, вы смотрели в спецификацию или из общих соображений говорите?
Читал статьи авторов GHC.
> А откуда он вообще может знать, кому что нужно?
Ну, в данном случае зависимость по данным довольно очевидна.
> После вычисления очередного числа все треды просыпаются, обрабатывают одну итерацию и опять засыпают, пока один из них не посчитает следующее число и не разбудит оставшихся?
Очень похоже на то. Простецкая параллелизация не срабатывает. Есть идея лучше?
Вот у интерпретатора питона есть глобал интерпретер лок, который когда-то пытались убрать, но обнаружили, что в результате интерпретатор замедляется более чем в два раза на однопроцессорной машине, и решили пока не убирать. Например.
Не, я не хочу, не желаю верить в то, что у каждого thunk есть признак вычисленности специально для мультитредовости, который при каждом доступе специально обрабатывается нефиговой логикой, со спинлоком+syncronized xchg и прочими радостями. Работает же всё на фон-неймановской архитектуре, как бы любители ФП ни стремились забыть об этом.
Там же, кстати, дедлоки могут быть! Первый тред вычисляет один thunk, второй - другой, вдруг им обоим нужно поиспользовать друг-друга и привет! Следовательно, нужна вообще жуткая (и жутко тормозная) логика.
> Ну, в данном случае зависимость по данным довольно очевидна.
А в общем случае сводится к решению проблемы останова.
> Есть идея лучше?
Ну, я вижу три возможности.
Если всё так, как вы говорите, то функциональный язык Хаскель не предназначен для написания многопоточных программ.
Или мультитредовая библиотека использует замечательное свойство чисто-функционального языка и ничтоже сумняшеся перевычисляет те thunks, которые на момент обращения были невычислеными, результат-то не изменится.
Тогда где-то может быть специальная читерская монада, позволяющая зафорсить thunk (в лиспотерминах) (это не обычная монада - нам не просто порядок вычислений надо гарантировать, нам надо гарантировать, что вычисления _полностью_ случаться до того, как нам захочется посмотреть на результат из разных тредов), и правильные пацаны мучаясь и страдая применяют её ко всем параметрам той функции, которую они хотят распараллелить, фактически убивая ленивость. И изобретают совсем уж жуткие приспособления для мультитредовой обработки бесконечных ленивых списков. В таком случае функциональный язык хаскелль очень фигово приспособлен для написания многопоточных программ, почти совсем не приспособлен.
Либо же предлагается жрать что дают, то есть смириться с тем, что если удачно реализуется рейс-кондишен в сильно многопоточной программе, то она выполнится на восьми ядрах за то же время, что на одном, сожрав в процессе в восемь раз больше памяти и, кстати, дополнительно сколько-то времени на копирование этой памяти взад-вперёд. И функциональный язык Хаскель, таким образом, опять-таки не предназначен для написания многопоточных программ. QED.
PS: я не знаю, может быть они нашли какое-нибудь простое и красивое решение. Если да, хочу услышать, а нет -- ну, значит, нет.
Это, конечно, не так. Этот признак просто есть. Ну блин, надо же как-то отличать вычисленные значения от невычисленных, даже в однопоточной программе!
> который при каждом доступе специально обрабатывается нефиговой логикой
Да логика-то как раз очень простая! Такая вещь как вычисление некоторого значения ВООБЩЕ не попадёт в более чем один тред.
> Там же, кстати, дедлоки могут быть! Первый тред вычисляет один thunk, второй - другой, вдруг им обоим нужно поиспользовать друг-друга и привет! Следовательно, нужна вообще жуткая (и жутко тормозная) логика.
Да ни фига. Фишка в том, что если двум значениям надо использовать друг друга - то в программе циклическая зависимость, будь она мультитредной или однотредной! То есть, однотредная программа ЗАВИСНЕТ ТОЖЕ!
Разпараллелизация подобным образом СЕМАНТИКУ ПРОГРАММЫ НЕ МЕНЯЕТ!
> А в общем случае сводится к решению проблемы останова.
Да, конечно. А все вменяемые оптимизаторы занимаются частичным решением этой самой проблемы. В любом языке, не обязательно функциональном.
> Если всё так, как вы говорите, то функциональный язык Хаскель не предназначен для написания многопоточных программ.
Которые на нём отлично работают.
Контрольный пример:
fib 0 = 1
fib 1 = 1
fib n = let {a = fib (n-1); b = fib (n-2)} in a `par` b `par` (a+b)
Не обращайте внимание на глупость алгоритма, она намеренная, для демонстрации.
Так вот, разрешите такой программе использовать два проца - и скорость выполнения взлетает почти в два раза. Проверено.
> Или мультитредовая библиотека использует замечательное свойство чисто-функционального языка и ничтоже сумняшеся перевычисляет те thunks, которые на момент обращения были невычислеными, результат-то не изменится.
Это - вообще полный бред, перевычисление просто займёт лишнее время. А мультитредовость не в библиотеке сидит, а в компиляторе.
> если удачно реализуется рейс-кондишен в сильно многопоточной программе, то она выполнится на восьми ядрах за то же время, что на одном,
Естественно. А что, можно сделать иначе? Неважно, в функциональном языке или в императивном.
> дополнительно сколько-то времени на копирование этой памяти взад-вперёд.
А это-то с чего?
Если б логика была простая, написание многопоточных программ вообще не было бы проблемой. Вот считали мы из этого поля 0, "не вычислено", что дальше? Ведь в этот момент какой-то другой тред уже мог начать, а то и закончить вычисление. Поэтому на самом деле нужно доступиться к значению ещё раз, при помощи какой-нибудь инструкции вроде lock cmpxchg, которая сожрёт полтысячи тактов на прямой доступ к памяти, заблокировав на это время запись для всех остальных ядер, но присвоит туда единицу только если там по-прежнему ноль.
Это не то, чтобы ужас-ужас-ужас, нам ведь это только для невычисленных thunks делать надо, причём то же самое случится сразу после при выделении памяти из managed heap, но всё равно, затормаживать создание объектов ещё в два раза, особенно в языке с иммутабельностью, в котором оно случается часто, без надежды как-то хитроумно соптимизировать с выделением личного хипа каждому треду...
> однотредная программа ЗАВИСНЕТ ТОЖЕ
Неа, однотредовая программа упадёт, а не зависнет, не правда ли?
> Не обращайте внимание на глупость алгоритма
Не могу! Что он делает? Разве в хаскеле нет автоматической мемоизации? Если есть, то откуда ускорение? И почему для каждого значения заводятся _три_ параллельных потока (то есть два дополнительных)? Уж не потому ли, что reasoning о выполнении параллельных программ в ленивом языке настолько сложен, что даже в подобном тривиальном примере совершенно неочевидно, что одного дополнительного потока достаточно, и не понятно сразу, как сделать так, чтобы его действительно было достаточно?
> При помощи, например, комбинатора seq
Ах, он всё-таки есть, значит, не всё потеряно.
Короче говоря, я ещё раз сформулирую мой поинт: если при написании программы придерживаться концепции о том, что она сама должна быть полностью понятна программисту, а не "тесты проходит - ну и отлично", то ленивость оказывается проблемой при распараллеливании. Потому что суть распараллеливания состоит в том, чтобы выделить какие-то приблизительно равные по сложности вычисления и запустить параллельно, а если сложность каждого конкретного вычисления оказывается секретной тайной, зависящей от миллиона нелокальных причин, то сделать это тяжело.
При том, что code-level parallelization вообще-то никому нафиг не нужен, особенно ручной, нужно параллелить высокоуровневые куски, причём сразу с рассчётом на то, что параллелиться они будут не на текущие четыре tightly coupled ядра, а практически на отдельные процессоры.
В таком случае во-первых никто не мешает убирать сайд-эффекты именно в этих высокоуровневых интерфейсах, как это вполне успешно делается уже лет десять в разнообразных ЭнтерпрайзЖаваБинах, во-вторых отсутствия сайд-эффектов оказывается _недостаточно_, потому как необходимо дополнительно контролировать объёмы и виды данных, передающихся между этими энтитями (что просто копируется, вместо чего передаётся прокси), в-третьих, ленивость (то есть практическая невозможность контролировать не только объёмы данных, но и объёмы вычислений) оказывается вообще злом.
Мы вообще о чём говорим - о написании многопоточных программ, или о распараллеливании однопоточных? Это разные вещи.
> Неа, однотредовая программа упадёт, а не зависнет, не правда ли?
Может упасть, может зависнуть. Если бы она всегда падала, halting problem была бы решена давным-давно.
> Разве в хаскеле нет автоматической мемоизации?
Конечно, нет. Хотя бы потому, что а) хранить результаты всех предшествующих вычислений - глупо (далеко не факт, что они будут нужны), б) аргумент функции - не обязательно что-то столь же простое, как и число, и обнаружение того, что функция вызывается с тем же аргументом, что и раньше, равносильно решению той же halting problem.
Сделать свою мемоизацию, когда это нужно, в том варианте, который тебе нужен - практически тривиальная задача.
> И почему для каждого значения заводятся _три_ параллельных потока (то есть два дополнительных)?
Можно второй par заменить на seq, непринципиально. Потоки очень лёгкие, это вам не системные треды.
> Уж не потому ли
Нет. Скорее, потому, что заведение дополнительного потока - очень дешёвая операция.
> если сложность каждого конкретного вычисления оказывается секретной тайной
Не оказывается. Как правило, оценить сложность вычисления довольно просто.
> ленивость (то есть практическая невозможность контролировать не только объёмы данных, но и объёмы вычислений)
Это ложь.
О написании многопоточных, конечно!
> Может упасть, может зависнуть.
Разве в однопоточной программе увидев на очередном необходимом танке тег "вычисляется" программа не должна тут же упасть со словами "я зациклилось"?
> Это ложь.
ок!
А такого не бывает. И правильно не бывает, ленивость - она не зря ленивость, она по делу: некоторые значения вычислять не надо вообще, а часть из них (фишка ленивого языка!) в данных обстоятельствах вычислены быть не могут:
f x y z = if x then y else z -- определение функции f
g x = f (x == 0) 0 (1/x) -- соответственно, определение g
В этом случае выражение "g 0" отлично отработает, несмотря на то, что по дороге возникнет выражение "1/0". Просто оно не будет вычислено.
Если же тебе вдруг кажется, что какие-то вещи надо вычислить до распараллеливания - нет проблем, напиши это явно. При помощи, например, комбинатора seq, или же соответствующей стратегией.
ветер. это - ветер.
> Это итераторы. Или энумераторы, не знаю, есть ли разница.
To understand iterators we first need to understand enumerators.