откуда у параллелизма ноги

[sassa_nf]

В императивных языках учитывается модель памяти. Это такая вещь, которая приводит в соответствие program order и platform memory order.

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

Comments

[juan-gandhi.livejournal.com]

:) ну это если декларативно, не специфицируя порядок вычислений.

[nponeccop.livejournal.com]

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

[juan-gandhi.livejournal.com]

Да уж пожалуйста, как говорит моя соседка по дивану.

[sassa-nf.livejournal.com]

ну я озадачен. В том смысле, в каком рассуждают о program order в, скажем, Java, у хаскелла вроде бы order нет. Это понятно, что есть порядок, заданный зависимостями данных.

Ну ещё есть вариант, что я термином злоупотребляю :)

После нескольких лет ковыряния в concurrency, смотрел на хаскелл и недоумевал - а какие вычисления будут гарантированно видимы, если, там, какой-то архитектурный барьер (ну, tvar или чё там есть - я ещё не дочитал). Потому что в Java вот есть program order, и трюк заключается в умышленном ordering каких-то вычислений по одну сторону барьера, а других - по другую сторону. В хаскелле нет такого же program order (programmer intended order; ну, или пора тогда вам все-таки разъяснительную работу провести :)).

Конечно, ленивые вычисления внутри реализованы на мутабельности, но её монотонность помогает контроллировать гонки (thunk -> value). Расстановка барьеров и порядок скедюлинг становится полностью задачей компилятора и (green thread) скедюлера. Поскольку нет программно заданных барьеров, это и хорошо (можно бить, где хочешь), и плохо (приходится заниматься микро-синхронизацией). Вот это вот "плохо" - очень сложная задача; статья 2005 года как бы намекает, что они не берутся за weaker memory platforms, ибо только на TSO существует дешёвый способ делать тот вид микро-синхронизации (racy publishing). Но я всеми руками за "хорошо": нет program order - невозможно допустить concurrency ошибку.

[nponeccop.livejournal.com]

Хехе, мое предположение выше оказалось верным.

Это популярное заблуждение, что в хаскеле "есть порядок, заданный зависимостями данных". В хаскеле совершенно нормальный program order, заданный точно так же статически синтаксической структурой программы, как и в любых других языках.

Источник заблуждения я не так давно обнаружил - это пейпер аж 1976 года, "A lazy evaluator" by Henderson and Morris, POPL'76. Во всяком случае, более ранние упоминания мне неизвестны.

Вот моя попытка как-то объяснить, что происходит http://stackoverflow.com/a/8012765/805266 , но на самом деле конечно you need to learn the precise semantics - just learning a metaphor doesn't let you understand the details.

[sassa-nf.livejournal.com]

Ну пока я не обнаружил противоречия ни с layman definition, ни со своим пониманием его. Я понимаю, что data dependency не означает, что f([1..10]) требует вычисления всего списка. На пальцах data dependency в этом случае требует создания объекта список, но не объявлена dependency от значений элементов. Какие значения элементов вычислять - это определяется способом использования списка; например, data dependency от элемента появляется, когда из списка изымается элемент, но минимально требуется зависимость только от того одного элемента. Реализация или специализация списка может зависеть, а может и не зависеть от вычисления других элементов списка.

Щас проверим. Пример с (map (+1) [1..10]) !! 6 - он такой точно как и [1..10] !! 6. Случай с map отличается не mapом, а списком. Во втором случае список Integer, а в первом случае - список результатов (_ + 1). В первом случае "вычисление" закончилось тем, что сконструировало thunk для вычисления (_ + 1) для первых 5 элементов и вычислило значение из thunk одного элемента, который мы изымаем. Но! при этом значения списка [1..10] вычислены точно столько же, как и во втором случае.

Что я имею в виду иллюстрируется продолжением вашего эксперимента на stackoverflow:

Prelude> let l = [1..10]
Prelude> :print l
l = (_t1::[Integer])
Prelude> let m = map (+1) l
Prelude> :print m
m = (_t2::[Integer])
Prelude> m !! 6
8
Prelude> :print m
m = (_t3::Integer) : (_t4::Integer) : (_t5::Integer) :
    (_t6::Integer) : (_t7::Integer) : (_t8::Integer) : 8 :
    (_t9::[Integer])
