Powtórka z rozrywki

Kolejna konferencja IGK zakończyła się wczoraj tradycyjnym konkursem zespołowego programowania gier Compo. Podobnie jak w zeszłym roku startowało wiele zespołów, w tym także i mój, czyli Rzeźnicy Inc. ;) I podobnie jak zawsze, wszyscy starali się zakodować jak najlepiej wyglądające, najbardziej grywalne, najoryginalniejsze i w ogóle najlepsze gry. Naturalnie nie wszystkim się to udało, ale akurat w przypadku mojej drużyny rezultat był chyba całkiem niezły. W każdym razie zasłużył na drugie miejsce, czyli analogicznie jak w zeszłym roku. Krótko mówiąc: trzymamy poziom :)

W najbliższych dniach postaram się zamieścić na stronie jakąś grywalną wersję naszej pracy.

Moda na krytykowanie OOP-u

Nauczyłem się już lubić fakt, że w przypadku informatyki powiedzenie o “ciekawych czasach” jest truizmem, bo ciekawie jest po prostu zawsze – głównie ze względu na tempo zmian w wielu dziedzinach. Nawet w tych, wydawałoby się, zastygłych na lata. Niecałe trzy lata temu zżymałem się na przykład na zbytnią ufność w doskonałość obiektowych metod programowania. Dzisiaj zaś przychodzi mi robić coś zdecydowanie przeciwnego.
Programowanie obiektowe jest obecnie sztandarowym kozłem ofiarnym i chłopcem do bicia, otrzymującym ciosy z wielu stron. Już nie tylko programiści gier twierdzą, że nie mogą sobie na nie pozwolić ze względu na wydajność i zamiast niego forsują Data Oriented Design. Pokazywałem niedawno, że sprzeczność między tymi dwoma podejściami jest raczej pozorna niż rzeczywista. Teraz natknąłem się na interesującą opinię, która podważa sens OOP-u jako metodologii, wychodząc z nieco innego punktu widzenia niż wydajność dla celów grafiki real-time:

Object-oriented programming (…) is both anti-modular and anti-parallel by its very nature, and hence unsuitable for a modern CS curriculum. [pogrubienie moje]

Anty-modularne i anty-współbieżne? Oczywiście; da się napisać kod obiektowy, który te dwa warunki będzie spełniał doskonale. Ale to nie oznacza, że każdy kod obiektowy je spełnia, a to właśnie jest implikowane powyżej. Nie da się tego określić inaczej niż jako stereotyp – i to w modelowej wersji, czyli negatywnego uogólnienia z pojedynczych przypadków.

Jako antidotum na te rzekome bolączki OOP-u często wymieniane jest programowanie funkcyjne. Nie ujmując mu niczego ze swojej elegancji, nie mogę jednak nie zauważyć, że zamiata ono wiele problemów pod dywan. Określanie wykonania programu jako serii transformacji danych nie rozwiązuje jednak problemu: gdzie i jak te dane mają być zapisywane i chronione przed równoczesnym dostępem z wielu ścieżek wykonania. Sytuacje, w których programowanie funkcyjne lub quasi-funkcyjne sprawdza się dobrze to takie, gdzie problemy te dały się w miarę łatwo rozwiązać. Tak jest chociażby w przypadku vertex i pixel shaderów, gdzie podział danych wejściowych i wyjściowych na rozłączne bloki jest wręcz naturalny. Fakt ten nie jest jednak zasługą programowania funkcyjnego, tylko natury zagadnienia – w tym przypadku renderowania grafiki opartej na wielokątach.

