Оптимизация функции списка, которая создает слишком много мусора (не переполнение стека)

Question

У меня есть та функция Haskell, которая вызывает более 50% всех выделений моей программы, в результате чего 60% моего времени выполнения занимает GC. Я бегу с небольшим стеком (-K10K) поэтому нет переполнения стека, но можно ли сделать эту функцию быстрее, с меньшим распределением?

Цель здесь - рассчитать произведение матрицы на вектор. Я не могу использовать hmatrix например, потому что это часть большей функции, использующей ad Пакет автоматической дифференциации, поэтому мне нужно использовать списки Num, Во время выполнения я предполагаю использование Numeric.AD модуль означает, что мои типы должны быть Scalar Double,

listMProd :: (Num a) => [a] -> [a] -> [a]
listMProd mdt vdt = go mdt vdt 0
  where
    go [] _  s = [s]
    go ls [] s = s : go ls vdt 0
    go (y:ys) (x:xs) ix = go ys xs (y*x+ix)

По сути, мы перебираем матрицу, умножаем и добавляем накопитель, пока не достигнем конца вектора, сохраним результат, затем продолжаем перезапускать вектор снова. у меня есть quickcheck тест, подтверждающий, что я получаю тот же результат, что и матричное / векторное произведение в hmatrix.

Я пробовал с foldl, foldr и т.д. Ничто из того, что я пробовал, не делает функцию быстрее (и некоторые вещи, как foldr вызвать утечку пространства).

Запуск с профилированием говорит мне, помимо того факта, что эта функция - то, где большая часть времени и распределения тратится, что есть множество Cells будучи созданным, Cells будучи типом данных из ad пакет.

Простой тест для запуска:

import Numeric.AD

main = do
    let m :: [Double] = replicate 400 0.2
        v :: [Double] = replicate 4 0.1
        mycost v m = sum $ listMProd m v 
        mygrads = gradientDescent (mycost (map auto v)) (map auto m)
    print $ mygrads !! 1000

Это на моей машине говорит мне, что GC занята 47% времени.

Есть идеи?

Answer 1

Очень простая оптимизация - сделать go Функция строго по параметру аккумулятора, поскольку она мала, может быть распакована, если a является примитивным и всегда должен быть полностью оценен:

{-# LANGUAGE BangPatterns #-}
listMProd :: (Num a) => [a] -> [a] -> [a]
listMProd mdt vdt = go mdt vdt 0
  where
    go [] _  !s = [s]
    go ls [] !s = s : go ls vdt 0
    go (y:ys) (x:xs) !ix = go ys xs (y*x+ix)

На моей машине это дает 3-4-кратное ускорение (скомпилировано с -O2).

С другой стороны, промежуточные списки не должны быть строгими, чтобы их можно было объединить.