Optimaliseren van de interoperabiliteit tussen Lua en C++

Inleiding

De Roblox-engine is geschreven in een combinatie van C++ en Lua, waarbij de code die rekenintensieve bewerkingen uitvoert in geoptimaliseerd C++ is geschreven, terwijl de spellogica en scripts in Lua zijn geschreven, om de ontwikkeling te vergemakkelijken. Om dit model effectief te laten zijn, moeten de overgangen tussen Lua en C++ zo snel mogelijk zijn, aangezien elke seconde die in dit niemandsland wordt doorgebracht in feite verspilde milliseconden zijn.

De afgelopen maanden hebben we verschillende verbeteringen doorgevoerd in dit deel van het systeem. Eén onderdeel in het bijzonder – het daadwerkelijk aanroepen van C++-methoden vanuit Lua – was bijzonder interessant, omdat het leidde tot aanzienlijke snelheidsverbeteringen en het vereiste dat we diep in de kern van Lua moesten graven om te begrijpen hoe de zaken onder de motorkap werkten.

Uiteindelijk hebben we de Lua VM zelf aangepast, maar voordat we daarop ingaan, moeten we eerst wat basiswerk verrichten.

Compilers, VM en bytecode

Wanneer Lua-broncode wordt gecompileerd, wordt deze gecompileerd tot Lua-bytecode, die vervolgens door de Lua VM wordt uitgevoerd. Lua-bytecode bevat in totaal ongeveer 35 instructies, voor zaken als het lezen/schrijven van tabellen, het aanroepen van functies, het uitvoeren van binaire bewerkingen, sprongen en voorwaardelijke constructies, enzovoort. De Lua VM is registergebaseerd, in tegenstelling tot stackgebaseerd zoals veel andere VM's, dus een deel van wat de compiler doet wanneer deze bytecode genereert, is bepalen welke registers elke instructie moet gebruiken.

Elke instructie heeft de vorm “OP_CODE A B” of “OP_CODE A B C”, waarbij “OP_CODE” de opcode is (bijvoorbeeld CALL voor het aanroepen van een functie) en A/B/C de opcode-argumenten zijn. De argumenten (of registers) zijn geen werkelijke waarden. In plaats daarvan zijn het indexen die verwijzen naar een van twee tabellen: de constantentabel (geschreven als Kst(..)) of de registertabel (geschreven als R(..)).

Voor een gedetailleerde beschrijving van Lua-bytecode, zie “Een eenvoudige inleiding tot Lua 5.1 VM-instructies.” Het is veel spannender dan het klinkt; dat beloof ik!

Om je een idee te geven van hoe Lua-bytecode eruitziet, gaan we eerst enkele eenvoudige programma's bekijken en vervolgens doorgaan naar enkele relevantere voorbeelden.

Met behulp van het hulpprogramma Chunkspy kunnen we Lua-bytecode disassembleren naar Lua-assembly en een lijst van de code en de constantentabel opvragen, zodat we in feite kunnen zien welke bytecode wordt gegenereerd voor een bepaalde Lua-broncode.

Voorbeelden van eenvoudige bytecode

Een eenvoudig programma als "x = 10" wordt gecompileerd tot:

.const "x";  0

.const 10;  1

[1]  loadk       0   1       ;   10

[2]  setglobal   0   0       ;   x 

De eerste twee regels tonen de constantentabel (met de tekenreekswaarde "x" in slot 0 en de gehele waarde 10 in slot 1), en de volgende twee regels zijn de gedisassembleerde opcodes.

[Regel 1] Als we de LOADK-opcode opzoeken in "No Frills", zien we dat deze de vorm "LOADK A Bx --- R(A) := Kst(Bx)" heeft. LOADK heeft dus twee argumenten (registers A en B) en de bewerking bestaat erin de waarde die in de constantentabel staat op de positie die door het tweede register wordt aangegeven, Kst(Bx), toe te wijzen aan het register op de positie die door het eerste argument wordt aangegeven, R(A). “Bx” betekent gewoon dat, omdat de opcode slechts twee argumenten heeft, het B-register wordt uitgebreid en meer bits toegewezen krijgt.