I właśnie o tym powinniśmy pamiętać, gdy wyzłośliwiamy się nie tylko na OOP, ale dowolny inny paradygmat programowania. Otóż porzucenie go nie sprawi od razu, że magicznie zaczniemy pisać kod doskonale modularny. A już nie pewno nie spowoduje, że niezwykle trudne zagadnienia współbieżności staną się nagle banalnie proste. To niestety tak nie działa.
Nie znaczy to oczywiście, że nie powinniśmy poszukiwać nowych, lepszych metodologii do konkretnych zastosowań. Dlatego przecież wiele języków (np. C++, C#, Python) ewoluuje w kierunku wieloparadygmatowości, aby możliwe było dobranie właściwych narzędzi dla danej sytuacji. Nie wydaje mi się jednak, aby uleganie trendy nurtom krytykowania jakichkolwiek rozwiązań poprzez odwoływanie się do stereotypów i nieuzasadnionych wyobrażeń o nich było w tym procesie specjalnie produktywne. Zdaję sobie jednak sprawę, że “funkcje wirtualne to zuo!” brzmi lepiej niż “wywoływanie funkcji wirtualnych skutkuje narzutem wydajnościowym związanym z dodatkowym adresowaniem pamięci (które nie jest cache-friendly) i może powodować niepożądane skutki uboczne, jeśli ich wersje w klasach pochodnych nie są thread-safe“. Mam jednak nadzieję, iż nikt nie ma wątpliwości, które z tych dwóch stwierdzeń jest bardziej racjonalne.

Podziękowania dla Rega za podesłanie linków, które zainspirowały mnie do podjęcia tego tematu.

Importy niezupełnie z zagranicy

Przeglądając plik źródłowy programu w dowolnym niemal języku, gdzieś bardzo blisko początku znajdziemy zawsze region z importami. Niekoniecznie będą one oznaczone słowem kluczowym import – czasem to będzie using, być może do spółki z #include – ale zawsze będą robiły zasadniczo to samo. Chodzi o poinformowanie kompilatora lub interpretera, że w tym pliku z kodem używamy takich-a-takich funkcji/klas/itp. z takich-a-takich modułów/pakietów. Dzięki temu “obce” nazwy użyte w dalszej części będą mogły być połączone z symbolami zdefiniowanymi gdzie indziej.

Każdy import w jakiś sposób rozszerza więc przestrzeń nazw danego modułu i zazwyczaj wszystko jest w porządku, dopóki dokładnie wiemy, jak to robi. Dlatego też powszechnie niezalecane są “dzikie” importy (wild imports), które nie wyliczają jawnie wszystkich dodawanych nazw, zwykle ukrywając je za gwiazdką (*). Ale nawet jeśli ich nie używamy, to nie oznacza to, że żadne problemy z importowanymi nazwami nas nie spotkają. Oto kilka innych potencjalnych źródeł kłopotów:

• Importowanie nazwy, która jest identyczna z jednym z symboli zdefiniowanych w tym samym pakiecie. Import będzie wtedy ją przesłaniał – ale oczywiście tylko wtedy, jeśli go rzeczywiście dodamy. A to nie jest takie pewne zwłaszcza w języku interpretowanym, gdzie nawet symbol o zupełnie innej semantyce może łatwo przejść niezauważony aż do momentu uruchomienia kodu z jego błędnym wystąpieniem. Możemy więc nieświadomie używać nazwy lokalnej tam, gdzie należałoby raczej zaimportować zewnętrzną – lub odwrotnie.
• Zaimportowane nazwy mogą być kwalifikowane lub nie, zależnie od języka i/lub sposobu importowania. I tak chociażby fraza import foo.bar.baz; wprowadza do przestrzeni modułu nazwę baz (czyli niekwalifikowaną) w przypadku Javy. W przypadku Pythona ten sam efekt wymaga z kolei instrukcji from foo.bar import baz, a zwykła instrukcja import da nam jedynie kwalifikowaną nazwę foo.bar.baz – która z kolei w Javie i C# jest dostępna bez żadnych importów, a w C++ po dodaniu dyrektywy #include… Całkiem intuicyjne, czyż nie? ;-) Skoro tak, to dodajmy do tego jeszcze fakt, iż…
• Nazwy importowane można w większości języków aliasować. Oznacza to, że wynikowa nazwa wprowadzona do przestrzeni może być zupełnie inna niż ta, która jest zdefiniowana w źródłowym module. Aliasowania używa się najczęściej do skracania prefiksów nazw kwalifikowanych i choć ułatwiają one ich wpisywanie, to w rezultacie ogólna czytelność kodu może się pogorszyć.
• W wielu językach importy mają zasięg. Przekłada się on potem na zasięg zaimportowanych nazw, którego ograniczenie jest często dobrym pomysłem. Sam import występujący poza początkiem pliku może jednak mieć niepożądane efekty – jak choćby załadowanie do pamięci importowanego modułu dopiero w momencie jego pierwszego użycia, co może wiązać się z potencjalnie dużym, chwilowym spadkiem wydajności.
• Jeśli nie jesteśmy uważni, możemy rozpropagować zaimportowane nazwy do kolejnych modułów, które bynajmniej wcale z nich nie korzystają. Chyba najbardziej znanym przykładem jest wstawianie deklaracji using w plikach nagłówkowych C++, ale to nie jedyny przypadek i nie jedyny język, w którym importy z jednego modułu mogą zaśmiecić przestrzeń nazw innego.

Podsumowując, importy – chociaż często zarządzane prawie całkowicie przez IDE – to w sumie dość poważna sprawa i warto zwrócić na nie uwagę przynajmniej od czasu do czasu.

Najboleśniejszy strzał w stopę

Znanych jest mnóstwo kruczków w języku C++, o których trzeba pamiętać, jeśli chcemy efektywnie w nim programować i nie tracić zbyt dużo czasu na odczytywanie niespecjalnie zrozumiałych komunikatów kompilatora czy - gorzej - drapanie się po głowie podczas debugowania naszego programu. O wielu z nich miałem okazję pisać, ale oczywiście ten temat-rzeka daleki jest od wyczerpania :) W jego nurcie wyróżnia się jednak jeden wybitnie złośliwy przypadek, który przez długi czas uważałem aczkolwiek za ciekawostkę, na którą w praktyce raczej nikt się nie natknie...
Rzecz jasna, myliłem się. Okazuje się, że okaz ten jak najbardziej występuje w rzeczywistym świecie. Nie objawia się wprawdzie zbyt często, ale dzięki temu jest jeszcze bardziej podstępny, posiadając tym większą siłę rażenia, gdy w końcu na kogoś trafi. Dobrze więc wiedzieć, co robić, aby się przed nim bronić :] I tym właśnie chciałbym się dzisiaj zająć.

