Wiedza czysto użytkowa

Spotykam się ostatnio z osobliwym podejściem do przeróżnych wiadomości tyczących się programowania. Mogę je określić dość zaskakująco jako nadmiar “chęci rozumienia” lub ewentualnie “nieuzasadnioną dociekliwość”. Dotyczy to bardzo wielu narzędzi używanych w zasadzie każdej dziedzinie programowania – jak języki, środowiska czy biblioteki – oraz większości jego aspektów.

Czym to się objawia? Otóż symptomem jest pragnienie dogłębnego zrozumienia jakiegoś mechanizmu w sposób jak najszerszy i jak najgłębszy jednocześnie – zanim jeszcze spróbuje się go zastosować. Ten pęd to wiedzy dla samej wiedzy skutkuje najczęściej pozyskaniem dużego zasobu informacji, z których sensownym połączeniem i – przede wszystkim – stosowaniem są później pewne, a często spore, kłopoty.
Czy twierdzę więc, że nadmiar wiedzy szkodzi? Bynajmniej. Chodzi mi raczej o chęć zadawania raczej pytań w rodzaju “jak to działa?” niż “jak tego użyć?”. Sądzę bowiem, że zdecydowana większość programistycznej wiedzy ma charakter czysto użytkowy i jako taka jest na tyle przydatna, na ile daje się użyć w praktyce. Koder powinien być raczej przygotowany na poszukiwanie potrzebnych informacji w trakcie rozwiązywania danego problemu, a nie na kompletne poznanie tematu przez przystąpieniem do pracy.

Jeśli aczkolwiek życzymy sobie poznać głębiej jakieś zagadnienie z racji tego, że jest ono interesujące, wszystko jest w porządku. Jeśli jednak chodzi nam tylko o osiągnięcie zamierzonego celu, nie musimy poznawać rozgałęzień każdej drogi, która do niego prowadzi. Jak zawsze, najważniejsze jest zachowanie odpowiedniej równowagi.

Kompilowanie efektów w locie

Model subtraktywny programowalnego potoku graficznego (nie ma to jak kilka trudnych słów na początek ;P) charakteryzuje się tym, że kody shaderów są w nim dość rozdęte objętościowo. Wynikową postać shadera otrzymuje się bowiem poprzez wybranie części kodu odpowiadającej aktualnym potrzebom związanym np. z materiałem i oświetleniem. Rzeczone części są wydzielone przy pomocy dyrektyw podobnych do preprocesora z C: #if, #else, itd.

Najprościej jest wtedy, gdy korzystamy z plików efektów (.fx) z DirectX. Wtedy można użyć funkcji D3DXCreateEffectFromFile lub D3DXCreateEffectFromFile, którym można przekazać wartości makr potrzebnych w danym przebiegu renderowania. Działa to tak, jakbyśmy użyli dyrektywy #define bezpośrednio w kodzie efektu i podobnie do makr definiowanych w wierszu poleceń kompilacji w przypadku normalnych programów.
Otrzymany w ten sposób skompilowany shader należy oczywiście zachować, aby można było szybko przełączać między potrzebnymi wersjami w czasie renderowania. Wciąż jednak wymaga to ponownej kompilacji wszystkich używanych wersji shadera przy każdym uruchomieniu aplikacji – co jest marnotrawieniem czasu, jeżeli plik z kodem efektu się nie zmienia.

Można coś na to poradzić, stosując interfejs ID3DXEffectCompiler zamiast zwykłego ID3DXEffect. Ten pierwszy ma bowiem dodatkową, bardzo przydatną metodę CompileEffect:

W wyniku jej użycia możemy dostać bufor (czyli w gruncie rzeczy kawałek pamięci wypełniony danymi binarnymi) zawierający efekt w postaci skompilowanej. Najważniejsze jest to, że w tej postaci możemy zapisać go do pliku (zwykle z rozszerzeniem .fxo) i później tylko szybko odczytać – bez czasochłonnej rekompilacji. W ten sposób można stworzyć mechanizm cache‘owania skompilowanych shaderów, który przyspieszy uruchamianie aplikacji.

Refleksje

