Lis w operze

Parę dni temu odbyła się premiera nowej wersji przeglądarki Opera, oznaczonej numerkiem 9.5. Z kolei jutro z wielką pompą opublikowana zostanie trzecia edycja Firefoksa. Przy tej zresztą okazji Mozilla organizuje Dzień Pobierania, z zamiarem ustanowienia rekordu ilości ściągnięć oprogramowania w ciągu jednej doby. (Mam aczkolwiek przeczucie, że prawdopodobne jest ustanowienie innego rekordu: najdłużej niedziałającego serwera pobierania ;]).
Zbieżność tych dwóch wydarzeń zapewne nie jest przypadkowa. Tym bardziej dziwi mnie to, że przy tej okazji zaprzysięgli fani któregoś z tych dwóch programów zajmują się głównie wykazywaniem w każdym możliwym miejscu, iż to właśnie ich ulubiona przeglądarka jest lepsza od tej drugiej. Naturalnie, argumentów jest przy tym mnóstwo: a to gesty myszki, a to współdzielenie zakładek i Ulubionych między komputerami, nie wspominając o tysiącach dostępnych rozszerzeń i wtyczek, coraz lepszych wynikach testów typu Acid3, wbudowanych klientach innych usług niż WWW, kilogramach skórek i pewnie wielu jeszcze innych zaletach. Część z nich może i jest ważna i interesująca. Rzecz w tym, że – statystycznie rzecz biorąc – nie obchodzą one psa z kulawą nogą.

Smutna prawda jest taka, że nadal większość użytkowników Internetu korzysta z “jedynie słusznej” przeglądarki pewnej znanej skądinąd firmy, a o dywagacjach na temat wyższości innych nad jeszcze innymi nigdy tak naprawdę nie słyszeli i raczej nie mają zamiaru usłyszeć. A to z wielu powodów niepokojące, chociażby ze względu na bezpieczeństwo czy powszechność stosowania standardów sieciowych. Wzajemne zwalczanie się zwolenników przeglądarek “niezależnych” (że je tak umownie nazwę…) na pewno nie zaradzi temu, iż połowa internautów wciąż używa do przeglądania Sieci programów przestarzałych i dziurawych jak ser szwajcarski.
A bliskość premier nowych edycji dwóch bezpiecznych, wygodnych i nowoczesnych przeglądarek to przecież całkiem dobra okazja, żeby coś na to poradzić. Zamiast więc bezowocnie spierać się, czy Safari jest lepsze od Opery, a ta od Firefoksa czy Camino, można by wspólnie zwiększyć wysiłki na rzecz uświadamiania użytkownikom niesłusznie najpopularniejszych przeglądarek, że istnieją dla nich o wiele lepsze alternatywy. Cóż bowiem z tego, że oto “wszyscy” przerzucą się czy na to Firefoksa, Operę czy inny tego typu program, jeśli ci ‘wszyscy’ to tak naprawdę ledwie 1/3 internautów?…

Stos wywołań funkcji

Jedną z bardziej przydatnych informacji podczas znajdowania przyczyn błędów wykonania jest śledzenie stosu (stack trace; właściwie to nie ma dobrego polskiego tłumaczenia, jak zwykle zresztą :]). Dzięki niemu możemy mieć informacje o kolejnych wywołaniach funkcji, które doprowadziły błędu wykonania. Zwykle stack trace jest dostępny z poziomu złapanego obiektu wyjątku – np. poprzez właściwość System.Exception.StackTrace w .NET czy metody java.lang.Throwable.get/printStackTrace w Javie.

Standardowa klasa exception w C++ nie posiada podobnej funkcjonalności, bo w tym języku stos nie jest automatycznie śledzony. Przy pewnym wysiłku możemy aczkolwiek zapewnić sobie podobną funkcjonalność – chociażby tak:

Przechowujemy po prostu globalną listę z danymi wszystkich wywoływanych funkcji. Elementy do niej dodawane są przy wejściu w każdą funkcję, która na początku ma makro GUARD:

zaś zdejmowane wtedy, gdy pomocniczy obiekt typu Trace wyjdzie poza swój lokalny zasięg – czyli po opuszczeniu funkcji. To sprawia, że na liście mamy zawsze informacje o wszystkich wywołaniach funkcji prowadzących do aktualnego miejsca (jakie one są, zależy od kompilatora; użyte wyżej makro __FUNCTION__ nie jest na przykład standardową częścią C++). Tworząc obiekt wyjątku, możemy więc zapisać kopię tej listy, by można ją było odczytać w bloku catch i wyświetlić.
Rozwiązanie nie jest oczywiście bardzo ładne, bo wymaga dodatkowej linijki w każdej funkcji. Zdaje się jednak, że nie ma żadnego sposobu, by tę niedogodność wyeliminować. Ja przynajmniej takiego nie znam :)

Kontenery haszujące w Visual C++

W standardowej bibliotece pojemników (STL) języka C++ jest póki co poważny brak. Nie ma mianowicie kontenerów opierających się na mechanizmie haszowania (hashing), znanego też pod mniej jednoznaczną nazwą mieszania. Mówiąc zupełnie najprościej, takie pojemniki są pewnym uogólnieniem zwykłych tablic, które nie są jednak indeksowane liczbami całkowitymi, a kluczami dowolnego typu. Klucze te są jednak wpierw przepuszczane przez pewną funkcję (funkcję haszującą) i dopiero wynik używany jest do znalezienia wartości, z którą ów klucz jest związany. Istnieje też kilka metod rozwiązywania problemu kolizji, gdy kilka kluczy zostanie odwzorowanych na to samo miejsce w tablicy.
Zaletą haszowania jest szybkość: średnio dostęp do wartości związanej z danym kluczem jest wykonywanym w czasie stałym. Tak, stałym, czyli O(1). Jakkolwiek można być pesymistą i przewidywać, że przy odpowiednio złośliwym doborze kluczy czas ten urośnie do liniowego (O(n), ale w praktyce tablice haszujące zachowują się świetnie. No a to jest przecież najważniejsze :)

W STL nie ma jednak kontenerów używających haszowania. Mimo to wiele kompilatorów oferuje je we własnym zakresie. I tak nasz ulubiony Visual C++ udostępnia dwa “półstandardowe” nagłówki: hash_set i hash_map. Zawierają one klasy (multi)map oraz (multi)zbiorów, z wierzchu wyglądających właściwie identycznie jak zwykłe mapy i zbiory (std::map i std::set) z STL. Klasy te nazywają się hash_set, hash_map, itp., i celem zachowania zgodności ze standardem C++ umieszczone są nie w przestrzeni std, lecz stdext.

O istnieniu tych klas warto pamiętać, gdy tworzymy kod kluczowy pod względem wydajności. W programowaniu gier często są to na przykład przeróżne menedżery zasobów, które odwzorowują pewne identyfikatory (np. łańcuchy znaków) na obiekty w rodzaju modeli, tekstur, próbek dźwiękowych, itd. Szybkość działania przechowujących je pojemników może być ważna i warto poszukać alternatyw dla standardowej klasy map (która przecież teoretycznie “wyciąga” tylko O(logn) dla wyszukiwania). Jeśli przy okazji martwimy się przenośnością na inne kompilatory niż VC++ lub zgodnością ze standardem, to możemy spróbować przełączania między zwykłymi a haszującymi pojemnikami, np. tak:

Naturalnie ‘kod niezależny od kontenera’ to dość często utopia, ale przy korzystaniu tylko z prostych operacji typu wstawianie-usuwanie-wyszukiwanie nie powinniśmy napotkać większych problemów.

Triki z PowerShellem #4 – DirectX

