CUDA ogłaszają

Mijający rok (jak zresztą kilka poprzednich) to czas zwiększającej się wydajności układów graficznych. Obecnie są one już nieporównywalnie szybsze niż tradycyjne procesory w komputerach. Charakteryzują się jednak o wiele mniejszą uniwersalnością (wyspecjalizowaniem we współbieżnych obliczeniach na złożonych danych), co jest oczywiście całkiem zrozumiałe – w końcu głównym zadaniem układów GPU jest, jak sama nazwa wskazuje, efektywne przetwarzanie grafiki.
Mimo tego pojawiają się coraz śmielsze pomysły, by zaprząc karty graficzne także do innych zadań. Od kiedy funkcjonalność shaderów, jakie można na nich uruchamiać, stała się stosunkowo dużo, jest to zupełnie możliwe. Zastosowania tzw. GPGPU – czyli wykonywania ogólnych (niekoniecznie graficznych) obliczeń na GPU obejmują przetwarzanie dźwięku, analizę sygnałów (np. szybką tranformatę Fouriera), sieci neuronowe czy nawet operacje na bazach danych.

Ten trend zdaje się być wspomagany przez głównych graczy na rynku. I tak nVidia na początku roku przedstawiła technologię o wdzięcznej nazwie CUDA (Compute Unified Device Architecture). W skrócie jest to zestaw narzędzi, które umożliwiają programowanie układów graficznych (jak na razie tylko kart nVidii serii 8) w języku C. Obejmuje on kompilatory, debuggery i biblioteki matematyczne, które mają na celu wspomaganie tego procesu. Wszystko to wygląda całkiem obiecująco, zwłaszcza w programowaniu gier (wydaje się np. całkiem możliwe liczenie fizyki wielu małych obiektów w sposób współbieżny na GPU), chociaż na razie jest to raczej melodia przyszłości.
Jeszcze bardziej mgliście wygląda sprawa z przyszłą wersją DirectX, oznaczoną numerem 11. Pojawiła się plotka, że pojawi się w niej nowy (czwarty już) typ shadera, czyli compute shader. Miałby on służyć właśnie do takich ogólnych obliczeń na GPU w sposób ustalony całkowicie przez programistę. Widać więc, że jeśli producenci kart chcą dotrzymywać kroku w zgodności z wiodącym graficznym API, takie CUDA jak u nVidii będą wkrótce nie cudowne, ale zupełnie zwyczajne :)

Granice

Bariery, granice, strefy rozdzielające i podobne twory potrafią często utrudniać życie i prowadzić do straty cennego czasu. Jednak w prawdziwym świecie jest możliwe, aby przynajmniej w pewnym obszarze je znieść lub uczynić niewidocznymi – tak jak to stanie się dzisiaj o północy z zachodnią i południową granicą Polski. Naturalnie jest to wielkie przedsięwzięcie logistyczne, organizacyjne i polityczne. Ale doprowadzono je do końca, nie pierwszy raz zresztą – widać więc, że to możliwe.
Podczas programowania też napotykamy na przeróżne granice. Tutaj sytuacja nie przedstawia się aż tak różowo. Nikt ich nie zniesie jakimś odgórnym traktatem i zawsze pozostanie nam ich mozolne przekraczanie…

Cóż to za bariery? Są one bardzo różnego rodzaju, mają jednak pewną wspólną cechę. Występują mianowicie tam, gdzie spotykają się takie okołoprogramistyczne twory, które nie są ze sobą do końca kompatybilne – a mimo to muszą ze sobą współpracować. Przykładów jest mnóstwo i zwykle każdy z nich wymaga osobnego rozwiązania. Oto kilka próbek:

• 
  Wzorzec Most pozwala przekraczać granicę
  między interfejsem a implementacją

  Pewne języki programowania (z C/C++ na czele) mienią się wieloplatformowymi. Teoretycznie więc granica między systemami operacyjnymi powinna być łatwo przekroczona poprzez ponowną kompilację. W praktyce pisanie programów działających na wielu systemach wymaga albo wielkiej dbałości o zgodność, albo napisania po prostu osobnych kodów dla fragmentów, które na różnych systemach implementuje się różnie.