Dzisiaj zastanowimy się nad refleksjami. Nie, nie jest to wcale masło maślane. Mechanizm refleksji (reflection – odbicie) jest zwany też introspekcją i polega na tym, iż działający program “wie” o swojej wewnętrznej strukturze. Prostą odmianą jest tutaj dynamiczna informacja o typie (RTTI), czyli możliwość określenia faktycznego typu obiektu znanego poprzez wskaźnik lub referencję.
W bardziej zaawansowanej wersji, obecnej na przykład w języku Java i na platformie .NET, refleksje są jednak czymś więcej. Stanowią faktyczne ‘odbicie’ struktury programu w postaci informacji dostępnych w czasie wykonania. Przy ich pomocy można na przykład uzyskać dokładne informacje o polach, metodach i właściwościach każdej klasy oraz jej miejscu w hierarchii dziedziczenia, nie mówiąc już o możliwości tworzenia jej instancji. Dostępność takich informacji umożliwia łatwe stworzenie modułu serializacji lub bardziej zaawansowanego odśmiecania pamięci, bazującego na przechodzeniu grafu odwołań między obiektami.

Ale C++ posiada tylko bardzo proste RTTI, które do takich celów jest daleko niewystarczające. Czy można jednak naprawić tę przypadłość? Jest na to kilka sposobów:

• Można spróbować odczytać informacje debugowania generowane przez nasz kompilator. To może dawać kompletne informacje o wszystkich typach użytych w programie, ale ma dwie zasadnicze wady. Po pierwsze, wymaga kompilacji programu przynajmniej z pewnymi ustawieniami trybu debugowania także w wersji wydaniowej. A po drugie, jest w oczywisty sposób nieprzenośnie pomiędzy różnymi kompilatorami. Poza tym nie wydaje mi się, żeby było to proste rozwiązanie.
• Innym podejściem jest odczytanie wszystkich danych bezpośrednio, czyli samodzielne przeanalizowanie kodu źródłowego i wygenerowanie na tej podstawie koniecznych informacji. Najpewniej wynikiem byłyby dodatkowy kod poddawany normalnej kompilacji. Wadą jest tu stopień skomplikowania: parsowanie kodu C++ łącznie z rozwijaniem dyrektyw preprocesora zdecydowanie nie jest prostym zadaniem. Ponadto proces kompilacji projektu stałby się bardziej złożony.
• Jeżeli ktoś byłby dostatecznie zdesperowany, mógłby teoretycznie… stworzyć własny kompilator C++, obsługujący refleksje natywnie. Nie da się ukryć, że potrzeba by sporej siły, by zamachnąć się motyką na takie słońce :)
• Wreszcie możliwe jest, aby programista podawał niezbędne informacje – zwykle jako kombinacja dziedziczenia i makr preprocesora. To podejście jest (stosunkowo) najprostsze w implementacji, ale zapewne najbardziej nieporęczne w użytkowaniu. Może być też podatne na błędy. Jednocześnie jednak ma największe szanse być przenośne i… działające :)

Gdybym aczkolwiek kiedyś cierpiał na dużą nadwyżkę wolnego czasu, to pewnie rozważyłbym implementację rozwiązania drugiego (lub jakiejś kombinacji rozwiązania drugiego i pierwszego, na przykład zlecającej rozwijanie makr programowi kompilującemu). Do tego czasu jednak C++ już dawno będzie posiadał wbudowany system refleksji ;)

Finalne demo Rega

Regedit zaprezentował dzisiaj w końcu demko prezentujące możliwości jego silnika, który – jak sam utrzymuje – niedawno ukończył. Wprawdzie ja nadal mam wątpliwości, czy wyrazy ‘silnik’ i ‘ukończony’ w ogóle powinny pojawiać się obok siebie, ale nie zmienia to faktu, że przynajmniej aktualnie istniejąca część jego engine‘u prezentuje się imponująco. Moje gratulacje!

Po więcej szczegółów zapraszam tutaj:

The Final Quest

A ja w międzyczasie mogę dumać nad tym, ile to jeszcze miesięcy i lat zajmie mi dojście do podobnego poziomu ;)

