DOD organizuje dane

Moi koledzy-częściowo-po-fachu, czyli programiści silników gier, wymyślili niedawno magiczny trzyliterowy akronim DOD – skrót od Data-Oriented Design, czyli projektowanie oparte o dane. Oczywiście określenie ‘niedawno’ jest względnym i pewnie wielu z nich orzekło by, że DOD jest z nimi już całkiem długo. Każdy mem potrzebuje jednak czasu na rozprzestrzenienie się, a w przypadku tego fala tweetów na jego temat dotarła do mnie dopiero niedawno. Niedługo potem rzecz wydała mi się cokolwiek podejrzana.

Podstawowe pytanie brzmi rzecz jasna: o co w tym właściwie chodzi?… Ponieważ mówimy o programowaniu gier, to odpowiedź jest jasna: jeśli nie wiadomo o co chodzi, to chodzi o wydajność. W zaawansowanych grach czasu rzeczywistego mamy do czynienia z ogromną ilością danych, na których trzeba wykonać wiele, często skomplikowanych operacji, a wszystko to jeszcze musi być zrobione dostatecznie szybko, aby możliwe było pokazanie na ekranie kolejnej klatki bez widocznych przycięć. Dlatego też już dawno zauważono, że kodowanie “blisko sprzętu” się opłaca, bo pozwala maksymalnie wykorzystać jego możliwości.
To oczywiście nakłada na kod pewne wymagania oraz stwarza konieczność zwrócenia uwagi na rzeczy, którymi “normalnie” nie ma potrzeby się zajmować. Ładnym przykładem jest chociażby zarządzanie pamięcią. W wielu językach jest ono albo kompletnie pomijalne (garbage collector), albo sprowadza się do dbania o to, aby każdy zaalokowany blok był w końcu zwolniony. Gdy jednak stawiamy na wydajność, powinniśmy też zainteresować się szybkością samej operacji alokacji oraz takim rozmieszczeniem przydzielanych bloków, aby komunikacja na linii procesor-pamięć odbywała się z jak najmniejszą liczbą zgrzytów.
Ten i wiele podobnych szczegółów platformy sprzętowej powodują, że pisanie efektywnego kodu w silnikach gier to często dość literalne postępowanie według zasady Do It Yourself, połączone z ignorowaniem części feature‘ów wysokopoziomowych języków programowania, o których wiadomo, że negatywnie odbijają się na wydajności. Cóż, życie; nie ma w tym nic zaskakującego. Myślę, że każdy co bardziej zaawansowany programista zdążył zdać sobie sprawę z tego, że wszelkie koderskie udogodnienia związane z podniesieniem poziomu abstrakcji mają swój koszt liczony w dodatkowych cyklach procesora (i nie tylko). Rezygnacja z nich jest więc dobrym posunięciem, jeśli chcemy te “stracone” cykle odzyskać.
Robiąc to, będziemy mieli ciastko, ale już nie będziemy mogli go zjeść – a to oczywiście nie jest przyjemne. I po części zapewne stąd wzięło się pojęcie DOD, które nie odnosi się do niczego w gruncie rzeczy nowego, ale pozwala łatwiej odnosić się do tego rodzaju koderskich praktyk poprzez nadanie im nazwy. A przy okazji – jak mi się wydaje – w jakiś nie do końca wytłumaczalny sposób redukuje dysonans poznawczy programistów silników gier, którzy świadomie muszą pozbawiać się możliwości przestrzegania “jedynie słusznych” zasad pisania kodu.

Jak dotąd wszystko jest w gruncie rzeczy bardzo ładne i sensowne, i bez problemu zgadzam się z postulatami Data-Oriented Design tam, gdzie się one aplikują. Zgadzam się nawet z tą domniemaną ukrytą motywacją, zwłaszcza że sam nieraz narzekałem na owe “jedynie słuszne” rady. Za to nijak nie mogę pojąć, dlaczego następnym krokiem – po wynalezieniu pojęcia DOD – był mniej lub bardziej frontalny atak na programowanie obiektowe, określane nieco bardziej znanym (ale naturalnie również trzyliterowym) akronimem OOP.
Nie, nie chodzi o to, że programowanie obiektowe jest doskonałe – bo nie jest, nie było, nigdy nie będzie i nawet nie aspiruje do miana finalnego rozwiązania dla dowolnego problemu (już nie wspominając o tym, że takowe po prostu nie istnieją). Rzecz w tym, że zwolennicy DOD (DOD-a? :]) w nieprzemyślany sposób wybrali sobie przeciwnika, nie zauważając, że jest on paradygmatem zupełnie innego rodzaju niż ich własny. A to przecież takie proste:

• OOP sugeruje, że naturalną architekturą dla systemów jest ta oparta o obiekty, będące mniej lub bardziej abstrakcyjnymi bytami, połączonymi relacjami i wchodzącymi ze sobą w interakcje
• DOD wskazuje na to, że głównym zadaniem kodu jest transformacja danych w inne dane i że optymalizacja procesu przetwarzania danych jest priorytetem przy tworzeniu wewnętrznej struktury programu

Widać to, prawda?… Miedzy powyższymi dwoma podejściami nie tylko nie ma sprzeczności. One są od siebie po prostu niezależne, co oznacza również, że mogą występować razem w jednym programie.

“Mapa nie jest terytorium.”

Jeśli Data-Oriented Design koniecznie potrzebuje jakiegoś przeciwnika, to są nim raczej inne xOD-y, których jest już przynajmniej kilka, chociaż wiele nie zostało jeszcze nawet nazwanych. (Dobry przykład to projektowanie oparte o user experience, czyli wrażenie użytkownika, gdzie priorytetem jest m.in. responsywność, nie będąca wcale synonimem wydajności). To, co piewcy DOD zdają się krytykować w swoich publikacjach, to jakieś “projektowanie oparte o eleganckie abstrakcje”, czyli pisanie kodu, który jest sztuką dla sztuki: ładnie wygląda (w założeniu), ściśle trzyma się założeń używanego paradygmatu przy jednoczesnym eksploatowaniu wszelkich jego “zdobyczy” (czyli np. wzorców projektowych). I chociaż bywają w swoich wysiłkach niezwykle twórczy (w prezentacjach z tego tematu spotkałem nawet cytaty z Baudrillarda), to nie zmienia to faktu, że kopią leżącego (czy raczej biją martwego konia, jakby to powiedzieli Amerykanie ;-)). Bo jeśli ktoś naprawdę posuwa się do takich absurdów jak czteropoziomowa hierarchia dziedziczenia obiektów gry, to znaczy że ma znacznie poważniejsze problemy niż okazjonalny cache miss :)

Nieoficjalne debugowanie na Androidzie

System Android, jak powszechnie wiadomo, jest licencjonowany kategorią open source, więc istnieje możliwość w miarę łatwego umieszczenia go na urządzeniach mobilnych bez konieczności współpracy z Google. Wykorzystują to producenci różnego rodzaju mniej lub bardziej “nieoficjalnego” sprzętu, działającego pod kontrolą tego systemu. Mogą to być produkty, które trudno klasyfikować inaczej niż jako tanie imitacje, ale także sprzęt produkowany przez (u)znane firmy – jak choćby tablet stworzony przez Creative. Ich wspólną cechą jest domyślny brak wsparcia przez narzędzia wspomagające pisanie aplikacji dostępne w ramach SDK Androida – przede wszystkim Android Debug Bridge (adb), czyli usługę umożliwiającą między innymi debugowanie aplikacji bezpośrednio na urządzeniu. Dla zwykłego użytkownika to oczywiście żadna wada, ale co mają zrobić biedni programiści?…
Okazuje się jednak, że przeszkodę tę da się pokonać. Dzisiaj udała mi się ta sztuka ze wspomnianym tabletem Creative’a i dlatego czuję się upoważniony podzielić się swoim rozwiązaniem :) Wydaje się ono przy tym na tyle ogólne, że powinno stosować do dowolnego urządzenia.

Kiedy kod jest przejrzysty

Pisanie kodu to czasami niewdzięczne zajęcie, ale tylko z rzadka. Nieprzyjemnych wrażeń o wiele częściej, jak sądzę, dostarcza czytanie kodu. Jest tak po części pewnie dlatego, że statystycznie programista przeznacza na to zajęcie znacznie więcej czasu (wystarczy policzyć chociażby debugowanie). Innym powodem może być też to, że dokładne zdefiniowanie takiego określenia jak przejrzysty kod okazuje się zaskakująco trudno, bo kategoria ta wydaje się w dużym stopniu subiektywna.