• Programy do grafiki 3D zapisują stworzone modele w wielu różnych formatach. Niektóre odpowiadają naszym oczekiwaniom i możemy je odczytywać bezpośrednio (co aczkolwiek banalne nie jest, ale o tym kiedy indziej), ale jeśli chcemy zapisywać z modelem jakieś niestandardowe informacje albo robić to w nieprzewidziany sposób, potrzebujemy zwykle pluginu do edytora 3D. W tym przypadku wtyczka ta jest sposobem na przekroczenie granicy między wspomnianym edytorem a naszym silnikiem.
• Kiedy aplikacja zaczyna się komunikować przez sieć, owo przełamywanie barier (w tym przypadku jednej maszyny) jest od razu widoczne i, oczywiście, przysparza kłopotów :) Zależnie od tego, o jakim poziomie abstrakcji mówimy, możemy spotkać się z: taką obsługą odczytu i zapisu danych, by nie blokowało to reszty aplikacji; niedostatkami istniejących i nieco przestarzałych protokołów sieciowych (albo koniecznością tworzenia własnych) czy nawet inną kolejnością bajtów przy interpretowaniu danych liczbowych na maszynie źródłowej i docelowej.

Można by niemalże pomyśleć, że kodowanie polega przede wszystkim na godzeniu ze sobą takich niezgodnych platform, systemów, bibliotek, i tak dalej. Jednak wśród tych wszystkich granic tak naprawdę tą najważniejszą, którą powinniśmy nieustannie przekraczać, jest granica naszych własnych możliwości.

Spłaszczanie drzewa

Czasami przychodzi nam operować na strukturach drzewiastych. Drzewko, jak sama nazwa wskazuje, składa się z elementów połączonych relacjami nadrzędny-podrzędny . (OK, może nazwa tego nie wskazuje, ale wiadomo to skądinąd ;]). W językach programowania połączenia te realizujemy poprzez wskaźniki albo podobne mechanizmy, jak na przykład referencje.

Drzewa mogą być oczywiście ustalonego rzędu (jak choćby drzewa binarne) i wtedy ich przechowywanie nie nastręcza większych trudności. Nieco gorzej jest wtedy, gdy każdy węzeł może mieć dowolną liczbę węzłów podrzędnych. Wtedy często wygodnie jest przechowywać je w formie dynamicznej struktury danych: tablicy albo listy. Przynajmniej dopóty, dopóki nasze drzewo rezyduje wyłącznie w pamięci…
Może bowiem przyjść konieczność zapisania go w trwalszym miejscu. Pół biedy, jeśli docelowy format sam w sobie ma strukturę drzewiastą i umożliwia uporządkowanie danych w sposób hierarchiczny – tak jak chociażby XML. Ale nie zawsze mamy taki luksus. Weźmy na przykład wirtualny system plików (VFS), w którego archiwum chcemy zapisać (drzewiastą, rzecz jasna) strukturę katalogów – w formie binarnej. Podobnych sytuacji jest całkiem sporo, zwłaszcza gdy mamy do czynienia z relacyjnymi bazami danych.

Prawdopodobnie właśnie stamtąd wywodzi się najprostsze i chyba najczęściej stosowane rozwiązanie problemu. Polega ono na oznaczeniu każdego węzła drzewa unikalnym identyfikatorem (np. liczbą) i zapisaniu razem z węzłem (oprócz związanych z nim danych) także identyfikatora węzła nadrzędnego. W ten sposób zachowujemy wszystkie informacje o hierarchii. Metoda ta ma tę zaletę, że jest prosty i wymaga niewielkiej liczby dodatkowych danych.
Wadą mogłoby być to, iż w tej postaci nijak nie da się takiego drzewa przejść ani wyszukiwać w nim. Lecz to nie jest tak naprawdę ważne, gdyż dla potrzeb programu możemy na podstawie tej reprezentacji skonstruować normalne, “wskaźnikowe” drzewo. W tym celu wystarczy najpierw stworzyć wszystkie węzły (zapisując oba związane z nimi identyfikatory), a następnie odbudować powiązania między nimi, posługując się odwzorowaniem identyfikator -> węzeł, utworzonym podczas wczytywania. Bardzo przydaje się do tego struktura danych w rodzaju mapy (słownika).

