Оптимизация строгости и распределение памяти в Haskell

Question

Я изучил некоторый Haskell, реализовав алгоритм выбора функций.

Я получил производительность от 20 с на наборе эталонных данных до 5 с, где программа C обрабатывает тот же набор данных за 0,5 с,Набор данных можно найти здесь .Для запуска вызовите скомпилированный двоичный файл следующим образом: ./Mrmr 10 test_nci9_s3.csv.

Код: здесь , и меня интересует оптимизация взаимной привязки :In 1010 *

mutualInfoInnerLoop :: Double -> Data.Vector.Unboxed.Vector (Int, Int) -> Double -> (Int, Int, Double) -> Double
mutualInfoInnerLoop n xys !acc (!i, !j, !px_py)
    | n == 0 || px_py == 0 || pxy == 0 = acc
    | otherwise                        = pxy * logBase 2 ( pxy / px_py ) + acc
    where
        pxy = ( fromIntegral . U.foldl' accumEq2 0 $ xys ) / n
        accumEq2 :: Int -> (Int, Int) -> Int
        accumEq2 !acc (!i', !j')
            | i' == i && j' == j = acc + 1
            | otherwise          = acc

Профилировщик говорит:

COST CENTRE                    MODULE               %time %alloc

mutualInfoInnerLoop            Main                  75.0   47.9
mutualInfo                     Main                  14.7   32.1
parseCsv                       Main                   5.9   13.1
CAF                            GHC.Float              1.5    0.0
readInt                        Main                   1.5    1.2
doMrmr                         Main                   1.5    4.0

, который показывает, что взаимный доступ к данным составляетInInfoInnerLoop как 50% выделений, с 75% времени выполнения в программе.Распределения приводят в замешательство.

Кроме того, Ядро для этой функции имеет подпись:

mutualInfoInnerLoop_rXG
  :: GHC.Types.Double
     -> Data.Vector.Unboxed.Base.Vector (GHC.Types.Int, GHC.Types.Int)
     -> GHC.Types.Double
     -> (GHC.Types.Int, GHC.Types.Int, GHC.Types.Double)
     -> GHC.Types.Double
[GblId,
 Arity=4,
 Caf=NoCafRefs,
 Str=DmdType U(L)LU(L)U(U(L)U(L)U(L))m]

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

Я пробовал BangPatterns, пробовал MagicHash и не могу заставить его работать быстрее.

У кого-нибудь есть предложения?

Answer 1

Я, безусловно, не эксперт в этом, но я вижу одно небольшое улучшение. В вашем источнике я вижу это:

mutualInfo n ... = foldl' (mutualInfoInnerLoop n $ U.zip xs ys) ...

Вам не нужно проверять n == 0 каждый раз, когда вызывается функция, поскольку вы никогда не меняете аргумент n при ее вызове. Аргумент xys также не меняется, это означает, что pxy не изменяется при каждом вызове, поскольку он зависит исключительно от xys и n. Давайте воспользуемся этими преимуществами, чтобы убедиться, что создано замыкание, которое оценивает эти вещи только один раз.

mutualInfoInnerLoop n xys
  | n == 0 || pxy == 0 = const
  | otherwise          = go
  where pxy = (fromIntegral . U.foldl' accumEq2 0 $ xys) / n
        accumEq2 :: Int -> (Int, Int) -> Int
        accumEq2 !acc (!i', !j')
              | i' == i && j' == j = acc + 1
              | otherwise          = acc
        go !acc (!i, !j, !px_py)
          | px_py == 0 = acc
          | otherwise  = pxy * logBase 2 ( pxy / px_py ) + acc

Я не уверен, что GHC достаточно умен, чтобы выполнять эту оптимизацию самостоятельно, и я не уверен, что это экономит много времени / пространства, но это лучшее, что у меня есть. Интересно, не слишком ли уж строгий характер этих взрывающих шаблонов?