Jakiś czas temu pokazałem, że w PowerShellu można zrobić rzeczy, które są – jak na konsolkę tekstową – co najmniej niespotykane. Przedstawiłem na przykład sposób na wyświetlenie zwykłego windowsowego okienka. Nie było ono aczkolwiek zbyt interesujące, jako że w środku było zupełnie puste – chociaż, oczywiście, Aero robił co mógł, by wyglądało ono na atrakcyjniejsze niż było w rzeczywistości ;)
Jako że zajmowania się rzeczami zupełnie nieprzydatnymi nigdy dość, postanowiłem więc pewnego razu spróbować wnieść w stworzoną formę nieco więcej życia. Efekty okazały się raczej ciekawe, przedstawiając się następująco:

Tak, to jest trójkąt. Tak, on się obraca. Tak, na pasku tytułowym okna jest napisane Direct3D… Wszystkie te trzy fakty nie są żadnym zbiegiem okoliczności :) Za wszystko odpowiedzialny jest ten ono skrypt:

Przyznam, że byłem mocno zaskoczony, iż taki trik jest w ogóle możliwy przy pomocy czegoś, co w założeniu jest tylko powłoką tekstową dla poleceń administracyjnych. A tu proszę: DirectX w całej (aczkolwiek zarządzanej) okazałości!
Nietrudno rzecz jasna zauważyć, że powyższy skrypt jest w dużym stopniu tłumaczeniem na język PowerShella odpowiedniego kodu, który mógłby zostać napisany w dowolnym języku programowania z platformy .NET. Trzeba było jedynie poradzić sobie z pewnymi niedogodnościami, jak na przykład koniecznością ręcznego załadowania assemblies czy jakimś obejściem braku sensownej możliwości reakcji na zdarzenia – tutaj “program” po prostu kończy się po 5 sekundach.

Właśnie ta niemożność sprawia, że tandem PowerShell + DirectX zapewne nie ma przed sobą świetlanej przyszłości w grach :) Przez chwilę zastanawiałem się, czy wobec tego nie da się go użyć do tworzenia dem… Niestety, już powyższy skrypt zajmuje ponad 2 kilobajty, nie potrafiąc przy tym zbyt wiele, więc ta możliwość też prawdopodobnie odpada.
Pozostaje zatem pokazywanie podobnych trików linuksowcom i wytykanie im, że ich bash czegoś takiego nie potrafi ;D

Nadmuchiwanie obiektów

Od kilku dni nadspodziewanie popularnym sportem jest piłka nożna, co zapewne nie jest przypadkowe ;-) A jeśli już chodzi o piłkę, to musi być ona odpowiedniej jakości. I mówię tu o tym niewielkim, prawie okrągłym obiekcie: aby był przydatny, musi być… nadmuchany :) I właśnie o ‘nadmuchiwaniu’ powiem dzisiaj słów kilka.
Chodzi mi oczywiście o graficzny efekt rozszerzania się obiektu 3D, wyglądający tak, jakby ktoś w ów obiekt pompował powietrze. Można by pomyśleć, że osiągnięcie go jest niezmiernie trudne, bo przecież wchodząca w grę mechanika płynów (ruch gazu “wypełniającego” obiekt) jest jakąś kosmiczną fizykę. Ale – jak to często bywa – przybliżony a wyglądający niemal równie dobrze rezultat możemy dostać o wiele mniejszym wysiłkiem.

Jak? Sztuczka jest bardzo prosta. Aby nasz mesh zaczął się rozciągać na wszystkie strony, należy po prostu odpowiednio poprzesuwać mu wierzchołki. Wspomniane ‘wszystkie strony’ oznaczają tak naprawdę tyle, że każdy punkt powierzchni obiektu oddala się od niej w kierunku prostopadłym. Kierunek tego ruchu jest wyznaczony po prostu przez normalną.
Efekt jest w istocie trywialny i jego kod w HLSL/Cg może wyglądać na przykład tak:

Wśród zastosowań tego prostego triku można wymienić chociażby wyświetlanie poświaty wokół obiektów. Wystarczy do tego narysować obiekt najpierw w wersji zwykłej, a potem półprzezroczystej i nieco napompowanej.

A tak prezentują się rezultaty, gdy zaczniemy nadmuchiwać poczciwą futbolówkę:

Na Euro jak znalazł ;]

Skróty i linki NTFS

System Windows od niepamiętnych czasów (a dokładniej od wersji 95) pozwala na tworzenie skrótów (shortcut), czyli plików będących odwołaniami do innych plików lub katalogów. Skróty mają zwykle rozszerzenie .lnk i występują głównie w katalogach tworzących strukturę Menu Start.
Wewnętrznie nie ma w nich nic pomysłowego, gdyż są to zwykłe pliki w formacie na wpółbinarnym, zawierające docelową ścieżkę lub URI (np. adres internetowy). Ich obsługa realizowana jest na poziomie Eksploratora Windows, więc nie są one specjalnie funkcjonalne. Otwarcie pliku skrótu w dowolnym programie nie spowoduje na przykład odczytania zawartości docelowego pliku, lecz samego skrótu (który zwykle ma kilkaset bajtów). Podobnie skrót do katalogu Foo o nazwie Bar.lnk nie spowoduje, że do pliku Foo/Coś.txt odwołamy się poprzez Bar.lnk/Coś.txt.

Ilustracja działania linków twardych
(Źródło: Wikipedia)

Taką funkcjonalność zapewniają jednak linki twarde i symboliczne, obecne w nowszym wersjach NTFS. Są one bardzo podobne do swoich odpowiedników w systemach plików ext2 i ext3 (uniksowych). I tak:

• Link twardy (hardlink) to jakby alternatywna nazwa dla pliku, czyli nowa pozycja systemu plików odwołująca się do tych samych danych. Używając którejkolwiek z nich, można zmienić zawartość pliku i modyfikacje te będące widoczne dla innych, nawet jeśli uzyskają oni dostęp do pliku za pomocą innych jego nazw.
  W Windows 2000 i nowszych linki twarde można tworzyć poleceniem fsutil hardlink create link cel, a w Windows Vista dodatkowo mklink /H link cel. Programowo robi się funkcją WinAPI o nazwie CreateHardLink.
• Link symboliczny (symlink) jest z kolei łączem do istniejącej nazwy pliku lub katalogu; zamiast do faktycznych danych na dysku odwołuje się więc do innego elementu systemu plików. To właściwie taki skrót pozbawiony ograniczeń, o których wspominałem na początku. Możliwe jest jednak, aby programy operowały bezpośrednio na linkach symbolicznych, o ile odpowiednio ładnie o to poproszą :)
  W miarę porządna implementacja obsługi symlinków jest niestety zawarta dopiero w Windows Vista; można je tworzyć programem mklink (trzeba jednak zaznaczać jawnie, czy robimy link do pliku czy do katalogu). We wcześniejszych wersjach możliwe jest jedynie tworzenie NTFS junctions, będących “linkami” tylko do katalogów oraz obarczonych innymi ograniczeniami (na przykład Eksplorator w Windows XP dość słabo sobie z nimi radzi).

Jak nietrudno zauważyć, podstawową zaletą linków nad zwykłymi skrótami jest to, że te pierwsze są obsługiwane na poziomie systemu plików. Wobec tego działają one w dowolnym programie i zupełnie przezroczyście dla aplikacji. Trochę szkoda, że ten przydatny drobiazg pochodzący z systemów uniksowych dopiero teraz pojawia się w Windows… ale przecież lepiej późno niż wcale ;]

O (nie)zawodności TCP

Dowiadując się, czym jest protokół TCP, można przy okazji usłyszeć lub przeczytać, że jest on niezawodny (reliable). Można wtedy pomyśleć, że to jakiś rodzaj białej magii – zwłaszcza, gdy pomyślimy sobie, jakie przeszkody mogą spotkać przesyłany kawałek danych podczas podróży tysiącami kilometrów kabli (a ostatnio i bez nich). Zatory w transmisji, źle skonfigurowane routery, nagła zmiana topologii sieci, i tak dalej… Mimo to niektóre programistyczne interfejsy próbują nam wmówić, że odczyt i zapis danych “w sieci” jest w gruncie rzeczy niemal identyczny np. z dostępem do dysku. To pewnie też skutek “myślenia magicznego” na temat pojęcia niezawodności w kontekście TCP.