Pośrodku podium

Ostatnio na stronie Warsztatu pojawiła się sonda (ponownie zresztą). Pierwsze pytanie było nader interesujące, bowiem dotyczyło tego, czy warsztatowicze… prowadza aktualnie blogi albo noszą się z takim zamiarem w przyszłości. Wyniki wskazywały, że piszący stanowią około jedną czwartą tego community.

Bardziej interesujący był mini-konkurs na najlepszego bloga, odbywający się poprzez mechanizm oceniania komentarzy do wspomnianej sondy. Okazało się, że strona z moimi wypocinami – mimo stosunkowo krótkiego czasu istnienia – zdołała zebrać na tyle dużo głosów, by ostatecznie uplasować się na drugim miejscu. To bardzo miłe i zaskakujące – zwłaszcza, jeśli spojrzymy, kto zajął miejsce trzecie ;)
Gratuluję też morituriusowi zwycięstwa i mam oczywiście nadzieję, że pisanie devlogów będzie zataczało coraz szersze kręgi, zwłaszcza na Warsztacie.

Rozmiar a pojemność

Od kiedy w Bibliotece Standardowej języka C++ istnieje szablon vector, nie trzeba się już martwić kłopotami z dynamiczną alokacją pamięci dla tablic o zmiennym rozmiarze. Szablon ten jest na tyle sprytny, że zapewnia wszystkie zalety zwykłych tablic – łącznie z możliwością uzyskania wskaźnika na ciągły obszar pamięci zawierający elementy. Jednocześnie sam kontroluje rozmiar tablicy oraz wykorzystanie pamięci.
W sensownej implementacji STL jest to osiągnięte poprzez strukturę samorozszerzalnej tablicy. W skrócie można to określić jako alokację większej ilości pamięci niż faktycznie potrzeba – po to, aby dodawanie nowego elementu trwało w przybliżeniu czas stały (w tzw. sensie zamortyzowanym). Całkowita ilość pamięci wykorzystywana aktualnie przez wektor to jego pojemność i jest ona możliwa do pobrania metodą capacity (zwraca ona liczbę elementów, które jeszcze się zmieszczą bez realokacji). Natomiast metoda size zwraca liczbę aktualnie zawartych w tablicy obiektów, czyli jej rozmiar.
Istotne jest, aby te dwie wartości rozróżniać. Kiedy zaś zrównają się ze sobą, następne dodanie elementu wymusi ponowną alokację bloku pamięci dla całej tablicy (zwykle dwukrotnie większego) i przekopiowanie jej zawartości w nowe miejsce.

Taka operacja jest oczywiście kosztowna (liniowa względem rozmiaru tablicy) i dlatego chcielibyśmy, żeby odbywała się jak najrzadziej. Używając metody reserve możemy naraz zaalokować pamięć na tyle elementów, ile będziemy potrzebowali – a więc zwiększyć jej pojemność (lecz nie rozmiar!), jak to widać na poniższym mało inteligentnym przykładzie:

Tworzymy tutaj kopię wektora, używając konstruktora kopiującego. Trik polega na tym, że w czasie tworzenia tej kopii zostanie przydzielona dokładnie taka ilość pamięci, jaka jest potrzebna dla elementów wektora. Potem jeszcze zamieniamy ten chwilowy wektor z oryginalnym… i już :)

Najrzadsze słowo kluczowe

