Umschreiben als eine praktische Optimierungstechnik in GHC: Wird es wirklich benötigt?

Question

Ich las das Papier von Simon Peyton Jones, et al. benannt “Playing by the Rules: Rewriting as a practical optimization technique in GHC”. Im zweiten Abschnitt, nämlich “ Die Grundidee ” sie schreiben:

Betrachten Sie die vertraute map Funktion, die eine Funktion auf jedes Element einer Liste gilt. Geschrieben in Haskell, sieht map wie folgt aus:

map f []  = [] 
map f (x:xs) = f x : map f xs 

Nehmen wir nun an, dass der Compiler den folgenden Aufruf von map Begegnungen:

map f (map g xs) 

Wir wissen, dass dieser Ausdruck entspricht zu

(wobei “. ” ist Funktionszusammensetzung), und wir wissen, dass der letztere Ausdruck effizienter ist als der erstere, weil es keine Zwischenliste gibt. Aber der Compiler hat kein solches Wissen.

Eine mögliche Erwiderung ist, dass der Compiler klüger sein sollte --- aber der Programmierer wird immer Dinge wissen, die der Compiler nicht herausfinden kann. Ein anderer Vorschlag ist dies: Erlaube dem Programmierer, dieses Wissen direkt dem Compiler mitzuteilen. Das ist die Richtung, die wir hier erkunden.

Meine Frage ist, warum können wir den Compiler nicht schlauer machen? Die Autoren sagen, dass “ aber der Programmierer immer Dinge wissen wird, die der Compiler ” nicht herausfinden kann. Allerdings, das ist keine gültige Antwort, weil der Compiler in der Tat herausfinden kann, dass map f (map g xs) zu map (f . g) xs äquivalent ist, und hier ist, wie:

map f (map g xs) 

1. map g xs mit map f [] = [] vereint.

   Daher map g [] = [].

2. map f (map g []) = map f [].

   map f [] vereint mit map f [] = [].

   Daher map f (map g []) = [].

3. map g xs vereint mit map f (x:xs) = f x : map f xs.

   Daher map g (x:xs) = g x : map g xs.

4. map f (map g (x:xs)) = map f (g x : map g xs).

   map f (g x : map g xs) vereint mit map f (x:xs) = f x : map f xs.

   Daher map f (map g (x:xs)) = f (g x) : map f (map g xs).

Daher haben wir jetzt die Regeln:

map f (map g [])  = [] 
map f (map g (x:xs)) = f (g x) : map f (map g xs) 

Wie Sie f (g x) ist nur (f . g) und map f (map g xs) sehen kann, wird rekursiv aufgerufen werden. Dies ist genau die Definition von map (f . g) xs. Der Algorithmus für diese automatische Konvertierung scheint ziemlich einfach zu sein. Warum also nicht das implementieren, statt die Regeln neu zu schreiben?

Answer 1

Aggressive Inlining kann viele der Gleichheiten herleiten, für die Umformregeln kurz sind. Der Unterschied ist, dass das Inlining "blind" ist, so dass Sie nicht im Voraus wissen, ob das Ergebnis besser oder schlechter sein wird, oder sogar wenn es enden wird.

Rewrite-Regeln können jedoch völlig nicht offensichtliche Dinge tun, basierend auf viel höheren Fakten über das Programm. Stellen Sie sich Regeln zum Umschreiben vor, wenn Sie dem Optimierer neue Axiome hinzufügen. Indem Sie diese hinzufügen, haben Sie einen reichhaltigeren Regelsatz zur Anwendung, wodurch komplizierte Optimierungen einfacher angewendet werden können.

Stream fusion ändert beispielsweise die Datentypdarstellung. Dies kann nicht durch Inlining ausgedrückt werden, da es sich um eine Änderung des Darstellungstyps handelt (wir stellen das Optimierungsproblem in Bezug auf die Stream ADT neu ein). Einfaches Umschreiben in Regeln, unmöglich mit Inlining allein.

Answer 2

Etwas in dieser Richtung wurde in einer Bachelorarbeit von Johannes Bader, einem meiner Studenten, untersucht: Finding Equations in Functional Programs (PDF file).

es bis zu einem gewissen Grad durchaus möglich ist, aber

• es ziemlich schwierig ist. Das Finden solcher Gleichungen ist in gewisser Weise so schwierig wie das Finden von Beweisen in einem Theoremproofer, und es ist nicht oft sehr nützlich, weil es dazu neigt, Gleichungen zu finden, die der Programmierer selten direkt schreiben würde.

Es ist jedoch nützlich, nach anderen Transformationen wie Inlining und verschiedene Form der Fusion zu bereinigen.

Answer 3

Dies könnte als ein Gleichgewicht zwischen den Abwägungserwartungen im konkreten Fall und der Abwägung im allgemeinen Fall angesehen werden. Dieses Gleichgewicht kann lustige Situationen erzeugen, in denen Sie wissen, wie man etwas schneller macht, aber es ist besser für die Sprache im Allgemeinen, wenn Sie das nicht tun.

Im speziellen Fall von Karten in der Struktur, die Sie geben, könnte der Computer Optimierungen finden. Was ist jedoch mit verwandten Strukturen? Was ist, wenn die Funktion keine Karte ist? Was ist, wenn es eine zusätzliche Indirektionsebene gibt, z. B. eine Funktion, die die Map zurückgibt? In diesen Fällen kann der Compiler nicht einfach optimieren. Dies ist das allgemeine Fallproblem.

Wie wenn man den Sonderfall zu tun optimieren, eines von zwei Ergebnissen

• Niemand tritt beruht darauf, weil sie nicht sicher sind, ob es dort ist oder nicht.In diesem Fall werden Artikel wie die, die du zitierst, geschrieben
• Leute beginnen sich darauf zu verlassen, und jetzt ist jeder Entwickler gezwungen sich zu erinnern "Karten, die in dieser Konfiguration gemacht werden, werden für mich automatisch in die schnelle Version konvertiert, aber wenn ich es tue es in dieser Konfiguration nicht. Damit beginnt die Art, wie Menschen die Sprache verwenden zu manipulieren und Lesbarkeit tatsächlich reduzieren kann!

Angesichts der Notwendigkeit für Entwickler über solche Optimierungen im allgemeinen Fall zu denken, wir erwarten, dass diese Optimierungen im einfachen Fall sehen die Entwickler tun ,

Nun, wenn es sich herausstellt, dass der spezielle Fall, den Sie interessiert sind, für etwas massiv wie 2% der weltweiten Codebasis in Haskell, würde es eine viel stärkere sein Argument für die Anwendung Ihrer Spezialfalloptimierung