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

Question

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

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

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

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

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

Однако я чувствую, что это слишком просто. Есть ли какие-то "ошибки", которые я пропустил?

1

haskell concurrency design ioref shared-state

Источник

user525980 12 апр '12 в 00:12

3 ответа

Другие вопросы по тегам haskell concurrency design ioref shared-state

user370541 12 апр '12 в 10:11 2012-04-12 10:11 · Answer 1 · 2012-04-12 10:11

Этот дизайн, вероятно, будет в порядке, если верно следующее:

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

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

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

atomicModifyIORef это очень дешево, потому что это просто создает гром
так как atomicModifyIORef дешево, это не приведет к конфликту потоков
Дешевый доступ к данным + нет конкуренции = параллелизм 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)

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

!() <- atomicModifyIORef aVar doubleList1 - создается только thunk, данные не оцениваются. Неприятный сюрприз для того, кто читает ветку aVar Следующий!
!oList <- atomicModifyIORef aVar doubleList2 - новый список оценивается только настолько, чтобы определить начальный конструктор, то есть (:) или же [], Тем не менее никакой реальной работы не было сделано.
!oSum <- atomicModifyIORef aVar doubleList3 - оценивая сумму списка, это гарантирует, что вычисление будет полностью оценено.

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

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

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

user690385 12 апр '12 в 00:19 2012-04-12 00:19 · Answer 2 · 2012-04-12 00:19

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

user176841 12 апр '12 в 02:11 2012-04-12 02:11 · Answer 3 · 2012-04-12 02:11

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

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