Teilberechnung in Haskell optimieren

8

Ich bin gespannt, wie ich diesen Code optimieren kann:

%Vor%

Nehmen wir an, dass f , f0 , g , g0 und h teuer sind, aber die Erstellung und Speicherung von l ist extrem teuer.

Wie bereits beschrieben, wird l gespeichert, bis das zurückgegebene Tupel vollständig ausgewertet oder der Garbage Collection-Vorgang abgeschlossen ist. 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.

Es scheint, dass dieses Verhalten durch Schreiben von:

behoben werden konnte %Vor%

Oder das sehr ähnlich:

%Vor%

Wir könnten vielleicht eine Reihe interner Typen angeben, um die gleichen Effekte zu erzielen, was schmerzhaft aussieht. Gibt es noch andere Optionen?

Außerdem hoffe ich natürlich mit meinem inline s, dass der Compiler sum , f0 und g0 zu einer einzelnen Schleife zusammenfasst, die l Term für Term konstruiert und konsumiert. 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 wird und / oder Inlining erzwingt? Pragmas, die Warnungen oder Fehler erzeugen, wenn Inlining oder Fusion während des Kompilierens fehlschlagen?

Abgesehen davon bin ich neugierig, warum seq , inline , lazy usw. im Prelude alle durch let x = x in x definiert sind. Ist das nur, um ihnen eine Definition für den zu überschreibenden Compiler zu geben?

    
Jeff Burdges 22.04.2012, 09:54
quelle

1 Antwort

3

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 %Vor%

oder die deepseq -Version davon, könnte der Compiler in der Lage sein, die Berechnungen von a , b und c zusammenzufassen, die während einer einzelnen Durchquerung von% parallel ausgeführt werden sollen (nicht im Sinne des Nebenläufers). co_de%, aber vorläufig bin ich ziemlich überzeugt, dass GHC das nicht tut, und ich wäre überrascht, wenn JHC oder UHC das tun würden. Und dafür muss die Struktur der Berechnung l und b 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.

Abhängig von c und f0 könnte es so einfach sein wie eine strikte linke Faltung mit dem entsprechenden Akkutyp und der Kombinationsfunktion, wie der berühmte Durchschnitt

%Vor%

Aber wenn die Struktur von g0 und / oder f0 nicht passt, sagen wir eine linke Falte und die andere eine rechte Falte, kann es unmöglich sein, die Berechnung in einer Traversierung durchzuführen. In solchen Fällen können Sie g0 neu erstellen und l speichern. Das Speichern von l ist mit explizitem Teilen ( l ) einfach zu erreichen, aber es kann schwierig sein, es neu zu erstellen, wenn der Compiler eine übliche Teilausdruck-Eliminierung durchführt (leider hat GHC eine Tendenz, Listen dieser Form zu teilen) es tut wenig CSE). Für GHC können die Flags where l = map h [1..n] und fno-cse dazu beitragen, das unerwünschte Teilen zu vermeiden.

    
Daniel Fischer 22.04.2012 12:41
quelle

Tags und Links