Erkennen Compiler wie Javac reine Funktionen automatisch und parallelisieren sie?

Es ist bekannt, dass reine Funktionen das Parallelisieren erleichtern. Was ist an der funktionalen Programmierung, die sie an die parallele Ausführung anpasst?

Sind Compiler wie Javac intelligent genug, um zu erkennen, ob eine Methode eine reine Funktion ist? Man kann immer Klassen implementieren, die funktionale Schnittstellen wie Function implementieren , aber Nebenwirkungen haben.

Sind Compiler wie Javac intelligent genug, um zu erkennen, ob eine Methode eine reine Funktion ist?

Es ist keine Frage von "klug genug". Dies wird als Reinheitsanalyse bezeichnet und ist im allgemeinen Fall nachweislich unmöglich: Es ist gleichbedeutend mit der Lösung des Halteproblems.

Jetzt tun Optimierer natürlich die ganze Zeit nachweislich Unmögliches. "Nachweislich Unmöglich im Allgemeinen" bedeutet nicht, dass es niemals funktioniert, sondern nur, dass es nicht in allen Fällen funktioniert. Es gibt also tatsächlich Algorithmen, mit denen überprüft werden kann, ob eine Funktion rein ist oder nicht. Oftmals lautet das Ergebnis "Ich weiß nicht", was bedeutet, dass Sie aus Gründen der Sicherheit und Richtigkeit davon ausgehen müssen dass diese bestimmte Funktion unrein sein könnte.

Und selbst in den Fällen, in denen es funktioniert , sind die Algorithmen komplex und teuer.

Das ist also Problem Nr. 1: Es funktioniert nur für Sonderfälle .

Problem Nr. 2: Bibliotheken . Damit eine Funktion rein ist, kann sie immer nur reine Funktionen aufrufen (und diese Funktionen können nur reine Funktionen aufrufen usw.). Javac kennt sich offensichtlich nur mit Java aus, und es kennt sich nur mit Code aus, den es sehen kann. Wenn Ihre Funktion also eine Funktion in einer anderen Kompilierungseinheit aufruft, können Sie nicht wissen, ob sie rein ist oder nicht. Wenn es eine Funktion aufruft, die in einer anderen Sprache geschrieben ist, können Sie es nicht wissen. Wenn es eine Funktion in einer Bibliothek aufruft, die möglicherweise noch nicht installiert ist, wissen Sie es nicht. Und so weiter.

Dies funktioniert nur, wenn Sie eine Ganzprogrammanalyse haben, wenn das gesamte Programm in derselben Sprache geschrieben ist und alles auf einmal kompiliert wird. Sie können keine Bibliotheken verwenden.

Problem Nr. 3: Planung . Sobald Sie herausgefunden haben, welche Teile rein sind, müssen Sie sie noch für separate Threads einplanen. Oder nicht. Das Starten und Stoppen von Threads ist sehr teuer (insbesondere in Java). Auch wenn Sie einen Thread-Pool führen und diese nicht starten oder stoppen, ist das Wechseln des Thread-Kontextes ebenfalls teuer. Sie müssen sicherstellen, dass die Berechnung erheblich länger ausgeführt wird als für die Planung und den Kontextwechsel erforderlich. Andernfalls verlieren Sie die Leistung und gewinnen sie nicht.

Wie Sie wahrscheinlich schon vermutet haben, ist es im allgemeinen Fall nachweislich unmöglich, herauszufinden, wie lange eine Berechnung dauern wird (wir können nicht einmal herausfinden, ob sie eine begrenzte Zeit in Anspruch nehmen wird, geschweige denn, wie viel Zeit) und selbst in diesem Fall schwierig und teuer der Sonderfall.

Nebenbei: Javac und Optimierungen . Beachten Sie, dass die meisten Implementierungen von Javac nicht viele Optimierungen durchführen. Die Java-Implementierung von Oracle basiert beispielsweise auf der zugrunde liegenden Ausführungs-Engine, um Optimierungen vorzunehmen . Dies führt zu einer Reihe weiterer Probleme: Zum Beispiel entschied Javac, dass eine bestimmte Funktion rein und teuer genug ist, und kompiliert sie, um auf einem anderen Thread ausgeführt zu werden. Dann kommt der Optimierer der Plattform (zum Beispiel der HotSpot C2 JIT-Compiler) und optimiert die gesamte Funktion weg. Jetzt haben Sie einen leeren Thread, der nichts tut. Oder stellen Sie sich vor, Javac entschließt sich erneut, eine Funktion für einen anderen Thread zu planen, und der Plattformoptimierer könnte dies tun Optimieren Sie es vollständig, es sei denn, es kann kein Inlining über Threadgrenzen hinweg ausgeführt werden. Daher wird eine Funktion, die vollständig optimiert werden kann, jetzt unnötig ausgeführt.

So etwas zu tun ist nur dann wirklich sinnvoll, wenn Sie einen einzelnen Compiler haben, der die meisten Optimierungen auf einmal ausführt, sodass der Compiler alle verschiedenen Optimierungen auf verschiedenen Ebenen und deren Interaktionen miteinander kennt und ausnutzen kann.

Beachten Sie, dass zum Beispiel die HotSpot C2 JIT - Compiler tatsächlich tut einige Auto-Vektorisierung durchführen, die auch eine Form der Auto-Parallelisierung.

Die überstimmte Antwort bemerkte nichts. Die synchrone Kommunikation zwischen Threads ist extrem teuer. Wenn die Funktion mit einer Rate von vielen Millionen Aufrufen pro Sekunde ausgeführt werden kann, tut es Ihnen mehr weh, sie zu parallelisieren, als sie unverändert zu lassen.

Die schnellste Form der synchronen Inter-Thread-Kommunikation unter Verwendung von Busy-Loops mit atomaren Variablen ist leider ineffizient. Wenn Sie auf Bedingungsvariablen zurückgreifen müssen, um Energie zu sparen, leidet die Leistung Ihrer Inter-Thread-Kommunikation.

Der Compiler muss also nicht nur feststellen, ob eine Funktion rein ist, sondern auch die Ausführungszeit der Funktion abschätzen, um festzustellen, ob die Parallelisierung ein Nettogewinn ist. Außerdem müsste zwischen Busy-Loops mit atomaren Variablen oder Bedingungsvariablen gewählt werden. Und es müsste Fäden hinter Ihrem Rücken erstellen.

Wenn Sie die Threads dynamisch erstellen, ist dies sogar langsamer als die Verwendung von Bedingungsvariablen. Der Compiler müsste also eine bestimmte Anzahl von Threads einrichten, die bereits ausgeführt werden.

Die Antwort auf Ihre Frage lautet also Nein . Compiler sind nicht "schlau" genug, um reine Funktionen automatisch zu parallelisieren, insbesondere in der Java-Welt. Sie sind schlau, wenn sie nicht automatisch parallelisiert werden!