LongAdder – wydajny licznik z Javy 8

Photo by William Hook on Unsplash

Niedawno trafiłem na ciekawą strukturę z Javy 8 – LongAdder. Okazało się, że w niektórych przypadkach jest dużo lepszym wyborem niż AtomicLong. Dlaczego? Zapraszam do wspólnej podróży.

Do tej pory zawsze używałem klas z grupy Atomic – były bezpieczne wielowątkowo, korzystały z operacji compare-and-swap i miały być wydajne. Okazuje się, że dzięki zastosowaniu pewnego tricku LongAdder potrafi być nawet 6 razy wydajniejszy!

O co chodzi?

Klasy z rodziny AtomicLong używają instrukcji procesora compare-and-swap do aktualizowania wartości. Jest to bardzo wydajny mechanizm wykorzystujący bezpośrednio instrukcje maszynowe procesora do ustawienia wartości z minimalnym efektem na wykonywanie się innych wątków. Z minimalnym, nie oznacza z żadnym. Pod dużym obciążeniem wątek będzie nieustannie próbował zapisać wartość w nieskończonej pętli aż do momentu, gdy mu się to uda.

Oznacza to, że w sytuacji gdy wiele wątków stara się pisać w jednym czasie do zmiennej typu AtomicLong prowadzi to do spinlocków i spadków wydajności.

LongAdder na ratunek

LongAdder korzysta z pewnej optymalizacji, dzięki której obcy jest mu powyższy problem. Zamiast zapisywać zmiany wartości do jednego miejsca, zapisuje je do wielu miejsc. Dzięki temu nie ma sytuacji, w której wiele wątków konkuruje o dostęp do zapisu w to samo miejsce. W ten sposób wydajność zdecydowanie wzrasta.

W AtomicLongu wiele wątków stara się modyfikować ten sam obszar pamięci
W LongAdderze wątki piszą do różnych obszarów pamięci

Ta struktura ma jednak też swoje minusy. O ile zapisywanie jest bardzo wydajne – O(1) – o tyle odczyt wymaga już wykonywania operacji sumowania wszystkich wartości. Algorytm musi przeiterować przez wszystkie liczby z pól tablicy, które były użyte w LongAdderze – to daje nam wydajność rzędu O(n). Co więcej, operacja odczytu niekoniecznie będzie dokładna. Jeśli w tym samym momencie ktoś będzie próbował pisać do LongAddera, spowoduje to pominięcie nowej wartości w obliczeniach. Zarówno zapis jak i odczyt są więc operacjami nieblokującymi. Daje to bardzo wysoką wydajność, ale też nie przychodzi bez innych kosztów – w tym wypadku dokładności.

Co to oznacza? LongAdder najlepiej sprawdza się w sytuacji, w której liczba zapisów zdecydowanie przekracza liczbę odczytów. I w której nie zależy nam na każdorazowej dokładności odczytanych wyników. Zbieranie statystyk, metryk i tym podobnych wielkości będzie idealnym zastosowaniem tej klasy.

Testy

Aby to potwierdzić wykonałem dwa testy. Jeden, w którym na 1000 zapisów wartości przypada 1 odczyt i drugi, w którym przy każdym zapisie odczytujemy aktualną wartość. Test uruchomiłem na 100 wątkach, na dwurdzeniowym procesorze Intel Core i5.

Oto wyniki (im więcej, tym lepiej):

100 wątków, odczyt wartości co 1000 iteracji:

  • AtomicLong – 39.927 operacji na sekundę
  • LongAdder – 232.363 operacji na sekundę (5,82 raza więcej)

100 wątków, odczyt wartości przy każdej iteracji:

  • AtomicLong – 37.728 operacji na sekundę
  • LongAdder – 42.800 operacji na sekundę (1,13 raza więcej)

W pierwszym wypadku LongAdder był wydajniejszy 5,82 raza, a w drugim o 1,13. Widać więc jego przewagę nad AtomicLongiem i to, że najlepsze rezultaty osiąga przy częstych zapisach i rzadkich odczytach.

Podsumowanie

LongAdder to jedna z czterech klas jednej rodziny wprowadzonych do Javy 8 w ramach usprawnień dotyczących współbieżności.
Jeśli będziesz potrzebował wydajnego licznika bezpiecznego wielowątkowo od teraz powinieneś preferować te klasy, zamiast klas typu Atomic.

Author: Dariusz Mydlarz

Cześć, nazywam się Dariusz Mydlarz i od 2012 pracuję jako programista. Tworzę w ekosystemie Javy i uwielbiam systemy backendowe. Chcę w tym miejscu pomagać Ci stawać się lepszym programista. Jeśli mogę Ci jakoś pomoc, po prostu napisz do mnie.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *