Optimierung der Interoperabilität zwischen Lua und C++

Einleitung

Die Roblox-Engine ist in einer Kombination aus C++ und Lua geschrieben, wobei der Code für rechenintensive Operationen in optimiertem C++ verfasst ist, während die Spielelogik und Skripte zur Vereinfachung der Entwicklung in Lua geschrieben sind. Damit dieses Modell effektiv ist, müssen die Übergänge zwischen Lua und C++ so schnell wie möglich erfolgen, da jede in diesem Niemandsland verbrachte Zeit im Grunde nur verschwendete Millisekunden sind.

In den letzten Monaten haben wir verschiedene Verbesserungen an diesem Teil des Systems eingeführt. Ein Aspekt – nämlich der eigentliche Aufruf von C++-Methoden aus Lua heraus – war besonders interessant, da er zu erheblichen Geschwindigkeitssteigerungen führte und es erforderte, tief in die Innereien von Lua einzutauchen, um zu verstehen, wie die Dinge unter der Haube funktionieren.

Letztendlich haben wir die Lua-VM selbst modifiziert, aber bevor wir darauf eingehen, müssen wir einige Grundlagen schaffen.

Compiler, VM und Bytecode

Wenn Lua-Quellcode kompiliert wird, wird er in Lua-Bytecode übersetzt, den die Lua-VM dann ausführt. Lua-Bytecode umfasst insgesamt etwa 35 Befehle, beispielsweise für das Lesen/Schreiben von Tabellen, das Aufrufen von Funktionen, die Durchführung von binären Operationen, Sprünge und bedingte Anweisungen und so weiter. Die Lua-VM ist registerbasiert, im Gegensatz zu vielen anderen VMs, die stapelbasiert sind. Daher besteht ein Teil der Arbeit des Compilers bei der Erzeugung von Bytecode darin, zu bestimmen, welche Register die einzelnen Befehle verwenden sollen.

Jeder Befehl hat die Form „OP_CODE A B“ oder „OP_CODE A B C“, wobei „OP_CODE“ der Opcode ist (zum Beispiel CALL zum Aufrufen einer Funktion) und A/B/C die Opcode-Argumente sind. Die Argumente (oder Register) sind keine tatsächlichen Werte. Stattdessen handelt es sich um Indizes, die auf eine von zwei Tabellen verweisen: die Konstantentabelle (geschrieben als Kst(..)) oder die Registertabelle (geschrieben als R(..)).

Eine detaillierte Beschreibung des Lua-Bytecodes finden Sie unter „A No-Frills introduction to Lua 5.1 VM Instructions“. Es ist viel spannender, als es klingt; versprochen!

Um dir einen Eindruck davon zu vermitteln, wie Lua-Bytecode aussieht, werden wir zunächst einige einfache Programme durchgehen und dann zu relevanteren Beispielen übergehen.

Mit dem Dienstprogramm Chunkspy können wir Lua-Bytecode in Lua-Assembler-Code disassemblieren und eine Auflistung des Codes sowie der Konstantentabelle erhalten, sodass wir im Grunde sehen können, welcher Bytecode für einen beliebigen Lua-Quellcode generiert wird.

Einfache Bytecode-Beispiele

Ein einfaches Programm wie „x = 10“ wird wie folgt kompiliert:

.const "x";  0

.const 10;  1

[1]  loadk       0   1       ;   10

[2]  setglobal   0   0       ;   x 

Die ersten beiden Zeilen zeigen die Konstantentabelle (mit dem String-Wert „x“ in Slot 0 und dem Integer-Wert 10 in Slot 1), und die folgenden beiden Zeilen sind die disassemblierten Opcodes.

[Zeile 1] Wenn wir den Opcode LOADK in „No Frills“ nachschlagen, sehen wir, dass er die Form „LOADK A Bx --- R(A) := Kst(Bx)“ hat. LOADK hat also zwei Argumente (die Register A und B) und seine Operation besteht darin, den Wert, der in der Konstantentabelle an der durch das zweite Register angegebenen Stelle steht, Kst(Bx), dem Register an der durch das erste Argument angegebenen Stelle zuzuweisen, R(A). „Bx“ bedeutet lediglich, dass das B-Register erweitert und mit mehr Bits belegt wird, da der Opcode nur zwei Argumente hat.