A w praktyce nie kryje się za nim żadna magia. Niezawodność TCP ma swoje granice i obsługuje dokładnie tyle możliwych sytuacji i zdarzeń losowych, ile zostało przewidzianych – jawnie lub nie – w specyfikacji tego protokołu. (Zawartej w RFC 793, jeśli kogokolwiek ona interesuje ;]). Analogicznie jest na przykład z dostępem do dysków wymiennych: stare wersje Windows potrafiły radośnie krzyknąć sławetnym bluescreenem, gdy użytkownik ośmielił się wyciągnąć dysk z napędu w trakcie pracy aplikacji, która z niego korzystała. Była to bowiem sytuacja nieprzewidziana na odpowiednio wysokiej warstwie systemu.
Jakie więc niespodziewane sytuacje i problemy dotyczące TCP należy przewidywać, jeśli piszemy programy sieciowe? Jest ich przynajmniej kilka:

• Pakiety TCP po drodze od nadawcy i odbiorcy mogą ulegać podzieleniu (fragmentacji) w celu przepchnięcia ich przez podsieci o różnych możliwościach przesyłu. Wszystkie kawałki są oczywiście składane przez odbiorcę w miarę ich napływania wraz z dodatkowymi informacjami, pozwalającymi na odtworzenie kolejności bajtów. Jednak fragmentacja sprawia, że nie musimy odebrać danych w porcjach tej samej długości, w jakiej były wysyłane. Dowolna ilość wywołań funkcji typu Send u nadawcy może przekładać się na równie dowolną liczbę wywołań Receive w celu odebrania wysłanych informacji. Stąd wynika konieczność rozróżniania porcji danych we własnym zakresie, o czym pisałem jakiś czas temu.
• Połączenie TCP może się zakończyć się nieoczekiwanie, jak choćby poprzez nagłe zakończenie wykorzystującego je procesu u jednej ze stron komunikacji. Wykrycie takiej sytuacji polega niestety wyłącznie na opóźnieniach (timeout) w otrzymywaniu pakietów potwierdzających (ACK) dostarczanie danych. To sprawia, że nie można odróżnić zerwania połączenia od zatorów w transmisji na poziomie samego protokołu TCP.
  Dlatego też trzeba sobie z tym radzić na wyższym poziomie, implementując w protokołach aplikacyjnych mechanizmy typu ping-pong do okresowego sprawdzania, czy połączenie “żyje”. Należy przy tym sprawdzać czas odpowiedzi nie względem jakichś twardych limitów, tylko poprzednio rejestrowanych interwałów.
• 
  Diagram stanów
  połączenia TCP

  Wreszcie, połączenie TCP można też zakończyć grzecznie (wymianą pakietów z flagami: FIN, FIN/ACK i ACK), co powinno dać się wykryć przez sieciowy interfejs programistyczny. W praktyce bywają z tym problemy, a jako takie powiadamianie o rozłączeniu działa tym lepiej, im niższy poziom API jest używany. W miarę pewnie wygląda to na warstwie POSIX-owych gniazdek (w Windows zaimplementowanych jako biblioteka WinSock) oraz w ich bezpośrednim opakowaniu na platformie .NET (System.Net.Sockets.Socket) lub w Javie (java.net.Socket). Wraz ze wzrostem poziomu abstrakcji (jak chociażby w specjalizacjach “sieciowych” strumieni I/O) sprawa wygląda już nieco gorzej…

Z niezawodnością TCP nie ma co więc przesadzać. W szczególności nie powinniśmy oczekiwać, że zapewni nam ona ochronę przed wszystkimi wyjątkowymi sytuacjami, jakie mogą wydarzyć się podczas komunikacji sieciowej. O przynajmniej kilku musimy pomyśleć samodzielnie.