Szare shadery

Dawno, dawno temu – co w dziedzinie programowania grafiki oznacza perspektywę kilkuletnią – większość przetwarzania odbywała się we wbudowanym, stałym potoku graficznym. Shadery wprawdzie były, ale oferowane przez nie możliwości były dosyć ubogie (zwłaszcza jeśli chodzi o te do pikseli), a poza tym należało kodować je w niezbyt przyjaznym języku podobnym do asemblera. Pewnie dlatego, a dodatkowo także z powodu małego wsparcia kart graficznych, większość efektów realizowano przy pomocy odpowiednich tekstur, stanów ich faz i tym podobnych wynalazków. Bardzo często tak było po prostu łatwiej.
Zadziwiające jest to, że teraz nierzadko bywa dokładnie odwrotnie :) Chociaż na początku można jeszcze uważać, że ustawianie przeróżnych stanów stałego potoku i poleganie wbudowanie jest łatwiejsze, a shadery dają “tylko” większe możliwości, to jednak z czasem to myślenie zawsze powinno się zmienić. W końcu przecież napisanie algorytmu określającego dokładnie krok po kroku, co się dzieje z wierzchołkiem lub pikselem, dla programisty z założenia musi być łatwiejsze niż ustawianie jakichś dziwnych flag, będącymi swoistymi wytrychami do standardowego sposobu przetwarzania.

Zresztą nie wszystko można tymi wytrychami łatwo osiągnąć. Weźmy niezwykle prosty efekt wyświetlania w skali szarości, jak na czarno-białym zdjęciu. Jeżeli chodzi o realizację tego efektu na fixed pipeline, to chwilowo nie mam na to żadnego sensownego pomysłu – oczywiście poza podmianą wszystkich tekstur na ich ‘szare’ wersje.
A wystarczyłoby tylko użyć prostego pixel shadera, który jawnie implementuje wzór na obliczenie natężenia koloru:

I już, efekt gotowy. Nietrudno byłoby też połączyć go z jakimkolwiek innym. W ogólności jest jednak ‘trochę’ trudniej – ale to już temat na inną okazję ;P

Sprzątanie śmieci

Pamięcią operacyjną można w programowaniu zarządzać na dwa sposoby. Pierwszy to ręczne tworzenie obiektów i niszczenie ich, gdy nie są już potrzebne. Daje to kontrolę nad czasem ich życia, ale dopuszcza też możliwość powstawania błędów, jak wycieki pamięci czy próby podwójnego jej zwalniania. Aby im zapobiec, każdy obiekt musi mieć ściśle określonego właściciela, odpowiedzialnego za jego zniszczenie.
Drugi sposób to użycie mechanizmu odśmiecania pamięci (garbage collecting), które powinien sam wykrywać “porzucone” obiekty i je zwalniać, kiedy zachodzi ku temu potrzeba. Pozwala to oczywiście przestać martwić się o ich niszczenie. Zwykle nie oznacza to jednak, że wszystkie wyciekające fragmenty pamięci zostaną zwolnione natychmiast. Tracimy więc kontrolę nad czasem życia obiektów.

Nie da się jednak ukryć, że od kiedy komputery mają dość mocy obliczeniowej, aby wyświetlać miękkie cienie pod okienkami, mogą też z powodzeniem zajmować się automatycznym porządkowaniem sterty w swoim wolnym czasie. Dlatego zdecydowana większość nowych języków programowania jest wyposażona w odśmiecacze, które na dodatek są zawsze włączone i zwykle nie da się z nich zrezygnować. Najlepiej byłoby naturalnie mieć tutaj wybór, lecz rzadko jest on nam dany.
Nie inaczej jest w C++, tyle że tutaj mamy chyba jednak tę gorszą opcję – czyli konieczność ręcznego zarządzania alokacją i zwalnianiem. Można aczkolwiek to zmienić, lecz nie odbędzie się to w sposób przezroczysty dla programisty.

Odśmiecanie można przeprowadzić dwiema podstawowymi metodami, które mają naturalnie wiele wariantów. Są to:

• Śledzenie odwołań. Oznacza to posługiwanie się strukturą grafu w celu oznaczania elementów nieosiągalnych z bieżącego miejsca w programie, a następnie ich sukcesywnego zwalniania. Wymaga to wiedzy o tym, jak jeden obiekt może odwoływać się do drugiego i w C++ wymagałoby na przykład dziedziczenia po ustalonej klasie bazowej połączonego z kilkoma innymi wymaganiami.
• Zliczanie referencji. Polega to na trzymaniu obok każdego obiektu licznika odwołań do tego właśnie obiektu. Każde kopiowanie i przypisywanie wskaźnika zmienia ten licznik i jeśli spadnie on do zera, obiekt kwalifikuje się do usunięcia. W C++ metodę tę można zaimplementować chociażby przy pomocy inteligentnych wskaźników.

W swoim pierwszym (działającym :)) ośmiecaczu dla C++ zastosowałem drugą metodę – oczywiście ze względu na jej prostotę. Jak wiadomo jednak nie jest ona doskonała, gdyż jej piętą achillesową są odwołania cykliczne. Można jej zaradzić na przykład poprzez tak zwane słabe referencje… Ale na szczęście póki co nie potrzebuję jeszcze takich “zakręconych” (dosłownie i przenośni) relacji między obiektami ;P

Tablice bardzo dynamiczne

W każdym poważnym języku programowania mamy do dyspozycji tablice o zmiennym rozmiarze, możliwym do ustalenia w czasie działania programu. Teoretycznie można by się bez nich obyć, jeżeli język posiada jakąś formę wskaźnika czy referencji, lecz konieczność ciągłego używania list na pewno nie byłaby przyjemna.
Z drugiej strony tablice mogą też być indeksowane więcej niż jednym indeksem, czyli być wielowymiarowe. Niekiedy wszystkie podtablice w danym wymiarze muszą mieć ten sam rozmiar (czyli całość być prostokątem, prostopadłościanem, itd.), ale np. C++ i C# pozwalają na dowolność i tworzenie chociażby macierzy trójkątnych zawierających tylko interesujące nas komórki.

To całkiem nieźle, lecz nie spotkałem jeszcze żadnego języka, który osiągnąłby zen w kwestii dynamicznych tablic, a mianowicie umożliwiał zmianę liczby wymiarów w trakcie działania programu. Być może powodem jest fakt, że w przypadku takich wybitnie elastycznych tablic nie da się już zapewnić dostępu do pojedynczego elementu w czasie stałym. Dla n wymiarów może on bowiem wynieść O(n²).
Jak więc można taką bardzo dynamiczną tablicę symulować? Ano trzeba samemu przeprowadzić jej linearyzację, czyli ponumerowanie wszystkich elementów tak, by można było obliczyć adres każdego w – liniowej przecież – pamięci operacyjnej. Przykładowo dla tablicy dwuwymiarowej element (x, y) będzie miał zlinearyzowany indeks równy zwykle x + y * width. Numerując z kolei trójwymiarową “kostkę”, otrzymalibyśmy formułę: x + y * width + z * height * width.

I tak dalej… W przypadku ogólnym aczkolwiek wzór może być trochę straszny :) Dla n-wymiarów o rozmiarach c₁, …, c_n, element opisany indeksami a₁, …, a_n (liczonymi od zera) w wersji zlinearyzowanej znajdzie się na miejscu l:

Formuła przekłada się oczywiście na dwie zagnieżdżone pętle – stąd więc jej oczekiwana złożoność. Można ją jednak łatwo zoptymalizować, przechowując wartość wewnętrznego iloczynu dla każdego z n wymiarów. Wtedy dostęp będzie już w czasie liniowym – oczywiście cały czas względem liczby wymiarów, a nie rozmiaru tablicy, więc nie jest aż tak źle :)
Taką dynamicznie wielowymiarową tablicę prawdopodobnie najłatwiej i najlepiej jest zaimplementować C++. I, co ciekawsze, nie będzie to wcale odkrywanie koła na nowo – czegoś takiego nie ma bowiem ani STL (daleko jej do tego), ani nawet boski boost ;]