Ottimizza una funzione di lista che crea troppa garbage (non stack overflow)

Question

Ho la funzione Haskell, che causa oltre il 50% di tutte le allocazioni del mio programma, causando il 60% del mio tempo di esecuzione da parte del GC . Corro con un piccolo stack (-K10K) quindi non c'è overflow dello stack, ma posso rendere questa funzione più veloce, con meno allocazione?

L'obiettivo qui è calcolare il prodotto di una matrice mediante un vettore. Ad esempio, non posso usare hmatrix perché fa parte di una funzione più grande che utilizza il pacchetto ad Automatic Differentiation, quindi ho bisogno di usare gli elenchi di Num. A runtime suppongo che l'uso del modulo Numeric.AD significhi che i miei tipi devono essere 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) 

Fondamentalmente ciclo attraverso la matrice, moltiplicando l'aggiunta di un accumulatore fino a raggiungere l'estremità del vettore, memorizzando il risultato, quindi continuando a riavviare il vettore. Ho un test quickcheck che verifica che ottengo lo stesso risultato del prodotto matrice/vettore in hmatrix.

Ho provato con foldl, foldr, ecc. Niente di quello che ho provato rende la funzione più veloce (e alcune cose come foldr causano una perdita di spazio).

Esecuzione con profilatura mi dice, in cima al fatto che questa funzione è dove la maggior parte del tempo e l'allocazione è speso, che ci sono un sacco di Cells essere creato, Cells essendo un tipo di dati dal pacchetto ad.

Un semplice test da eseguire:

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 

questo sulla mia macchina mi dice GC è occupato il 47% del tempo.

Qualche idea?

Answer 1

Una molto semplice ottimizzazione è quello di rendere la funzione go rigorosa dal suo parametro di accumulatore, perché è piccola, può essere unboxed se a è primitiva e sempre deve essere valutato appieno:

{-# 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) 

Sulla mia macchina, dà 3-4 volte più veloce (compilato con -O2).

D'altro canto, gli elenchi intermedi non devono essere rigorosi in modo da poter essere fusi.