[Regel 2] SETGLOBAL heeft de vorm “SETGLOBAL A Bx --- Gbl[Kst(Bx)] := R(A).” Het wijst een waarde toe aan de globale tabel met behulp van de sleutel die wordt gegeven door de constantentabel op de positie van het tweede argument. Omdat het tweede argument 0 is en de waarde van de constantentabel op 0 “x” is, schrijft het iets naar de globale tabel met behulp van de sleutel “x.” Wat er ook in de registertabel staat op de positie die wordt aangegeven door het eerste argument, is wat er wordt geschreven, en de vorige instructie heeft daar de waarde 10 in geladen.

Laten we eens kijken naar een iets ingewikkelder voorbeeld: “x = 10; y = x.” Ik laat het handmatig uitvoeren van de code over aan de lezer als oefening. :)

.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 voor functieaanroepen

Laten we eens kijken naar de code die wordt gegenereerd voor "foo(10):"

.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

 
Om functieaanroepen uit te voeren, moet de functie in het eerste register worden geladen en de argumenten in de daaropvolgende registers. De semantiek voor “CALL A B C” is zodanig dat A de functie bevat, B het aantal argumenten is (eigenlijk is het het aantal argumenten +1, vanwege de manier waarop “...” is geïmplementeerd), en C het aantal retourwaarden is (ook hier weer het aantal retourwaarden +1, om meerdere retourwaarden te kunnen verwerken).

We zijn bekend met de eerste twee regels; ze laden een waarde in registertabelvak 0 en de waarde 10 in registertabelvak 1. De derde regel voert de functieaanroep uit, waarbij de waarde in register A (registertabel-slot 0, dat werd geladen met “foo”) wordt gebruikt, waarbij B het aantal argumenten specificeert en C het aantal retourwaarden (onthoud dat er bij zowel B als C 1 bij de waarden moet worden opgeteld). Voordat de functie kan worden aangeroepen, controleert de VM ook of de waarde in R(A) daadwerkelijk aanroepbaar is.

