Параллельные «вставки» в двоичный файл в Haskell

Question

У меня есть список n-битных "слов"

type BitWord = [Bool]

и дерево, в котором хранится слово сверху вниз:

data Tree = Bs Tree Tree  -- Bs (zero_bit) (one_bit)
          | X -- incomplete word
          | B -- final bit of word

У меня есть функция:

seenPreviously :: BitWord -> Tree -> (Tree,Bool)

Функция перебирает биты в BitWord, спускаясь по Tree влево с нулевым битом и наоборот. Мы возвращаем новое дерево с этим BitWord «объединенным» вместе с True, если нам нужно было добавить поддеревья в какой-то момент (т. Е. BitWord еще не было в дереве), и False в противном случае.

Я отображаю эту функцию на [BitWord], передавая дерево как состояние.

У меня такой вопрос : может ли это быть полезным от параллелизма, предлагаемого Control.Parallel? И если да, то как я могу рассуждать о лени и оценке только слабой головы нормальной формы и т. Д .?

Мой инстинкт состоит в том, что я могу вставлять (фактически создавая поддерево) в левую ветвь, делая то же самое в правой ветви, как два независимых потока. Что-то вроде:

parallelMapSt :: [ BitWords ] -> Tree -> [Bool]
parallelMapSt [] _ = []
parallelMapSt (w:ws) t = let (b,t') = seenPreviously w t
                             bs     = parralelMapSt ws t'
                          in t' `par` bs `pseq` (b:bs)

Поток, оценивающий b, зависит от некоторых ранее запущенных потоков (принадлежащих BitWords, которые имеют общий префикс с w), но не от всех, так что может показаться, что есть возможность работать параллельно здесь, но я действительно не уверен.

Answer 1

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

Answer 2

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

Однако, если мы сможем немного перефразировать проблему так, чтобы порядок и расположение вставок не имели значения, проблема довольно проста:

import Control.Parallel

data Tree = Bs Bool         -- ^ is an empty word inserted here?
               (Maybe Tree) -- ^ '0' subtree
               (Maybe Tree) -- ^ '1' subtree
     deriving Show

insertMany :: [[Bool]] -> Maybe Tree
insertMany []  = Nothing
insertMany xss = hasEnd `par` fs `par` ts `pseq` Just (Bs hasEnd fs ts)
 where
    hasEnd = any null xss
    fs = insertMany [ xs | False : xs <- xss]
    ts = insertMany [ xs | True  : xs <- xss]

У меня сейчас нет нескольких ядер, поэтому я не могу проверить это, но оно должно хорошо масштабироваться. По сути, мы получили параллельную сортировку по осям в несколько строк - не слишком потертая!

Answer 3

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