Сжатие большей производительности из монадических потоков в Haskell - PullRequest
0 голосов
/ 11 июня 2018

Самый простой монадический «поток» - это просто список монадических действий 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

  1. Тот факт, что LFSR выбраны в качестве игрушечной проблемы, не означает, что Haskell не может сделать это эффективно - см. Вопрос SO "Эффективное переключение битов в реализации LFSR" .
  2. Итерация 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

1 Ответ

0 голосов
/ 12 июня 2018

После расшифровки продукта сборки GHC для RunRepeat.hs я прихожу к такому выводу: GHC не встроит вызов функции C step_lfsr(state_t*), тогда как компилятор C сделает это, и в этом вся разница для этой проблемы с игрушкой .

Я могу продемонстрировать это, запретив использование прагмы __attribute__ ((noinline)).В целом, исполняемый файл C становится медленнее, поэтому разрыв между Haskell и C. сокращается.

Вот результаты:

=== RunRepeat =======
#iter:    100000000
Baseline: 0.334414
IO:       0.325433
factor:   0.9731440669349967
=== RunRepeatAlloca =======
#iter:    100000000
Baseline: 0.330629
IO:       0.333735
factor:   1.0093942152684732
=== RunRepeatLoop =====
#iter:    100000000
Baseline: 0.33195399999999997
IO:       0.33791
factor:   1.0179422450098508

Т.е. больше нет штрафов за вызовы FFI на lfsr_step.

=== RunAvg =========
#iter:    10000000
Baseline: 3.4072e-2
IO:       1.3602589999999999
factor:   39.92307466541442
=== RunAvgStreaming ===
#iter:    50000000
Baseline: 0.191264
IO:       0.666438
factor:   3.484388070938598

Старые добрые списки не сливаются, поэтому огромный удар по производительности и библиотека streaming также не оптимальны.Но Data.Vector.Fusion.Stream.Monadic получает в пределах 20% производительности C:

=== RunVector =========
#iter:    200000000
Baseline: 0.705265
IO:       0.843916
factor:   1.196594188000255

Уже было замечено, что GHC не выполняет встроенные вызовы FFI: "Как заставить GHC встроить вызовы FFI?".

Для ситуаций, когда выгода от встраивания столь высока, т.е. рабочая нагрузка на вызов FFI настолько мала, возможно, стоит изучить inline-c.

...