Pewną pomocą jest tutaj fakt, iż opisywany błąd zdaje się zazwyczaj pojawiać w pewnym konkretnym scenariuszu. Jego wystąpienie w owym kontekście jest przy tym tak zaskakujące, że zetknięcie się z nim skutecznie "uodparnia" na wszelkie inne, podobne okoliczności w których problem może wystąpić. Rzeczony scenariusz jest przy tym bardzo typowy: chodzi o wczytanie zawartości pliku (otwartego jako strumień std::ifstream) do kolekcji albo zmiennej, na przykład łańcucha znaków typu std::string.
Są naturalnie tacy, co bawiliby się tutaj w bufor pomocniczy, pętlę i funkcję getline lub coś w tym guście. Programiści lubiący operować na nieco wyższym poziomie wiedzą jednak, że std::string możemy inicjalizować zakresem znaków określonym - jak każdy zakres w C++ - parą iteratorów. Trochę mniej znanym faktem jest z kolei to, że iterować można również po strumieniach. Mamy na przykład coś takiego jak std::istream_iterator, który potrafi automatycznie dekodować ze strumienia egzemplarze ustalonego typu danych:

Jeśli nam to nie odpowiada i wolimy dostęp do "surowych" bajtów, wtedy z pomocą przychodzi bardziej wewnętrzny std::istreambuf_iterator. To właśnie przy jego pomocy możemy szybko przejść po zawartości strumienia plikowego i umieścić ją w stringu:

Jak pewnie można się domyślić, zakres zdefiniowany przez te iteratory w obu przypadkach zaczyna się na początku strumienia. Kończy się zaś w miejscu, gdzie odczyt następnej porcji danych nie jest już możliwy. W naszym "rozwiązaniu" problemu wczytywania całego pliku będzie to więc koniec tego pliku, czyli to co nam chodzi.

