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

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

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

Код здесь, и меня интересует оптимизация взаимного интерфейса:

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

Что показывает, что mutualInfoInnerLoop составляет 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]

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

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

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

Ответ 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 достаточно умен, чтобы самостоятельно выполнять эту оптимизацию, и я уверен, что это экономит много времени и пространства, но это лучшее, что у меня есть. С этими штриховыми рисунками, посыпанными на всем протяжении, я задаюсь вопросом, является ли это случаем слишком большой строгости.