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

Question

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

Целью здесь является вычислить произведение матрицы на вектор. Например, я не могу использовать hmatrix, потому что это часть большей функции с использованием пакета ad Automatic Differentiation, поэтому мне нужно использовать списки 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).

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