Weźmy na przykład komentarze. Potoczna koderska mądrość mówi nam, że łatwy do zrozumienia kod zapewne posiada dużo komentarzy, bo w końcu jak inaczej opisać zawiłości konstrukcji językowych i bibliotecznych, które się w nim znajdują?… Może to i przekonująca logika, ale ja mam lepszą. Można by przecież liczbę tych zawiłości minimalizować jeśli nie eliminować zupełnie. Kod przejrzysty powinien dokumentować się w zasadzie sam. Wyjątki istnieją, oczywiście, bo zawsze znajdą się jakieś kruczki, haki i inne triki, które można opatrzyć jedynie napisem // Magic. Do not touch. (o ile nie chcemy opisywać ich działania w elaboracie na piętnaście linii). Jeśli jednak większość kodu wygląda “magicznie”, to jego autora należy czym prędzej przeszkolić w bardziej mugolskich technikach programowania :)

Trochę odrębnie od przygodnych komentarzy traktuję wstawki mające służyć na dokumentację do poszczególnych elementów kodu. Tworzenie jej w pełnej formie, z opisem każdego pola, metody i parametru jest nie tylko czasochłonne, ale i w dużej części niezbyt sensowne. Z drugiej jednak strony brak chociaż słowa wzmianki nt. tego, co dana klasa czy metoda w zasadzie robi to zbrodnia popełniona na nieszczęśnikach, którzy potem muszą przedzierać się przez taką terra incognita. Można obyć się bez wiedzy, jak dany element działa, ale informacja o tym, do czego służy lub co ma w założeniu robić jest po prostu niezbędna.

Komentarze, według mnie, to jednak w ostatecznym rozrachunku sprawa drugorzędna. Znacznie ważniejsza – być może nawet pierwszorzędna – zdaje mi się bowiem odpowiednia organizacja na każdym poziomie projektu. Zaczyna się ona od rozmieszczenia funkcjonalności w klasach, modułach i pakietach, a kończy na układzie samych deklaracji w plikach. Ogólna zasada jest tu bardzo prosta: chodzi o to, by elementy podobne i odpowiedzialne za zbliżone zadania były fizycznie blisko siebie. Regułę tę można łamać w przypadkach uzasadnionych i chęć podziału kodu na warstwy (np. logiki i interfejsu) jest na pewno jednym z nich. Często nie da się tego jednak powiedzieć np. o grupowaniu ze sobą w klasie metod o tej samej widoczności zamiast podobnej i/lub zależnej funkcjonalności

Wreszcie, o przejrzystości kodu decydują też wrażenia wzrokowe otrzymywane w czasie jego oglądania. Wpatrywanie się w długie, gęsto zapełnione znakami wiersze o znikomej ilości pustych przestrzeni jest zajęciem męczącym i dlatego powinniśmy oszczędzać go sobie i innym. Stosujmy więc białe znaki, i to rozrzutnie. Spacje, podziały wiersza oraz puste wiersze (a czasami i wcięcia, jeśli język na to pozwala) używane w przemyślany sposób poprawiają wizualny odbiór listingów i jednocześnie poprawiają wspomnianą wcześniej organizację – tym razem na poziomie mikro.

Podstawowa wielowątkowość w Javie

W Javie nietrudno natrafić na metody z klasy Object, bo pojawiają się one w kontekście dowolnego obiektu, do którego się odwołujemy. Wśród tych metod można zauważyć kilka, których przeznaczenie nie jest zrazu oczywiste; są to wait, notify i notifyAll. Lektura dokumentacji może nas pouczyć, że mają one coś wspólnego z wątkami… Ale czemu coś takiego jak wątki ma swoje “wtyki” już na tak niskim poziomie? Ano dlatego, że w Javie wielowątkowość jest pewnego rodzaju młotkiem, którego posiadanie zamienia wiele napotkanych zadań i problemów w gwoździe. Opowiem dzisiaj co nieco o podstawach posługiwania się tym tępym narzędziem :)

Zacznijmy od tego, że kiedy rozdzielamy program na więcej niż jeden wątek, prawie natychmiast pojawia się problem synchronizacji. Może on mieć wiele form, ale zaryzykuję stwierdzenie, że najczęściej występują dwie poniższe:

• ochrona jakiegoś zasobu (w bardzo ogólnym sensie) przez równoczesnym dostępem z więcej niż jednego wątku
• oczekiwanie wątków na jakieś zdarzenia i ich powiadamianie, gdy te zdarzenia zachodzą

Implementacje pierwszego przypadku nazywa się powszechnie sekcjami krytycznymi. W Javie siedzą one tak głęboko, że są częścią samego języka i mają swoje własne słowo kluczowe: synchronized. (Jest to właściwie dokładny odpowiednik lock z C#). Słowem tym możemy oznaczać metody lub bloki kodu, czyniąc je kodem synchonizowanym. Taki kod może być – dla danego obiektu – wykonywany tylko przez jeden wątek naraz. Wszystko więc, do czego się w takim kodzie odwołujemy, jest chronione przed jednoczesnym dostępem wielu wątków – tak jak w przykładzie poniżej:

I tak mniej więcej przedstawiaj się podstawy wielowątkowości w Javie. Bardziej zaawansowane obiekty sychronizacyjne – jak choćby te z pakietu java.util.concurrent wykorzystują te własnie podstawowe mechanizmy zapewniania wyłączności oraz powiadamiania. Jeśli piszemy kod, który korzysta z współbieżności w prosty sposób, możemy wykorzystać je bezpośrednio.

Formatowanie tekstu

Tematem budowania łańcuchów znaków zajmowałem się już kiedyś, badając efektywność tej operacji w C++ dla trzech różnych sposobów. Tym razem przyjrzę się sprawie z perspektywy bardziej niezależnej od języka. Ostatnio poczyniłem bowiem pewną obserwację. Zauważyłem mianowicie, że “tradycyjne” podejście do składania stringów – przez konkatenację kolejnych podciągów – staje się… hmm… niemodne, jeśli można tu użyć takiego określenia.

Ci, którzy kodują nieco dłużej niż ja pewnie zwrócą mi zaraz uwagę, że takie naprawdę tradycyjne podejście do problemu to to, które implementują funkcje z języka C podobne do printf:

Polega ono na uprzednim zdefiniowaniu wzorca tekstu (tzw. formatu, tutaj jest to drugi argument fprintf), zawierającego symbole zastępcze takie jak %s czy %d. Są one następnie zastępowane podanymi wartościami (tutaj: tag oraz errno) w celu wyprodukowania finalnego ciągu. Nie ma tu jawnej operacji łączenia dwóch napisów. Zamiast tego mały parser przegląda podany wzorzec i w miejscu symboli zastępczych wstawia do wyniku podane wartości, przepisując bez zmian resztę znaków.
Wkrótce jednak nadszedł C++ z klasami string i ostream, oferującymi podobne możliwości bez użycia wzorców. Zamiast tego posługiwały się operatorami + i << w celu wyprodukowania tekstowego wyjścia:
cerr << "[" << tag << "] Error (errno=" << errno << ")" << endl;[/cpp] To działa, ale - jak można zobaczyć w porównaniu - wygląda często znacznie mniej przejrzyście. Nie dziwi więc, że w tym względzie historia zdaje się zatoczyć koło. Obecnie bowiem operacja formatowania napisów (w sensie powyższej funkcji fprintf, a nie określania czcionki czy stylu tekstu) jest wbudowana w wiele nowoczesnych, popularnych języków programowania, jak choćby C#, Pythona czy Javę. Najczęściej też, co ciekawe, trzyma się ona z grubsza oryginalnej składni wzorców pochodzącej jeszcze z C, dodając oczywiście jakieś własne, bardziej zaawansowane rozszerzenia:

Czasami jednak – jak widać wyżej – tak nie jest :) Na obecność mechanizmu formatowania łańcuchów znaków możemy aczkolwiek liczyć w każdym szanującym się języku. I to łącznie z C++, gdzie wszystko prawie wszystko, czego w nim pierwotnie nie ma, zawiera się w jakiejś bibliotece boost – w tym przypadku jest to boost::format.

Android jest fajny

Od jakiegoś czasu zajmuję się programowaniem na platformę mobilną Android i zaczynam się już w niej całkiem dobrze orientować. Nie mogę oczywiście twierdzić, że poznałem ją kompleksowo i od podszewki, ale prawdopodobnie mogę już podzielić się swoimi wrażeniami na jej temat.
A te generalnie są pozytywne. Zalety Androida jako platformy programistycznej mogą podzielić w sumie na dwie kategorie: dostępności i wygody.

Przez dostępność rozumiem tutaj fakt, że pisanie aplikacji na tę platformę nie wymaga żadnych specjalnych wysiłków związanych np. z pozyskaniem SDK czy wręcz urządzenia do testowania. Pakiet programistyczny Androida jest bowiem dostępny za darmo i działa pod każdym sensownym systemem operacyjnym (Windows, linuksy i Mac OS X). To trochę (a w zasadzie zupełnie) inaczej niż w przypadku drugiej porównywalnej, a konkurencyjnej platformy mobilnej, co niewątpliwie działa Androidowi na korzyść. Jeśli zaś chodzi o urządzenie, to do testowania z powodzeniem wystarcza dołączony emulator – o ile tylko dysponujemy odpowiednio mocnym komputerem, który udźwignie działającego w nim małego “Linuksa”.
Kiedy jednak już zechcemy przetestować naszą aplikację na rzeczywistym, fizycznym urządzeniu, to i wtedy nie będzie z tym większych problemów. Przy dostępnych pluginów możemy bowiem zintegrować Android SDK z naszym środowiskiem programistycznym (takim jak eclipse czy NetBeans), zyskując dostęp chociażby do pracy krokowej, breakpointów, podglądu zmiennych i innych tego rodzaju narzędzi do debugowania, działających bez problemu także w przypadku aplikacji uruchamianej na zewnętrznym urządzeniu. Rozumiem, że w dzisiejszych czasach nie jest to może nic nadzwyczajnego, ale ja wciąż pamiętam takie, gdy główną metodą znajdowania błędów w aplikacji mobilnej był odpowiednik zwykłego printfa :)

Wygodą programowania pod Androidem przejawia się też w całkiem przemyślanej architekturze systemu i API. Wyjaśnię tu pokrótce, że aplikacje androidowe składają się z komponentów czterech różnych rodzajów, z których prawdopodobnie najważniejszymi są aktywności (activities) i serwisy (services). Te pierwsze to komponenty UI, będące odpowiednikami okienek, form, widoków czy ekranów, zawierających interaktywne kontrolki. Te drugie to procesy działające w tle, mogące np. wykonywać dłuższe czynności takie jak ściąganie z plików.
Ważną cechą wszystkich komponentów aplikacyjnych jest to, że mogą być one tak zadeklarowane, by możliwe było ich użycie także z zewnętrznych programów. Taka komunikacja międzyaplikacyjna odbywa się przede wszystkim za pomocą “magicznych” obiektów typu Intent, zawierających określenie żądanej akcji (np. wyświetlenia listy kontaktów) oraz ewentualne parametry. Komunikacja między poszczególnymi komponentami – nawet w ramach jednej aplikacji – odbywa się głównie za ich pomocą, dzięki czemu możliwe jest prawie automatyczne udostępnienie wybranej części funkcjonalności aplikacji na zewnątrz. No, a przynajmniej taka jest teoria, bo – jak można się domyślić – bardzo typowym błędem w programach androidowych jest to, że “Intenty nie dochodzą” ;-)
Dostępne dla programisty API też wygląda całkiem przyjemnie; wydaje się klarowne i przemyślane. Ma też niewątpliwą zaletę w postaci posiadania doskonałej dokumentacji, bez problemu porównywalnej chociażby z MSDN Library. Dobrze wygląda też kwestia dołączania zewnętrznych zasobów (takich jak obrazki czy układy kontrolek) do aplikacji i dostępu do nich w kodzie, który jest niemal tak samo wygodny, jak w przypadku aplikacji okienkowych w .NET-cie.

