W poszukiwaniu straconego czasu

2011-11-28 23:20

Kilka tygodni temu świat obiegła wiadomość o eksperymencie, wskazującym na możliwość istnienia neutrin poruszających się z szybkością większą niż świetlna. Rzeczone cząstki zostały wykryte o około 60 nanosekund wcześniej niż powinny, co wskazywałoby na to, iż właśnie o tyle szybciej przebyły nieco ponad 700-kilometrową odległość między szwajcarskim a włoskim laboratorium.

Czy owe 60 nanosekund to długo? No cóż, przychodzą tu do głowy dwie skrajne odpowiedzi. Z jednej strony to bardzo długo: w tym czasie fala elektromagnetyczna przebiegnie jakieś 60 metrów, a niedokładność tego rzędu byłaby kilkakrotnie większa niż zwyczajnego odbiornika GPS w nowoczesnym telefonie. Z drugiej strony jest to oczywiście niewyobrażalnie krótkie mgnienie oka – ale tylko w sensie metaforycznym, bo to rzeczywiste trwa przecież miliony razy dłużej.

Bardziej interesujące jest, jak taki odcinek czasowy ma się do przedziałów czasu, z którymi możemy mieć do czynienia podczas programowania. O ile rzędów wielkości różnią się od niego typowe interwały, z którymi stykamy się w różnego rodzaju aplikacjach?
Okazuje się, że o całkiem sporo… albo o bardzo niewiele. Na każdym z poziomów pośrednich dzieje się jednak zawsze coś ciekawego.

W serii tubek

Jeśli zostawimy na boku rzeczywiście długie, a stosunkowo rzadkie operacje – liczone w minutach, godzinach czy nawet dniach – to najdłuższe przedziały czasowe ważne dla programisty (i użytkownika) układają się w okolicach sekundy. Mniej więcej tyle trwa bowiem załadowanie pojedynczej strony internetowej, na przykład takiej jak niniejsza. Czas ten może się aczkolwiek dość mocno wahać w zależności od wielu czynników, jak choćby liczba zewnętrznych plików – takich jak obrazki czy skrypty – które muszą zostać pobrane osobnymi żądaniami HTTP. Zwykle jednak po około sekundzie użytkownik ma już coś, czemu może się przyjrzeć, podczas gdy mniej ważne elementy (w rodzaju widgetów sieci społecznościowych) mogą ładować się później.

Podobno nie jest to wcale przypadek, gdyż owa sekunda lub dwie jest tym granicznym czasem, po którym użytkownik zacznie się niecierpliwić. Jak wiele zasad z dziedziny UX, tak i ta ma spore szanse być bzdurą, ale mimo to pozostaje ona dobrą miarą wydajności serwisów internetowych. Naprawdę trudno już znaleźć jakikolwiek dobry powód, aby granica kilku sekund mogła być w uzasadniony sposób przekraczana.

Wąskie gardła


Przykładowy wykres operacji I/O
podczas pojedynczego żądania HTTP

Z naiwnego punktu widzenia stworzenie kilkunastu kilobajtów tekstu i paru obrazków w dwie sekundy zakrawa zresztą na niesamowitą opieszałość. Co zajmuje tutaj aż tyle czasu? Odpowiedź jest rzecz jasna prosta: I/O. Jeśli nawet pominiemy długi czas przesyłu gotowej odpowiedzi HTTP, to mamy jeszcze cały proces jej generowania, który niemal w całości składa się właśnie z operacji I/O. Odczytywanie statycznych plików, zapytania do bazy danych, pobieranie i ustawianie wartości w memcache, wywołania API zewnętrznych serwisów webowych… Każda z tych typowych czynności wymaga uderzenia w bramkę wejścia-wyjścia: głowicę dysku, kabel sieciowy, albo jedno i drugie.

Czas trwania tych operacji oscyluje zwykle w przedziale od kilkudziesięciu do 100 milisekund, tworząc więc kolejny interesujący rząd wielkości. Mnóstwo koderskiego wysiłku – teoretycznego i praktycznego – nastawione jest na efektywne radzenie sobie z nieznośną długością tych czasów. Typowe techniki to: przedkładanie szybszych operacji nad wolniejsze (np. wspomniany memcache zamiast bazy danych) i pożyteczniejsze spędzanie czasu oczekiwania (równoległość, współbieżność i asynchroniczność).

Schodzimy głębiej

Domyślam się, że mówienie o operacjach zajmujących pod sto milisekund dla wielu programistów może być jak rozmowa o populacji koników polnych w Chinach. I rzeczywiście – jeśli mówimy o aplikacjach czasu rzeczywistego, ten rząd wielkości jest poza wszelką dyskusją. Trzeba mu uciąć przynajmniej jeszcze jedno zero.

