Wąskie szyjki od butelek

Kilka dni temu zajmowałem się optymalizacją szybkości aplikacji, która działa na platformie Google App Engine. Żeby dobrze podejść do tego zadania, zacząłem oczywiście od poszerzenia swojej wiedzy na temat zagadnienia, co obejmowało chociażby obejrzenie odpowiedniej prezentacji z zeszłorocznego Google I/O. Przedstawiono tam odpowiednie narzędzie służące do profilowania (Appstats), czyli niezbędnego etapu przygotowawczego (o czym mam nadzieję wszyscy pamiętają ;]). Dodatkowo dowiedziałem się też o najważniejszych źródłach opóźnień w tego rodzaju aplikacjach – i to okazało się dość zaskakujące.

Ogólny wniosek, jaki zdołałem stamtąd wyciągnąć, dotyczy właśnie prawidłowego wykrywania wąskich gardeł (zwanych bottlenecks – tytułowe szyjki od butelek). W przypadku wspomnianej aplikacji okazało się na przykład, że nawet stosunkowo skomplikowana logika (przetwarzanie sporych porcji danych w JSON-ie, renderowanie długich szablonów HTML, itd.) napisana całkowicie w wysokiego poziomu języku interpretowanym (Python) relatywnie zajmuje dosłownie chwilę. Nieporównywalnie dłuższy czas związany jest z dowolnym wywołaniem API platformy, bo każde z nich wymaga sieciowej wycieczki do osobnego serwera, który może je obsłużyć. To zaś sprawia, że wszelkie próby optymalizacji samych algorytmów (nawet potworków rzędu czy ) nie mają sensu, jeśli nie wiąże się to ze zmniejszeniem ilości wspomnianych wywołań, czyli np. dostępu do magazynu danych.

Podobne pozornie zaskakujące wnioski można wyciągnąć, gdy przyjrzymy się wewnętrznej strukturze innych platform. Bardzo dobrym przykładem jest chociażby diagram opóźnień I/O w komputerach PC. Łatwo na nim zauważyć, w których miejscach należy jak najbardziej ograniczyć ruch danych, aby uzyskać odpowiedni wzrost wydajności. Przy takim spojrzeniu na aplikacje, podejście znane jako DOD (Data Oriented Design) nabiera też nieco więcej sensu ;-)

Stosu przepełnienie

Większość programistów zna (albo powinna znać) serwis Stack Overflow. Dla niezorientowanych wyjaśniam, że jest to specyficznego rodzaju forum dyskusyjne dla koderów, nastawione przede wszystkim na zadawanie pytań i udzielanie na nie odpowiedzi. Ze względu na swoje rozmiary mierzone liczbą zgromadzonej wiedzy, stanowi ono też doskonałe źródło szybkiej informacji w tych częstych przypadkach, gdy potrzebujemy prostego rozwiązania jakiegoś niezbyt skomplikowanego problemu.
Oprócz bycia nieocenioną pomocą w pracy programisty, SO jest też ciekawym przypadkiem sprawnie działającej społeczności, na straży której nie stoją całe zastępy moderatorów. Zamiast tego to sami użytkownicy – za pomocą sukcesywnie zdobywanych przywilejów, takich jak edycja czy tagowanie pytań – wcielają w życie zasady dyskusji. Podobno fachowo idea ta nazywa się crowdsourcingiem; możemy dołączyć to słówko do pokaźnej już liczby dziwnych pojęć spod znaku Web 2.0 :)

Centralnym mechanizmem, wokół którego kręci się światek Stack Overflow (oraz niezliczonych innych stron opartych na tym samym silniku) jest reputacja poszczególnych użytkowników. To zwykły numer, w swoim znaczeniu podejrzanie podobny do tzw. karmy, nad której obecnością na forum Warsztatu raz się nawet nieco rozpisałem. Reputacja jest zwiększana między innymi wtedy, gdy nasze pytania lub odpowiedzi zostaną poparte (upvote) przez innych użytkowników. To nam daje punkty, które w większej ilości przekładają się na przywileje quasi-moderatorskie. W sumie jest to więc klasyczny przykład sprzężenia zwrotnego dodatniego (positive feedback loop), występującego w świecie w najprzeróżniejszych formach – od giełdy po FarmVille.

Jak w każdym takim systemie, także i tutaj wszystkie trybiki nie zawsze jednak działają idealnie. Ponieważ reputacja w serwisie SO jest dobrem mającym wartość także poza nim, nie dziwi duża chęć do jej zwiększania, występująca u wielu użytkowników. Nie jest to wbrew pozorom nic trudnego – nawet mimo obecności licznych ekspertów z niemal każdej poddziedziny związanej z programowaniem, którzy weryfikują i oceniają udzielane odpowiedzi.
Jest tak z prostej przyczyny: w serwisie pojawia się całe mnóstwo pytań trywialnych, na które bez problemu odpowie każda średnio zaawansowana w danym temacie osoba. Ze względu na ilość użytkowników (ponad 700 tysięcy) fakt ten generuje dość komiczne sytuacje, gdy w przeciągu mniej niż minuty pojawiają się trzy albo cztery niemal dokładnie identyczne odpowiedzi. Zabawa czasami zamienia się więc raczej w konkurs szybkiego pisania na klawiaturze :)

Mimo tych wad muszę stwierdzić, że uczestnictwo w dyskusjach na SO jest w ogólnym rozrachunku bez wątpienia pożyteczne. Wymierną osobistą korzyścią jest oczywiście sama reputacja, przeliczalna rozmiar ego po bardzo korzystnym kursie ;] Ważniejsza jest aczkolwiek możliwość utrwalania i poszerzania swojej wiedzy w wybranych działkach koderskiej działalności.

Kwitnące zbiory

Przedstawię dzisiaj interesującą strukturę danych, będącą pewnego rodzaju uogólnieniem lub modyfikacją kontenerów typu bitset. Nazywa się ona filtrem Blooma (Bloom filter) i stanowi przykład struktury probabilistycznej, czyli działającej… czasami ;) Nie niweluje to aczkolwiek w żaden sposób jej przydatności, o czym zresztą opowiem dalej.

Filtr Blooma to tablica bitowa, w której przechowujemy pewien zbiór. Liczba owych bitów – i to jest pierwsza różnica w stosunku do bitsetu – nie jest równa liczbie wszystkich możliwych elementów zbioru. Wręcz przeciwnie, zwykle jest ona znacznie, znacznie mniejsza.
Drugą różnicą jest reprezentacja elementu, która dla odmiany zajmuje więcej miejsca. Definiuje je określona z góry liczba bitów, rozrzuconych po całej tablicy i ustawionych na 1. Sposób owego rozmieszczenia jest określony przez zestaw funkcji haszujących, przyjmujących element zbioru jako swój argument i zwracających indeks jednej z pozycji w tablicy. Owych funkcji jest zaś tyle, ile bitów reprezentacji.

Poglądowe przedstawienie filtru Blooma

Jak wyglądają operacje na tak zaimplementowanych zbiorze? Sprawdzenie przynależności jest proste, bo sprowadza się do obliczenia wartości wszystkich funkcji haszujących dla danego elementu i upewnieniu się, że na zwróconych przez nie pozycjach tablicy jest zapisana jedynka. Dodawanie, jak można się domyślić, polega na ustawieniu tychże jedynek. A co wobec tego z usuwaniem elementu?
Otóż usuwania… nie ma :) Jest to zamierzony efekt, konsekwencja założeń które czynią filtr Blooma strukturą probabilistyczną. Dopuszcza ona mianowicie fałszywe pozytywy. Są to przypadki, w których filtr odpowiada pozytywnie na pytanie o przynależność elementu, gdy w rzeczywistości element ten do zbioru nie należy. Jest to jednak jedyny rodzaj dopuszczalnych błędów. Wykluczone są w szczególności sytuacje odwrotne: gdy element jest w zbiorze, ale filtr odpowiada coś przeciwnego (byłby to z kolei fałszywy negatyw). Usuwanie – polegające na wyzerowaniu odpowiednich bitów – mogłoby jednak do dopuścić do takiej sytuacji. Wynika to z faktu, że każdy z bitów w tablicy odpowiada za przechowywanie więcej niż jednego elementu.

