Блог

Я пытаюсь следить за реализацией проблемы обратного отсчета, показанной в этом видео (https://www.youtube.com/watch?v=rlwSBNI9bXE amp;) и я подумал, что было бы неплохо попробовать работать параллельно?

 data Op =
    Add
  | Sub
  | Mul
  | Div deriving (Eq)

data Expr = 
    Val Int 
  | App Op Expr Expr

--{ helper functions }  

solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
  [e | ns' <- choices ns, (e, m) <- results ns', m == n]
 

Я попытался следовать некоторым другим сообщениям о том, как это сделать, и придумал что-то вроде этого

 instance NFData Op where
  rnf Add = Add `deepseq` ()
  rnf Sub = Sub `deepseq` ()
  rnf Mul = Mul `deepseq` ()
  rnf Div = Div `deepseq` ()

instance NFData Expr where
  rnf (Val a)     = a `deepseq` ()
  rnf (App o l r) = (rnf  o) `deepseq` (rnf l) `deepseq` (rnf r)

solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
  ([e | ns' <- choices ns, (e, m) <- results ns', m == n]
    `using` parList rdeepseq)
 

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

Как мне заставить это работать параллельно?

когда я запускаю в GHCI

 >λ= r = (solutions' [1,3,7,10,25,50] 765)
(0.00 secs, 0 bytes)
>λ= mapM_ print r
*** Exception: stack overflow
>λ=
 

если я скомпилирую с
ghc ./Countdown.hs RTS -N8 -s

а затем запустите исполняемый файл, он не завершается.

Хорошо, итак, я просто нажал на случайную временную метку в видео, и по чистой случайности я получил слайд, который описывает, что не так.

Для нашего примера допустимы только около 5 миллионов из 33 миллионов возможных выражений.

Итак, это означает, что вы оцениваете

 _fiveMillionList `using` parList rdeepseq
 

Теперь, способ (`using` parList _strat) работы заключается в том, что он немедленно запускает весь корешок списка. Когда вы начинаете вычислять свое выражение, parList оно заставляет все ячейки списка существовать. Кроме того, как отмечает @DavidFletcher, ваш параллелизм на самом деле бесполезен. Поскольку фильтрация находится под using , принудительное использование всего корешка списка также заставляет существовать все 33 миллиона Expr s, потому что вам нужно знать, сколько элементов прошло (==) тест, поэтому вам нужно создать Expr s для их тестирования. Им не обязательно существовать одновременно, но, в конце концов, 5 миллионов из них (не считая Expr рекурсивно содержащихся в них s) плюс 5 миллионов (:) конструкторов будут храниться в памяти. Чтобы добавить оскорбление к травме, вы продолжаете создавать еще 5 миллионов объектов в виде пустых искр. И все это управляется 5 миллионами вызовов функции Eval монады (>>=) . Я не уверен, какой из них точно находится в памяти достаточно долго, чтобы вызвать переполнение стека, но я уверен, что parList это виновник.

Возможно, попробуйте более разумный Strategy . Я думаю, что вы в значительной степени вынуждены использовать parBuffer , потому что вам нужна лень. Используя parBuffer n strat , если вы оцениваете a (:) -cell, тогда стратегия гарантирует, что n - 1 были запущены следующие элементы. Таким образом, по сути, он «опережает» любого потребителя, который начинается с начала списка, поддерживая буфер из параллельно вычисляемых элементов. Что-то вроде parBuffer 1000 rdeepseq должно быть хорошо.

 instance NFData Op where
  -- (seq/deepseq) x y is defined by
  -- "if you want to evaluate (seq/deepseq) x y to WHNF, then you must
  -- evaluate x to WHNF/NF, then evaluate y to WHNF."
  -- but e.g. Add is already in WHNF and NF, so seq Add and deeqseq Add are no-ops
  -- the actual evaluation is already finished by the case in rnf's equations
  -- you could even write rnf x = x `seq` (), but I think it's best to be explicit
  rnf Add = ()
  rnf Sub = ()
  rnf Mul = ()
  rnf Div = ()

instance NFData Expr where
  rnf (Val a)     = a `deepseq` ()
  -- rnf o, rnf l :: ()
  -- WHNF and NF are the same thing for the type (); all constructors are nullary
  -- therefore (deepseq (rnf x) y) = seq (rnf x) y
  -- but then seq (rnf x) y = deepseq x y {by definition}
  rnf (App o l r) = o `deepseq` l `deepseq` rnf r