Are we fast yet czyli Java i Firefox OS

Jak pisałem ostatnio pracuję nad emulatorem J2ME na Firefox OS. Niestety pierwsze rozczarowanie przyszło, gdy aplikacja wylądowała po raz pierwszy na żywym sprzęcie, a dokładnie na Keonie (niewiele lepsze gówno niż Alcatel One Touch Fire). Wydajność była słaba, w męczonym przeze mnie Raymanie na oko wyciągało mniej niż 5 FPS (nie było wtedy jeszcze zaimplementowanego licznika klatek). W czasach gdy chodziłem do podstawówki i była moda na emulatory nie było najmniejszego problemu z emulowaniem gier na niemal martwą platformę, bo mój komputer (Pentium II) był kilkanaście razy wydajniejszy od SNESa. Problem w tym, że tu mamy telefony z podzespołami, które mogły robić wrażenie w 2010 roku podczas, gdy topowe telefony wspierające natywnie emulowaną platformę były niewiele słabsze, a sama platforma... wciąż żyje.

...ale to nie znaczy, że można się poddawać

Sytuacja wymagała ostrej optymalizacji. Czy się udało? Rzucę teraz wykresami...



Benche wzięte z Computer Language Benchmarks Game. Gwoli ścisłości ten niebieski wykres to Doppio, najbardziej chyba dojrzała maszyna wirtualna Javy napisana w JS. Zółty (może trochę słabo widoczny :) ) to wersja 0.7 mojego emulatora sprzed kilku dni. Chciałem dorzucić do porównania wcześniejsze wersje, ale 0.4 nie dała rady odpalić benchmarków, więc ostatecznie porównuję z 0.5 i 0.6. Ten wpis ma na celu opisanie w jaki sposób emulacja przyspieszyła stukrotnie w ciągu miesiąca.

Jak to działało (i po części działa do teraz)

Wersja 0.5 nie różniła się zbytnio sposobem wykonywania kodu od poprzednich. Metoda Javy opisana jest przez opkody, które tłumaczyłem do funkcji JS (jeden opkod, jedna funkcja). Powstawała z tego tablica funkcji, które wykonywałem po kolei. Pojedyńcza funkcja dostawała jako jedyny argument obiekt opisujący kontekst wykonywania i starała się robić to co prawdziwa maszyna Javy, czyli mogła np. zdjąć dwie liczby ze stosu i wrzucić na niego wynik ich dodania, wywołać metodę z innego obiektu albo nakazać egzekutorowi zrobić skok do innego indeksu w tablicy. Tak to działa w sumie do dzisiaj choć już nie zawsze i z kilkoma zmianami...

Scalanie kodu

Pierwsza i dająca największego kopa zmiana to podział tych funkcji, które dostajemy w wynikowej tablicy na dwa typy. Generatory (każdy opkod ma swój generator, który na podstawie otrzymanych danych zwraca odpowiednią dopasowną funkcję) mogą zwrócić albo po staremu funkcję (ile razy już użyłem tego słowa w tym akapicie?) albo stringa z kodem. Co to daje? Że mogę sąsiadujące ze sobą kawałki kodu scalić w jeden (o ile w miejsce pomiędzy nimi nie jest zagrożone skokiem). W ostatnim etapie ze wszystkich kawałków kodu tworzę funkcje i ostatecznie wszystko jest po staremu, poza tym, że mam mniej funkcji w tablicy niż wcześniej. Co ciekawe ten prosty trik był na tyle skuteczny, że nawet po przerobieniu kilkunastu najczęściej używanych opkodów na nową konwencję wzrost wydajności był wyraźny. Ostatecznie doszło do tego, że metoda, która wcześniej składała ze 199 kawałków zeszła do ~25. Koszt przejścia egzekutora z jednego kawałka na kolejny jest spory i... właściwie większość tego spadku między czerwonym, a pomarańczowym słupkiem wynikła właśnie z tego.

Redukcja operacji na stosie

Podglądając co z tego scalania się zrodziło szybko dostrzegłem sytacje tego typu:
context.stack.push(context.locals[0]);
context.stack.push(1);
var a = context.stack.pop();
var b = context.stack.pop();
context.stack.push(a + b);

Jak łatwo się domyśleć wrzucanie czegoś do tablicy tylko po to, żeby to za chwilę odczytać jest bezsensowne i kosztowne obliczeniowo. Wprowadziłem więc mechanizm, który te zjawisko redukuje (niemal do zera). Dla każdego popa szuka najbliższego pusha i wiąże je zmienną pomocniczą. Po jego użyciu powstaje taki kod:
var tmp1 = context.locals[0];
var tmp2 = 1;
var a = tmp2;
var b = tmp1;
context.stack.push(a + b);

Teraz dla odmiany mamy nadmiarowe zmienne, ale to nie jest problemem, bo wedle moich testów silnik sam takie rzeczy optymalizują, więc mogę sobie pozwolić na ping-pong między zmiennymi bez obaw o wydajność. Ta optymalizacja zmniejszyła czas wykonywania o jakieś 20-30%.

Kompilacja do metody natywnej

Kolejna rzecz jaką zauważyłem to, że niektóre (bardzo niewiele, ale byłem nastawiony, że w przysłości pojawi się ich więcej) metody po scaleniu redukują się do tablicy z pojedyńczą funkcją. W takich sytuacjach (o ile spełnione są pewne warunki) sprowadzam metodę do całkowicie natywnej, JavaScriptowej postaci bez egzekutora i innych narzutów. Wzrost wydajności praktycznie żaden przy odsetku jaki stanowiły wówczas takie metody, ale potraktowałem to jako inwestycję w przyszłość (spoiler: będzie ich więcej).

