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 email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *