Вложенная в вектор параллельная стратегия на Haskell

Question

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

Вот что у меня есть:

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import Data.Vector.Strategies 
import Control.DeepSeq

main = do
  let res = genVVec 200 `using` parVector 2
  print res

genUVec :: Int -> U.Vector Int
genUVec n = U.map (ack 2) $ U.enumFromN n 75

genVVec :: Int -> V.Vector (U.Vector Int)
genVVec n = V.map genUVec $ V.enumFromN 0 n

ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))

instance (NFData a, U.Unbox a) => NFData (U.Vector a) where
  rnf = rnf . U.toList

дает:

$ ./vectorPar +RTS -N8 -s >/dev/null
   SPARKS: 200 (17 converted, 183 pruned)
   Total time    1.37s  (  1.30s elapsed)
$ ./vectorPar +RTS -s >/dev/null
   SPARKS: 200 (0 converted, 200 pruned)
   Total time    1.25s  (  1.26s elapsed)

Я также пытался изменитьparVector функция в векторных стратегиях напрямую, но мои попытки неуклюжи и неэффективны.

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

Answer 1

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

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import Data.Vector.Strategies
import Control.DeepSeq
import Control.Parallel.Strategies

main = do
  let res = genVVec 200 `using` (rdeepseq `dot` parVector 20)
  print res

genUVec :: Int -> U.Vector Int
genUVec n = U.map (ack 2) $ U.enumFromN n 75

genVVec :: Int -> V.Vector (U.Vector Int)
genVVec n = V.map genUVec $ V.enumFromN 0 n

ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))

instance (NFData a, U.Unbox a) => NFData (U.Vector a) where
  rnf vec = seq vec ()

instance (NFData a) => NFData (V.Vector a) where
  rnf = rnf . V.toList

Я также изменил ваш NFData (U.Vector a) экземпляр. Поскольку U.Vector распакован, оценки в WHNF достаточно, и форсирование каждого элемента посредством преобразования списка является расточительным. На самом деле определение по умолчанию для rnf работает нормально, если хотите.

С этими двумя изменениями я получаю следующее

SPARKS: 200 (200 converted, 0 pruned)

и время выполнения было уменьшено почти на 50%. Я также отрегулировал размер фрагмента вектора до 20, но результат очень похож на размер фрагмента 2.

Answer 2

Примечание: виновный автор векторных стратегий здесь (это очень маленькое название, поскольку это была просто взломанная функция, и я подумал, что другие найдут ее полезной).

Ваше наблюдение о том, что parVectorнеправильно в том, что он позволяет GCed искры перед использованием кажется правильным.Совет SimonM означает, что я должен делать именно то, чего я пытался избежать, создать новый вектор, какой-то ценой, вместо старого.Зная, что это необходимо, есть небольшая причина, чтобы не менять parVector на гораздо более простое определение:

parVector2 :: NFData a => Int -> Strategy (V.Vector a)
parVector2 n = liftM V.fromList . parListChunk n rdeepseq . V.toList

Обратите внимание, что исправление, данное Джоном Л., работает только потому, что оно «бьет» сборщика, заставляявычисления произойдут до сбора.

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