Ottimizzazione dell'interoperabilità tra Lua e C++

Introduzione

Il motore Roblox è scritto in una combinazione di C++ e Lua, con il codice che esegue operazioni computazionalmente intensive scritto in C++ ottimizzato, mentre la logica di gioco e gli script sono scritti in Lua, per facilitare lo sviluppo. Affinché questo modello sia efficace, è necessario che le transizioni tra Lua e C++ siano il più veloci possibile, poiché qualsiasi tempo trascorso in questa terra di nessuno è essenzialmente solo millisecondi sprecati.

Negli ultimi due mesi, abbiamo implementato vari miglioramenti a questa parte del sistema. Una parte in particolare — l’effettiva invocazione dei metodi C++ da Lua — è stata particolarmente interessante, poiché ha portato a notevoli miglioramenti di velocità e ha richiesto di scavare nelle viscere di Lua per capire come funzionavano le cose sotto il cofano.

Abbiamo finito per modificare la stessa VM di Lua, ma prima di arrivare a questo, dobbiamo gettare alcune basi.

Compilatori, VM e bytecode

Quando il codice sorgente Lua viene compilato, viene convertito in bytecode Lua, che viene poi eseguito dalla VM Lua. Il bytecode Lua ha circa 35 istruzioni in totale, per operazioni come la lettura/scrittura di tabelle, la chiamata di funzioni, l'esecuzione di operazioni binarie, salti e condizioni, e così via. La VM di Lua è basata su registri, a differenza di molte altre VM che sono basate su stack, quindi parte di ciò che fa il compilatore quando genera il bytecode è determinare quali registri ogni istruzione debba utilizzare.

Ogni istruzione ha la forma “OP_CODE A B” o “OP_CODE A B C”, dove “OP_CODE” è il codice operativo (ad esempio, CALL per chiamare una funzione) e A/B/C sono gli argomenti del codice operativo. Gli argomenti (o registri) non sono valori effettivi. Sono invece indici che puntano a una di due tabelle: la tabella delle costanti (scritta Kst(..)) o la tabella dei registri (scritta R(..)).

Per una descrizione dettagliata del bytecode di Lua, consultare "A No-Frills introduction to Lua 5.1 VM Instructions". È molto più interessante di quanto sembri, ve lo assicuro!

Per darvi un'idea di come si presenta il bytecode di Lua, esamineremo prima alcuni programmi semplici e poi passeremo ad esempi più rilevanti.

Utilizzando l'utilità Chunkspy, possiamo disassemblare il bytecode Lua in assembly Lua e ottenere un elenco del codice, oltre alla tabella delle costanti, in modo da poter vedere essenzialmente quale bytecode viene generato per un dato codice sorgente Lua.

Esempi di bytecode di base

Un programma semplice come "x = 10" viene compilato in:

.const "x";  0

.const 10;  1

[1]  loadk       0   1       ;   10

[2]  setglobal   0   0       ;   x 

Le prime due righe mostrano la tabella delle costanti (con il valore stringa “x” nello slot 0 e il valore intero 10 nello slot 1), mentre le due righe successive sono gli opcode disassemblati.

[Riga 1] Cercando il codice operativo LOADK in “No Frills”, vediamo che ha la forma “LOADK A Bx --- R(A) := Kst(Bx)”. Quindi, LOADK ha due argomenti (i registri A e B) e la sua operazione consiste nell’assegnare il valore trovato nella tabella delle costanti allo slot indicato dal secondo registro, Kst(Bx), al registro R(A) allo slot indicato dal primo argomento. “Bx” significa semplicemente che, poiché il codice operativo ha solo due argomenti, il registro B viene esteso e gli vengono assegnati più bit.

[Riga 2] SETGLOBAL ha la forma “SETGLOBAL A Bx --- Gbl[Kst(Bx)] := R(A).” Assegna un valore alla tabella globale utilizzando la chiave indicata dalla tabella delle costanti nello slot del secondo argomento. Poiché il secondo argomento è 0 e il valore della tabella delle costanti a 0 è “x”, scrive qualcosa nella tabella globale utilizzando la chiave “x”. Ciò che viene scritto è il contenuto della tabella dei registri nello slot indicato dal primo argomento, che l’istruzione precedente ha caricato con il valore 10.

Vediamo un esempio un po' più complicato: “x = 10; y = x”. Lascio l'esecuzione manuale del codice come esercizio per il lettore. :)

.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 per le chiamate di funzione

Diamo un'occhiata al codice generato per "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

 
Per eseguire le chiamate di funzione, la funzione deve essere caricata nel primo registro e gli argomenti in quelli successivi. La semantica di “CALL A B C” è tale che A contiene la funzione, B è il numero di argomenti (in realtà, è il numero di argomenti +1, a causa del modo in cui è implementato “...” ) e C è il numero di valori di ritorno (anche in questo caso, è il numero di valori di ritorno +1, per gestire più valori di ritorno).