Lua heeft een mechanisme waarmee gebruikers de functionaliteit van tabellen kunnen uitbreiden door een metatabel aan een bestaande tabel te koppelen. De metatabel bevat fallback-methoden die worden aangeroepen als een bepaalde methode of bewerking niet op de hoofdtabel kan worden uitgevoerd (zie https://www.lua.org/pil/13.html voor een uitgebreide beschrijving).

Voor onze doeleinden zijn de meest relevante vermeldingen in de metatabel de velden “__index” en “__call”. __index wordt gebruikt bij het opzoeken van een element in een tabel, dus de code “local x = my_table[10]” zou eerst de __index-methode op my_table aanroepen. Als dat mislukt, zou het in plaats daarvan proberen __index aan te roepen op de metatabel van my_table. __call wordt op vergelijkbare wijze gebruikt wanneer je iets als een functie probeert te behandelen en het aanroept, bijvoorbeeld “local x = foo(42)”

Om Lua en C++ te laten samenwerken, hebben ze een manier nodig om functies en gegevens te kunnen delen. Lua maakt dit mogelijk door een gegevenstype genaamd UserData aan te bieden. UserData-objecten kunnen in C++ worden aangemaakt, en omdat het native Lua-gegevenstypen zijn, kunnen ze worden voorzien van metatabellen waardoor Lua-code ermee kan communiceren alsof het gewone Lua-objecten zijn.

Aanroepen van lidfuncties

Oké, terug naar de bytecode! Het volgende voorbeeld is iets interessanter omdat het laat zien wat er gebeurt als je code hebt zoals “foo:bar(10),” die de bar-methode aanroept op de instantie foo (een instantie van de klasse Foo).

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

 
Het nieuwe hier is de self-instructie [regel 2], die we nog niet eerder hebben gezien. Self heeft de syntaxis “SELF A B C --- R(A) := R(B)[RK(C)]; R(A+1) := R(B),” dus laten we dit eens ontleden. In de registertabel op slot R(A) wordt het resultaat geplaatst van het opzoeken in de tabel in registerslot R(B) met behulp van de sleutel in slot RK(C). Ook wordt de inhoud van slot R(B) gekopieerd naar slot R(A+1), maar daarover later meer. Je ziet misschien dat de waarde van het C-register 257 is. Dit klopt, omdat Lua RK(C) gebruikt om de waarde op te zoeken, en RK gebruikt ofwel de registertabel ofwel de constantentabel, afhankelijk van de waarde van het 9e bit. Als dit een 1 is, wat in dit geval zo is, dan wordt de constantentabel gebruikt; anders gaat de opzoekactie naar de registertabel (na het wegfilteren van het hoogste bit).

Regel 3 plaatst 10 in slot 2, en ten slotte voert regel 4 de functieaanroep uit.

De SELF-instructie dient twee doelen. Ten eerste zoekt deze naar de methode “bar” in de Foo-klasse en plaatst deze in R(A). Ten tweede, omdat foo een instantiemethode is en we de instantie van de klasse nodig hebben waarop we de methode aanroepen bij het uitvoeren van de aanroep, plaatst deze instructie deze instantie in R(A+1). Als je bekend bent met klassen in Python, herken je het concept wellicht: methoden worden meestal geschreven als “def my_method(self, arg1, arg2..),” waarbij self de klasse-instantie is.

We moeten hier wat dieper op ingaan en kijken wat er gebeurt als het foo-instantie een C++-object is, in Lua weergegeven als een UserData-object.

De SELF-aanroep kan worden gezien als een tabelopzoeking, d.w.z. Foo[“bar”] (Foo met een hoofdletter staat voor de klasse Foo, in tegenstelling tot foo, de instantie), en we weten dat opzoekingen de __index-methode gebruiken. Toen de foo-instantie in C++ werd aangemaakt, werd er een metatabel aan de instantie gekoppeld, en het __index-veld van die metatabel was ingesteld op een stukje C++-code dat wordt aangeroepen wanneer __index wordt aangeroepen.

Wanneer C/C++ vanuit Lua wordt aangeroepen, is het enige dat wordt doorgegeven een lua_State-object. Dit object bevat alles wat betrekking heeft op de momenteel actieve Lua-thread. De belangrijkste informatie in het state-object is de Lua-stack, die de functieargumenten bevat (toegankelijk via de lua_tointeger/tostring enz. familie van functies) en ook wordt gebruikt om waarden terug te sturen naar Lua.

In pseudo-C++ ziet onze __index-functie er ongeveer zo uit:

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;

           }

}

 
Veel interne details worden hier buiten beschouwing gelaten, maar dit is de kern ervan. Aangezien het UserData-object als eerste argument op de Lua-stack wordt doorgegeven, kunnen we een descriptor vinden die de daadwerkelijke C++-klasse beschrijft, en via de descriptor kunnen we zien of deze klasse een methode met de opgegeven naam heeft. Als dat het geval is, wordt een functiepointer naar een method invoker op de Lua-stack geplaatst en geven we 'succes' terug.

Na deze aanroep plaatst de Lua VM de rest van de argumenten in de registertabel en roept vervolgens de functie aan die we hebben geretourneerd vanuit de metaIndex-methode, die weer C++ aanroept en in de invoker-functie terechtkomt:

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);
}

 
De methodInvoker maakt ook gebruik van de ClassDescriptor, maar deze keer kan hij de lidfunctie aanroepen en de juiste argumenten van de stack halen.

De laatste loodjes!

Nu we de twee rondjes van Lua naar C++ duidelijk kunnen zien, kunnen we proberen uit te zoeken hoe we dit kunnen optimaliseren.

Ons einddoel is om één enkele functieaanroep van Lua naar C++ te doen en alle stukjes die we nodig hebben op de Lua-stack te hebben om de methode in één keer op te zoeken en aan te roepen. Het probleem lijkt te zijn dat we één register te weinig hebben. Wanneer we onze gecombineerde opzoek-/aanroepfunctie aanroepen, willen we dat de Lua-stack eruitziet als [self, method name, arg1, arg2, ...], maar als we naar SELF kijken, zien we dat het zijn eerste slot gebruikt voor het resultaat van het opzoeken van de methodefunctie en het tweede slot voor het opslaan van de instantie.