W takich aplikacjach – na przykład w grach – 10 milisekund to dobry czas na obliczenie i wyrenderowanie pojedynczej klatki animacji. Graczom pokazany byłby jako 100FPS, chociaż w pierwotnej postaci jest znacznie bardziej miarodajny. W tym czasie musi wydarzyć się mnóstwo rzeczy, włączając w to: przetworzenie zdarzeń wejścia, kolejny krok obliczeń fizycznych, odpowiednia zmiana stanu AI, a wreszcie uaktualnienie buforów graficznych i przesłanie ich do GPU.
Wszystkie te czynności składają się z tysięcy większych i mniejszych zadań – aż do poziomu pojedynczych funkcji w kodzie. Ich dokładny czas trwania jest oczywiście bardzo różny, lecz używając finalnego ograniczenia (10ms) można szacować przybliżony czas ich trwania – albo po prostu uruchomić profiler i sprawdzić :) Zobaczymy wtedy, że większe operacje mogą zajmować kilkaset mikrosekund, zaś te mniejsze co najwyżej kilka – lub nawet mniej niż mikrosekundę.

Niżej już tylko metal

Skoro zeszliśmy już na poziom pojedynczych funkcji, to teraz pozostaje nam już tylko przyjrzeć się temu, z czego się one składają: instrukcjom kodu. Niemożliwe jest rzecz jasna stwierdzenie, ile zajmie wykonanie dowolnego wiersza kodu źródłowego – już choćby dlatego, że wyniki te mogą różnić się bardzo dla poszczególnych języków programowania.

I tak stworzenie pojedynczego, w miarę prostego obiektu w Javie zajmuje obecnie mniej więcej pół mikrosekundy, co jest dość niezłym wynikiem jak na operację wymagają przecież alokacji pamięci (mniejsza już o to, gdzie jest ona alokowana). Z drugiej strony język w rodzaju Pythona może zużyć nawet dwu-trzykrotnie dłuższy czas na jedną operację arytmetyczną. Obrazuje to sporą różnicę wydajnościową między językami interpretowanymi a kompilowanymi – nawet jeśli te drugie docelowo wykonywane są na maszynie wirtualnej.

O wiele lepsze wyniki osiągane są w przypadku chociażby C, bowiem tutaj mówimy już granicach wyznaczanych często przez sam sprzęt. Dlatego też powinniśmy raczej mówić o czasie dostępu do pamięci i poszczególnych rodzaju cache procesora, zamiast o instrukcjach w wysokopoziomowych (tj. powyżej asemblera) językach programowania.

I właśnie na tym poziomie odnajdziemy nasze 60 nanosekund. Jest to dość zgrubne przybliżenie czasu potrzebnego na cały proces dostępu do dowolnej komórki pamięci – przy czym słówko ‘dowolnej’ jest tu kluczowe. W sprzyjających okolicznościach możemy bowiem uwinąć się znacznie szybciej, jeśli zechcemy danych znajdujących się już w którymś z poziomów cache procesora (L1 i L2). Omijając całą wycieczkę przez magistralę możemy uzyskać wynik w zaledwie kilka nanosekund.
Nietrudno doszukać się tu analogii między opisanymi nieco wyżej długimi operacjami typu I/O, których ilość należy minimalizować. W tym przypadku nieznośnie długi czas dostępu do pamięci spoza cache (cache miss) jest tym, co inspiruje metodologię zwaną Data Oriented Design, o której swego czasu pisałem co nieco. Jak widać, nawet pozornie odległe dziedziny programowania mogą mieć ze sobą więcej wspólnego niż to się może wydawać :)

Czas… kończyć

Nie da się ukryć, że 0.00000006 sekundy nie jest przedziałem czasu, z którym większość programistów ma na co dzień do czynienia. Zwykle obchodzą nas interwały, które są tysiące, miliony, a niekiedy nawet miliardy razy dłuższe. Okazuje się jednak, że i tak krótki czas może mieć w informatyce całkiem duże znaczenie w określonych sytuacjach.

Jednak w przeciwieństwie do fizyki cząstek, 60-nanosekundowa optymalizacja może nas jedynie cieszyć ;-)

Tags: , , , ,
Author: Xion, posted under Computer Science & IT, Thoughts »


3 comments for post “W poszukiwaniu straconego czasu”.
  1. Marszal:
    November 30th, 2011 o 17:56

    Świetny tekst, nawet przybiera formę artykułu :)

    Pozdrawiam
    Marszal

  2. Grzegorz Stępnik:
    December 1st, 2011 o 8:23

    Xion możesz złożyć wpisy z bloga z powiedzmy roku i wydać ciekawą Xiążkę pt.: “Teoria [na temat] wszystkiego” :P

  3. fir:
    March 20th, 2012 o 14:29

    gdzie tam cieszyć, cieszyc to moze kilka cykli na operacje – a nie 200scie

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.