chip Kann ein Compiler automatisch reine Funktionen ohne die Typinformation über Reinheit erkennen?




compiler linker (4)

Das Bestimmen, ob eine Funktion rein ist (selbst in dem begrenzten Sinne, der von GCC verwendet wird), ist äquivalent zu dem Halteproblem, so dass die Antwort "nicht für beliebige Funktionen" ist. Es ist möglich, automatisch zu erkennen, dass einige Funktionen rein sind, andere nicht, und den Rest als "unbekannt" kennzeichnen, was in einigen Fällen eine automatische Parallelisierung ermöglicht.

Meiner Erfahrung nach sind selbst Programmierer nicht sehr gut darin, solche Dinge herauszufinden, also möchte ich, dass das Typsystem mir hilft, nicht nur für den Optimierer, sondern für mich .

Ich streite also mit meinem Freund, der behauptet, dass ein Compiler wie GCC eine reine Funktion automatisch ohne jegliche Art von Information erkennen kann. Ich bezweifle das.

Sprachen wie D oder Haskell haben Reinheit in ihren Typsystemen und ein Programmierer definiert explizit, welche Funktion rein ist oder nicht. Eine reine Funktion hat keine Nebenwirkungen und kann daher sehr einfach parallelisiert werden.

Die Frage ist also: Ist das alles notwendig oder nicht? Könnte ein Compiler Reinheit ohne Meta- oder Typinformationen erkennen, indem er annimmt, dass alles, was IO ausführt oder auf globale Variablen automatisch zugreift, nicht rein ist?


Answer #1

Ich entdeckte beim Schreiben eines Artikels , der die C # - und C ++ - Performance vergleicht, dass Visual C ++ tatsächlich eine reine Funktion mittlerer Komplexität erkennen kann, während er eine Funktion aufruft , die ein Polynom berechnet .

Ich habe die Polynomfunktion in einer Schleife aufgerufen, um Zeit auf der Uhr aufzuessen. Der Compiler hat den Aufruf so optimiert, dass er einmal ausgeführt wurde, bevor die Schleife gestartet wurde, und das Ergebnis innerhalb der Schleife wiederverwendet. Um das zu tun, müsste es wissen, dass es keine Nebenwirkungen gibt.

Ich muss allerdings sagen, es ist schön, dass wir garantieren können, dass der Compiler eine Optimierung durchführen kann, indem wir eine Funktion als rein markieren, und es dient auch als eine Form der Dokumentation.


Answer #2

Sicher, Sie können in einigen Fällen reine Funktionen erkennen. Zum Beispiel,

int f(int x)
{
    return x*2;
}

kann mit einfacher statischer Analyse als rein erkannt werden. Die Schwierigkeit besteht darin, dies zu tun, und das Erkennen von Schnittstellen, die einen "internen" Zustand verwenden, aber extern rein sind, ist im Grunde unmöglich.

GCC hat die -Wsuggest-attribute=pure und -Wsuggest-attribute=const , die Funktionen vorschlagen, die Kandidaten für die attributes pure und const könnten. Ich bin mir nicht sicher, ob es konservativ ist (dh viele reine Funktionen vermisst, aber es niemals für eine nicht-reine Funktion vorschlägt) oder den Benutzer entscheiden lässt.

Beachten Sie, dass die GCC-Definition von pure "nur von Argumenten und globalen Variablen abhängt":

Viele Funktionen haben außer dem Rückgabewert keine Auswirkungen und ihr Rückgabewert hängt nur von den Parametern und / oder globalen Variablen ab. Eine solche Funktion kann einer gemeinsamen Teilausdruckseliminierung und Schleifenoptimierung unterzogen werden, genau wie es ein arithmetischer Operator wäre. Diese Funktionen sollten mit dem Attribut pure deklariert werden.

- attributes

Strenge Reinheit, dh die gleichen Ergebnisse für dieselben Argumente unter allen Umständen, wird durch das Attribut const , aber eine solche Funktion kann nicht einmal einen Zeiger, der an sie übergeben wird, dereferenzieren. So sind die Möglichkeiten der Parallelisierung für pure Funktionen begrenzt, aber im Vergleich zu den reinen Funktionen, die Sie in einer Sprache wie Haskell schreiben können, können wesentlich weniger Funktionen aufgebaut werden.

Die automatische Parallelisierung reiner Funktionen ist übrigens nicht so einfach, wie Sie vielleicht denken; Der schwierige Teil wird entscheiden, was parallelisiert werden soll. Parallele Berechnungen, die zu billig sind, und Overhead machen es sinnlos. Parallelisieren Sie nicht genug und Sie profitieren nicht davon. Ich kenne keine praktische funktionale repa , die aus diesem Grund eine automatische Parallelisierung durchführt, obwohl Bibliotheken viele Operationen im Hintergrund ohne explizite Parallelität im Benutzercode parallelisieren.


Answer #3

Es gibt ein anderes Problem. Erwägen

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}

Die Funktion ist effektiv rein, obwohl sie unreinen Code enthält, aber dieser Code kann nicht erreicht werden. Nehmen wir nun an, dass false durch g(i) aber wir wissen ziemlich sicher, dass g (i) falsch ist (z. B. könnte g prüfen, ob sein Argument eine Lychrel-Zahl ist ). Um zu beweisen, dass Isthispure tatsächlich rein ist, müsste der Compiler beweisen, dass keine Lychrel-Zahlen existieren.

(Ich gebe zu, dass dies eine ziemlich theoretische Überlegung ist. Man könnte auch entscheiden, dass, wenn eine Funktion irgendeinen unreinen Code enthält, dieser selbst unrein ist. Aber dies ist nicht durch das C-System, IMHO, gerechtfertigt.)





d