Standardowy C++ ma ponad 50 podstawowych słów kluczowych. To naprawdę całkiem sporo, chociaż nowsze języki wykazują jeszcze większą tendencję do produkowania tych elementów składni. Te kilkadziesiąt na razie jednak wystarcza w zupełności. Oczywiście są sytuacje, w których dla przejrzystości przydałoby się dodatkowe słówko (jak na przykład coś podobnego abstract przy deklarowaniu metod czysto wirtualnych). Jeśli jednak nie jesteśmy specjalistami od C++, to może nam się przytrafić spotkanie z keywordem, którego nigdy wcześniej na oczy nie oglądaliśmy.

Dla mnie – i podejrzewam, że nie tylko dla mnie – ostatnim takim przypadkiem było ujrzenie tajemniczego słowa kluczowego mutable. Być może nie jest ono, jak tutaj sugeruję, najrzadziej używanym słowem kluczowym C++ w ogóle, ale jestem przekonany, że mieści się ono co najmniej w pierwsze trójce. A skoro już o nim wspominam, to wypadałoby wyjaśnić, do czego ono służy.
mutable jest mianowicie modyfikatorem, którym możemy opatrzyć pole klasy – na podobnej zasadzie jak np. static czy const (z którymi zresztą mutable wzajemnie się wyklucza). Pole posiadające taki atrybut może być następnie modyfikowane z poziomu każdej metody swojej klasy – włącznie z tymi metodami, które są zadeklarowane jako stałe (const).
Imponujące? Bynajmniej. Mówiąc mniej formalnie, mutable pozwala na to, by obiekt mógł być stały pod względem koncepcyjnym nawet jeśli z pewnych “technicznych” powodów musimy zmienić zawartość niektórych jego pól. C++ jest pedantyczny i traktuje każdą modyfikację wartości składowych obiektu jako niedozwoloną w metodzie stałej. Czasami jednak chcemy tak zrobić, jako że dla nas obiekt ten nadal będzie niezmieniony – mimo tego, iż ze ścisłego, bitowego punktu widzenia zostanie on zmodyfikowany.

Taka sytuacja może zajść na przykład wtedy, gdy pewne dane chcemy wyliczać na żądanie – wtedy, kiedy będą potrzebne. Żeby przykład był życiowy, weźmy element trójwymiarowej sceny, któremu przypiszemy macierz translacji, skalowania i obrotu. W pewnym momencie będziemy chcieli je przemnożyć i dostać macierz całej transformacji, ale nie opłaca się tego robić za każdym razem, gdy zmienia się któraś z macierzy składowych. Jednak metoda zwracająca nam iloczyn powinno zasadniczo być stała, co przeszkadza cacheowaniu tegoż iloczynu jako pola w obiekcie.
I tutaj z pomocą przychodzi nam mutable:

W ten sposób mamy za darmo elegancję, szybkość i spójność koncepcyjną. Znajomość egzotycznych elementów języka może więc wbrew pozorom przynosić czasem konkretne korzyści :)

PS. Jak widać, ten element jest na tyle egzotyczny, że nawet skrypt kolorujący składnię C++ nie potrafi sobie z nim poradzić ;-)

Różne rodzaje książek koderskich

Programowanie to nie tylko ciągłe stukanie w klawiaturę i pisanie kilometrowych listingów (względnie intensywne wyklikiwanie interfejsu użytkownika). Zawsze od czasu do czasu przychodzi czas, gdy trzeba się odwołać do źródła wiedzy fachowej. Na pierwszej linii frontu stoi wtedy zwykle dokumentacja do konkretnego środowiska czy języka, ale nie jest to jedyne źródło wiedzy, z którego programista korzysta. Wśród nich są również książki.

Literatura programistyczna jest naturalnie niezwykle bogata i dotyczy każdego pola koderskiej działalności, wszystkich możliwych bibliotek, języków, metodologii i wszelkich innych aspektów programowania. W takiej klasyfikacji nietrudno się odnaleźć i zazwyczaj łatwo możemy stwierdzić, o czym dana pozycja traktuje. Trochę gorzej bywa z oceną, jak dany temat został w tej konkretnej książce potraktowany.
Jako że przydarzyło mi się przeczytać dość sporą liczbę programistycznych książek, a jeszcze większą – mniej lub bardziej pobieżnie przekartkować, mogę chyba pokusić się o klasyfikację na podstawie tego drugiego, mniej widocznego kryterium. Uważam zatem, że możemy wyróżnić kilka rodzajów książek programistycznych:

• Kompletne omówienia, czyli – nie bójmy się użyć tego słowa – wykłady. Takie książki nie muszą mieć oczywiście arcyporywającego stylu, charakteryzującego większość podręczników akademickich. Wręcz przeciwnie, mogą być napisane w sposób żywy, wciągający i intrygujący. Ich naczelną cechą jest to, że koncentrując się na danym temacie opisują go w sposób dokładny, obszerny i uporządkowany. Kolejne rozdziały przedstawiają poszczególne zagadnienia, pełne są omówień, przykładów, czasem dygresji. To coś w rodzaju koderskiej beletrystyki, dobrej do czytania w wolnych chwilach i do nauki zupełnie nowych treści.
• Książki kucharskie. Jak sama ich nazwa wskazuje, zawierają one przepisy (czasem zwane wręcz recepturami) na mniej lub bardziej konkretne rozwiązania praktycznych problemów. Mogą to być kompletne sposoby na realizację jakichś fragmentów programu albo tylko artykuły sygnalizujące istnienie pewnych narzędzi i metodyk. Zawsze jednak zakładają pewną wiedzę czytelnika w danym temacie, co nie przeszkadza im jednocześnie wyłożyć przy okazji jakichś drobnych fragmentów obszerniejszych zagadnień. Najważniejsze jest jednak to, że są one skoncentrowane na praktycznym wykorzystaniu zawartych w nich “sztuczek”.
• Notatki z pola bitwy to bardzo ciekawy typ książek, z którymi zetknąłem się dopiero niedawno. W założeniu mają one umożliwić “zaglądanie do warsztatu” doświadczonego programisty i stanowią luźny (lecz uporządkowany) zbiór uwag, fragmentów kodu i komentarzy, tyczących się jakiegoś zagadnienia – zwykle języka, biblioteki lub technologii. Ich celem jest przekazanie wiedzy maksymalnie praktycznej i jednocześnie obszernej. Wymagają dobrego przygotowania ze strony czytelnika, lecz jeśli spełnia on wymagania, może on zyskać nie tylko przydatne informacje, ale i bardzo użyteczne umiejętności.
• Leksykony i materiały referencyjne. Te pozycje mają najwięcej wspólnego z klasyczną, elektroniczną dokumentacją. Systematyczny opis funkcji, klas, właściwości, pól, metod, wyjątków, sygnałów, interfejsów i wszystkich tych elementów, które składają się na dane narzędzie programistyczne. Te grube książki najlepiej jest trzymać na biurku w trakcie pisania kodu. Ich przewaga nad dokumentacją polega zwykle na trafnych przykładach zastosowań opisywanych elementów i lepszą organizacją treści.
• Ciekawostki okołokoderskie. W tych książkach możemy znaleźć właściwie wszystko: od przykładów najczęściej popełnianych błędów po wskazówki, w jaki sposób należy czytać kod napisany przez innych. Jeśli wpadnie nam w ręce któraś z tego rodzaju książek, zwykle albo ją pokochamy i będziemy co jakiś czas do niej wracać, albo uznamy pomysł jej napisania za zupełnie nietrafiony i szybko o niej zapomnimy. Nie muszę chyba wspominać, że systematyczne ułożenie wiedzy i orientacja na teorię/praktykę nie są kategoriami, których powinniśmy używać do oceniania takich książek. W większości jest to bowiem całkowity freestyle – z różnymi skutkami, oczywiście.

Jak w każdej arbitralnej klasyfikacji, także i tutaj szufladki te są rzecz jasna rozmyte i wiele książek zmieściłoby się bez problemu na kilku półkach. Prawdopodobnie takie właśnie są najlepsze i najbardziej użyteczne. W końcu skoro już decydujemy się na treści zapisane na papierze, powinniśmy dążyć do korzystania z nich na wiele sposobów… ;]