Optymalizacja współdziałania Lua/C++

Wprowadzenie

Silnik Roblox jest napisany w językach C++ i Lua, przy czym kod wykonujący operacje wymagające dużej mocy obliczeniowej jest napisany w zoptymalizowanym C++, a logika gry i skrypty są napisane w Lua, co ułatwia tworzenie gier. Aby ten model był skuteczny, przejścia między Lua a C++ muszą być jak najszybsze, ponieważ każdy czas spędzony w tej „strefie niczyjej” to w zasadzie zmarnowane milisekundy.

W ciągu ostatnich kilku miesięcy wprowadziliśmy różne ulepszenia w tej części systemu. Jedna część – konkretnie wywoływanie metod C++ z Lua – była szczególnie interesująca, ponieważ doprowadziła do znacznej poprawy szybkości i wymagała zagłębienia się w trzewia Lua, aby zrozumieć, jak wszystko działa pod maską.

Ostatecznie zmodyfikowaliśmy samą maszynę wirtualną Lua, ale zanim do tego przejdziemy, musimy położyć pewne podstawy.

Kompilatory, maszyna wirtualna i kod bajtowy

Kiedy kod źródłowy Lua jest kompilowany, jest on kompilowany do kodu bajtowego Lua, który następnie uruchamia maszyna wirtualna Lua. Kod bajtowy Lua ma w sumie około 35 instrukcji, służących do takich rzeczy jak odczyt/zapis tabel, wywoływanie funkcji, wykonywanie operacji binarnych, skoki i warunki itp. Maszyna wirtualna Lua jest oparta na rejestrach, w przeciwieństwie do wielu innych maszyn wirtualnych opartych na stosie, więc częścią zadania kompilatora podczas generowania kodu bajtowego jest określenie, których rejestrów powinna używać każda instrukcja.

Każda instrukcja ma postać „OP_CODE A B” lub „OP_CODE A B C”, gdzie „OP_CODE” to kod operacji (na przykład CALL dla wywołania funkcji), a A/B/C to argumenty kodu operacji. Argumenty (lub rejestry) nie są rzeczywistymi wartościami. Zamiast tego są to indeksy, które wskazują na jedną z dwóch tabel: tabelę stałych (zapisywana jako Kst(..)) lub tabelę rejestrów (zapisywana jako R(..)).

Szczegółowy opis kodu bajtowego Lua można znaleźć w artykule „A No-Frills introduction to Lua 5.1 VM Instructions”. Jest to o wiele bardziej ekscytujące, niż się wydaje; obiecuję!

Aby dać ci wyobrażenie o tym, jak wygląda kod bajtowy Lua, najpierw omówimy kilka prostych programów, a następnie przejdziemy do bardziej istotnych przykładów.

Korzystając z narzędzia Chunkspy, możemy zdekompilować kod bajtowy Lua do asemblera Lua i uzyskać listę kodu, a także tabelę stałych, dzięki czemu możemy zasadniczo zobaczyć, jaki kod bajtowy jest generowany dla danego kodu źródłowego Lua.

Podstawowe przykłady kodu bajtowego

Prosty program, taki jak „x = 10”, kompiluje się do:

.const "x";  0

.const 10;  1

[1]  loadk       0   1       ;   10

[2]  setglobal   0   0       ;   x 

Pierwsze dwie linie pokazują tabelę stałych (z wartością ciągu znaków „x” w slocie 0 i wartością całkowitą 10 w slocie 1), a kolejne dwie linie to zdekompilowane kody operacyjne.

[Wiersz 1] Sprawdzając kod operacyjny LOADK w „No Frills”, widzimy, że ma on postać „LOADK A Bx --- R(A) := Kst(Bx)”. Zatem LOADK ma dwa argumenty (rejestry A i B), a jego działanie polega na przypisaniu wartości znalezionej w tabeli stałych w miejscu określonym przez drugi rejestr, Kst(Bx), do rejestru w miejscu określonym przez pierwszy argument, R(A). „Bx” oznacza po prostu, że ponieważ kod operacyjny ma tylko dwa argumenty, rejestr B jest rozszerzony i przypisano mu więcej bitów.