Nieprzypadkowo jednak słowo 'rozwiązanie' ująłem w cudzysłów. Powyższe dwie instrukcje zawierają bowiem ów wyjątkowo perfidny błąd, o którym wspominałem na początku. Dość powiedzieć, że jeśli spowoduje on wygenerowanie przez kompilator bardzo tajemniczego komunikatu, będzie to lepszy z jego dwóch możliwych rezultatów. Drugim jest kompilacja zakończona powodzeniem i... kod, który robi dokładnie nic. Nie tylko nic nie wczytuje, ale nawet nie tworzy zmiennej typu string! To raczej zaskakujące, nieprawdaż? ;)

Jedna funkcja w wielu wersjach

Wytykanie niedoskonałości i różnego rodzaju felerów języka C++ to jedno z ulubionych zajęć niektórych programistów, zwłaszcza tych którzy z jakichś powodów muszą z tego języka korzystać. Sam czasami to robię, ale dzisiaj chcę zwrócić uwagę na to, co C++ robi dobrze - albo przynajmniej lepiej niż w wielu innych, popularnych językach. A chodzi tu o swobodę w definiowaniu wielu wersji tej samej funkcji, różniących się listą parametrów. Nazywa się to zwykle przeciążaniem, chociaż nie jest to jedyny sposób na osiągnięcie takiego efektu.

Innym są bowiem parametry domyślne i istnieje przynajmniej jeden język, w którym jest to sposób jedyny. Tak jest bowiem w Pythonie i nawet czasami ma to sens, biorąc pod uwagę brak deklarowanych typów w tym języku. Jednak równie często wymaga to czegoś w stylu samodzielnego rozstrzygania przeciążania już wewnątrz funkcji:

Powyższe ify to nic innego jak boilerplate code: redundantne, powtarzalne fragmenty kodu, które w dodatku robią tutaj to, co w innych językach spoczywa na barkach kompilatora. Usprawiedliwieniem może być pewnie to, że przecież Python nie jest kompilowany ;P

Ale jak wspomniałem wcześniej, język spod znaku węża posiada możliwość definiowania argumentów domyślnych, za co należy mu oddać honor. Niestety nie da się tego powiedzieć o kilku innych, popularnych dziś językach, jak choćby C# i Javie. Jeśli chcemy mieć w nich dwie sygnatury tej samej metody, musimy ją przeciążyć. Otrzymujemy wtedy dwie wersje (lub więcej), z których jedna - ta posiadająca mniej argumentów - jest po prostu wywołaniem drugiej. Widuje się to często w konstruktorach, z których czasem układa się swego rodzaju sztafeta wywołań:

Jak łatwo zauważyć, jest ona wybitnie rozwlekła, trudna w utrzymaniu i modyfikacji, a także mało czytelna, gdyż wartości domyślne argumentów są ukryte w wywołaniach zamiast w deklaracjach funkcji. Jej odpowiednik z argumentami domyślnymi byłby natomiast krótki, przejrzysty, zrozumiały i łatwy do ewentualnej zmiany.

"Problem" z tworzeniem wielu wersji funkcji polega właśnie na tym, iż mimo istnienia dwóch sposobów na osiągnięcie tego samego efektu, bardzo często jeden jest wyraźnie lepszy niż drugi. Stąd każdy język nieposiadający wsparcia dla któregoś z nich niejako z automatu kreuje sytuacje, dla których rozwiązania trzeba szukać na około.
I tu pozytywnie wyróżnia się C++, który pozwala na stosowanie obu technik (przeciążania lub argumentów domyślnych) w zależności od potrzeb. Również razem, jeśli rezultat nie powoduje niejednoznaczności w wywołaniach. Z pewnością jest to cenna cecha tego języka, równoważąca znaczącą część jego znanych niedostatków :)

Optymalizacja jest trudna

