2011-09-20 17:45:33
Kompresor obsługujący SMP

Ponad rok temu pomyślałem sobie, że skoro rynek jest już solidnie nasycony systemami SMP (tj. z procesorami wielordzeniowymi, z procesorami obsługującymi HyperThreading, lub chociaż systemami z wieloma procesorami) - czemu użytkownicy mają czekać czort wie ile na zrobienie się kopii zapasowej albo zaktualizowanie skompresowanego pliku użytkownika? Zacząłem badać teren i następnego dnia miałem wstępną, sensownie działajacą implementację kompresora.

Pierwotna implementacja miała tę zaletę, że dobrze wykorzystywała wszystkie rdzenie - tworzonych było tyle wątków ile logicznych procesorów, następnie każdy wątek wczytywał blok danych (256KB), kompresował i zapisywał. Było to o tyle dobre, że cała praca była prawie idealnie rozłożona między wątki. Jednak były też poważne problemy, po których dałem sobie spokój a później zapomniałem o sprawie. Chodziło o narzut takiego algorytmu - ponieważ bloki nie były kompresowane niezależnie (inaczej narzut skoczyłby do kosmosu z racji tworzenia słownika od zera), każdy blok musiał być otagowany - nie tylko rozmiarem przed i po kompresji, ale i numerem wątku. To oznaczało narzut przynajmniej 9 bajtów na blok, dla pliku o rozmiarze 2GB to oznaczało ponad 4KB narzutu (plus narzut n słowników kompresora). Dekompresja okazała się koszmarem - szczególnie w przypadku gdy jeden z wątków kompresora natrafił na szczególnie ciężkie dane i pracował powoooli, zaś inne pędziły jak oszalałe. Ostatecznie, mimo usilnych prób, dekompresja była w najlepszym przypadku dwa razy wolniejsza z racji zbyt wolnego I/O - nie zamierzałem wychodzić z założenia, że użytkownik będzie dysponował sensownym dyskiem SSD i ostatecznie zarchiwizowałem kod, i zająłem się IMAPem.

Kilka dni temu pomyślałem sobie, że może jednak warto iść po linii najmniejszego oporu i zamiast karmić każdy wątek pierwszym wolnym blokiem źródłowego pliku, lepiej będzie podzielić plik na części, a każdą z takich części na n podczęści, gdzie n jest liczbą wątków. Oznaczało to, że użycie pamięci do kompresji będzie straszliwe - części nie mogą być za małe gdyż znowu odezwie się narzut tagów. Przyjąłem więc rozmiar części na 256MB, co daje 128MB na wątek w przypadku takiego Core 2 Duo. Narzut? Rozmiar części po kompresji, rozmiar części przed kompresją (nie muszą być równe!) = 8 bajtów. To - razy ilość wątków, czyli np. 2 = 16. Dla 2GB pliku - 128 bajtów (plus, oczywiście, słowniki). Tyle co nic. Zacząłem więc implementować i testować, i wcale nie było tak źle, jednak problemy z I/O znowu dały się we znaki - i to już przy kompresji. Zapis i odczyt tak dużych bloków trochę trwa, a ponieważ czasy dostępu do dysku za pośrednictwem trybu PIO (Programmable Input/Output) mamy za sobą i nawet na dość leciwych komputerach urzęduje DMA (Direct Memory Access), podczas odczytu i zapisu procesor najzwyczajniej w świecie nudzi się. Oczywiste zatem było przesunięcie odczytu i zapisu w czasie tak, by wykonywało się w czasie kompresji. Niestety, to podwoiło użycie pamięci - jeśli ktoś nie liczył, to przypomnę - część ma 256MB, trzeba zaalokować kolejnych ok. 256MB (i liczyć się z tym, że może być potrzeba więcej) na bufor wyjściowy, jeśli bufory teraz podwoimy (bufory bieżące i bufory tyłu/przodu), to użycie pamięci skacze do - uwaga - 1GB. Trochę dużo, więc dodałem ogranicznik i na maszynach z mniej niż 2GB RAM rozmiar części był zmniejszany do 128MB (=512MB), zaś na maszynach z mniej niż 1GB - do 64MB (=256MB). Następnie poprawiłem czas "rozpędzania" i "hamowania" kompresora - zamiast czekać aż wczyta się cała pierwsza część, mechanizm wczytuje pierwszą podczęść i uruchamia pierwszy wątek, następnie drugą i drugi wątek, i tak dalej - następnie wczytywana jest cała kolejna część (w czasie gdy poprzednia jest właśnie kompresowana). Przy "hamowaniu" kompresora, wątek zarządzający całym procesem czeka na pierwszy wątek kompresujący aż skończy swoją pracę, następnie natychmiast zapisuje skompresowane dane. Następnie wątek zarządzajacy czeka na drugi wątek i znowu zapisuje dane, i tak dalej. Czas wykorzystany na zapis pozostałe wątki mogą wykorzystać na dokończenie swojej części pracy - w efekcie, często udaje się - przynajmniej w części - pokryć zapis danych kompresją ostatniej części.

Dekompresja okazała się dużo wygodniejsza dla I/O, ponieważ dekompresować mogłem do jednego, wielkiego bufora i zapisywać ten bufor w czasie dekompresji kolejnego. Czas dekompresji w przypadku tego rozwiązania był identyczny jak w przypadku standardowego kompresora, chociaż dekompresja na n wątkąch nie ma za wiele sensu, gdyż dalej ogranicza nas I/O - pamięć, mimo wszystko, jest dużo szybsza niż najszybsze dyski talerzowe.

W stress-testach, które trwały kilka dni (!), okazało się że to, co dobrze wygląda w teorii, niespecjalnie ma się w praktyce. Problem nudzących się wątków (gdy jeden wątek kompresujący skończy swoją pracę wcześniej niż reszta) okazał się poważniejszy niż myślałem, szczególnie na dwurdzeniowych maszynach - średnie przyspieszenie wynosiło zaledwie około 50%, trochę daleko od ideału. Częściowym rozwiązaniem okazało się zmniejszenie wielkości części - po zmniejszeniu rozmiaru części do 128MB, przyspieszenie na moim Core 2 Duo E4400 sięgło około 71%, czyli całkiem blisko fizycznym możliwościom SMP opartego o 2MB współdzielonej pamięci podręcznej drugiego poziomu: o ile na jednym rdzeniu czas tworzenia kopii (niecałe 9GB danych) wynosił 14 minut i 42 sekundy, to na dwóch spadł do 8 minut i 28 sekund. Dalsze zmniejszanie wielkości części tylko zwiększało narzut (nie przyspieszając całego procesu), więc na tym poprzestałem. Dalsze usprawnienie wzięło się z obserwacji kompresora działającego na Atomie 330 - mimo że to dwa rdzenie z HT, zyski tutaj wynosiły nawet 140% (skrócenie czasu kompresji z 32 minut i 35 sekund do 13 minut i 34 sekund). Sprawdziłem więc, jak zareaguje Core 2 Duo na podwojenie ilości wątków (4 zamiast 2) - no i proszę państwa, rewelacja - nagle zysk wydajności skoczył do 82%! Nie jest to 100%, ale skrócenie czasu tworzenia kopii z 14 minut i 42 sekund do 8 minut i dwóch sekund to jednak jakieś osiągnięcie. Przez chwilę brałem pod uwagę 6 albo 8 wątków, ale szybko wybiłem sobie to z głowy (narzut przełączania aktywnego wątku i zaśmiecania pamięci podręcznej był na tyle duży, że zysk wydajności spadł znowu do 70%). Następnie sprawdziłem, jak na tę zmianę zareaguje Atom 330. I znowu zaskoczenie - zysk po podwojeniu ilości wątków podskoczył do 170%: czas kompresji skrócił się do 12 minut i 2 sekund. Nieźle. :)

Dzisiejszy build biblioteki hcm_extra.dll posiada już ten kompresor, zaś dzisiejszy build samego Hellcore Mailera posiada obsługę tej wersji biblitoeki, zatem nic nie stoi na przeszkodzie by każdy mógł przetestować to u siebie. Jedyny haczyk tkwi w tym, że z tego powodu zmienił się format plików .HBK (plików kopii) i starsze wersje programu nie odczytają ich. Obecne (i kolejne) wersje programu poradzą sobie zarówno z tym formatem, jak i starym.

Co następne? Zastanawiam się nad kompresją ciągłą, ale nie sądzę by w przypadku Hellcore Mailera coś to dało - co nie zabrania mi tego sprawdzić w praktyce. ;-) No i oczywiście wracam do dopieszczania IMAPa i poprawiania błędów.


Może Cię zainteresować...

Link | Komentarzy: 8 | HCM, Programowanie, Tech
Pokazuj komentarze.
Komentowanie wyłączone dla tego wpisu.
Powered by:
Hellcore Mailer - polski program pocztowyOpera Web BrowserFreeBSD - The Power to Serve!Slackware
RSSy:
Sidekick:
Projekty:
O autorze:
Zobacz:
Kategorie:
Archiwum:
Szukaj: