Самый простой монадический «поток» - это просто список монадических действий Monad m => [m a].Функция sequence :: [m a] -> m [a] оценивает каждое монадическое действие и собирает результаты.Оказывается, что sequence не очень эффективен, потому что он работает со списками, а монада является препятствием для достижения слияния ни с чем, кроме простейших случаев.
Вопрос заключается в следующем:Каков наиболее эффективный подход для монадических потоков?
Чтобы исследовать это, я предлагаю игрушечную проблему наряду с несколькими попытками улучшить производительность.Исходный код можно найти на github .Единственный эталонный тест, представленный ниже, может вводить в заблуждение для более реалистичных задач, хотя я думаю, что это своего рода сценарий наихудшего случая, то есть наиболее вероятные накладные расходы на полезное вычисление.
- максимальная длина 16 бит L inear F Eedback S hift R egister (LFSR), реализованный в C несколько сложным образом, с оболочкой Haskell в монаде IO.«Слишком сложный» относится к ненужному использованию struct и его malloc - цель этого усложнения состоит в том, чтобы сделать его более похожим на реалистичные ситуации, когда все, что у вас есть, - это оболочка Haskell вокруг FFI к C struct с семантикой OO-ish new, set, get, operate (т. Е. Очень императивный стиль).Типичная программа на Haskell выглядит следующим образом:
import LFSR
main = do
lfsr <- newLFSR -- make a LFSR object
setLFSR lfsr 42 -- initialise it with 42
stepLFSR lfsr -- do one update
getLFSR lfsr >>= print -- extract the new value and print
Задачей по умолчанию является вычисление среднего значения (удваивается) из 10 000 000 итераций LFSR.Эта задача может быть частью набора тестов для анализа «случайности» этого потока 16-разрядных целых чисел.
0.Базовая линия
Базовая линия - это реализация C среднего значения за n итераций:
double avg(state_t* s, int n) {
double sum = 0;
for(int i=0; i<n; i++, sum += step_get_lfsr(s));
return sum / (double)n;
}
Реализация C не предназначена для того, чтобы быть особенно хорошей или быстрой.Это просто обеспечивает значимые вычисления.
1.Списки на Haskell
По сравнению с базовой линией C в этой задаче списки на Haskell медленнее в 73 раза.
=== RunAvg =========
Baseline: 1.874e-2
IO: 1.382488
factor: 73.77203842049093
Это реализация (RunAvg.hs):
step1 :: LFSR -> IO Word32
step1 lfsr = stepLFSR lfsr >> getLFSR lfsr
avg :: LFSR -> Int -> IO Double
avg lfsr n = mean <$> replicateM n (step1 lfsr) where
mean :: [Word32] -> Double
mean vs = (sum $ fromIntegral <$> vs) / (fromIntegral n)
2.Использование библиотеки streaming
Это дает нам возможность в пределах 9x от базовой линии,
=== RunAvgStreaming ===
Baseline: 1.9391e-2
IO: 0.168126
factor: 8.670310969006241
(Обратите внимание, что тесты довольно неточны в этихкороткое время выполнения.)
Это реализация (RunAvgStreaming.hs):
import qualified Streaming.Prelude as S
avg :: LFSR -> Int -> IO Double
avg lfsr n = do
let stream = S.replicateM n (fromIntegral <$> step1 lfsr :: IO Double)
(mySum :> _) <- S.sum stream
return (mySum / fromIntegral n)
3.Использование Data.Vector.Fusion.Stream.Monadic
Это дает лучшую производительность на данный момент, в пределах 3x от базовой линии,
=== RunVector =========
Baseline: 1.9986e-2
IO: 4.9146e-2
factor: 2.4590213149204443
Как обычно, вот реализация (RunAvgVector.hs):
import qualified Data.Vector.Fusion.Stream.Monadic as V
avg :: LFSR -> Int -> IO Double
avg lfsr n = do
let stream = V.replicateM n (step1' lfsr)
V.foldl (+) 0.0 stream
Я не ожидал найти хорошую реализацию монадического потока в Data.Vector.Помимо предоставления fromVector и concatVectors, Data.Vector.Fusion.Stream.Monadic имеет очень мало общего с Vector из Data.Vector.
Просмотр отчета о профилировании показывает, что Data.Vector.Fusion.Stream.Monadic имеет значительную утечку пространства, но это не звучит правильно.
4.Списки не обязательно медленны
Для очень простых операций списки совсем не страшны:
=== RunRepeat =======
Baseline: 1.8078e-2
IO: 3.6253e-2
factor: 2.0053656377917912
Здесь цикл for выполняется в Haskell вместо его нажатия внизна C (RunRepeat.hs):
do
setLFSR lfsr 42
replicateM_ nIter (stepLFSR lfsr)
getLFSR lfsr
Это просто повторение вызовов на stepLFSR без передачи результата обратно на уровень Haskell.Это дает представление о том, какое влияние окажут накладные расходы на вызов оболочки и FFI.
Анализ
Приведенный выше пример repeat показывает, что большая часть, но не все (?), Потери производительности связаны с накладными расходами на вызов оболочки и / илиФФИ.Но я не уверен, где искать твики, сейчас.Может быть, это так же хорошо, как и в отношении монадических потоков, и на самом деле это все о сокращении FFI, теперь ...
Sidenotes
- Тот факт, что LFSR выбраны в качестве игрушечной проблемы, не означает, что Haskell не может сделать это эффективно - см. Вопрос SO "Эффективное переключение битов в реализации LFSR" .
- Итерация 16-битного LFSR 10M раз - довольно глупая вещь.Потребуется максимум 2 ^ 16-1 итераций, чтобы снова достичь исходного состояния.При максимальной длине LFSR потребуется ровно 2 ^ 16-1 итераций.
Обновление 1
Попытка удалитьwithForeignPtr звонки можно сделать, введя Storable и затем используя alloca :: Storable a => (Ptr a -> IO b) -> IO b
repeatSteps :: Word32 -> Int -> IO Word32
repeatSteps start n = alloca rep where
rep :: Ptr LFSRStruct' -> IO Word32
rep p = do
setLFSR2 p start
(sequence_ . (replicate n)) (stepLFSR2 p)
getLFSR2 p
, где LFSRStruct' равно
data LFSRStruct' = LFSRStruct' CUInt
, а обертка -
foreign import ccall unsafe "lfsr.h set_lfsr"
setLFSR2 :: Ptr LFSRStruct' -> Word32 -> IO ()
-- likewise for setLFSR2, stepLFSR2, ...
См. RunRepeatAlloca.hs и src / LFSR.hs .С точки зрения производительности это не имеет значения (в пределах временной вариации).
=== RunRepeatAlloca =======
Baseline: 0.19811199999999998
IO: 0.33433
factor: 1.6875807623970283