Профилирование программы Haskell

Ответ 1

Огромное улучшение уже достигнуто за счет включения предложения JohnL использования foldM в likelihoodWeighting. Это уменьшило использование памяти примерно в десять раз здесь и значительно сократило время GC почти или фактически незначительно.

Профилирование с текущим источником дает

probabilityIO              AI.Util.Util          26.1   42.4    413 290400000
weightedSample.go          AI.Probability.Bayes  16.1   19.1    255 131200080
bnParents                  AI.Probability.Bayes  10.8    1.2    171   8000384
bnVals                     AI.Probability.Bayes  10.4    7.8    164  53603072
bnCond                     AI.Probability.Bayes   7.9    1.2    125   8000384
ndSubRef                   AI.Util.Array          4.8    9.2     76  63204112
bnSubRef                   AI.Probability.Bayes   4.7    8.1     75  55203072
likelihoodWeighting.func   AI.Probability.Bayes   3.3    2.8     53  19195128
%!                         AI.Util.Util           3.3    0.5     53   3200000
bnProb                     AI.Probability.Bayes   2.5    0.0     40        16
bnProb.p                   AI.Probability.Bayes   2.5    3.5     40  24001152
likelihoodWeighting        AI.Probability.Bayes   2.5    2.9     39  20000264
likelihoodWeighting.func.x AI.Probability.Bayes   2.3    0.2     37   1600000

и использование памяти в 13 МБ, о которых сообщается -s, ~ 5 Мбайт. Это уже не так уж плохо.

Тем не менее, остаются некоторые моменты, которые мы можем улучшить. Во-первых, относительно небольшая вещь, в большой схеме, AI.UTIl.Array.ndSubRef:

ndSubRef :: [Int] -> Int
ndSubRef ns = sum $ zipWith (*) (reverse ns) (map (2^) [0..])

Отмена списка, а отображение (2^) по другому списку неэффективно, лучше

ndSubRef = L.foldl' (\a d -> 2*a + d) 0

которому не нужно хранить весь список в памяти (возможно, это не так уж важно, поскольку списки будут короткими), как это делает вспять, и не нужно выделять второй список. Снижение распределения заметно, около 10%, и эта часть работает значительно быстрее,

ndSubRef                   AI.Util.Array          1.7    1.3     24   8000384

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

Добавьте в строчку weightedSample немного строгости, чтобы увидеть, как это меняет вещи:

weightedSample :: Ord e => BayesNet e -> [(e,Bool)] -> IO (Map e Bool, Prob)
weightedSample bn fixed =
    go 1.0 (M.fromList fixed) (bnVars bn)
    where
        go w assignment []     = return (assignment, w)
        go w assignment (v:vs) = if v `elem` vars
            then
                let w' = w * bnProb bn assignment (v, fixed %! v)
                in go w' assignment vs
            else do
                let p = bnProb bn assignment (v,True)
                x <- probabilityIO p
                go w (M.insert v x assignment) vs

        vars = map fst fixed

