Совместимость Haskell с использованием простого IORef?

Question

Я задавал несколько вопросов о параллелизме в Haskell, в частности TVar, и у меня были проблемы с livelock с TVar.

Вместо этого я предложил это решение.

(1) Оберните все общие данные в программу в одной структуре данных и оберните их в IORef. (2) Просто внесите любые изменения, используя atomicModifyIORef.

Я считаю, что это предотвращает как взаимные блокировки, так и livlocks (тогда как TVar предотвращает только первые). Кроме того, поскольку atomicModifyIORef просто связывает другой thunk в цепочку (которая представляет собой пару операций с указателем), это не шея бутылки. Все фактические операции над данными могут выполняться параллельно, если они не взаимно зависят друг от друга. Система исполнения Haskell будет работать именно так.

Я, однако, считаю, что это слишком просто. Есть ли какие-то «пропахи», которые я пропустил?

Answer 1

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

Answer 2

AFAICT Если ваши вычисления оставляют неузнанные thunks после того, как он делает свою вещь с содержимым IORef, то thunk будет просто оцениваться в любом потоке, который пытается использовать результат, а не оцениваться параллельно, как вам хотелось бы. См. Раздел gotchas от MVar docs, here

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

Answer 3

Эта конструкция, вероятно, будет хорошо, если выполняются следующие условия:

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

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

Ваш дизайн, как представляется, руководствуясь следующей цепочкой рассуждений:

1. atomicModifyIORef очень дешево, потому что он просто создает санки

2. потому что atomicModifyIORef дешево, это не будет вызывать нить

3. Недорогой доступ к данным + без конкуренции = параллелизм FTW!

Вот недостающий шаг в этом рассуждении: ваши IORef модификации только создавать санки, и вы не имеете никакого контроля над тем, где санками оцениваются. Если вы не можете контролировать, где данные оцениваются, у вас нет реального параллелизма.

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

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

Рассмотрим эти функции, предназначенные для изменения aVar :: IORef [Int]

doubleList1 :: [Int] -> ([Int],()) 
doubleList1 xs = (map (*2) xs,()) 

doubleList2 :: [Int] -> ([Int], [Int]) 
doubleList2 xs = let ys = map (*2) xs in (ys,ys) 

doubleList3 :: [Int] -> ([Int], Int) 
doubleList3 xs = let ys = map (*2) xs in (ys, sum ys) 

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

1. !() <- atomicModifyIORef aVar doubleList1 - только преобразователь создан, никакие данные не оценены. Неприятный сюрприз для любой темы, прочитанной от aVar.

2. !oList <- atomicModifyIORef aVar doubleList2 - новый список оценивается только до сих пор, чтобы определить начальный конструктор, то есть (:) или []. Все еще не было сделано никакой реальной работы.

3. !oSum <- atomicModifyIORef aVar doubleList3 - оценивая сумму списка, это гарантирует, что вычисление будет полностью оценено.

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

В третьем случае вы знаете, что работа была выполнена в заданной резьбе. Сначала создается thunk и обновляется IORef, затем поток начинает оценивать сумму и, наконец, возвращает результат. Но предположим, что какой-то другой поток считывает данные во время вычисления суммы. Он может начать оценивать сам кузнец, и теперь у вас есть два потока, делающих дублирующую работу.

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