Przypuszczam, że wobec powyższych cech filtrów Blooma pojawiają się dwa pytania, z których jedno dotyczy częstotliwości pojawiania się fałszywych pozytywów. Zależy to oczywiście od rozmiaru tablicy (m), liczby funkcji haszujących (k), a także liczby elementów będących aktualnie w zbiorze (n). Ogólny wzór jest, jak widać, raczej nieoczywisty ;)
Dlatego pozwolę sobie raczej przejść do drugiego pytania: o zastosowania. Te są całkiem rozliczne – dotyczą chociażby przyspieszania dostępu do dużych kolekcji danych. Jeśli koszt wczytania danych odpowiadających danemu kluczowi jest spory (bo wymaga np. odczytu z dysku lub sieci), wówczas utrzymywanie w pamięci filtru Blooma może znacząco polepszyć efektywność poprzez szybkie odrzucanie zapytań o nieistniejące klucze. Oczywiście filtr będzie czasami się mylił, ale jego użycie i tak pozwoli ograniczyć liczbę drogich odwołań co najmniej o rząd wielkości.

Przykładową implementację filtru Blooma – wykorzystującą do haszowania generator liczb pseudolosowych – można zobaczyć choćby tutaj.

Recykling nazw w kodzie

W dziedzinie optymalizacji kodu pojawia się często pojęcie aliasowania. Z grubsza polega ono na tym, że jakaś komórka pamięci (lub bardziej ogólnie: zmienna) może być dostępna pod więcej niż jedną “nazwą” czyli np. wskaźnikiem lub referencją. Taka sytuacja sprawia, że kompilator ma mniejsze pole manewru w zakresie optymalizacji dostępu do niej. Typową konsekwencją jest konieczność ponownego odczytywania wartości tej komórki zamiast posłużenia się cache‘owanym rezultatem zapisanym w jednym z rejestrów procesora.
Aliasing w większym lub mniejszym stopniu dotyczy właściwie wszystkich języków kompilowanych. Jest on jednak brany pod uwagę głównie tam, gdzie jego wpływ na wydajność jest największy, tj. w kodzie kompilowanym bezpośrednio do instrukcji maszynowych konkretnego sprzętu. Kod w C i C++ to najważniejszy przykład tego rodzaju.

Niejako na przeciwnym biegunie – zwłaszcza pod względem liczby warstw abstrakcji pod spodem – sytuują się języki interpretowane z dynamicznym typowaniem. Javascript i Python są tutaj typowymi reprezentantami. W nich problem “aliasowania” przybiera według mnie formę dokładnie odwrotną i nie dotyczy już kwestii wydajnościowych – z których wspomniane języki przecież nie słyną :) Przeciwnie: ów symetryczny problem jest związany z ich wyróżniającą zaletą: prostotą i czytelnością kodu.
O jaki więc rodzaj aliasowania chodzi? Ano taki, który polega na używaniu jednej nazwy do wielu różnych wartości. Przy czym ‘nazwę’ rozumiem tu w sensie stricte programistycznym, obejmującym także jej zasięg i uwzględniającym wszystkie dodatkowe cechy tego pojęcia – jak choćby przesłanianie (name shadowing).
Od razu zastrzegam jednak, żeby nie rozumieć tego zbyt dosłownie. W tym sensie chociażby poniższa pętla:
for (int i = 0; i < 10; ++i) { /* ... */ }[/cpp] nie stanowi odpowiedniego przykładu mimo tego, iż zmienna i jest tutaj używana do “nazwania” aż dziesięciu formalnie różnych wartości (). Koncepcyjnie każda z nich jest bowiem tym samym, tj. wartością licznika pętli w danej iteracji.

Wątpliwej słuszności jest dopiero praktyka recyklingu tych samych nazw do różnych celów. Jest tu oczywiście spory margines niepewności jeśli chodzi o definicję słowa ‘różny’. Być może dla niektórych osób coś podobnego do poniższego kodu jest już po złej stronie granicy między akceptowalną a niedobrą praktyką:

Inni z kolei mogą nie widzieć nic złego w użyciu jednej zmiennej (np. node) do przekopania się przez pięciokrotnie zagnieżdżoną strukturę XML-a czy JSON-a. Wypada tylko mieć nadzieję, że osoba utrzymująca potem taki kod będzie prezentowała podobny poziom wrażliwości ;-)

Nietrudno zauważyć, że wielokrotne używanie tych samych nazw do różnych celów jest zupełnie możliwe także w językach kompilowanych ze statycznym typowaniem. Dynamiczne typowanie zapewnia jednak o wiele większą “zachętę” do takich praktyk, pozwalając chociażby na takie oto smaczki:

Czy mieszczą się one w kategorii prostoty i czytelności, każdy pewnie oceni indywidualnie. Nie da się jednak ukryć, że kryją one w sobie wielki potencjał zarówno upraszczania, jak i zaciemniania kodu. To wielka moc, z którą naturalnie jest związana wielka odpowiedzialność :)

Podstawy autouzupełniania

Część bywalców kanału #warsztat może wiedzieć, że od jakiegoś czasu w wolnych chwilach rozwijam pewien niewielki projekt. Jest to prosty IRC-owy bot, który potrafi wykonywać różne predefiniowane czynności, dostępne za pomocą komend rozpoczynających się od kropki. Wśród nich mamy między innymi wysyłanie zapytań do wyszukiwarki Google, wyświetlanie skrótów artykułów z Wikipedii, przekazywanie wiadomości między użytkownikami i jeszcze kilka innych. W sumie jest ich już około kilkanaście, więc pomyślałem, że dobrym rozwiązaniem byłby wbudowany system pomocy oraz podpowiedzi opartych na “domyślaniu się”, jakie polecenie użytkownik chciał wydać.
Brzmi to może nieco zagadkowo, ale w gruncie rzeczy chodzi o zwykłe autouzupełnianie (autocompletion), do którego jesteśmy przyzwyczajeni w wielu innych miejscach – takich jak środowiska programistyczne czy choćby wyszukiwarki internetowe. Oczywiście tutaj mówimy o nawet miliardy razy mniejszej skali całego rozwiązania, ale ogólna zasada we wszystkich przypadkach jest – jak sądzę – bardzo podobna.

Cały mechanizm opiera się właściwie o jedną strukturę danych zwaną drzewem prefiksowym (prefix tree). Jest to całkiem pomysłowa konstrukcja, w której każde dopuszczalne słowo (zwane tradycyjnie w takich drzewach kluczem) wyznacza pewną ścieżkę od korzenia drzewa. Kolejne krawędzie etykietowane są tu znakami słowa.
Najważniejszą cechą drzewa prefiksowego jest jednak to, że wspomniane ścieżki mogą się nakładać, jeśli początkowe części danych słów się pokrywają. Stąd zresztą bierze się nazwa struktury, gdyż pozwala ona szybko znaleźć ciągi zaczynające się od podanego tekstu – czyli właśnie prefiksu.

O kompatybilności wprzód i jej dziwactwach

Oto proste zadanie. Proszę sobie przypomnieć dowolną funkcję z dowolnej platformy/biblioteki/frameworka/itp. posiadającą przynajmniej jeden parametr, który nigdy nie został przez nas użyty w żadnym jej wywołaniu. Idealnie by było, gdyby ów argument występował na innej pozycji niż ostatnia – tak, żeby jego pominięcie wymagało podania zera, NULL-a, nulla, nila, Nila, None-a, pustego napisu/tablicy/listy lub dowolnej innej, “neutralnej” wartości.
Jeżeli udało nam się uporać z tą łamigłówką, to mam kolejną w postaci prostego pytania: dlaczego takie funkcje w ogóle istnieją? Zadając to pytanie na głos, często doczekamy się odpowiedzi, które niewiele mają wspólnego z prawdą. Bo istnieją rzadkie sytuacje, gdy ów felerny parametr jednak się przydaje. Bo nie ma innego dobrego miejsca, gdzie można by go umieścić. Bo język programowania jest kiepski i tak już musi być. Bo w sumie co to za kłopot z tym jednym nullem więcej. Bo.. bo… – i tak dalej.