Параметр веса go никогда не принудительно и не является параметром присваивания, таким образом, они могут создавать громы. Разрешите включение {-# LANGUAGE BangPatterns #-} и принудительные обновления немедленно вступят в силу, также оцените p, прежде чем передать его в probabilityIO:

go w assignment (v:vs) = if v `elem` vars
    then
        let !w' = w * bnProb bn assignment (v, fixed %! v)
        in go w' assignment vs
    else do
        let !p = bnProb bn assignment (v,True)
        x <- probabilityIO p
        let !assignment' = M.insert v x assignment
        go w assignment' vs

Это приводит к дальнейшему сокращению распределения (~ 9%) и небольшому ускорению (~% 13%), но общий объем использования памяти и максимальное место жительства сильно не изменились.

Я не вижу ничего другого, что может измениться там, поэтому посмотрим на likelihoodWeighting:

func m _ = do
    (a, w) <- weightedSample bn fixed
    let x = a ! e
    return $! x `seq` w `seq` M.adjust (+w) x m

В последней строке сначала w уже оценивается в weightedSample, поэтому нам не нужно seq здесь, для оценки обновленной карты требуется ключ x, поэтому seq ing, что тоже не нужно. Плохая вещь на этой строке M.adjust. adjust не имеет возможности заставлять результат обновленной функции, так что строит thunks в значениях карты. Вы можете принудительно оценивать удары, просматривая измененное значение и заставляя это, но Data.Map обеспечивает гораздо более удобный способ, так как ключ, на котором обновляется карта, гарантированно присутствует, insertWith':

func !m _ = do
    (a, w) <- weightedSample bn fixed
    let x = a ! e
    return (M.insertWith' (+) x w m)

(Примечание: GHC лучше оптимизируется с помощью шаблона bang на m, чем с return $! ... здесь). Это немного уменьшает общее распределение и не меняет время работы, но оказывает значительное влияние на используемую общую память и максимальное место жительства:

 934,566,488 bytes allocated in the heap
   1,441,744 bytes copied during GC
      68,112 bytes maximum residency (1 sample(s))
      23,272 bytes maximum slop
           1 MB total memory in use (0 MB lost due to fragmentation)

Наибольшее улучшение времени работы было бы, если избежать randomIO, используемый StdGen будет очень медленным.

Я удивляюсь, сколько времени выполняют функции bn*, но не вижу в них очевидной неэффективности.

Ответ 2

У меня проблемы с перевариванием этих профилей, но я получил свою задницу раньше, потому что MonadRandom в Hackage строг. Создание ленивой версии MonadRandom затруднило проблемы с памятью.

Мой коллега еще не получил разрешения на выпуск кода, но я положил Control.Monad.LazyRandom в онлайн pastebin. Или, если вы хотите увидеть некоторые отрывки, которые объясняют полностью ленивый случайный поиск, в том числе бесконечные списки случайных вычислений, посмотрите Отчет о работе: Haskell in Computational Biology.

Ответ 3

Я собрал очень элементарный пример, размещенный здесь: http://hpaste.org/71919. Я не уверен, что это похоже на ваш пример.. просто очень минимальная вещь, которая, казалось, сработала.

Компиляция с -prof и -fprof-auto и работа с 100000 итерациями дала следующую главу профилирующего вывода (помилуй мои номера строк):

  8 COST CENTRE                   MODULE               %time %alloc
  9 
 10 sample                        AI.Util.ProbDist      31.5   36.6
 11 bnParents                     AI.Probability.Bayes  23.2    0.0
 12 bnRank                        AI.Probability.Bayes  10.7   23.7
 13 weightedSample.go             AI.Probability.Bayes   9.6   13.4
 14 bnVars                        AI.Probability.Bayes   8.6   16.2
 15 likelihoodWeighting           AI.Probability.Bayes   3.8    4.2
 16 likelihoodWeighting.getSample AI.Probability.Bayes   2.1    0.7
 17 sample.cumulative             AI.Util.ProbDist       1.7    2.1
 18 bnCond                        AI.Probability.Bayes   1.6    0.0
 19 bnRank.ps                     AI.Probability.Bayes   1.1    0.0

И вот сводная статистика:

1,433,944,752 bytes allocated in the heap
 1,016,435,800 bytes copied during GC
   176,719,648 bytes maximum residency (11 sample(s))
     1,900,232 bytes maximum slop
           400 MB total memory in use (0 MB lost due to fragmentation)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    1.40s  (  1.41s elapsed)
GC      time    1.08s  (  1.24s elapsed)
Total   time    2.47s  (  2.65s elapsed)

%GC     time      43.6%  (46.8% elapsed)

Alloc rate    1,026,674,336 bytes per MUT second

Productivity  56.4% of total user, 52.6% of total elapsed

Обратите внимание, что профайлер указал пальцем на sample. Я принудительно использовал return в этой функции, используя $!, а затем следующую сводную статистику:

1,776,908,816 bytes allocated in the heap
  165,232,656 bytes copied during GC
   34,963,136 bytes maximum residency (7 sample(s))
      483,192 bytes maximum slop
           68 MB total memory in use (0 MB lost due to fragmentation)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    2.42s  (  2.44s elapsed)
GC      time    0.21s  (  0.23s elapsed)
Total   time    2.63s  (  2.68s elapsed)

%GC     time       7.9%  (8.8% elapsed)

Alloc rate    733,248,745 bytes per MUT second

Productivity  92.1% of total user, 90.4% of total elapsed

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

Ответ 4

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

Проблема в том, что вы перебираете список дважды, один раз для sequence и снова для sum. В Haskell несколько переходов списка больших списков действительно, очень плохо для производительности. Решение, как правило, должно использовать некоторый тип складок, например foldM. Ваша функция sampleMean может быть записана как

{-# LANGUAGE BangPatterns #-}

sampleMean2 :: MonadRandom m => Int -> m Float -> m Float
sampleMean2 n dist = foldM (\(!a) mb -> liftM (+a) mb) 0 $ replicate n dist

например, перемещение списка только один раз.

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