[Wiersz 2] SETGLOBAL ma postać „SETGLOBAL A Bx --- Gbl[Kst(Bx)] := R(A)”. Przypisuje wartość do tabeli globalnej przy użyciu klucza podanego przez tabelę stałych w slocie drugiego argumentu. Ponieważ drugi argument wynosi 0, a wartość tabeli stałych w slocie 0 to „x”, zapisuje coś do tabeli globalnej przy użyciu klucza „x”. Zapisywana jest zawartość tabeli rejestrów w slocie podanym przez pierwszy argument, który poprzednia instrukcja załadowała wartością 10.

Spójrzmy na nieco bardziej skomplikowany przykład: „x = 10; y = x”. Ręczne wykonanie kodu pozostawiam jako ćwiczenie dla czytelnika. :)

.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

Kod bajtowy dla wywołań funkcji

Przyjrzyjmy się kodowi wygenerowanemu dla „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

 
Aby wykonać wywołania funkcji, funkcja musi zostać załadowana do pierwszego rejestru, a argumenty do kolejnych. Semantyka „CALL A B C” jest taka, że A zawiera funkcję, B to liczba argumentów (w rzeczywistości jest to liczba argumentów +1, ze względu na sposób implementacji „...”), a C to liczba wartości zwracanych (ponownie jest to liczba wartości zwracanych +1, aby obsłużyć wiele wartości zwracanych).

Znamy już pierwsze dwie linijki; ładują one wartość do komórki 0 tablicy rejestrów oraz wartość 10 do komórki 1 tablicy rejestrów. Trzeci wiersz wykonuje wywołanie funkcji, wykorzystując wartość w rejestrze A (komórka 0 tablicy rejestrów, do której wczytano „foo”), gdzie B określa liczbę argumentów, a C liczbę wartości zwracanych (pamiętaj, że do wartości zarówno B, jak i C należy dodać 1). Zanim funkcja zostanie wywołana, maszyna wirtualna sprawdza również, czy wartość w R(A) faktycznie nadaje się do wywołania.

Lua posiada mechanizm, który pozwala użytkownikom rozszerzać funkcjonalność tabel poprzez powiązanie metatabeli z istniejącą tabelą. Metatabela zawiera metody awaryjne, które są wywoływane, jeśli dana metoda lub operacja nie może zostać wykonana na tabeli głównej (szczegółowy opis znajduje się na stronie https://www.lua.org/pil/13.html).

Dla naszych celów najbardziej istotnymi wpisami w metatabeli są pola „__index” i „__call”. __index jest używane podczas wyszukiwania elementu w tabeli, więc kod „local x = my_table[10]” najpierw wywołałby metodę __index na my_table. Gdyby to się nie powiodło, spróbowałby zamiast tego wywołać __index na metatabeli my_table. __call jest używane w podobny sposób, gdy próbujesz potraktować coś jako funkcję i wywołać ją, na przykład „local x = foo(42)”

Aby Lua i C++ mogły ze sobą współpracować, potrzebują sposobu na współdzielenie funkcji i danych. Lua ułatwia to, udostępniając typ danych o nazwie UserData. Obiekty UserData można tworzyć w środowisku C++, a ponieważ są to natywne typy danych Lua, można je wzbogacić o metatabele, które pozwalają kodowi Lua na interakcję z nimi tak, jakby były zwykłymi obiektami Lua.

Wywołania funkcji członkowskich

W porządku, wróćmy do analizy kodu bajtowego! Następny przykład jest nieco bardziej interesujący, ponieważ pokazuje, co się dzieje, gdy mamy kod typu „foo:bar(10)”, który wywołuje metodę bar na instancji foo (instancji klasy 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

 
Nowością jest tutaj instrukcja self [linia 2], której wcześniej nie widzieliśmy. Self ma składnię „SELF A B C --- R(A) := R(B)[RK(C)]; R(A+1) := R(B)”, więc przeanalizujmy to. W tabeli rejestrów w slocie R(A) umieści wynik wyszukiwania w tabeli w slocie rejestru R(B) przy użyciu klucza w slocie RK(C). Skopiuje również wszystko, co znajdowało się w slocie R(B), do slota R(A+1), ale więcej na ten temat później. Można zauważyć, że wartość rejestru C wynosi 257. Jest to poprawne, ponieważ Lua używa RK(C) do wyszukiwania wartości, a RK używa albo tabeli rejestrów, albo tabeli stałych, w zależności od wartości 9. bitu. Jeśli jest to 1, co ma miejsce w tym przypadku, używana jest tabela stałych; w przeciwnym razie wyszukiwanie odbywa się w tabeli rejestrów (po zamaskowaniu najwyższego bitu).

Wiersz 3 umieszcza 10 w slocie 2, a wreszcie wiersz 4 wykona wywołanie funkcji.

Instrukcja SELF służy dwóm celom. Po pierwsze, wyszukuje metodę „bar” w klasie Foo i umieszcza ją w R(A). Po drugie, ponieważ foo jest metodą instancji i potrzebujemy instancji klasy, na której wywołujemy metodę podczas wykonywania wywołania, umieszcza tę instancję w R(A+1). Jeśli znasz klasy w Pythonie, to prawdopodobnie rozpoznasz tę koncepcję: metody są zazwyczaj zapisywane jako „def my_method(self, arg1, arg2..),” gdzie self jest instancją klasy.

Musimy zagłębić się w to nieco bardziej i przyjrzeć się, co się dzieje, gdy instancja foo jest obiektem C++, reprezentowanym w Lua jako obiekt UserData.

Wywołanie SELF można postrzegać jako wyszukiwanie w tabeli, tj. Foo[„bar”] (wielka litera Foo oznacza klasę Foo, w przeciwieństwie do foo, które jest instancją), a wiemy, że wyszukiwania będą korzystać z metody __index. Kiedy instancja foo została utworzona w środowisku C++, z instancją powiązano metatabelę, a pole __index tej metatabeli zostało ustawione na fragment kodu C++, który zostanie wywołany po wywołaniu __index.

Gdy C/C++ jest wywoływane z Lua, jedyną przekazywana danymi jest obiekt lua_State. Obiekt ten zawiera wszystko, co dotyczy aktualnie uruchomionego wątku Lua. Najważniejszą informacją w obiekcie stanu jest stos Lua, który zawiera argumenty funkcji (dostępne poprzez rodzinę funkcji lua_tointeger/tostring itp.) i jest również używany do zwracania wartości z powrotem do Lua.

W pseudo-C++ nasza funkcja __index wygląda mniej więcej tak:

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;

           }

}

 
Wiele szczegółów wewnętrznych zostało pominiętych, ale oto sedno sprawy. Biorąc pod uwagę, że obiekt UserData jest przekazywany jako pierwszy argument na stosie Lua, jesteśmy w stanie znaleźć deskryptor opisujący rzeczywistą klasę C++, a za jego pomocą możemy sprawdzić, czy ta klasa posiada metodę o podanej nazwie. Jeśli tak, wskaźnik funkcji do wywołania metody jest umieszczany na stosie Lua i zwracamy wynik pozytywny.

Po tym wywołaniu maszyna wirtualna Lua umieści pozostałe argumenty w tablicy rejestrów, a następnie wywoła funkcję, którą zwróciliśmy z metody metaIndex, która ponownie wywoła C++ i trafi do funkcji wywołującej:

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

 
Metoda methodInvoker również korzysta z ClassDescriptor, ale tym razem jest w stanie wywołać funkcję składową i pobrać odpowiednie argumenty ze stosu.

Ostatnia prosta!

Teraz, gdy wyraźnie widzimy dwa cykle komunikacji między Lua a C++, możemy spróbować dowiedzieć się, jak to zoptymalizować.

Naszym ostatecznym celem jest wykonanie pojedynczego wywołania funkcji z Lua do C++ i umieszczenie wszystkich potrzebnych elementów na stosie Lua, aby móc jednocześnie wyszukiwać i wywoływać metody. Problem wydaje się polegać na tym, że brakuje nam jednego rejestru. Kiedy wywołujemy naszą połączoną funkcję wyszukiwania/wywołania, chcemy, aby stos Lua wyglądał jak [self, nazwa metody, arg1, arg2, ...], ale patrząc na SELF, widzimy, że wykorzystuje on swój pierwszy slot na wynik wyszukiwania funkcji metody, a drugi slot na przechowywanie instancji.