Prelude> :print l
l = 1 : 2 : 3 : 4 : 5 : 6 : 7 : (_t10::[Integer])

- да, как вы и демонстрируете, список значений m вычислился только частично. Но список значений l тоже вычислился, и вычислился до той же степени, как и в случае с просто [1..10] !! 6. Вот это, второе, и есть неочевидное, не контролируемое с точки зрения пользователя функции, поведение. Его-то и не нужно контролировать, но именно этот момент и является трудным для execution order control freaks, которыми люди становятся после серьёзных concurrency проблем в императиве. :)


Я вижу большую разницу между f([1..10]) в eager вычислении и f([1..10]) в ленивом. В том-то и штука, что при eager вычислении если после f поставить барьер, не зависимо от операций внутри f, вычисленным (и видимым) будет весь список; а при lazy вычислении нельзя сказать о вычисленной (а потому видимой) части списка ничего.

[nponeccop.livejournal.com]

Пример приведён не как объяснение ленивости, а как ответ на конкретный вопрос. То, что вы понимаете пример, не значит, что вы понимаете ленивость. То, что вы не понимаете сути происходящего, следует из неправильных выводов, которые вы делаете.

[sassa-nf.livejournal.com]

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

[nponeccop.livejournal.com]

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

[sassa-nf.livejournal.com]

Если чо, я ж почитал кусок книжки SPJ про реализацию языков. Классное чтиво, легко и непринуждённо надевается на голову - страница 409 и далее, где-то 30 страниц всего. Есть necessary computation (вычислить только один элемент списка), и есть speculative computation (а вдруг нам понадобится и 10-й элемент), как угадать, трудности с выделением enough parallelism, и т.д. Да, 1987-й год был давно, но чтиво как раз самое оно, самое что ни на есть введение в проблему и интересные направления оптимизации.

[nponeccop.livejournal.com]

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

Мне важно знать степень владения не для повышения ЧСВ, а для того, чтобы понять, поймёте ли вы мои развёрнутые ответы или нет, и не тратить зря свое и ваше время.

[sassa-nf.livejournal.com]

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

[sassa-nf.livejournal.com]

само собой.

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

[nponeccop.livejournal.com]

Это не так. Порядок не имеет значения не из-за ленивости, а из-за, хм, чёрч-россеровости нетипизированного лямбда-исчисления с WHNF. Стимулирует повышение паралеллизма чистота, возникающая из-за иммутабельности, чёрч-россеровости, ссылочной прозрачности и других факторов. В ленивых вычислениях необходима чёрч-россеровость, чтобы семантика кода не менялась от статического контекста, в который он синтаксически вложен, иначе неудобно. В хаскеле придумали (посредством монад, но существуют и др. решения), как сохранить чёрч-россеровость при наличии мутабельности.

Как-то так.

[sassa-nf.livejournal.com]

Я не пойму, на параллелизм влияет что-либо, кроме разрешения reordering вычислений? Можно ли сказать тогда, что ленивость - это предел разрешения reordering? Такая вот самая obvious фича, которая составляет самый relaxed порядок из partial order вычислений.

Чистота, чёрч-россеровость, ссылочная прозрачноть тоже попадалось в списке похвал функциональщине, но я пока не понял, как это сочетается с линеаризацией.

Я на академичность не претендую, но очень польщён просвещением.

[nponeccop.livejournal.com]

> Можно ли сказать тогда, что ленивость - это предел разрешения reordering?

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

Пределом разрешения reordering является сильная нормализация, которой даже в хаскеле нет, но есть в агде2. В хаскеле есть всего лишь чёрч-россеровость, более слабая форма reordering. Императивные языки тоже допускают reordering, но в ещё более слабой форме.

Расширенные возможности по reordering - это свойство чистых программ, а не ленивых. Скажем, mapreduce допускает реордеринг.

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

Исполнять редукции выгоднее всего в аппликативном ("неленивом"), а не в нормальном ("ленивом") порядке, поэтому компилятор хаскеля пробует заменять порядок редукции на аппликативный, где это увеличит скорость, не раздует потребление памяти и не приведёт к зацикливаниям. Все эти анализы неразрешимы (как следствие - неполны) и являются оптимизациями (не могут ухудшить потребление ресурсов по сравнению с нормальным порядком), так что для 99% практических нужд можно считать, что программы на хаскеле исполняются в фиксированном нормальном порядке.