Conosciamo bene le prime due righe; caricano un valore nello slot 0 della tabella dei registri e il valore 10 nello slot 1 della tabella dei registri. La terza riga è quella che esegue la chiamata alla funzione, utilizzando il valore nel registro A (slot 0 della tabella dei registri, che è stato caricato con “foo”), con B che specifica il numero di argomenti e C il numero di valori di ritorno (ricordate, sia a B che a C va aggiunto 1). Prima che la funzione possa essere chiamata, la VM verifica anche che il valore in R(A) sia effettivamente chiamabile.

Lua dispone di un meccanismo che consente agli utenti di estendere le funzionalità delle tabelle associando una metatabella a una tabella esistente. La metatabella contiene metodi di fallback che vengono invocati se un determinato metodo o operazione non può essere eseguito sulla tabella principale (vedere https://www.lua.org/pil/13.html per una descrizione approfondita).

Ai fini del nostro discorso, le voci più rilevanti nella metatabella sono i campi “__index” e “__call”. __index viene utilizzato quando si cerca un elemento in una tabella, quindi il codice “local x = my_table[10]” chiamerebbe prima il metodo __index su my_table. Se ciò fallisse, proverebbe invece a chiamare __index sulla metatabella di my_table. __call viene utilizzato in modo simile quando si cerca di trattare qualcosa come una funzione e la si chiama “local x = foo(42)”, per esempio

Affinché Lua e C++ possano interagire, hanno bisogno di un modo per condividere funzioni e dati. Lua facilita questo fornendo un tipo di dati chiamato UserData. Gli oggetti UserData possono essere creati in C++ e, poiché sono tipi di dati nativi di Lua, possono essere arricchiti con metatabelle che consentono al codice Lua di interagire con essi come se fossero normali oggetti Lua.

Chiamate alle funzioni membro

Ok, torniamo a dare un'occhiata al bytecode! Il prossimo esempio è un po' più interessante perché mostra cosa succede quando si ha un codice come “foo:bar(10),” che chiama il metodo bar sull'istanza foo (un'istanza della classe 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

 
La novità qui è l’istruzione self [riga 2], che non abbiamo visto prima. Self ha la sintassi “SELF A B C --- R(A) := R(B)[RK(C)]; R(A+1) := R(B)”, quindi analizziamola. Nella tabella dei registri allo slot R(A), inserirà il risultato della ricerca nella tabella allo slot R(B) utilizzando la chiave nello slot RK(C). Copierà inoltre qualsiasi cosa si trovasse nello slot R(B) nello slot R(A+1), ma ne parleremo più avanti. Potresti notare che il valore del registro C è 257. Questo è corretto perché Lua usa RK(C) per cercare il valore, e RK userà la tabella dei registri o la tabella delle costanti, a seconda del valore del 9° bit. Se è un 1, come in questo caso, allora viene usata la tabella delle costanti; altrimenti, la ricerca va alla tabella dei registri (dopo aver mascherato il bit più alto).

La riga 3 inserisce 10 nello slot 2 e, infine, la riga 4 eseguirà la chiamata di funzione.

L'istruzione SELF ha due scopi. Innanzitutto, cerca il metodo "bar" nella classe Foo e lo inserisce in R(A). In secondo luogo, poiché foo è un metodo di istanza e abbiamo bisogno dell'istanza della classe su cui stiamo invocando il metodo quando effettuiamo la chiamata, inserisce questa istanza in R(A+1). Se avete familiarità con le classi in Python, potreste riconoscere il concetto: i metodi sono solitamente scritti come "def my_method(self, arg1, arg2..)," dove self è l'istanza della classe.

Dovremo approfondire un po' questo argomento e dare un'occhiata a cosa succede quando l'istanza foo è un oggetto C++, rappresentato in Lua come un oggetto UserData.

La chiamata SELF può essere vista come una ricerca in tabella, ovvero Foo[“bar”] (Foo maiuscolo rappresenta la classe Foo, al contrario di foo, l’istanza), e sappiamo che le ricerche useranno il metodo __index. Quando l'istanza foo è stata creata in C++, una metatabella è stata associata all'istanza, e la metatabella aveva il suo campo __index impostato su un pezzo di codice C++ che verrà chiamato quando viene invocato __index.

Quando C/C++ viene chiamato da Lua, l'unico dato che viene passato è un oggetto lua_State. Questo oggetto contiene tutto ciò che riguarda il thread Lua attualmente in esecuzione. L'informazione più importante nell'oggetto state è lo stack di Lua, che contiene gli argomenti della funzione (accessibili tramite la famiglia di funzioni lua_tointeger/tostring ecc.) e viene utilizzato anche per restituire valori a Lua.

In pseudo-C++, la nostra funzione __index ha un aspetto simile a questo:

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;

           }

}

 
Molti dettagli interni sono stati tralasciati, ma ecco il succo della questione. Dato che l'oggetto UserData viene passato come primo argomento nello stack Lua, siamo in grado di trovare un descrittore che descrive l'effettiva classe C++ e, tramite il descrittore, possiamo verificare se questa classe possiede un metodo con il nome specificato. Se lo possiede, un puntatore di funzione a un invocatore di metodo viene inserito nello stack Lua e restituiamo un esito positivo.