[Zeile 2] SETGLOBAL hat die Form „SETGLOBAL A Bx --- Gbl[Kst(Bx)] := R(A).“ Es weist der globalen Tabelle einen Wert zu, wobei der Schlüssel verwendet wird, der durch den Eintrag der Konstantentabelle an der vom zweiten Argument angegebenen Stelle gegeben ist. Da das zweite Argument 0 ist und der Wert der Konstantentabelle an der Stelle 0 „x“ lautet, schreibt es unter Verwendung des Schlüssels „x“ etwas in die globale Tabelle. Was auch immer sich in der Registertabelle an der vom ersten Argument angegebenen Stelle befindet, wird geschrieben – und dies wurde durch den vorherigen Befehl mit dem Wert 10 geladen.

Schauen wir uns ein etwas komplizierteres Beispiel an: „x = 10; y = x“. Die manuelle Ausführung des Codes überlasse ich dem Leser als Übung. :)

.const "x";   0

.const 10;    1

.const"y";    2

[1]  loadk       0   1       ;   10

[2]  setglobal   0   0       ;   x

[3]  getglobal   0   0       ;   x

[4]  setglobal   0   2       ;   y

Bytecode für Funktionsaufrufe

Schauen wir uns den für „foo(10):“ generierten Code an:

.const "foo"; 0

.const 10;    1

[1]  getglobal  0    0  ;  foo   //  R(A)  :=  Gbl[Kst(Bx)]

[2]  loadk      1     1 ;  10   //  R(A)  :=  Kst(Bx)

[3]  call       0     2      1

 
Um Funktionsaufrufe auszuführen, muss die Funktion in das erste Register und die Argumente in die nachfolgenden Register geladen werden. Die Semantik für „CALL A B C“ ist so, dass A die Funktion enthält, B die Anzahl der Argumente ist (tatsächlich ist es die Anzahl der Argumente +1, aufgrund der Art und Weise, wie „...“ implementiert ist) und C die Anzahl der Rückgabewerte ist (auch hier ist es die Anzahl der Rückgabewerte +1, um mehrere Rückgabewerte zu behandeln).

Die ersten beiden Zeilen sind uns bekannt; sie laden einen Wert in den Registertabellen-Slot 0 und den Wert 10 in den Registertabellen-Slot 1. Die dritte Zeile führt den Funktionsaufruf aus, wobei der Wert in Register A (Registertabellen-Slot 0, der mit „foo“ geladen wurde) verwendet wird, wobei B die Anzahl der Argumente und C die Anzahl der Rückgabewerte angibt (denken Sie daran, dass sowohl zu B als auch zu C jeweils 1 addiert werden sollte). Bevor die Funktion aufgerufen werden kann, überprüft die VM außerdem, ob der Wert in R(A) tatsächlich aufrufbar ist.

Lua verfügt über einen Mechanismus, der es Benutzern ermöglicht, die Funktionalität von Tabellen zu erweitern, indem sie eine Metatabelle mit einer bestehenden Tabelle verknüpfen. Die Metatabelle enthält Fallback-Methoden, die aufgerufen werden, wenn eine bestimmte Methode oder Operation nicht auf der Haupttabelle ausgeführt werden kann (eine ausführliche Beschreibung finden Sie unter https://www.lua.org/pil/13.html).

Für unsere Zwecke sind die relevantesten Einträge in der Metatabelle die Felder „__index“ und „__call“. __index wird beim Nachschlagen eines Elements in einer Tabelle verwendet, sodass der Code „local x = my_table[10]“ zunächst die __index-Methode auf my_table aufrufen würde. Sollte dies fehlschlagen, würde stattdessen versucht werden, __index auf der Metatabelle von my_table aufzurufen. __call wird in ähnlicher Weise verwendet, wenn man versucht, etwas als Funktion zu behandeln und es aufzurufen, zum Beispiel „local x = foo(42)“

Damit Lua und C++ zusammenarbeiten können, benötigen sie eine Möglichkeit, Funktionen und Daten gemeinsam zu nutzen. Lua erleichtert dies durch die Bereitstellung eines Datentyps namens UserData. UserData-Objekte können in der C++-Umgebung erstellt werden, und da es sich um native Lua-Datentypen handelt, können sie mit Metatabellen versehen werden, die es Lua-Code ermöglichen, mit ihnen zu interagieren, als wären sie ganz normale Lua-Objekte.

Aufrufe von Mitgliedsfunktionen

Okay, zurück zum Bytecode! Das nächste Beispiel ist etwas interessanter, da es zeigt, was passiert, wenn man Code wie „foo:bar(10),” hat, der die Methode bar auf der Instanz foo (eine Instanz der Klasse Foo) aufruft.

foo:bar(10)

.const "foo";   0

.const "bar";   1

.const  10;     2

[1]  getglobal  0    0         ;  foo

[2]  self       0     0    257 ;  "bar"

[3]  loadk      2     2        ;  10

[4]  call       0     3      1

 
Neu ist hier die self-Anweisung [Zeile 2], die wir bisher noch nicht gesehen haben. Self hat die Syntax „SELF A B C --- R(A) := R(B)[RK(C)]; R(A+1) := R(B)“, also lassen Sie uns das einmal aufschlüsseln. In der Registertabelle wird an der Stelle R(A) das Ergebnis der Tabellensuche an der Stelle R(B) unter Verwendung des Schlüssels an der Stelle RK(C) abgelegt. Außerdem wird der Inhalt der Stelle R(B) in die Stelle R(A+1) kopiert, aber dazu später mehr. Vielleicht fällt dir auf, dass der Wert des C-Registers 257 ist. Dies ist zulässig, da Lua RK(C) verwendet, um den Wert nachzuschlagen, und RK je nach Wert des 9. Bits entweder die Registertabelle oder die Konstantentabelle verwendet. Ist es eine 1, was in diesem Fall zutrifft, wird die Konstantentabelle verwendet; andernfalls erfolgt die Suche in der Registertabelle (nach Ausblenden des höchsten Bits).

Zeile 3 setzt 10 in Slot 2, und schließlich führt Zeile 4 den Funktionsaufruf aus.

Die SELF-Anweisung erfüllt zwei Zwecke. Erstens sucht sie nach der Methode „bar“ in der Klasse Foo und legt sie in R(A) ab. Zweitens, da foo eine Instanzmethode ist und wir beim Aufruf die Instanz der Klasse benötigen, auf der wir die Methode aufrufen, legt sie diese Instanz in R(A+1) ab. Wenn Sie mit Klassen in Python vertraut sind, erkennen Sie das Konzept vielleicht: Methoden werden üblicherweise als „def my_method(self, arg1, arg2..)” geschrieben, wobei self die Klasseninstanz ist.

Wir müssen uns damit etwas eingehender befassen und uns ansehen, was passiert, wenn die foo-Instanz ein C++-Objekt ist, das in Lua als UserData-Objekt dargestellt wird.

Der SELF-Aufruf kann als Tabellenabfrage betrachtet werden, d. h. Foo[„bar“] (das große Foo steht für die Klasse Foo, im Gegensatz zu foo, der Instanz), und wir wissen, dass Abfragen die __index-Methode verwenden. Als die foo-Instanz in der C++-Umgebung erstellt wurde, wurde der Instanz eine Metatabelle zugeordnet, und das __index-Feld dieser Metatabelle wurde auf einen C++-Codeabschnitt gesetzt, der aufgerufen wird, wenn __index aufgerufen wird.

Wenn C/C++ von Lua aus aufgerufen wird, wird als einzige Datenübertragung ein lua_State-Objekt übergeben. Dieses Objekt enthält alles, was mit dem aktuell laufenden Lua-Thread zusammenhängt. Die wichtigste Information im State-Objekt ist der Lua-Stack, der die Funktionsargumente enthält (auf die über die Funktionen der Familie lua_tointeger/tostring usw. zugegriffen wird) und auch dazu dient, Werte an Lua zurückzugeben.

In Pseudo-C++ sieht unsere __index-Funktion in etwa so aus:

int  metaIndex(lua_State*  L)

{

           //  first  argument  is  the  userdata  object

           UserData*  userdata  =  lua_touserdata(L,  1);


           //  get  some  kind  of  descriptor,  that  contains  information

           //  about  what  methods the  class  exposes

           ClassDescriptor*  desc =  getDescriptorForUserData(userdata);


           //  See  if  the  class  has  the  requested  method

           const  char*  methodName  =  lua_tostring(L,  2);

           MemberFunctionPtr  method  = desc->hasMethod(methodName);

           if  (method)

           {

                   //  Upvalues  are  values  that  are  available  when  a  C

                   //  function  is  invoked.

                   lua_pushupvalue(L,  method);

                   lua_pushcfunction(L,  methodInvoker);

                   return  1;

           }

           else

           {

                   lua_pushnil(L);

                   return  0;

           }

}

 
Viele interne Details werden hier übersprungen, aber hier ist der Kern der Sache. Da das UserData-Objekt als erstes Argument auf dem Lua-Stack übergeben wird, können wir einen Deskriptor finden, der die eigentliche C++-Klasse beschreibt, und über den Deskriptor können wir sehen, ob diese Klasse eine Methode mit dem angegebenen Namen hat. Wenn ja, wird ein Funktionszeiger auf einen Methodenaufrufer auf den Lua-Stack geschoben, und wir geben Erfolg zurück.

Nach diesem Aufruf legt die Lua-VM die restlichen Argumente in die Registertabelle und ruft dann die Funktion auf, die wir aus der metaIndex-Methode zurückgegeben haben. Diese ruft wiederum C++ auf und landet in der Aufruferfunktion:

int  methodInvoker(lua_State*  L)

{ &nbsp;  <br>  &nbsp; &nbsp;    &nbsp;//  Get  the  userdata  and  the  class  descriptor

           UserData*  userdata  =  lua_touserdata(L,  1);

           ClassDescriptor*  desc  =  getDescriptorForUserData(userdata);

           Class*  instance  =  (Class*)userdata;


           //  Using  Lua's  upvalue  mechanism,  get  the  'method'

           //  that  was  stored  in  metaIndex.

           MemberFunctionPtr  method  =  lua_getupvalue(L,  1);


           //  This  is  hand-wavey,  but  we  have  some  mechanism  of  being

           //  able  to  invoke  a  member  function  via  the  class  descriptor,

           //  and  also  pop  arguments  from  the  Lua  stack,  and  push  return  values

           return  desc-&gt;invokeFunction(instance,  method,  L);
}

 
Der methodInvoker verwendet ebenfalls den ClassDescriptor, kann diesmal jedoch die Member-Funktion aufrufen und die richtigen Argumente vom Stack entfernen.

Die Zielgerade!

Da wir nun die beiden Hin- und Rückläufe von Lua nach C++ klar erkennen können, können wir versuchen, herauszufinden, wie wir dies optimieren können.

Unser Endziel ist es, einen einzigen Funktionsaufruf von Lua nach C++ durchzuführen und alle benötigten Elemente auf dem Lua-Stack zu haben, um die Methodensuche und den Aufruf auf einmal durchführen zu können. Das Problem scheint zu sein, dass uns ein Register fehlt. Wenn wir unsere kombinierte Such-/Aufruffunktion aufrufen, soll der Lua-Stack wie folgt aussehen: [self, Methodenname, arg1, arg2, ...], aber wenn wir uns SELF ansehen, stellen wir fest, dass es seinen ersten Slot für das Ergebnis der Methodensuche und den zweiten Slot zum Speichern der Instanz verwendet.

Eine wichtige Erkenntnis kam, als wir uns die Funktionsweise der Metamethode __call ansahen. Wenn ein Objekt über die Metamethode __call verfügt, wird das Objekt selbst auf den Stack geschoben und alle Argumente werden nach oben verschoben, bevor die Funktion _call aufgerufen wird. Indem wir diese Funktionalität nutzten, gab es eine Möglichkeit, „self“ auf den Stack zu bringen, ohne es explizit in einem Register speichern zu müssen.

Der zweite Teil bestand darin, auch den Methodennamen auf den Stack zu bringen. Dazu mussten wir etwas trickreich vorgehen und die Funktionsweise des SELF-Opcodes ändern.

Denken Sie daran, dass SELF im Standardfall versuchen würde, die Mitgliedsfunktion zu finden und diese zusammen mit der Instanz in R(A+1) in R(A) zu speichern. Wir haben die Suche letztendlich ganz übersprungen und das eigentliche Objekt in R(A) sowie den Methodennamen in R(A+1) gespeichert.

Wenn wir nun sicherstellten, dass das Objekt in R(A) eine __call-Metamethode hatte, würden wir am Ende auch self auf den Stack schieben. Wir hätten also einen Stack, der wie [self, Methodenname, Argumente…] aussah, und führten nur einen einzigen Aufruf in C++ durch. Perfekt! Nun ja, fast. :)