Ogólnie zatem Android jako platforma programistyczna przedstawia się całkiem przyjemnie – pod jednym wszak warunkiem: że nie wzdrygamy się na myśl o kodowaniu w Javie. Nie ma tu niestety żadnego sensownego wsparcia dla jakiegokolwiek innego języka, poza małą częścią platformy związaną z aplikacjami natywnymi (pisanymi głównie – jeśli nie wyłącznie – w C). To ma oczywiście swoje dobre strony, chociażby w postaci bardzo dużej integracji maszyny wirtualnej z systemem, na czym z pewnością zyskuje wydajność ich obu.
W sumie więc jeśli ktoś posiada odpowiednie urządzenie – albo przymierza się do kupna takowego – polecam zaznajomienie się z platformą Android, bo może być to przyjemne i produktywne doświadczenie koderskie :)

Obiekt na chwilę

Swego rodzaju miejską legendą pewnego forum nt. programowania jest “algorytm” znany pod intrygującą nazwą sortowania przez ListBox. Adept kodowania postawiony przed problemem posortowania listy obiektów postanowił mianowicie, że akceptowalnym rozwiązaniem dla niego jest następująca sekwencja czynności:

1. Stworzenie obiektu kontrolki typu listbox, czyli typowej przewijalnej listy elementów, która byłaby niewidoczna, niepodłączona pod hierarchię kontrolek w interfejsie lub po prostu miała zerowe rozmiary.
2. Wypełnienie jej zawartości na napisy odpowiadające elementom do posortowania.
3. Ustawienie właściwości Sorted tej kontrolki na true, dzięki czemu jej elementy (wcześniej dodane) będą zawsze posortowane.
4. Pobranie zawartości kontrolki, którą są posortowane elementy.

Genialne, nieprawdaż? :) Zauważmy, że to kreatywne rozwiązanie trudnego problemu wymagało zaledwie jednego dużego i skomplikowanego obiektu, który zasadniczo jest też z zupełnie innej bajki (bo z warstwy GUI) niż kod logiki programu, który to zapewne potrzebował rozwiązania. No ale w końcu programowanie premiuje myślenie wybiegające poza schematy, więc nie ma chyba żadnego powodu, żeby powyższy sposób uznać na niewłaściwy, czyż nie? ;-)

Żarty żartami, ale… No właśnie, w rzeczywistości zastosowane tu “podejście” nie jest wcale tak obce niektórym faktycznym rozwiązaniom rzeczywistych problemów programistycznych. Na wiele pytań odpowiedzią jest bowiem często utworzenie obiektu “tylko na chwilę” – zazwyczaj jedynie dla wywołania jednej jego metody.
Weźmy na przykład pobranie aktualnego zrzutu stosu (stacktrace) w Javie. Prawdopodobnie najmniej kłopotliwą metodą jest utworzenie obiektu wyjątkopodobnego (Throwable) i i wywołanie jego metody getStackTrace:

Jest to na tyle nietypowe, że pewnie sporo osób odruchowo otoczyłoby instrukcję konstruującą obiekt nawiasami, chociaż nie jest to składniowo wymagane.
Inny przykład? Dokonanie HTML-owego escape‘owania tekstu w JavaScripcie wspomaganym biblioteką jQuery. W tym celu tworzy się nigdzie nieprzyłączony węzeł DOM, ustawia jego zawartość tekstową i natychmiast ją pobiera:

I wreszcie rzecz ze znanego i lubianego podwórka C++: konwersja liczb do i z formatu binarnego przy pomocy chwilowych obiektów typu bitset:

Podobnych przykładów dałoby się znaleźć oczywiście znacznie więcej. Fakt ten nie jest zupełnie obojętny dla programistów, jako że przynajmniej w niektórych językach utworzenie obiektu może być operacją dość kosztowną. Nie dotyczy to akurat C++, gdzie możliwe jest alokowanie dowolnych obiektów na stosie, lecz raczej tych platform, gdzie obiekty tworzy się na stercie. Często mają też one stały, dodatkowy narzut na sam fakt swego istnienia, spowodowany odziedziczeniem funkcjonalności po klasie “najbardziej bazowej” (zwanej zwykle Object) – narzut zarówno czasowy, jak i pamięciowy. Dlatego też wielokrotne tworzenie małych i krótko żyjących obiektów może być poważnym uszczerbkiem wydajnościowym. Można jednak liczyć na to, że z biegiem czasu sytuacja pod tym względem będzie się poprawiać – tak jak chociażby w przypadku Javy i wprowadzonych optymalizacji w obsłudze obiektów typu String.