Optimierung der Teilberechnung in Haskell

Question

Ich bin gespannt, wie dieser Code zu optimieren:

fun n = (sum l, f $ f0 l, g $ g0 l) 
    where l = map h [1..n] 

Unter der Annahme, dass f, f0, g, g0 und h alle teuer sind, aber die Erstellung und Speicherung von l extrem ist teuer.

Wie beschrieben, l wird gespeichert, bis das zurückgegebene Tupel vollständig ausgewertet oder Müll gesammelt wird. Stattdessen sollten length l, f0 l und g0 l alle ausgeführt werden, wenn einer von ihnen ausgeführt wird, aber f und g sollten verzögert werden.

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

Oder die sehr ähnlich:

Es scheint könnte dieses Verhalten durch schriftlich fixiert werden

Wir

fun n = (a,b,c) `deepSeq` (a, f b, g c) 
    where ... 

vielleicht eine Reihe von internen Typen angeben könnten auch die gleichen Effekte zu erzielen, was schmerzhaft aussieht. Gibt es noch andere Möglichkeiten?

Auch hoffe ich natürlich mit meinem inline s, dass der Compiler Sicherungen sum, f0 und g0 in eine einzige Schleife, und verbraucht durch Begriff l Begriff konstruiert. Ich könnte dies durch manuelles Inlining explizit machen, aber das wäre scheiße. Gibt es Möglichkeiten, explizit zu verhindern, dass die Liste l jemals erstellt und/oder inlining gezwungen wird? Pragmas, die Warnungen oder Fehler erzeugen, wenn Inlining oder Fusion während des Kompilierens fehlschlagen?

Als beiseite, ich bin neugierig, warum seq, inline, lazy usw. sind alle definiert durch let x = x in x im Vorspiel. Ist das nur, um ihnen eine Definition zu geben, damit der Compiler sie überschreiben kann?

Answer 1

Wenn Sie sicher sein wollen, ist der einzige Weg, es selbst zu tun. Für jede gegebene Compiler-Version können Sie mehrere Quellformulierungen ausprobieren und den generierten Core/Assembly/llvm Byte-Code/was auch immer überprüfen, ob er das tut, was Sie wollen. Aber das könnte mit jeder neuen Compiler-Version brechen.

Wenn Sie schreiben

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

oder die deepseq Version davon, könnte der Compiler der Lage sein, die Berechnungen von a, b und c zu fusionieren parallel (nicht im Gleichzeitigkeit Sinn) ausgeführt werden während eines einzigen Traversal von l, aber vorerst bin ich ziemlich überzeugt, dass GHC nicht, und ich würde mich wundern, wenn JHC oder UHC tat. Und dafür muss die Struktur der Berechnung b und c einfach genug sein.

Die einzige Möglichkeit, das gewünschte Ergebnis über Compiler und Compilerversionen hinweg portabel zu erhalten, besteht darin, dies selbst zu tun. Zumindest für die nächsten Jahre.

Je nach f0 und g0, könnte es so einfach sein wie eine strenge linke Falte mit entsprechendem Akkutyp zu tun und Funktion kombiniert, wie die berühmten Durchschnitt

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Double 

average :: [Double] -> Double 
average = ratio . foldl' count (P 0 0) 
    where 
    ratio (P n s) = s/fromIntegral n 
    count (P n s) x = P (n+1) (s+x) 

aber wenn die Struktur der f0 und/oder g0 passt nicht, sagen wir eine linke Falte und die andere eine rechte Falte, es kann unmöglich sein, die Berechnung in einer Traversierung zu tun. In solchen Fällen besteht die Wahl zwischen l und speichern l. Speichern l ist einfach mit expliziten Freigabe (where l = map h [1..n]) zu erreichen, aber neu zu erstellen kann schwierig sein, wenn der Compiler einige gemeinsame Teilausdruck Eliminierung (unglücklicherweise hat GHC eine Tendenz, Listen dieser Form zu teilen, obwohl es wenig CSE tut). Für GHC können die Flags fno-cse und -fno-full-laziness dazu beitragen, unerwünschte Freigabe zu vermeiden.