Иммутабельность способствует чистоте (и реордерингу), но возможна чистота вместе с мутабельностью (IORef в хаскеле).

К паралеллизму всё вышесказанное имеет, однако, весьма косвенное отношение.

Для паралеллизма важно, чтобы все программы из threads interleaving space имели одну и ту же семантику. Этому как раз способствует immutability. Если вы будете в хаскеле использовать IORefs (чистота без immutability) многопоточно, то получите по голове теми же проблемами с изменением семантики в зависимости от интерливинга, что и в императивных программах.

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

[thesz.livejournal.com]

>Ленивость как таковая вообще не допускает reordering.

Допускает. Это вот normal order evaluation не допускает ("всегда внутренний левый"), а lazy evaluation (graph reduction) допускает.

[nponeccop.livejournal.com]

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

Общепринято считать семантикой функциональной части хаскеля call by need lambda calculus with whnf (формально это другое исчисление по сравнению с call by need lambda calculus with nf), а семантикой императивной - семантику из tackling the squad.

Lazy evaluation и call by need lambda calculus - это одно и то же. "Normal order reduction" - это call by name lambda calculus.

Системы редукции графов могут быть использована как формализм (clean), так и как средство реализации call by need (haskell). Общепринято как раз считать редукцию графов деталью реализации ghc. Call by need прекрасно описывается через дырки (evaluation contexts) безо всяких графов или через interaction nets, которые, насколько мне известно, не являются TGRS в общепринятом смысле.

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

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

Можно спросить в кафе, пусть нас рассудят :)

[sassa-nf.livejournal.com]

"Для паралеллизма важно, чтобы все программы из threads interleaving space имели одну и ту же семантику."

о. вот это и есть linearizability.


"Компилятор может слегка отклоняться от порядка, предписываемого ленивостью"

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

В частности, в разделе проблем обсуждаются вопросы "как не засорить память промежуточными данными, которые потребитель не успевает проглотить". Я это воспринял как отсутствие ограничения на порядок исполнения, и лишь как оптимизацию.

Или в каком смысле тогда порядок предписан?


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


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

Ага, хорошо. Агду пока страшно :)

Тогда этот пост о том, что я обнаружил, что reordering в хаскеле > reordering в императиве.


Ну, и спасибо за экскурс. Теперь понятно, почему никто не мог ответить "какая в хаскелле модель памяти?" - потому что на самом деле нужно искать литературу по чёрч-россеровости и сильным норальным формам.

[nponeccop.livejournal.com]

> нужно искать литературу по чёрч-россеровости
> и сильным норальным формам.

Ищите литературу по strictness analysis - это часть оптимизатора, которая решает, что можно переставлять, а что нельзя. Возможно, там будет менее академическим языком описано то, что вы ищете.

[nponeccop.livejournal.com]

> Blackholing - это, конечно, всего-лишь
> реализация концепции не-повторения вычислений.

Тут важно, что ленивостью предписано, в каких случаях вычисления повторяются, а в каких нет. Это не "автоматическая дедупликация всего", а жесткие и очень примитивные синтаксические правила, вроде того как в Си жестко задано, что longFunction в int x = longFunction(); for (;;) { }; вычисляется один раз если снаружи цикла, и столько раз сколько отрабатывает цикл, если внутри.

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

Да, для тонкого управления есть strictness annotations, и в высокопроизводительном коде приходится подсказывать компилятору.

[nponeccop.livejournal.com]

> я обнаружил, что reordering в
> хаскеле > reordering в императиве.

Ага. Но не по той причине, и к паралеллизму не относится.

> Теперь понятно, почему никто не мог ответить
> "какая в хаскелле модель памяти?"

Система типов позволяет реализовывать произвольные модели памяти, и есть достаточно много разных библиотек с разными моделями:

http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_and_parallelism

Есть все традиционные и все экзотические модели :)

Наиболее интересные на мой взгляд - это

