Zoptymalizuj funkcję listy, która tworzy zbyt dużo śmieci (nie przepełnienie stosu)

Question

Mam tę funkcję Haskella, która powoduje ponad 50% wszystkich alokacji mojego programu, powodując, że 60% mojego czasu pracy jest pobierane przez GC . Używam małego stosu (-K10K), więc nie ma przepełnienia stosu, ale czy mogę uczynić tę funkcję szybszą, z mniejszą alokacją?

Celem jest obliczenie iloczynu macierzy przez wektor. Nie mogę użyć na przykład hmatrix, ponieważ jest to część większej funkcji przy użyciu pakietu ad Automatic Differentiation, więc potrzebuję użyć list z Num. W czasie pracy sądzę, że użycie modułu Numeric.AD oznacza, że ​​moje typy muszą być 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) 

Zasadniczo pętla poprzez mnożenie macierzy i dodanie akumulator, aż do osiągnięcia końca wektorze przechowywania wyników, a dalej znowu ponownym wektor. Mam test quickcheck sprawdzający, czy otrzymuję taki sam wynik, jak produkt macierzy/wektor w hmatrix.

Próbowałem z foldl, foldr, itp. Nic nie próbowałem sprawia, że ​​funkcja jest szybsza (i niektóre rzeczy jak foldr powodują wyciek przestrzeni).

Biegając z profilowaniem mówi mi, oprócz faktu, że ta funkcja jest gdzie większość czasu spędza się i przydziału, że istnieje mnóstwo Cells tworzone, Cells jest typ danych z pakietu ad.

Prosty test do uruchomienia:

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 

to na moim komputerze mówi mi GC jest zajęty 47% czasu.

Wszelkie pomysły?

Answer 1

Bardzo prosta optymalizacja jest, aby funkcja go ścisłe jego parametrów akumulatora, ponieważ jest niewielki, może być unboxed jeśli a jest prymitywny i zawsze musi być w pełni ocenione:

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

Na moim komputerze, daje przyspieszenie 3-4x (skompilowane z -O2).

Z drugiej strony listy pośrednie nie powinny być ścisłe, aby można je było łączyć.