Nachdem ich KMath kennengelernt hatte , beschloss ich, diese Optimierung auf eine Vielzahl von mathematischen Strukturen und Operatoren zu verallgemeinern, die auf ihnen definiert sind.
KMath ist eine Bibliothek für Mathematik und Computeralgebra, die die kontextorientierte Programmierung in Kotlin in großem Umfang nutzt. KMath trennt mathematische Entitäten (Zahlen, Vektoren, Matrizen) und Operationen auf ihnen - sie werden als separates Objekt geliefert, eine Algebra, die dem Typ der Operanden entspricht, Algebra <T> .
import scientifik.kmath.operations.*
ComplexField {
(i pow 2) + Complex(1.0, 3.0)
}Nach dem Schreiben eines Bytecode-Generators unter Berücksichtigung von JVM-Optimierungen können Sie daher schnelle Berechnungen für jedes mathematische Objekt erhalten - es reicht aus, Operationen in Kotlin zu definieren.
API
Zunächst war es notwendig, eine API für Ausdrücke zu entwickeln und erst dann mit der Grammatik der Sprache und dem Syntaxbaum fortzufahren. Es kam auch die clevere Idee, Algebra über den Ausdrücken selbst zu definieren, um eine intuitivere Oberfläche zu bieten.
Die Basis der gesamten Ausdrucks-API ist die Ausdruck <T> -Schnittstelle . Der einfachste Weg, sie zu implementieren, besteht darin, die Aufrufmethode direkt aus den angegebenen Parametern oder beispielsweise verschachtelten Ausdrücken zu definieren. Eine ähnliche Implementierung wurde als Referenz in das Root-Modul integriert, wenn auch die langsamste.
interface Expression<T> {
operator fun invoke(arguments: Map<String, T>): T
}Fortgeschrittenere Implementierungen basieren bereits auf MST. Diese schließen ein:
- MST-Dolmetscher,
- Generator der MST-Klasse.
Eine API zum Parsen von Ausdrücken von einer Zeichenfolge zu MST ist bereits im KMath-Entwicklungszweig verfügbar, ebenso wie der mehr oder weniger endgültige JVM-Codegenerator.
Fahren wir mit MST fort. Derzeit gibt es in MST vier Arten von Knoten:
- Terminal:
- Symbole (d. h. Variablen)
- Zahlen;
- unäre Operationen;
- binäre Operationen.
Das erste, was Sie damit tun können, ist die Umgehung und Berechnung des Ergebnisses aus den verfügbaren Daten. Durch Übergabe der ID der Operation, zum Beispiel "+", und der Argumente, zum Beispiel 1.0 und 1.0 , in der Zielalgebra können wir auf das Ergebnis hoffen, wenn diese Operation definiert ist. Andernfalls fällt der Ausdruck bei der Auswertung mit einer Ausnahme.
Um mit MST zu arbeiten, gibt es neben der Ausdruckssprache auch Algebra - zum Beispiel MstField:
import scientifik.kmath.ast.*
import scientifik.kmath.operations.*
import scientifik.kmath.expressions.*
RealField.mstInField { number(1.0) + number(1.0) }() // 2.0Das Ergebnis der obigen Methode ist eine Implementierung von Ausdruck <T> , die beim Aufrufen eine Durchquerung des Baums verursacht, die durch Auswerten der an mstInField übergebenen Funktion erhalten wird .
Codegenerierung
Aber das ist noch nicht alles: Beim Durchlaufen können wir die Baumparameter nach Belieben verwenden und müssen uns nicht um die Reihenfolge der Aktionen und die Arität der Operationen kümmern. Dies wird verwendet, um Bytecode zu generieren.
Die Codegenerierung in kmath-ast ist eine parametrisierte Baugruppe der JVM-Klasse. Die Eingabe ist MST und die Zielalgebra, die Ausgabe ist die Instanz Expression <T> .
Die entsprechende Klasse, AsmBuilder , und einige andere Erweiterungen bieten Methoden zum obligatorischen Erstellen von Bytecode auf ObjectWeb ASM. Sie lassen MST-Traversal und Klassenassemblierung sauber aussehen und benötigen weniger als 40 Codezeilen.
Betrachten Sie die generierte Klasse für den Ausdruck "2 * x" . Der aus dem Bytecode dekompilierte Java-Quellcode wird angezeigt:
package scientifik.kmath.asm.generated;
import java.util.Map;
import scientifik.kmath.asm.internal.MapIntrinsics;
import scientifik.kmath.expressions.Expression;
import scientifik.kmath.operations.RealField;
public final class AsmCompiledExpression_1073786867_0 implements Expression<Double> {
private final RealField algebra;
public final Double invoke(Map<String, ? extends Double> arguments) {
return (Double)this.algebra.add(((Double)MapIntrinsics.getOrFail(arguments, "x")).doubleValue(), 2.0D);
}
public AsmCompiledExpression_1073786867_0(RealField algebra) {
this.algebra = algebra;
}
}Zuerst wurde hier die Aufrufmethode generiert , bei der die Operanden nacheinander angeordnet wurden (da sie tiefer im Baum liegen), dann der Aufruf add . Nach dem Aufruf wurde die entsprechende Brückenmethode aufgezeichnet. Als nächstes wurden das Algebra- Feld und der Konstruktor geschrieben . In einigen Fällen, in denen Konstanten nicht einfach in den Pool der Klassenkonstanten eingefügt werden können , wird auch das Konstantenfeld , das Array java.lang.Object , geschrieben .
Aufgrund der vielen Randfälle und Optimierungen ist die Generatorimplementierung jedoch ziemlich kompliziert.
Algebra-Aufrufe optimieren
Um eine Operation aus der Algebra aufzurufen, müssen Sie ihre ID und Argumente übergeben:
RealField { binaryOperation("+", 1.0, 1.0) } // 2.0Ein solcher Aufruf ist jedoch in Bezug auf die Leistung teuer: Um die aufzurufende Methode auszuwählen, führt RealField eine relativ teure Tableswitch-Anweisung aus , und Sie müssen sich auch an das Boxen erinnern. Obwohl alle MST-Operationen in dieser Form dargestellt werden können, ist es daher besser, einen direkten Aufruf zu tätigen:
RealField { add(1.0, 1.0) } // 2.0Es gibt keine spezielle Konvention zum Zuordnen von Operations-IDs zu Methoden in Algebra <T> -Implementierungen . Daher mussten wir eine Krücke einfügen, in die manuell geschrieben wurde, dass beispielsweise "+" der Methode add entspricht. Es gibt auch Unterstützung für günstige Situationen, in denen Sie eine Methode für eine Operations-ID mit demselben Namen, der erforderlichen Anzahl von Argumenten und deren Typen finden können.
private val methodNameAdapters: Map<Pair<String, Int>, String> by lazy {
hashMapOf(
"+" to 2 to "add",
"*" to 2 to "multiply",
"/" to 2 to "divide",
...private fun <T> AsmBuilder<T>.findSpecific(context: Algebra<T>, name: String, parameterTypes: Array<MstType>): Method? =
context.javaClass.methods.find { method ->
...
nameValid && arityValid && notBridgeInPrimitive && paramsValid
}Ein weiteres großes Problem ist das Boxen. Wenn wir uns die Java-Methodensignaturen ansehen, die nach dem Kompilieren desselben RealField erhalten werden, sehen wir zwei Methoden:
public Double add(double a, double b)
// $FF: synthetic method
// $FF: bridge method
public Object add(Object var1, Object var2)Natürlich ist es einfacher, sich nicht mit Boxen und Unboxing zu beschäftigen und die Bridge-Methode aufzurufen: Sie wurde hier aufgrund der Löschung des Typs angezeigt, um die Methode add (T, T): T korrekt zu implementieren , deren Typ T in ihrem Deskriptor tatsächlich in java.lang gelöscht wurde .Objekt .
Das direkte Aufrufen von add von zwei Doubles ist ebenfalls nicht ideal, da der Rückgabewert Bauxit ist (es gibt eine Diskussion darüber in YouTrack Kotlin ( KT-29460 ), aber es ist besser, es aufzurufen, um bestenfalls zwei Casts von Eingabeobjekten in java.lang zu speichern .Number und deren Unboxing verdoppeln .
Die Lösung dieses Problems dauerte am längsten. Die Schwierigkeit besteht hier nicht darin, Aufrufe der primitiven Methode zu erstellen, sondern darin, dass Sie sowohl primitive Typen (wie double) als auch deren Wrapper ( z. B. java.lang.Double ) auf dem Stapel kombinieren und das Boxen an den richtigen Stellen einfügen müssen (z. java.lang.Double.valueOf ) und Unboxing ( doubleValue ) - es war absolut nicht erforderlich, mit Anweisungstypen im Bytecode zu arbeiten.
Ich hatte Ideen, meine getippte Abstraktion über den Bytecode zu hängen. Dazu musste ich mich eingehender mit der ObjectWeb ASM-API befassen. Am Ende wandte ich mich dem Kotlin / JVM-Backend zu und untersuchte die StackValue- Klasse im Detail(Ein typisiertes Fragment des Bytecodes, das letztendlich dazu führt, dass ein Wert für den Operandenstapel erhalten wird), hat das Dienstprogramm Type herausgefunden , mit dem Sie bequem mit den im Bytecode verfügbaren Typen (Grundelemente, Objekte, Arrays) arbeiten und den Generator neu schreiben können mit seiner Verwendung. Das Problem, ob der Wert auf dem Stapel ein- oder ausgepackt werden soll, wurde von selbst gelöst, indem eine ArrayDeque hinzugefügt wurde, die die vom nächsten Aufruf erwarteten Typen enthält.
internal fun loadNumeric(value: Number) {
if (expectationStack.peek() == NUMBER_TYPE) {
loadNumberConstant(value, true)
expectationStack.pop()
typeStack.push(NUMBER_TYPE)
} else ...?.number(value)?.let { loadTConstant(it) }
?: error(...)
}Schlussfolgerungen
Am Ende konnte ich mit ObjectWeb ASM einen Codegenerator erstellen, um MST-Ausdrücke in KMath auszuwerten. Der Leistungsgewinn über eine einfache MST-Durchquerung hängt von der Anzahl der Knoten ab, da der Bytecode linear ist und keine Zeit für die Knotenauswahl und -rekursion verschwendet. Beispielsweise beträgt für einen Ausdruck mit 10 Knoten der Zeitunterschied zwischen der Auswertung mit der generierten Klasse und dem Interpreter 19 bis 30%.
Nachdem ich die Probleme untersucht hatte, auf die ich gestoßen war, kam ich zu folgenden Schlussfolgerungen:
- Sie müssen sofort die Funktionen und Dienstprogramme von ASM studieren - sie vereinfachen die Entwicklung erheblich und machen den Code lesbar ( Typ , InstructionAdapter , GeneratorAdapter ).
- MaxStack , , — ClassWriter COMPUTE_MAXS COMPUTE_FRAMES;
- ;
- , , , ;
- , — , , ByteBuddy cglib.
Danke fürs Lesen.
Autoren des Artikels:
Jaroslaw Sergejewitsch Postowalow , MBOU „Lyceum № 130 benannt nach Akademiker Lavrentyev “, Mitglied des Labors für mathematische Modellierung unter der Leitung von Voytishek Anton Vatslavovich
Tatyana Abramova , Forscherin des Labors für Methoden nuklearphysikalischer Experimente bei JetBrains Research .