Potęga w 4 kilobajtach

Screen z demka 4k
autorstwa Charibo

Ostatnio na Warsztacie zapanował niecodzienny pęd do sceny – demosceny, rzecz jasna. Jego główną przyczyną, a może i skutkiem, jest oczywiście rozpoczynający się dzisiaj konkurs na najlepsze demo 4k. Pod tym tajemniczym skrótem kryje się maksymalny rozmiar takiego dema (co obejmuje plik wykonywalny i wszystkie wykorzystywane dane), który nie może przekroczyć granicy 4096 bajtów.
“A co można napisać na takim malutkim kawałeczku?”, pewnie chciałoby się spytać. Okazuje się, że całkiem sporo – pod warunkiem, że znamy kilka sztuczek oraz korzystamy z odpowiednich narzędzi. Jest to na przykład specjalny linker, który dokonuje wyjątkowo efektywnej kompresji wynikowego pliku. Oprócz należy też odpowiednio skonfigurować kompilator, włączając wszelkie optymalizacje rozmiaru generowanego kodu (kosztem jego szybkości) oraz pozbywając się niepotrzebnych dodatków.

Takich dodatkiem jest na przykład biblioteka czasu wykonania (runtime). Jej wykluczenie sprawia jednak, że tracimy kilka mechanizmów języka C++, jak chociażby część funkcji matematycznych. Do szczególnie dotkliwych może należeć na przykład brak operacji potęgowania w jakiejkolwiek formie – zarówno funkcji pow, jak i exp. Jeśli ich potrzebujemy, musimy sami je sobie zapewnić, co w przypadku niecałkowitego wykładnika może być kłopotliwe. Chyba że odwołamy się bezpośrednio do jednostki zmiennoprzecinkowej – na przykład tak:

Samodzielnie wyprodukowanie tego kawałka nie było aczkolwiek takie proste (głównie ze względu na kłopotliwe wymagania co do argumentu instrukcji F2XM1, która dokonuje potęgowania). Dlatego prezentuję go tu dla potomności i pożytku wszystkich tworzących małe dema, licząc, że komuś może się przydać :)

Sinus, cosinus

Jeśli w praktyce obliczamy wartości funkcji sinus lub cosinus dla danego kąta, to bardzo często zdarza się, że tak naprawdę potrzebujemy ich obu. Jest tak przy obliczaniu punktów okręgu, przy rozkładzie wektorów sił i jeszcze dla wielu innych okoliczności. Zależy nam naturalnie, aby policzyć to wszystko tak szybko, jak tylko się da, dlatego dobrze jest stosować funkcje w rodzaju sincos, które wyznaczają obie wartości jednocześnie.

Niestety nie każdy język programowania taką funkcję posiada. Mają ją języki shaderowe (GLSL, HLSL i asembler GPU) oraz np. Delphi, ale już nasz ulubiony C++ nie. Można by oczywiście uzupełnić ten brak poprzez taką implementację:

ale chyba nie trzeba nikogo przekonywać, że większego sensu ona nie ma :) Nie występuje tu bowiem żaden zysk na wydajności, bo wartości są obliczane oddzielnie.

Co więc można zrobić? Ano wykorzystać to, co drzemie w jednostce zmiennoprzecinkowej procesora, ale nie jest używane przez wszystkie języki wyższego poziomu. Istnieje mianowicie instrukcja FSINCOS, która wykonuje całą potrzebną “magię”. Należy ją tylko opakować:

Jakkolwiek tajemniczo to może wyglądać, funkcja ta po prostu ładuje argument (kąt) na stos FPU, by potem odebrać wyniki – cosinus i sinus. W przypadku operowania na liczbach typu float nie ma możliwości podania zbyt dużego/małego argumentu, więc nie trzeba sprawdzać rejestru flag.

I tyle – funkcja mała, acz użyteczna. Asembler czasem się przydaje, proszę państwa ;P

Rozpoznawanie możliwości procesora

Niektóre funkcje dobrze jest pisać w asemblerze. Tak, wiem że dzisiaj – w epoce języków (zbyt) wysokiego poziomu – brzmi to dziwnie, ale to prawda. To najprostszy sposób na poprawienie wydajności często wykonywanych operacji, np. kalkulacji z użyciem wektorów i macierzy.
Rzecz w tym, że korzystając bezpośrednio z zaawansowanych możliwości oferowanych przez współczesne procesory, jednocześnie uzależniamy się od nich. Przykładowo, transformację wektora przez macierz można naturalnie po prostu przetłumaczyć z odpowiedniego wzoru na instrukcje jednostki zmiennoprzecinkowej i uzyskać kod działający na każdym procesorze. Jeżeli jednak użyjemy np. SSE2, możemy uzyskać kilkakrotny wzrost wydajności – lecz wówczas nasza funkcja będzie działała tylko na nowszych procesorach.

Najlepiej byłoby więc mieć kilka wersji takiej funkcji i wybierać odpowiednią dla procesora pracującego na danej maszynie. Jak jednak wykryć, co potrafi dana jednostka? Otóż z pomocą przychodzi nam system operacyjny. W Windows na przykład istnieje funkcja o wiele mówiącej nazwie IsProcessorFeaturePresent, przy pomocy której możemy sprawdzić obecność rozszerzeń MMX, 3DNow!, SSE i SSE2.
Oczywiście, takiego sprawdzenia należy dokonać raz na początku działania programu. Jeśli jednak po prostu zapiszemy jego rezultat w formie globalnych flag boolowskich, to ich odczytywanie np. przy każdym dodawaniu wektorów będzie nie tylko kłopotliwe, ale i nieefektywne.

Lepszym rozwiązaniem jest stworzenie odpowiedniej liczby globalnych wskaźników na funkcje, inicjowanych w czasie uruchamiania programu; tak jak poniżej:

Dzięki temu zarówno w kodzie asemblerowym poszczególnych wersji (którego litościwie nie pokażę ;D), jak i wywołaniach, nie widać żadnego śladu po ‘magii’ wyboru funkcji dostosowanej do procesora. Narzut to rozwiązanie to naturalnie jedna dereferencja wskaźnika więcej; sprawdzanie flag (porównaniami i skokami) trwałoby znacznie dłużej.