Bevor wir das als erledigt betrachteten, wollten wir noch den letzten Schliff daran vornehmen. Wir wollten die Semantik der __call-Metamethode nicht überladen, also fügten wir stattdessen eine spezifische Metamethode für diese Art von Aufruf hinzu – genannt __namecall –, die nur für UserData-Objekte verfügbar war. Wir modifizierten auch den SELF-Opcode, sodass er die neue Semantik nur verwendet, wenn das Objekt eine __namecall-Metamethode besitzt.

Als Zweites haben wir vor allem dafür gesorgt, dass der neue und der alte Pfad Code problemlos gemeinsam nutzen können. Anstatt den Methodennamen als zweites Argument zu verwenden, haben wir ihn an das letzte Argument verschoben. Nachdem er also zum Nachschlagen des Methodenzeigers verwendet worden war, konnte er einfach vom Stack entfernt werden, und der Stack sah so aus, als wäre die Funktion über den alten Pfad aufgerufen worden.

Fazit

Wie groß ist die Auswirkung dieser Optimierung? Nun, wie bei den meisten Dingen in der Programmierung lautet die Antwort: „Es kommt darauf an.“ Bei Funktionen, die sehr ressourcenintensiv sind – und die man nicht oft aufruft –, wird man kaum eine Verbesserung feststellen. Bei kleineren Funktionen, die man häufig aufruft, können die Einsparungen jedoch beträchtlich sein.