Dopo questa chiamata, la VM Lua inserirà il resto degli argomenti nella tabella dei registri, quindi chiamerà la funzione che abbiamo restituito dal metodo metaIndex, che a sua volta richiamerà il C++ e arriverà alla funzione di invocazione:

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

 
Anche methodInvoker utilizza ClassDescriptor, ma questa volta è in grado di invocare la funzione membro e di estrarre gli argomenti corretti dallo stack.

Il tratto finale!

Ora che possiamo vedere chiaramente i due round trip da Lua a C++, possiamo provare a capire come ottimizzare il tutto.

Il nostro obiettivo finale è quello di effettuare una singola chiamata di funzione da Lua a C++ e avere tutti i pezzi necessari nello stack di Lua per poter eseguire la ricerca e l'invocazione del metodo in una sola volta. Il problema sembra essere che ci manca un registro. Quando chiamiamo la nostra funzione combinata di ricerca/invocazione, vogliamo che lo stack di Lua appaia come [self, nome del metodo, arg1, arg2, ...], ma osservando SELF, vediamo che utilizza il suo primo slot per il risultato della ricerca della funzione del metodo e il secondo slot per memorizzare l'istanza.

Una realizzazione chiave è arrivata quando abbiamo osservato il funzionamento del metametodo __call. Se un oggetto ha il metametodo __call, allora prima che la funzione _call venga invocata, l'oggetto stesso viene inserito nello stack e tutti gli argomenti vengono spostati verso l'alto. Sfruttando questa funzionalità, c'era un modo per ottenere “self” nello stack senza doverlo memorizzare esplicitamente in un registro.

La seconda parte consisteva nel portare anche il nome del metodo nello stack. Per questo, abbiamo dovuto ingegnarci e modificare il funzionamento dell'opcode SELF.

Ricordiamo che, nel caso predefinito, SELF avrebbe cercato di trovare la funzione membro e di memorizzarla in R(A) insieme all'istanza in R(A+1). Abbiamo finito per saltare del tutto la ricerca e abbiamo memorizzato l'oggetto effettivo in R(A) e il nome del metodo in R(A+1).

Se ora ci assicurassimo che l'oggetto in R(A) avesse un metametodo __call, finiremmo anche per spingere self nello stack. Quindi, avremmo uno stack che assomiglierebbe a [self, nome del metodo, args…] e faremmo una sola chiamata in C++. Perfetto! Beh, quasi. :)

Prima di considerarlo fatto, volevamo dargli qualche ritocco finale. Non volevamo sovraccaricare la semantica del metametodo __call, quindi abbiamo invece aggiunto un metametodo specifico per questo tipo di invocazione — chiamato __namecall — che era disponibile solo sugli oggetti UserData. Abbiamo anche modificato l’opcode SELF in modo che utilizzi la nuova semantica solo se l’oggetto ha un metametodo __namecall.

La seconda cosa che abbiamo fatto è stata principalmente rendere il nuovo percorso e quello vecchio in grado di condividere facilmente il codice. Invece di avere il nome del metodo come secondo argomento, lo abbiamo spostato all'ultimo argomento. Così, dopo che era stato utilizzato per cercare il puntatore al metodo, poteva essere facilmente rimosso dallo stack e lo stack appariva come se la funzione fosse stata invocata tramite il vecchio percorso.

Conclusione

Qual è l'impatto di questa ottimizzazione? Beh, come per la maggior parte delle cose in programmazione, la risposta è "dipende". Per le funzioni pesanti, che non si chiamano spesso, non si noterà un grande miglioramento. Ma per le funzioni più piccole che si chiamano spesso, il risparmio può essere considerevole.

Gli utenti del Forum degli sviluppatori hanno subito notato la comparsa di questo nuovo e strano metametodo, ed è stata presentata una tabella che confrontava la velocità di __namecall sia con il vecchio metodo di chiamata dei metodi di istanza, sia con una soluzione alternativa che gli sviluppatori avevano utilizzato per ottimizzare la chiamata dei metodi:

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

 
Il primo ciclo utilizza il nuovo percorso di codice __namecall, ma poiché tutta la magia avviene sotto il cofano, non è necessario che gli sviluppatori modifichino il codice esistente per beneficiare dell'ottimizzazione.

Il secondo ciclo emula il vecchio modo di effettuare una chiamata al metodo di istanza; prima si esegue una ricerca per trovare il metodo e poi lo si invoca.

Infine, il terzo ciclo mostra un'ottimizzazione comune che gli sviluppatori stavano effettuando, in cui il metodo veniva prima cercato, memorizzato in una variabile locale e poi la variabile veniva invocata.

La cosa interessante qui è che dimostra che, con l'ottimizzazione di __namecall, non è più necessario memorizzare esplicitamente nella cache le funzioni di istanza, poiché è veloce quanto l'ottimizzazione con cache, quindi il codice più semplice sarà anche il più performante.

Ora che __namecall è stato implementato e siamo soddisfatti dei risultati che stiamo vedendo, è il momento di concentrarci sull'utilizzo della memoria e vedere cosa possiamo fare per migliorare il client in quell'area!