Cloud Haskell
Software Transactional Memory
CHP: Communicating Haskell Processes
Repa

[nponeccop.livejournal.com]

> о. вот это и есть linearizability

Это называется serializability (of interleaving).

> Или в каком смысле тогда порядок предписан?

В таком же смысле, в каком он предписан в императивных языках. Если вы пишете

x = 5;
y = 6;
return x;


То предписано, что сначала делается x = 5, потом y = 6, потом return x.

Но если компилятор может доказать, что перестановка ничего не меняет - то он может всё попересталять:

return 5;
y = 6;
x = 5;

Но от этого никто не говорит, что в императивных программах порядок выполнения не определён :) И при написании программы рассуждает так, как будто порядок именно такой, как он написал и не рассматривает всевозможные эквивалентные порядки.

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

При оценке потребления ресурсов конечно приходится думать о порядке, но в 99% случаев считаешь, что порядок нормальный, и только в 1% надо пускать профайлер или смотреть в генерируемый код, чтобы узнать реальный порядок.

[sassa-nf.livejournal.com]

"Это называется serializability (of interleaving)."

здесь пересечение терминологии, по-видимому. Я о линеаризации в смысле как здесь: Linearizability: A Correctness Condition for Concurrent Objects, M. Herlihy and J.Wing, Proceedings of 14th ACM Symposium on Principles of Programming Languages, 1987


"Но от этого никто не говорит, что в императивных программах порядок выполнения не определён :) И при написании программы рассуждает так, как будто порядок именно такой, как он написал и не рассматривает всевозможные эквивалентные порядки."

Да, понятный пример. Тогда да, я думаю лишь о реализации, дающей результат, эквивалентный какому-то там каноническому, который я ещё не изучал.

[sassa-nf.livejournal.com]

А каким боком чёрч-россеровость к параллелизму? "Отклоняться от порядка редукций" всё-таки говорит о _порядке_ редукций, коего у параллельного graph reduction как бы и нет. Кто-то где-то должен был бы доказать параллельную теорему Чёрча-Россера :)

[nponeccop.livejournal.com]

> А каким боком чёрч-россеровость к параллелизму?

Никаким. Я же так и писал - "весьма косвенное отношение".

"Отклоняться от порядка редукций" ничего не значит, т.к. это нестрогая формулировка, объяснение на пальцах. Ознакомьтесь со строгой версией.

http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting - 3 глава про системы перезаписи графов, и 5 глава про concurrency. У пиратов есть в пдф одним куском.

Но это очень маленький кусочек необходимых знаний, если хотите глубоко копать. Например, вам должна стать непонятной связь FGRS и лямбда-исчисления. Вас должно запутать, что G-machine - это не реализация FGRS.

См. также
- The Call-by-Need Lambda Calculus by John Maraist, Martin Odersky, Philip Wadler;
- http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/ (4 глава)
- http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3918

и т. д.

Ещё учтите, что Parallelism != Concurrency и tackling the squad посвящён concurrency, а вы говорите именно о паралеллизме. И MPI is all about parallelism, but Erlang is all about concurrency.

Отвечая непосредственно на ваш вопрос - есть теоремы о возможности параллельных редукций с сохранением семантики.

[sassa-nf.livejournal.com]

ой, какая замечательная книжка!

[nponeccop.livejournal.com]

Я начинал с сикпа и с неё

[nponeccop.livejournal.com]

Мы тут ещё забыли "побочные эффекты". Это ещё отдельное понятие, которое не нужно путать с чистотой, ссылочной прозрачностью, функциональностью, иммутабельностью и другими похожими понятиями :)

Так вот, я придумал как перевести исходный текст поста на нормальный язык. Будет так:

В программах с побочными эффектами при параллелизации приходится учитывать эти эффекты.

Программы без эффектов хорошо параллелизируются, ибо в них отсутствуют эти самые эффекты.

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

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

Важна

а) возможность писать программы, доказуемо не имеющие эффектов
б) экономическая целесообразность писать большие программы доказуемо без эффектов

Пункт б) как раз в Хаскеле подкреплен ленивостью, чистотой, немутабельностью, типизированностью, выводом типов и другими полезными фишками. Но именно что "подкреплён". Основное - это пункт а)