Pamięć Transakcyjna – Wydajność

W poprzednich wpisach przedstawiłem Wam mechanizm Pamięci Transakcyjnej, a teraz chciałbym skupić się na jego wydajności względem zwykłych metod synchronizacji. Niestety pod biurkiem nie posiadam maszyny z kilkunastoma procesorami, dlatego w całej mierze opieram się na badaniu opisanym w dokumencie [1].

Przeprowadzono dwa rodzaje testów (w dokumencie opisano jeden więcej) na dwóch rodzajach maszyn. Obydwa testy polegały na konkurencyjnym dostępie do różnie zaimplementowanej hashmapy. Pierwsza maszyna, na jakiej przeprowadzano testy, miała jedynie 4 procesory, druga zaś miała ich aż 106! (to był rok 2003). W obu testach sukcesywnie zwiększano liczbę dostępnych jednostek.

Porównano 3 różne implementacje Hashmapy. Pierwsza jest standardowo dostępna w pakiecie java.util, HaspMap<K,V>, którą przed współbieżnym dostępem chroni pojedynczy mutex. Druga – z pakietu java.util.concurrent, ConcurrentHashMap<K,V>, zaimplementowana o wiele sprytniej, umożliwiająca m.in. jednoczesne czytanie. Ostatnia implementacja to zmodyfikowana wersja podstawowej hashmapy, w której usunięto mutex, a odpowiednie sekcje opatrzono transakcjami.

Pierwszy test polega na równoczesnym czytaniu i uaktualnianiu wpisów w 4096-elementowej hashmapie. Wyróżniono dwa przypadki: w pierwszym 1% wpisów uaktualniano, a 99% czytano, natomiast w drugim 16% zmieniano, a 84% czytano. Wyniki z 4 procesorowej maszyny (rysunek 1, tabela na górze) wskazują, że najlepszą implementacje miała hashmapa z pakietu java.util.concurrency. Autorzy tłumaczą, że to rozwiązanie jest o wiele bardziej zintegrowane z platformą niż ich własne, a ponadto operacje na kolekcji wykonywane były jedna po drugiej, wykorzystując 100% mocy, a taki przypadek jest mało prawdopodobny w realnych rozwiązaniach.

Inaczej sytuacja wygląda na maszynie ze 106 procesorami. Przy 1% zapisie rozwiązanie wykorzystujące transakcje wygrywało, ale dopiero przy 30 równoległych procesorach. Wytłumaczenie, jakie przytaczali badacze, odnosi się do narzutu spowodowanego zarządzaniem transakcjami. Przy małej ilości równoległych zapisów narzut ten powodował przegraną transakcji. Jednak przy dużej ilości równoległych operacji, transakcje były o tyle bardziej wydajne od java.util.concurrency, że dodatkowy narzut nie przeszkadzał w wygranej. Pamiętajmy, że rozwiązanie z pakietu java.util.concurency pozwala równocześnie czytać, a w rozwiązaniu transakcyjnym czytanie wywołuje zarządzanie transakcjami. Przy 16% uaktualnianiu transakcje wygrywały już od 5 równoległych procesów, ale  w takim stopniu, jak Formuła 1 z Fiatem 126p na 1/4 mili. Prezentują to wykresy a i b na rysunku 2. We wszystkich przypadkach rozwiązanie z pojedynczym mutexem można porównać do ślimaka.

Drugi rodzaj testów polegał na równoległych operacjach „swap”. Wybierano dwa klucze z tablicy hashującej, a następnie zamieniano wartości, na które te klucze się mapowały. Założenie było takie, aby taka operacja była atonomiczna. Pierwsze rozwiązanie, podobnie jak w teście pierwszym, bazowało na pojedynczym mutexie, natomiast w drugiej implementacji (java.util.concurrency) dodano blokady per klucz, a w trzecim przypadku, znów podobnie, użyto transakcji. Do testu użyto map wielkości 256 oraz 4096.

W przypadku więcej niż jednego procesora rozwiązanie z transakcjami bije na głowę pojedynczą blokadę. W porównaniu ze współbieżną hashmapą transakcje wypadają gorzej dla malej liczby procesorów (rysunek 1, tabela na dole). W przypadku maszyny z setką procesorów, wyraźnie widać przewagę transkacji nad pozostałymi metodami. Spowodowane jest to faktem, że niekolidujące aktualizacje mogą być faktycznie wykonywane równolegle, kiedy przy współbieżnej hashmapie procesy walczą o jedną blokadę (rysunek 2, wykresy c i d).

Podsumowując, jeżeli operacje na kolekcji wykonywane są równolegle, a prawdopodobieństwo tego, że procesy będą korzystać z tych samych pól, jest małe, transakcje wykazują znaczącą przewagę nad pozostałymi metodami synchronizacji. Operacje takie mogą faktycznie wykonywać się równoległe, a narzut spowodowany obsługą transakcji jest relatywnie bardzo mały w stosunku do zyskanej wydajności.

W przypadku niejasności odsyłam zainteresowany do lektury dokumentu [1].

Rysunek 1, Maszyna 4 rdzeniowa

Rysunek 2, Maszyna 106 rdzeniowa

Źródła:

Promuj