HTML nr 5 – książka

Właśnie skończyłem lekturę książki Wprowadzenie do HTML5 autorstwa Bruce’a Lawsona i Remy’ego Sharpa, wydanej w wersji polskiej przez Helion. Zakupiłem ją z nadzieją, że wprowadzi nieco porządku w cały ten buzz odnośnie HTML5, którego trudno nie zauważyć, jeśli tylko robi się cokolwiek chociaż pośrednio związanego z tą tematyką. I od razu mogę stwierdzić, że pod tym względem moje oczekiwania zostały rzeczywiście spełnione.

W książce można bowiem znaleźć przegląd kilku elementów składających się na standard HTML5 oraz paru technologii pobocznych, które formalnie do standardu nie należą, ale często są uwzględniane pod parasolem szerszej definicji całego zjawiska/technologii/ruchu/trendu/czegokolwiek-czym-to-jest. Wśród nich mamy takie podstawy jak nowe elementy strukturalne, nowe i przedefiniowane znaczniki opisu tekstu, poszerzone możliwości formularzy i różne drobne usprawnienia składniowo-semantyczne. Nie są one może tak ekscytujące jak “gwiazdy” technologii HTML5, ale fakt ich porządnego uwzględnienia jest według mnie tym bardziej godny uwagi.
Oczywiście nie zabrakło też wielu “nowych wspaniałych API”, dzięki którym możemy chociażby tworzyć SQL-owe bazy danych po stronie klienta i wykonywać szereg innych niezbędnych a właściwych dla stron WWW czynności ;D I tak możemy na przykład dowiedzieć się, co to właściwie jest ten Canvas, w jaki sposób zapewnić wsparcie dla techniki drag & drop i do czego w zasadzie mogą przydać się te całe webowe gniazdka (czyli Web Sockets). Ponieważ wszystko pokazane jest na prostych przykładach, opanowanie podstaw każdego z tych rozwiązań dla ogarniętego programisty nie stanowi żadnego problemu.

Kluczowym słówkiem są tu jednak owe ‘podstawy’. Chociaż różne tematy są tu opisane z różnym poziomem szczegółowości – czasem nawet zbyt dużym, jak choćby w przypadku <audio>/<video> – to jednak w żaden nie jest opisany wyczerpująco. Nie wskazuję tego jako wady, bo przecież mówimy o książce z wyraźnym napisem “wprowadzenie” na okładce. Poza tym w prawie każdym miejscu, gdzie autorzy świadomie coś pomijają, podawane są inne (zwykle internetowe) źródła, z których można czerpać bardziej szczegółowe informacje. Trzeba też powiedzieć szczerze, że właściwie żaden z opisywanych tematów (może poza Canvasem) osobno nie prezentuje się jako specjalnie skomplikowany bądź obszerny. Skondensowane wprowadzenie może więc równie dobrze być całkowicie wystarczające.

Podsumowując więc: lektura okazała się jak najbardziej pożyteczna. Książkę czyta się szybko i bez wielkiego wysiłku, a jednocześnie można się z niej dowiedzieć wielu interesujących rzeczy. Jeśli nawet nie zamierzamy – za przeproszeniem – programować w HTML5, to przeczytanie tej książki da nam ciekawy wgląd w technologie będące podobno przyszłością Internetu czy nawet aplikacji jako takich.

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.

Mniej CSS-a

Ktokolwiek, kto pisał dłuższy lub bardziej skomplikowany arkusz stylów CSS, wie jakim bólem siedzenia potrafi to być. Nie chodzi tu nawet o same style, których interakcje między sobą oraz z zawierającymi je selektorami mogą czasem być cokolwiek zagadkowe (tak, marginy i paddingi – o was mówię). Rzecz w tym, że sam język CSS jest po prostu biedny – nie tyle w zakresie możliwości (w końcu jest zupełny w sensie Turinga), co wygody użytkowania. Brakuje mu chociażby kilku kluczowych konstrukcji, jakich można by się spodziewać. Dobrym przykładem są stałe (zmienne) i możliwość wykonywania na nich operacji arytmetycznych – choćby w celu policzenia zależnych od siebie marginesów.

Z tą bolączką można sobie oczywiście radzić we własnym zakresie, podłączając na przykład arkusze CSS pod system szablonów normalnie używany do generowania stron HTML na poziomie serwera. Nie wydaje się to jednak najlepszym możliwym sposobem na zużywanie jego zasobów. Istnieją też na pewno bardziej interesujące rzeczy, które mógłby zrobić programista w czasie, gdy będzie takie (z natury raczej specyficzne) rozwiązanie implementował.

I tutaj pojawia się bardzo ciekawy projekt o nazwie LESS, rozszerzający składnię CSS-a o wiele przydatnych elementów, jakich domyślnie w nim nie uświadczymy. Najfajniejsze jest przy tym to, że trik ten odbywa się po stronie klienta przy pomocy odpowiedniego skryptu JavaScript. Możemy więc korzystać z niego niezależnie od backendu naszego serwera czy nawet w ogóle bez serwera, tj. do stron bez dynamicznie generowanej treści. Integracja jest zaś bardzo prosta: sprowadza się do dodania jednego znacznika <script> (oczywiście) oraz lekkiej modyfikacji referencji do arkuszy stylów, czyli znaczników <link rel="stylesheet">.

Co dostajemy w zamian? Oprócz wspomnianych na początku zmiennych i operacji na nich, mamy też w LESS-ie “funkcje” (czy raczej makra) z parametrami. Pozwala to chociażby na łatwiejsze dostarczanie stylów specyficznych dla przeglądarek. Możliwe jest też np. importowanie kodu z innych arkuszy LESS, zagnieżdżanie selektorów oraz… wstawianie komentarzy w stylu C++ :)
Powyższe wyliczenie dodatków nie brzmi może bardzo imponująco, lecz nie jest to wcale dziwne. Tak naprawdę sam CSS już dawno powinien oferować tego rodzaju możliwości. Wiemy jednak, jak jest w rzeczywistości. Sądzę więc, że tym bardziej warto jest używać rozwiązania, które zamienia CSS w coś, czego można w końcu normalnie używać :)

Prezentacja nt. Google App Engine

W zeszły piątek wziąłem udział w kolejnym evencie organizowanym przez warszawski oddział polskiej Grupy Użytkowników Technologii (w skrócie GTUG). Nie było to ponadto uczestnictwo pasywne. Wspólnie z kolegą z pracy wygłosiłem tam bowiem półtoragodzinną prezentację na temat technologii Google App Engine, czyli platformy do tworzenia aplikacji sieciowych, działającej w oparciu o ideę cloud computing.
Nosiła ona jakże pogodny tytuł Rozchmurz się! i przedstawiała całą platformę właściwie od podstaw, ale jednocześnie w jak najszerszym przekroju. Dodatkowo nie obyło się oczywiście bez kilku odniesień do osobistych doświadczeń z jej użytkowania. Ogólnie wydaje mi się, że mimo wyraźnie wieczorowej pory udało nam się nie uśpić publiczności całkowicie ;-)

Zamieszczam poniżej slajdy z prezentacji. Na stronie GTUG można natomiast obejrzeć galerię zdjęć z całego wydarzenia. Na dniach powinien również pojawić się filmik.

  Rozchmurz sie! -- Cloud computing z Google App Engine [PL] (805.8 KiB, 2,231 downloads)

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ść :)