Bezpieczne metody

Ponieważ niektóre rzeczy w JS dzieją się asynchronicznie wołana metoda mogła nakazać zwinąć ten mój Javowy pseudowątek i rozwinąć, gdy operacja się zakończy (np. ładowanie obrazków). To sprawiało, że nie mogłem pod żadnym pozorem scalać wywołań metod z resztą kodu. Jak łatwo się domyśleć wywołań innych metod w Javie jest całkiem sporo. Dlatego wprowadziłem coś takiego jak bezpieczne metody (i analogicznie niebezpieczne). Bezpieczne metody domyślnie są wszystkie z bibioteki standardowej oprócz kilku, które oznaczyłem jako niebezpieczne (czyli wspomniane wcześniej ładowanie obrazków albo usypianie wątków). Wszystkie metody z emulowanej aplikacji są domyślnie niebezpieczne. Potem informacja o "bezpieczności" metody propaguje dalej i z czasem też niektóre metody z aplikacji uznawane są za bezpieczne. Oczywiście wywołanie bezpiecznej metody może być bez problemu scalane z okolicznym kodem. Czyli kolejna redukcja :)

Double i Long

Do tej pory Double i Long były specjalnymi typami (bo sama maszyna wirtualna Javy traktuje je specjalnie) tworzonymi z konstruktorów. W momencie, gdy profiler wskazał, że ok. 10% działania programu to konstrukcja Longa postanowiłem coś z tym zrobić. Zamiast używać konstruktorów przerzuciłem się na duck-typing. Jeśli coś wygląda jak Long (albo Double) to nim jest. Tworzę anonimowe obiekty w miejscu, a ponadto jako, że są immutable to 0 i 1 trzymam w stałych, żeby nie tworzyć ich za każdym razem. Podane wyżej benchmarki jako, że intensywnie korzystają z Doubli bardzo polubiły tę optymalizację.

Pętle i instrukcje warunkowe

W tym momencie już tylko skoki psuły mi wydajność. Oczywiście natywny for jest dużo wydajniejszy niż egzekutor odtwarzający tę logikę. Temat był dość ciężki, w pewnym momencie miałem jakieś 200 linii heurystyki ogarniającej różne rodzaje pętli i ifów. I tak nie pokrywały wszystkiego, a poza tym alternatywy i koniunkcje logiczne też tworzyły skoki. No i oczywiście goto (na szczęście tego mało kto używa). Po długich przemyśleniach i poszukiwaniach znalazłem prosty, skuteczny i ostro porąbany sposób na zlikwidowanie większości skoków w kodzie. Ale do rzeczy. Jeśli jesteś zdrowym na umyśle programistą JS to pewnie nie słyszałeś o labelach, a tym bardziej ich nie używałeś. Okazało się, że dzięki nim można prosto odtworzyć większość pętli i nawet instrukcji warunkowych. Przykład pętli:
for (i = 0; i < l; i++) {
  ...
}

Przykład tej samej pętli zapisanej na labelach:
i = 0;
label1: do {
  if (i => l) break label1;
  ...
  i++
  continue label1;
} while (true);

Moja maszynka rozpisałaby to jeszcze bardziej absurdalnie (pewnie by było więcej pętli). Co najlepsze bez względu na ilość zagnieżdżeń działa to podobnie szybko co ładnie zapisany for. Tworzenie tych pętli ogarniają dwa ify w kodzie, a efekty są dość... powalające. Jeśli się zastanawiałeś, dlaczego żółty wykres na początku wpisu był taki krótki to jest odpowiedź. To chyba druga najbardziej skuteczna optymalizacja jaką zastosowałem. W każdym razie najbardziej trikowa.

I inne

Poczyniłem też dużo mniejszych optymalizacji, od czasu do czasu poprawiam wydajność pojedyńczych opkodów, nie mówiąc o tym, że niektóre generatory są jeszcze w starej "konwencji" i nie zwracają kawałków kodu tylko funkcje (pomimo, że mogą). Jak tylko natrafię na takie staram się poprawić, ale to wszystko stopniowo, nie chce mi się czytać ponad tysiąca linii kodu szukając słabych punktów. Poza tym dobra rada, jeśli liczy się wydajność nie używaj arguments. Jakiekolwiek użycie tego w kodzie wyłącza niektóre optymalizacje i wydajność w Firefoksie leci na łeb na szyje (w V8 trochę mniej, ale też spada).

Co dalej?

  • Zoptymalizowanie wywołań metod - to dość kluczowy element programu i wydaje mi się, że sporo można jeszcze poprawić.
  • TypedArray - oglądałem benchmark spectralnorm napisany w JavaScripcie, były tam użyte TypedArraye. Nie widzę przeciwskazań, żeby użyć ich u siebie, bo na szczęście Java jest typowana.
  • Natywne wyjątki - mimo że to dość proste do wykodzenia i oczywiste to jeszcze tego nie zrobiłem :)
  • Workery - właściwie poczyniłem już pewne kroki w tym temacie. Zrobiłem jednego workera trzymającego całą maszynę wirtualną i komunikacja z DOMem odbywała się przez przesyłanie odpowiednich komunikatów. Wydajność trochę wzrosła, niestety większość telefonów z Firefoksem jest jednordzeniowa, więc podejrzewam, że tam to może dać tylko niepotrzebny narzut.
  • Switch - być może wykorzystam pomysł mina86 z komentarzy pod poprzednim wpisem, żeby dobić niechcące się kompletnie scalić przypadki
  • I co mi tam jeszcze przyjdzie do głowy. Na razie wydajność jest zadowalająca, więc nie spieszę się z optymalizacją. Raczej skupiam się teraz na zgodności z J2ME.