Często powtarzanym bon motem jest twierdzenie, iż przedwczesna optymalizacja (preemptive optimization) jest źródłem wszelkiego zła. Dużo w tym racji i równie dużo przesady. Jednak na pewno faktem jest, że pisanie wydajnych i efektywnych, czyli zoptymalizowanych ("przedwcześnie" lub poniewczasie) programów nie jest prostym zadaniem.
W celu łatwiejszej identyfikacji obszarów, w których można zastosować polepszające wydajność poprawki, możliwe rodzaje optymalizacji zwykle dzieli się na kilka rodzajów. Niektóre z nich są aplikowane przez kompilator i pozostają w dużym stopniu poza kontrolą programisty, który może co najwyżej unikać sytuacji blokujących możliwość ich zastosowania - jeśli w ogóle o nich wie. Pozostałe można pewnie zaklasyfikować na kilka sposobów, a podziałem stosowanym przeze mnie jest następujący:

• Optymalizacje projektowe, odnoszące się do wewnętrznej struktury całego projektu i polegające na bardziej efektywnym zorganizowaniu jego modułów, funkcji i klas. Chociaż nie jest to regułą, często oznacza to oddalenie się od uczenie nazywanej "dziedziny problemu" i przybliżenie się do szczegółów technicznych konkretnej platformy.
• Optymalizacje zbliżone do refaktoringu kodu, niezmieniające drastycznie jego architektury, ale modyfikujące kluczowe aspekty implementacji wpływające na wydajność. Prawie zawsze są one związane ze specyficznymi cechami używanego języka lub środowiska.
• Optymalizacje algorytmów, czyli modyfikacje ogólnych przepisów pod kątem konkretnych danych lub zastosowań albo całkowite wymiany jednych algorytmów na inne. Jak nietrudno się domyślić, takie zmiany są raczej niezależne od szczegółów technicznych implementacji, przynajmniej teoretycznie ;)
• Optymalizacje instrukcji, znane też jako mikrooptymalizacje, to po prostu inny sposób wykonywania elementarnych operacji. Być może najbardziej znanym rodzajem takiej poprawki jest używanie przesunięcia bitowego do obliczania potęg liczb całkowitych dla podstawy 2.

Kolejność na powyższej liście odpowiada głównie zakresowi, w jaki optymalizacje wpływają na kształt programu i jego kod. Dość powszechna jest aczkolwiek opinia, że zmiany o bardziej dalekosiężnych skutkach dają też wyraźniejsze efekty, co generalnie nie musi być prawdą. Wystarczy przypomnieć sobie znaną zasadę Pareto, która w tym przypadku oznacza, że 10/20% jest wykonywana przez 90/80% czasu, więc nawet drastyczne optymalizacje zastosowane wobec pozostałej jego części dadzą raczej nikły efekt.
Optymalizację dodatkowo komplikuje wiele innych spraw, jak choćby to, że:

• Niskopoziomowe optymalizacje instrukcji są w zasadzie niepraktyczne w wielu współczesnych językach. Im więcej warstw abstrakcji w rodzaju maszyn wirtualnych oddziela kod źródłowy od instrukcji procesora, tym trudniej określić, jak dana modyfikacja rzeczywiście wpłynie na wydajność i czy nie będzie to przypadkiem wpływ negatywny.
• Optymalizacje projektowe niemal z założenia są "przedwczesne" i wymagają rozważenia jeszcze przed napisaniem kodu programu - lub napisaniem go od nowa. Wymagają więc one doświadczenia i umiejętności przewidywania ich skutków - krótko mówiąc, zdolności prawie profetycznych ;)
• Stosowanie algorytmicznych optymalizacji jest z kolei obciążone ryzykiem potknięcia się o praktyczny aspekt teoretycznych miar takich jak złożoność obliczeniowa. Pamiętać trzeba choćby o tym, że notacja dużego O zakłada rozmiar danych rosnący do nieskończoności i nieważność stałych czynników, co w praktyce nie musi być rozsądnymi założeniami. Dodatkowo niespecjalnie pomaga tu fakt, że współczesne aplikacje są raczej asynchroniczne i interaktywne, więc nie zawierają znowu aż tak wiele algorytmów w klasycznym, proceduralnym, synchronicznym rozumieniu.