Kluczowe spostrzeżenie pojawiło się, gdy przyjrzeliśmy się działaniu metametody __call. Jeśli obiekt posiada metametodę __call, to przed wywołaniem funkcji _call sam obiekt jest umieszczany na stosie, a wszystkie argumenty są przesuwane w górę. Wykorzystując tę funkcjonalność, znaleźliśmy sposób na umieszczenie „self” na stosie bez konieczności wyraźnego przechowywania go w rejestrze.

Druga część polegała na umieszczeniu nazwy metody również na stosie. W tym celu musieliśmy zastosować sprytne rozwiązanie i zmodyfikować działanie kodu operacyjnego SELF.

Pamiętaj, że w domyślnym przypadku SELF próbowałby znaleźć funkcję składową i zapisać ją w R(A) wraz z instancją w R(A+1). Ostatecznie całkowicie pominęliśmy to wyszukiwanie i zapisaliśmy rzeczywisty obiekt w R(A), a nazwę metody w R(A+1).

Gdybyśmy teraz upewnili się, że obiekt w R(A) posiada metametodę __call, to w rezultacie umieścilibyśmy również self na stosie. Mielibyśmy więc stos wyglądający jak [self, nazwa metody, argumenty…] i wykonalibyśmy tylko jedno wywołanie do C++. Idealnie! Cóż, prawie. :)

Zanim uznaliśmy to za skończone, chcieliśmy jeszcze trochę to dopracować. Nie chcieliśmy przeciążać semantyki metametody __call, więc zamiast tego dodaliśmy specjalną metametodę dla tego typu wywołań — nazwaną __namecall — która była dostępna tylko dla obiektów UserData. Zmodyfikowaliśmy też kod operacyjny SELF, żeby używał nowej semantyki tylko wtedy, gdy obiekt ma metametodę __namecall.

Drugą rzeczą, którą zrobiliśmy, było przede wszystkim umożliwienie łatwego współdzielenia kodu przez nową i starą ścieżkę. Zamiast umieszczać nazwę metody jako drugi argument, przenieśliśmy ją na ostatni argument. Dzięki temu, po wykorzystaniu jej do wyszukania wskaźnika metody, można ją było łatwo usunąć ze stosu, a stos wyglądał tak, jakby funkcja została wywołana poprzez starą ścieżkę.

Wnioski

Jak duży wpływ ma ta optymalizacja? Cóż, jak w przypadku większości rzeczy w programowaniu, odpowiedź brzmi: „to zależy”. W przypadku funkcji, które są ciężkie — i nie wywołuje się ich często — nie zauważy się dużej poprawy. Jednak w przypadku mniejszych funkcji, które wywołuje się często, oszczędności mogą być znaczne.

Użytkownicy forum deweloperskiego szybko zauważyli pojawienie się tej dziwnej, nowej metametody i przedstawiono tabelę porównującą szybkość __namecall zarówno ze starą metodą wywoływania metod instancji, jak i z obejściem, którego deweloperzy używali do optymalizacji wywoływania metod:

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

 
Pierwsza pętla wykorzystuje nową ścieżkę kodu __namecall, ale ponieważ cała magia dzieje się pod maską, programiści nie muszą zmieniać żadnego istniejącego kodu, aby skorzystać z optymalizacji.

Druga pętla emuluje stary sposób wywoływania metody instancji; najpierw wyszukuje metodę, a następnie ją wywołuje.

Wreszcie trzecia pętla pokazuje typową optymalizację stosowaną przez programistów, w której najpierw wyszukiwano metodę, zapisywano ją w zmiennej lokalnej, a następnie wywoływano tę zmienną.

Zaletą tego rozwiązania jest to, że pokazuje ono, iż dzięki optymalizacji __namecall nie ma już potrzeby jawnego buforowania funkcji instancji, ponieważ jest ona tak samo szybka jak optymalizacja z buforowaniem, więc najprostszy kod będzie również najbardziej wydajny.

Teraz, gdy wdrożono __namecall i jesteśmy zadowoleni z wyników, nadszedł czas, aby skupić się na wykorzystaniu pamięci i sprawdzić, co możemy zrobić, aby ulepszyć klienta w tym obszarze!