Die Teilnehmer des Entwicklerforums bemerkten schnell das Auftauchen dieser seltsamen, neuen Metamethode, und es wurde eine Tabelle präsentiert, die die Geschwindigkeit von __namecall sowohl mit der alten Methode zum Aufruf von Instanzmethoden als auch mit einem Workaround verglich, den Entwickler bisher zur Optimierung des Methodenaufrufs verwendet hatten:

local  part  =  workspace.Baseplate


local  count  =  1000000


local  start0  =  tick()

for  i=1,count  do

        part:IsA("BasePart")

end

local  end0  =  tick()



local  start1  =  tick()

for  i=1,count  do

       local  isa  =  part.IsA

       isa(part,  "BasePart")

end

local  end1  =  tick()



local  start2  =  tick()

local  isa  =  part.IsA

for  i=1,count  do

       isa(part,  "Basepart")

end

local  end2  =  tick()




print("namecall",  end0  -  start0)

print("index+call",  end1  -  start1)

print("call",  end2  -  start2)



>  namecall  0.49229717254639

>  index+call  0.78510332107544

>  call  0.49960780143738

 
Die erste Schleife nutzt den neuen __namecall-Codepfad, aber da die ganze Magie unter der Haube stattfindet, müssen Entwickler keinen bestehenden Code ändern, um von der Optimierung zu profitieren.

Die zweite Schleife emuliert die alte Vorgehensweise beim Aufruf einer Instanzmethode: Zuerst wird nach der Methode gesucht und dann wird sie aufgerufen.

Und schließlich zeigt die dritte Schleife eine gängige Optimierung, die Entwickler angewandt haben: Dabei wurde die Methode zunächst gesucht, in einer lokalen Variablen gespeichert und dann die Variable aufgerufen.

Das Schöne daran ist, dass es zeigt, dass es mit der __namecall-Optimierung nicht mehr notwendig ist, Instanzfunktionen explizit zwischenzuspeichern, da sie genauso schnell ist wie die zwischengespeicherte Optimierung – somit ist der einfachste Code auch der leistungsstärkste.

Nachdem __namecall nun implementiert wurde und wir mit den Ergebnissen zufrieden sind, ist es an der Zeit, unseren Fokus auf die Speichernutzung zu richten und zu prüfen, was wir tun können, um den Client in diesem Bereich zu verbessern!