Referenzanforderung: Optimierung der Verfahren für Listen in dynamischen Sprachen durch vorherige Durchführung von Sicherheitsüberprüfungen

7

Für mein Science-Fair-Projekt habe ich eine Optimierung der Sortierroutine von Python implementiert . Die Idee ist, die Sicherheitsüberprüfungen, die bei jedem Vergleich durchgeführt werden müssen, z. B. Typprüfungen und Zeichenbreitenprüfungen, außerhalb der Sortierschleife zu verschieben und sie alle in einem Durchgang durchzuführen. Basierend auf den Ergebnissen der Prüfungen wird dann eine optimierte Vergleichsfunktion aus einem Portfolio ausgewählt. Wenn die Prüfungen beispielsweise feststellen, dass alle Objekte vom gleichen Typ sind, kann die ausgewählte Vergleichsfunktion die normalerweise erforderliche Prüfung "Sind die Objekttypen kompatibel?" Überspringen. Usw.

Ich muss dies als Papier schreiben und arbeite derzeit an einer Literaturübersicht. Gibt es Artikel, die ähnliche Techniken in anderen dynamischen Sprachen / allgemein beschreiben?

Elliot Gorokhovsky
quelle
2
Dies hängt zwar nicht direkt zusammen, kann Ihnen aber hoffentlich dabei helfen, in potenziell nützliche Richtungen zu weisen. Dies erinnert bei vielen JIT / Dynamic-Compilern etwas an Inline-Caching. Die Idee ist, Traces, die möglicherweise "heiß" sind, in Buckets zu profilieren, die durch ihre Eigenschaften indiziert sind (z. B. Liste der Ints, Liste der Zeichenfolgen, gemischte Liste usw.). Angesichts dieser Buckets generieren wir dann dynamisch Code, der für jeden Eigenschaftssatz optimiert ist, und zwischenspeichern sie entsprechend. Infolgedessen enthält die Just-In-Time-Literatur einige Optimierungen, die mehr oder weniger in Ihre Form passen. Viel Spaß beim Nachschlagen!
Lee
1
@LeeGao Das klingt genau so, wie ich es tue, außer dass die "heißen" Traces fest codiert sind und wir nichts dynamisch generieren, sondern auch die optimierten Traces hart codieren. Was ist ein gutes Umfragepapier / Orientierungspapier für diese Technik? Ich habe versucht, "JIT-Eimer" zu googeln, konnte aber nichts finden :)
Elliot Gorokhovsky
1
"Inline-Caching" sollte Ihnen einige gute Ergebnisse bringen. "Bucket" ist nur ein Wort, das ich benutze, wenn ich versuche, es Freunden und Kollegen zu erklären. : P
Lee
@ LeeGao :) Ja, danke. Ich sehe jetzt, dass das, was ich tue, buchstäblich genau das ist, was Inline-Caching ist. Gut zu wissen!
Elliot Gorokhovsky

Antworten:

7

Mir ist so etwas nicht genau bekannt, aber es gibt einige Dinge, die wohl miteinander zusammenhängen.

Für die spezifische Sortierung hängt dies mit der Schwartzschen Transformation zusammen , allerdings mit einem ganz anderen Ziel. In der Schwartzschen Transformation durchlaufen Sie die Eingabe mit einer teuren Funktion, koppeln Eingabe und Ausgabe miteinander und sortieren dann nach der Ausgabe. Dies steht im Gegensatz zur Ausführung dieser teuren Funktion bei jeder Operation. In Ihrem Fall wären Ihre "teuren Funktionen" die Typprüfungen und die dynamischen Versendungen . Ein bisschen anders würden Sie eine Eigenschaft auch für die gesamte Liste überprüfen und dann basierend darauf auswählen, welche Vergleichsoperation verwendet werden soll.

Ganz anders ausgedrückt gibt es eine allgemeine Technik namens polymorphes Inline-Caching ( vom Self-Team entwickelt und unter anderem in der Arbeit von Craig Chamber behandelt ) und eine allgemeinere adaptive Optimierung , die in einigen virtuellen Maschinen verwendet wird. Polymorphes Inline-Caching löst das Problem, dass wir bei einem dynamischen Versand zu einem völlig unbekannten Code springen und ihn daher nicht inline einbinden und ihn und die aktuelle Funktion optimieren können. Die Lösung ist einfach: Führen Sie einfach einen ifTest durch, um festzustellen, ob wir uns in einem bestimmten Fall befinden. In diesem Fall können wir diesen Code einbinden, andernfalls führen wir den dynamischen Versand durch. Das Problem ist, dass es eine unbegrenzte, unbekannte Anzahl möglicher Fälle gibt. Dies ist jedoch kein Problem für aJust-In-Time (JIT) -Compiler, der dies nur für die zur Laufzeit tatsächlich angezeigten Fälle tun kann.

Dies löst Ihr Problem nicht, da der dynamische Versand auf der Laufzeitklasse eines Objekts basiert und nicht auf einem beliebigen Prädikat wie "Alle Elemente dieses Arrays haben denselben Typ". Hier kommt die adaptive Optimierung ins Spiel und Dinge wie die Verfolgung von JIT-Compilern. Es ist durchaus denkbar, dass das mehrmalige Abrollen einer Schleife oder das Inlinen einiger Rekursionsstufen dazu führen kann, dass viele Typprüfungen durch einfache Optimierungen des konstanten Ausbreitungsstils eliminiert werden und in einigen Fällen möglicherweise durch komplexere Optimierungen vollständig eliminiert werden. Trotzdem wird es oft nicht das Gleiche tun, wie Sie es vorschlagen, und es müsste zuerst eine Ablaufverfolgung für jede Verwendung der Sortierfunktion angezeigt werden. Wenn es jedoch weiß, dass alle Elemente Zahlen sind, beispielsweise aus früherem Code, kann die Überprüfung vollständig vermieden werden.

Derek Elkins verließ SE
quelle
Tatsächlich ist das polymorphe Inline-Caching sehr relevant, da ich viele Sonderfall-Vergleichsfunktionen (wie für Strings, Ints und Floats) habe, die inline sind. Mein Code geht durch und sucht nach diesen Sonderfällen. Wenn er einen findet, ersetzt er die Vergleichsfunktion durch eine Sonderfallfunktion.
Elliot Gorokhovsky