Optimiere eine Listenfunktion, die zu viel Müll erzeugt (kein Stack-Überlauf)

Question

Ich habe diese Haskell-Funktion, die mehr als 50% aller Zuweisungen meines Programms verursacht, wodurch 60% meiner Laufzeit vom GC belegt werden . Ich laufe mit einem kleinen Stack (-K10K), also gibt es keinen Stack-Überlauf, aber kann ich diese Funktion schneller machen, mit weniger Zuweisung?

Ziel ist es, das Produkt einer Matrix durch einen Vektor zu berechnen. Ich kann hmatrix zum Beispiel nicht verwenden, weil dies Teil einer größeren Funktion ist, die das ad Automatic Differentiation-Paket verwendet, also muss ich Listen von Num verwenden. Zur Laufzeit nehme ich an, dass die Verwendung des Numeric.AD Moduls bedeutet, dass meine Typen Scalar Double sein müssen.

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) 

Grundsätzlich wir Schleife durch die Matrix, Multiplizieren und Addieren eines Akkumulators, bis wir das Ende des Vektors erreicht, um das Ergebnis zu speichern, dann den Vektor fort wieder neu zu starten. Ich habe einen quickcheck Test, der bestätigt, dass ich das gleiche Ergebnis als das Matrix-/Vektorprodukt in der hmatrix erhalte.

Ich habe versucht mit foldl, foldr, etc. Nichts, was ich ausprobiert habe macht die Funktion schneller (und einige Dinge wie foldr verursachen ein Leck im Raum).

mit Profillauf sagt mir, oben auf der Tatsache, dass diese Funktion ist, wo die meiste Zeit und Zuteilung wird ausgegeben, dass es eine Menge Cells erstellt werden, Cells ein Datentyp aus dem ad Paket zu sein.

Ein einfacher Test auszuführen:

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 

Das auf meinem Rechner sagt mir GC ist besetzt 47% der Zeit.

Irgendwelche Ideen?

Answer 1

Eine sehr einfache Optimierung ist die go Funktion streng durch seine Akkumulator Parameter zu machen, weil es klein ist, kann unboxed sein, wenn a primitiv ist und muss immer vollständig ausgewertet werden:

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

Auf meinem Rechner, es gibt 3-4x Beschleunigung (kompiliert mit -O2).

Auf der anderen Seite sollten Zwischenlisten nicht streng sein, damit sie verschmolzen werden können.