Een belangrijk inzicht kwam toen we keken naar de manier waarop de __call-metamethod werkte. Als een object de __call-metamethod heeft, wordt het object zelf op de stack geplaatst en worden alle argumenten omhoog geschoven voordat de _call-functie wordt aangeroepen. Door mee te liften op deze functionaliteit was er een manier om “self” op de stack te krijgen zonder het expliciet in een register op te slaan.

Het tweede deel betrof het ook op de stack krijgen van de methodenaam. Hiervoor moesten we een beetje sluw te werk gaan en de werking van de SELF-opcode aanpassen.

Onthoud dat SELF in het standaardgeval zou proberen de lidfunctie te vinden en deze samen met de instantie in R(A+1) in R(A) op te slaan. We hebben uiteindelijk de zoekactie helemaal overgeslagen en het daadwerkelijke object in R(A) opgeslagen en de methodenaam in R(A+1).

Als we er nu voor zorgden dat het object in R(A) een __call-metamethod had, zouden we uiteindelijk ook self op de stack plaatsen. We zouden dus een stack hebben die eruitzag als [self, method name, args…] en slechts één enkele aanroep naar C++ uitvoerde. Perfect! Nou ja, bijna. :)

Voordat we dit als voltooid beschouwden, wilden we er nog wat laatste details aan toevoegen. We wilden de semantiek van de __call-metamethode niet overbelasten, dus voegden we in plaats daarvan een specifieke metamethode toe voor dit type aanroep – genaamd __namecall – die alleen beschikbaar was op UserData-objecten. We hebben ook de SELF-opcode aangepast, zodat deze alleen de nieuwe semantiek gebruikt als het object een __namecall-metamethode heeft.

Het tweede wat we deden, was ervoor zorgen dat het nieuwe pad en het oude pad gemakkelijk code konden delen. In plaats van de methodenaam als tweede argument te gebruiken, hebben we deze naar het laatste argument verplaatst. Dus nadat deze was gebruikt om de methodepunter op te zoeken, kon deze gemakkelijk van de stack worden gehaald en zag de stack eruit alsof de functie via het oude pad was aangeroepen.

Conclusie

Hoe groot is de impact van deze optimalisatie? Nou, zoals bij de meeste dingen in de programmering, is het antwoord: “dat hangt ervan af.” Voor functies die zwaar zijn – en die je niet vaak aanroept – zul je niet veel verbetering zien. Maar voor kleinere functies die je vaak aanroept, kan de besparing aanzienlijk zijn.

Mensen op het Developer Forum merkten al snel de verschijning van deze vreemde, nieuwe metamethod op, en er werd een tabel gepresenteerd waarin de snelheid van __namecall werd vergeleken met zowel de oude methode voor het aanroepen van instantiemethoden als met een workaround die ontwikkelaars hadden gebruikt om het aanroepen van methoden te optimaliseren:

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

 
De eerste lus maakt gebruik van het nieuwe __namecall-codepad, maar omdat alle magie onder de motorkap plaatsvindt, hoeven ontwikkelaars geen bestaande code te wijzigen om van de optimalisatie te profiteren.

De tweede lus emuleert de oude manier om een instantiemethode aan te roepen: eerst wordt de methode opgezocht en vervolgens aangeroepen.

En tot slot toont de derde lus een veelvoorkomende optimalisatie die ontwikkelaars toepasten, waarbij de methode eerst werd opgezocht, opgeslagen in een lokale variabele en vervolgens werd aangeroepen.

Het mooie hieraan is dat het laat zien dat het met de __namecall-optimalisatie niet langer nodig is om instantiefuncties expliciet in de cache op te slaan, aangezien het net zo snel is als de cached-optimalisatie, dus de meest eenvoudige code zal ook de best presterende zijn.

Nu __namecall is geïmplementeerd en we tevreden zijn met de resultaten die we zien, is het tijd om onze aandacht te richten op het geheugengebruik en te kijken wat we kunnen doen om de client op dat gebied te verbeteren!