Po uwzględnieniu tych uwag wychodzi na to, że najbezpieczniejszym rodzajem optymalizacji jest ten, który polega na odpowiednim refaktoringu kodu - zwłaszcza, jeśli jest on uzasadniony przeprowadzonym uprzednio profilowaniem. Może się bowiem okazać, że najbanalniejsza zmiana, jak np. wydzielenie globalnego obiektu tworzonego w często wywoływanej funkcji, daje natychmiastowy i zauważalny efekt. A jest to efektem jedynie tego, iż optymalizacja była po prostu zastosowana we właściwym miejscu.

I na pewno nie była "przedwczesna" ;P

Typy wyliczeniowe w Pythonie

W Pythonie jest wiele konstrukcji językowych, które wydawać się mogą dziwne dla programistów przyzwyczajonych do innych języków. O kilku z nich już pisałem, a o paru innych pewnie zdarzy mi się jeszcze napomknąć. Dzisiaj jednak chcę wspomnieć o mechanizmie dobrze znanym z wielu innych języków, którego Python nie posiada w ogóle i jakoś sobie z tym brakiem radzi. Mam tu na myśli tytułowe typy wyliczeniowe, czyli enumy.

Jeśli zazwyczaj programujemy w językach kompilowanych ze ściśle kontrolowanymi typami, taki brak może się wydawać co najmniej irytujący. Wiemy oczywiście, że podobną funkcję może pełnić zestaw odpowiednich stałych, ale odpowiedniość nie jest zwykle dokładna - w Javie czy C# konstrukcja enum tworzy na przykład dodatkowy zasięg. Lecz nie jest to jedyna i prawdopodobnie też najważniejsza różnica.
Zdaje mi się raczej, że kluczową cechą typów wyliczeniowych jest to, że definiują one tylko pewien abstrakcyjny zbiór możliwości - bez konieczności ustalania, czym dokładnie jest każda z nich. Naturalnie wiadomo, że "pod spodem" są to po prostu liczby (aczkolwiek w Javie jest trochę inaczej), ale nie musimy się zastanawiać, skąd się one wzięły. Nie musimy nawet wiedzieć, do jakiego typu liczbowego one należą, choć niekiedy (np. w C#) możemy to doprecyzować.

Ta ostatnia cecha nie jest jednak niczym niezwykłym w języku o dynamicznym typowaniu, takim jak Python. Nieokreśloność typu dotyczy tu bowiem każdej zmiennej i dlatego nie za bardzo pasuje tu koncepcja ograniczania jej wartości do jakiegoś z góry ustalonego zbioru. Technicznie rzecz ujmując, nie bardzo też da się to zrobić.
Podobnie niezbyt pasującą do Pythona koncepcją jest sterowanie logiką za pomocą zbioru wariantów wziętych "znikąd", czyli stałych wyliczeniowych o automatycznie generowanych wartościach. Brak w tym języku instrukcji switch jest pewnie również konsekwencją odejścia od tego rodzaju abstrakcji. Założenie jest raczej takie, aby w miarę możliwości operować na surowych danych i nie dokonywać na nich żadnych pojęciowych "wygładzeń". Ma to sens, gdyż dwa podstawowe cele abstrahowania wartości na zbiór przypadków - upraszczanie API i zwiększanie efektywności - niespecjalnie aplikują się do Pythona.

Jak to jednak bywa w prawdziwym świecie, coś w rodzaju typów wyliczeniowych przydaje się czasami mimo wszystko. Odpowiedzią jest wtedy rzeczywiście zestaw stałych, zapewne zgrupowanych pod szyldem wspólnego zasięgu klasy. Ponieważ musimy nadać im wartości, możemy zadbać o to, by bezpośrednio odnosiły się do danych, które przetwarzamy. A jeśli w skrajnym przypadku trzeba faktycznie wziąć je z powietrza, wystarczy zastosować poniższy idiom z rozpakowywaniem range'a:

Istnieją oczywiście bardziej wyrafinowane rozwiązania, pozwalające chociażby na iterowanie po wszystkich nazwach i wartościach naszego enuma. Sądzę jednak, że podobna funkcjonalność jest przydatna raczej rzadko.