W rzeczywistości prawidłową odpowiedzią jest zazwyczaj brzydkie słowo na ‘k’, czyli kompatybilność :) Pół biedy, jeśli chodzi tutaj o kompatybilność wsteczną – ona jest codziennością co bardziej złożonych aplikacji i systemów oraz wszelkich bibliotek, które mają swoją własną historię. Nie da się jej uniknąć i zwykle nawet nie warto próbować, chociaż oczywiście okresowe jej porzucanie jest w gruncie rzeczy wskazane.
Jest jednak jeszcze kompatybilność wprzód. Dziwna to idea, mająca na celu przewidywanie przyszłych wymagań wobec systemu i ułatwiająca lub wręcz umożliwiająca sprostanie im. Należy więc ona do dziedzin z pogranicza prorokowania i prognoz pogody, zatem z miejsca wydaje się cokolwiek podejrzana. Co więcej, potrafi się ona wkraść do projektu tak podstępnie i niezauważenie, że nie musi być nawet świadomie stosowana, by zostawić w nim swoje ślady. Ślady zupełnie niepożądane, o czym jednak przekonujemy się zwykle dopiero dużo później.

Mniej więcej coś takiego zdarzyło mi się ostatnio podczas tworzenia wersji androidowej swojej gry sprzed paru lat, czyli Taphoo. Sprawa dotyczy formatu niewielkich (<1 kB) plików, w którym obie wersje przechowują poszczególne etapy gry. Nie należy on w żadnym razie do przesadnie skomplikowanych, gdyż jest prostym formatem binarnym, składającym się z trzech części:

• stałego nagłówka o rozmiarze dwóch bajtów, równego zawsze 54 4C (w ASCII są to znaki TL, będące skrótem od Taphoo Level)
• wymiarów etapu: szerokości i wysokości, zapisanych na dwóch bajtach każda
• właściwej planszy, której każda komórka zajmuje dokładnie jeden bajt

Format etapów w Taphoo

Oryginalnie format ten służył jedynie windowsowej wersji gry, ale nie widziałem żadnych powodów, dla których nie mógłbym użyć go także w powstającym porcie na platformę Android. Z pewnością znaczącym czynnikiem było to, że razem z pierwotną wersją gry napisałem też do niej – nie chwaląc się – bardzo dobry edytor :) Rozsądne było więc, aby przepisać kod wczytujący poziomy na Javę i włączyć go do gry w wersji androidowej.
Intuicja każe przypuszczać, że wtedy właśnie pojawiły się kłopoty. Faktycznie tak było. W związku mam jeszcze jedną, ostatnią dzisiaj zagadkę, która powinna być stosunkowo łatwa do rozwiązania na podstawie informacji podanych wcześniej. Co mianowicie jest przykładem niepotrzebnej kompatybilności wprzód w opisanym wyżej formacie i jakie problemy może to stwarzać podczas portowania?…

Terminologia rozproszonych systemów kontroli wersji

W ostatnich latach rozproszone systemy kontroli wersji (w skrócie DVCS) stały się popularne, zwłaszcza w środowiskach związanych z open source. Warto je jednak znać nie tylko wtedy, gdy pracujemy nad projektami z otwartym źródłem. Jak bowiem pisałem wcześniej, mogą być one przydatne chociażby do małych jednoosobowych projektów. Ponadto bywają nierzadko używane w większych oraz mniejszych firmach. Ogólnie mamy więc duże szanse, aby prędzej lub później zetknąć się z takimi systemami.
Ten post jest adresowany przede wszystkim do osób, które nie miały wcześniej dłuższej styczności rozproszonymi systemami kontroli wersji. Ma on na celu wyjaśnienie wielu spośród tych tajemniczo brzmiących słówek, na jakie nieustannie można się natknąć, gdy pracujemy z DVCS-ami. Istnieje oczywiście szansa, że bardziej zaawansowani użytkownicy również wyciągną nowe wiadomości z lektury (albo chociaż przejrzenia) niniejszej notki. A jeśli nawet nie, to powtórzenie znanej sobie wiedzy na pewno im nie zaszkodzi ;)