Wiadomości o usługach

Dla zaawansowanych: bezblokowa kolejka MessageQueue w Androidzie 17

Czas czytania: 16 minut
Charles Munger i Shai Barack

W Androidzie 17 aplikacje kierowane na pakiet SDK 37 lub nowszy otrzymają nową implementację MessageQueue, która nie wymaga blokowania. Nowa implementacja zwiększa wydajność i zmniejsza liczbę pominiętych klatek, ale może powodować awarie klientów, którzy korzystają z pól prywatnych i metod klasy MessageQueue. Więcej informacji o tej zmianie i sposobach ograniczenia jej wpływu znajdziesz w dokumentacji dotyczącej zmiany zachowania kolejki komunikatów. Ten post na blogu technicznym zawiera omówienie ponownej architektury MessageQueue i informacje o tym, jak analizować problemy z konfliktami blokad za pomocą Perfetto.

Looper steruje wątkiem UI każdej aplikacji na Androida. Pobiera zadania z MessageQueue, przekazuje je do Handlera i powtarza te czynności. Przez 2 dekady MessageQueue używał pojedynczej blokady monitora (czyli bloku kodu synchronized), aby chronić swój stan.

Android 17 wprowadza znaczącą aktualizację tego komponentu: implementację bez blokad o nazwie DeliQueue.

Z tego posta dowiesz się, jak blokady wpływają na wydajność interfejsu, jak analizować te problemy za pomocą narzędzia Perfetto oraz jakie algorytmy i optymalizacje są używane do poprawy wydajności głównego wątku Androida.

Problem: rywalizacja o blokadę i odwrócenie priorytetów

Starsza funkcja MessageQueue działała jako kolejka priorytetowa chroniona przez jedną blokadę. Jeśli wątek w tle opublikuje wiadomość, gdy wątek główny wykonuje konserwację kolejki, wątek w tle zablokuje wątek główny.

Gdy co najmniej 2 wątki konkurują o wyłączne użycie tego samego blokowania, nazywa się to konfliktem blokowania. Ta rywalizacja może powodować odwrócenie priorytetów, co prowadzi do zacinania się interfejsu i innych problemów z wydajnością.

Odwrócenie priorytetów może wystąpić, gdy wątek o wysokim priorytecie (np. wątek interfejsu) musi czekać na wątek o niskim priorytecie. Rozważmy tę sekwencję:

  1. Wątek w tle o niskim priorytecie uzyskuje blokadę MessageQueue, aby opublikować wynik wykonanej pracy.
  2. Wątek o średnim priorytecie staje się gotowy do uruchomienia, a harmonogram jądra przydziela mu czas procesora, przerywając działanie wątku o niskim priorytecie.
  3. Wątek UI o wysokim priorytecie kończy bieżące zadanie i próbuje odczytać dane z kolejki, ale jest blokowany, ponieważ wątek o niskim priorytecie ma blokadę.

Wątek o niskim priorytecie blokuje wątek UI, a praca o średnim priorytecie dodatkowo go opóźnia.

perfetto1.png

Analizowanie rywalizacji za pomocą Perfetto

Możesz zdiagnozować te problemy za pomocą narzędzia Perfetto. W standardowym śledzeniu wątek zablokowany na blokadzie monitora przechodzi w stan uśpienia, a Perfetto wyświetla wycinek wskazujący właściciela blokady.

Podczas wysyłania zapytań o dane śledzenia szukaj wycinków o nazwie „monitor contention with …” (konkurencja monitora z …), po której następuje nazwa wątku będącego właścicielem blokady i miejsce w kodzie, w którym blokada została uzyskana.

Studium przypadku: zacinanie się Menu z aplikacjami

Aby to zilustrować, przeanalizujmy ślad, w którym użytkownik doświadczył zacięcia podczas przechodzenia do ekranu głównego na telefonie Pixel bezpośrednio po zrobieniu zdjęcia w aplikacji aparatu. Poniżej znajduje się zrzut ekranu Perfetto pokazujący zdarzenia prowadzące do pominiętej klatki:

launcherJ.png
  • Objaw: główny wątek Launchera nie zdążył z wyświetleniem klatki. Zablokowało się na 18 ms, co przekracza limit 16 ms wymagany do renderowania z częstotliwością 60 Hz.
  • Diagnoza: Perfetto wykazało, że wątek główny jest zablokowany na blokadzie MessageQueue. Blokada należała do wątku „BackgroundExecutor”.
  • Główna przyczyna: BackgroundExecutor działa z priorytetem Process.THREAD_PRIORITY_BACKGROUND (bardzo niskim). Wykonał zadanie niepilne (sprawdzanie limitów korzystania z aplikacji). W tym samym czasie wątki o średnim priorytecie wykorzystywały czas procesora do przetwarzania danych z kamery. Harmonogram systemu operacyjnego przerwał wątek BackgroundExecutor, aby uruchomić wątki kamery.

Ta sekwencja spowodowała, że wątek UI Launchera (wysoki priorytet) został pośrednio zablokowany przez wątek instancji roboczej aparatu (średni priorytet), który uniemożliwiał wątkowi w tle Launchera (niski priorytet) zwolnienie blokady.

Wykonywanie zapytań dotyczących śladów za pomocą PerfettoSQL

Za pomocą PerfettoSQL możesz wykonywać zapytania dotyczące danych śledzenia pod kątem określonych wzorców. Jest to przydatne, jeśli masz dużą bazę śladów z urządzeń użytkowników lub testów i szukasz konkretnych śladów, które wskazują na problem.

Na przykład to zapytanie znajduje rywalizację MessageQueue, która występuje w tym samym czasie co utracone klatki (zacinanie się):

INCLUDE PERFETTO MODULE android.monitor_contention;
INCLUDE PERFETTO MODULE android.frames.jank_type;

SELECT
  process_name,
  -- Convert duration from nanoseconds to milliseconds
  SUM(dur) / 1000000 AS sum_dur_ms,
  COUNT(*) AS count_contention
FROM android_monitor_contention
WHERE is_blocked_thread_main
AND short_blocked_method LIKE "%MessageQueue%" 

-- Only look at app processes that had jank
AND upid IN (
  SELECT DISTINCT(upid)
  FROM actual_frame_timeline_slice
  WHERE android_is_app_jank_type(jank_type) = TRUE
)
GROUP BY process_name
ORDER BY SUM(dur) DESC;

W tym bardziej złożonym przykładzie złącz dane śledzenia obejmujące wiele tabel, aby zidentyfikować rywalizację w kolejce komunikatów podczas uruchamiania aplikacji:

INCLUDE PERFETTO MODULE android.monitor_contention; 
INCLUDE PERFETTO MODULE android.startup.startups; 

-- Join package and process information for startups
DROP VIEW IF EXISTS startups; 
CREATE VIEW startups AS 
SELECT startup_id, ts, dur, upid 
FROM android_startups 
JOIN android_startup_processes USING(startup_id); 

-- Intersect monitor contention with startups in the same process.
DROP TABLE IF EXISTS monitor_contention_during_startup; 
CREATE VIRTUAL TABLE monitor_contention_during_startup 
USING SPAN_JOIN(android_monitor_contention PARTITIONED upid, startups PARTITIONED upid); 

SELECT 
  process_name, 
  SUM(dur) / 1000000 AS sum_dur_ms, 
  COUNT(*) AS count_contention 
FROM monitor_contention_during_startup 
WHERE is_blocked_thread_main 
AND short_blocked_method LIKE "%MessageQueue%" 
GROUP BY process_name 
ORDER BY SUM(dur) DESC;

Aby znaleźć inne wzorce, możesz użyć ulubionego modelu LLM do pisania zapytań PerfettoSQL.

W Google używamy BigTrace do uruchamiania zapytań PerfettoSQL na milionach śladów. Potwierdziliśmy w ten sposób, że to, co zaobserwowaliśmy, było w rzeczywistości problemem systemowym. Dane wykazały, że MessageQueue konflikt blokad wpływa na użytkowników w całym ekosystemie, co uzasadnia potrzebę wprowadzenia zasadniczej zmiany w architekturze.

Rozwiązanie: współbieżność bez blokad

Rozwiązaliśmy problem z MessageQueue konkurencją, wdrażając strukturę danych bez blokad, która do synchronizacji dostępu do stanu współdzielonego używa atomowych operacji na pamięci zamiast blokad wyłącznych. Struktura danych lub algorytm jest wolny od blokad, jeśli co najmniej jeden wątek może zawsze kontynuować działanie niezależnie od zachowania harmonogramu innych wątków. Zwykle trudno jest osiągnąć tę właściwość i w przypadku większości kodu nie warto się o nią starać.

Podstawowe elementy atomowe

Oprogramowanie bez blokad często korzysta z atomowych operacji odczytu, modyfikacji i zapisu, które są dostępne w sprzęcie.

Na starszych procesorach ARM64 operacje atomowe wykorzystywały pętlę Load-Link/Store-Conditional (LL/SC). Procesor wczytuje wartość i oznacza adres. Jeśli inny wątek zapisze dane pod tym adresem, zapisywanie się nie powiedzie, a pętla ponowi próbę. Ponieważ wątki mogą próbować dalej i odnieść sukces bez czekania na inny wątek, ta operacja nie wymaga blokady.

ARM64 LL/SC loop example
retry:
    ldxr    x0, [x1]        // Load exclusive from address x1 to x0
    add     x0, x0, #1      // Increment value by 1
    stxr    w2, x0, [x1]    // Store exclusive.
                            // w2 gets 0 on success, 1 on failure
    cbnz    w2, retry       // If w2 is non-zero (failed), branch to retr

(wyświetl w narzędziu Compiler Explorer)

Nowsze architektury ARM (ARMv8.1) obsługują rozszerzenia dużych systemów (LSE), które obejmują instrukcje w formie Compare-And-Swap (CAS) lub Load-And-Add (pokazane poniżej). W Androidzie 17 dodaliśmy do kompilatora środowiska wykonawczego Androida (ART) obsługę wykrywania, kiedy LSE jest obsługiwane, i emitowania zoptymalizowanych instrukcji:

/ ARMv8.1 LSE atomic example
ldadd   x0, x1, [x2]    // Atomic load-add.
                        // Faster, no loop required.

W naszych testach porównawczych kod o wysokim poziomie rywalizacji, który korzysta z CAS, osiąga około 3-krotne przyspieszenie w porównaniu z wariantem LL/SC.

Język programowania Java oferuje elementy atomowe za pomocą pakietu java.util.concurrent.atomic, które korzystają z tych i innych specjalistycznych instrukcji procesora.

Struktura danych: DeliQueue

Aby wyeliminować rywalizację o blokady w MessageQueue, nasi inżynierowie zaprojektowali nową strukturę danych o nazwie DeliQueue. DeliQueue oddziela Message wstawianie od Message przetwarzania:

  1. Lista Messages (stos Treiber): stos bez blokad. Każdy wątek może bez konfliktów umieszczać tu nowe elementy Messages.
  2. Kolejka priorytetowa (min-heap): stos Messages do obsługi, należący wyłącznie do wątku looper (dlatego dostęp do niego nie wymaga synchronizacji ani blokad).

Enqueue: umieszczanie na stosie Treiber

Lista Messages jest przechowywana w stosie Treibera [1], czyli stosie bez blokad, który do aktualizowania wskaźnika głowicy używa pętli CAS.

public class TreiberStack <E> {
    AtomicReference<Node<E>> top =
            new AtomicReference<Node<E>>();
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = top.get();
            if (oldHead == null) return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }
}

Kod źródłowy oparty na książce Java Concurrency in Practice [2], dostępny online i udostępniony w domenie publicznej.

Każdy producent może w dowolnym momencie dodać nowe Message do stosu. To tak, jakbyś wyciągnął(-ęła) numerek w delikatesach – Twój numer zależy od tego, kiedy się pojawiłeś(-aś), ale kolejność, w jakiej otrzymasz jedzenie, nie musi być zgodna z numerem. Ponieważ jest to połączony stos, każdy element Message jest podstosem. Możesz sprawdzić, jak wyglądała kolejka Message w dowolnym momencie, śledząc początek i przechodząc dalej. Nie zobaczysz żadnych nowych elementów Message dodanych na górze, nawet jeśli są one dodawane podczas przechodzenia.

Usuwanie z kolejki: zbiorcze przenoszenie do kopca minimalnego

Aby znaleźć następny element Message do przetworzenia, element Looper przetwarza nowe elementy Message ze stosu Treiber, przeglądając stos od góry i iterując, aż znajdzie ostatni przetworzony element Message. Gdy Looper przechodzi w dół stosu, wstawia Message do kolejki priorytetowej typu min-heap uporządkowanej według terminu. Ponieważ Looper jest wyłącznym właścicielem sterty, porządkuje i przetwarza Message bez blokad ani operacji atomowych.

dequeue.png

Podczas przechodzenia w dół stosu funkcja Looper tworzy też linki z ułożonych w stos Message do ich poprzedników, tworząc w ten sposób listę dwukierunkową. Tworzenie listy połączonej jest bezpieczne, ponieważ linki wskazujące w dół stosu są dodawane za pomocą algorytmu stosu Treiber z CAS, a linki w górę stosu są odczytywane i modyfikowane tylko przez wątek Looper. Te linki zwrotne są następnie używane do usuwania elementów z dowolnych punktów stosu w czasie O(1).Message

Taka konstrukcja zapewnia wstawianie w czasie O(1) dla producentów (wątków publikujących zadania w kolejce) i amortyzowane przetwarzanie w czasie O(log N) dla konsumenta (Looper).

Użycie min-heap do uporządkowania Message rozwiązuje też podstawową wadę starszej wersji MessageQueue, w której Message były przechowywane na liście jednokierunkowej (zakorzenionej u góry). W starszej implementacji usuwanie z początku kolejki miało złożoność O(1), ale wstawianie miało w najgorszym przypadku złożoność O(N), co powodowało słabe skalowanie w przypadku przepełnionych kolejek. Z kolei wstawianie do kopca minimalnego i usuwanie z niego elementów skaluje się logarytmicznie, co zapewnia konkurencyjną średnią wydajność, ale szczególnie dobrze sprawdza się w przypadku opóźnień na końcu kolejki.


 		Starsza wersja (zablokowana) MessageQueueDeliQueue
WstawO(N)

O(1) w przypadku wątku połączenia

O(logN) w przypadku wątku Looper

Usuń z głowyO(1)O(logN)

W starszej implementacji kolejki producenci i konsument używali blokady do koordynowania wyłącznego dostępu do bazowej listy jednokierunkowej. W przypadku DeliQueue stos Treibera obsługuje dostęp współbieżny, a pojedynczy konsument zarządza kolejnością zadań.

Usuwanie: spójność za pomocą znaczników usunięcia

DeliQueue to hybrydowa struktura danych, która łączy stos Treiber bez blokad z jednowątkową stertą minimalną. Utrzymywanie synchronizacji tych dwóch struktur bez globalnej blokady stanowi wyjątkowe wyzwanie: wiadomość może być fizycznie obecna w stosie, ale logicznie usunięta z kolejki.

Aby rozwiązać ten problem, DeliQueue używa techniki zwanej „tombstoning”. Każdy element Message śledzi swoją pozycję na stosie za pomocą wskaźników do tyłu i do przodu, indeksu w tablicy sterty oraz flagi logicznej wskazującej, czy został usunięty. Gdy wątek Message jest gotowy do uruchomienia, wątek Looper ustawia flagę usunięcia za pomocą operacji CAS, a następnie usuwa wątek ze sterty i stosu.

Gdy inny wątek musi usunąć element Message, nie wyodrębnia go od razu ze struktury danych. Zamiast tego wykonuje te czynności:

  1. Usunięcie logiczne: wątek używa operacji CAS, aby atomowo ustawić flagę usunięcia Message z wartości „fałsz” na „prawda”. Message pozostaje w strukturze danych jako dowód oczekującego usunięcia, tzw. „nagrobek”. Gdy Message zostanie oznaczony do usunięcia, DeliQueue traktuje go tak, jakby nie istniał już w kolejce.
  2. Odroczone czyszczenie: za usunięcie z struktury danych odpowiada wątek Looper, a jest ono odroczone do późniejszego czasu. Zamiast modyfikować stos lub stertę, wątek usuwający dodaje Message do innego stosu wolnych list bez blokad.
  3. Usuwanie strukturalne: tylko Looper może wchodzić w interakcję ze stertą lub usuwać elementy ze stosu. Po wybudzeniu czyści listę wolnych bloków i przetwarza zawarte w niej Message. Każdy element Message jest następnie odłączany od stosu i usuwany ze sterty.  

Dzięki temu zarządzanie stertą odbywa się w jednym wątku. Minimalizuje liczbę równoczesnych operacji i barier pamięci, dzięki czemu ścieżka krytyczna jest szybsza i prostsza.

Przechodzenie: niegroźne wyścigi o dane w modelu pamięci Java

Większość interfejsów API do współbieżności, takich jak Future w standardowej bibliotece Javy czy Job i Deferred w Kotlinie, zawiera mechanizm anulowania pracy przed jej zakończeniem. Instancja jednej z tych klas odpowiada 1:1 jednostce podstawowej pracy, a wywołanie cancel na obiekcie anuluje konkretne operacje z nim powiązane.

Współczesne urządzenia z Androidem mają wielordzeniowe procesory i równoczesne, generacyjne czyszczenie pamięci. Gdy Android był tworzony, przydzielanie jednego obiektu do każdej jednostki pracy było zbyt kosztowne. W związku z tym Handler w Androidzie obsługuje anulowanie za pomocą wielu przeciążeń removeMessages – zamiast usuwać konkretny Message, usuwa wszystkie Message, które spełniają określone kryteria. W praktyce wymaga to przeiterowania wszystkich elementów Message wstawionych przed wywołaniem funkcji removeMessages i usunięcia pasujących elementów.

Podczas iteracji do przodu wątek wymaga tylko jednej uporządkowanej operacji atomowej, aby odczytać bieżący początek stosu. Następnie do znalezienia kolejnego wystąpienia Message używane są zwykłe odczyty pól. Jeśli wątek Looper zmienia pola next podczas usuwania Message, zapisywanie przez wątek Looper i odczytywanie przez inny wątek są niezsynchronizowane – jest to wyścig o dane. Zwykle wyścig o dane to poważny błąd, który może powodować w aplikacji ogromne problemy – wycieki pamięci, nieskończone pętle, awarie, zawieszanie się i inne. Jednak w pewnych wąskich warunkach wyścigi o dane mogą być nieszkodliwe w ramach modelu pamięci Java. Załóżmy, że zaczynamy od stosu:

headMessage.png

Wykonujemy niepodzielną operację odczytu głowicy i widzimy A. Wskaźnik next węzła A wskazuje węzeł B. Podczas przetwarzania elementu B pętla może usunąć elementy B i C, aktualizując element A tak, aby wskazywał element C, a potem element D.

headMessage2.png

Chociaż węzły B i C są logicznie usunięte, węzeł B nadal ma wskaźnik do węzła C, a węzeł C do węzła D. Wątek odczytu nadal przechodzi przez odłączone usunięte węzły i ostatecznie ponownie łączy się z aktywnym stosem w miejscu D. 

Dzięki zaprojektowaniu DeliQueue w taki sposób, aby obsługiwał wyścigi między przechodzeniem a usuwaniem, umożliwiamy bezpieczną iterację bez blokad.

Zakończenie: natywne zliczanie odwołań

 jest obsługiwany przez natywną alokację, którą należy ręcznie zwolnić po zamknięciu Looper.Looper Jeśli inny wątek dodaje Message, gdy wątek Looper kończy działanie, może użyć natywnej alokacji po jej zwolnieniu, co stanowi naruszenie bezpieczeństwa pamięci. Zapobiegamy temu, używając oznaczonego licznika odwołań, w którym jeden bit atomu służy do wskazywania, czy Looper kończy działanie.

Przed użyciem natywnej alokacji wątek odczytuje atomową wartość refcount. Jeśli bit zakończenia jest ustawiony, zwraca informację, że Looper kończy działanie i nie można używać przydziału natywnego. Jeśli nie, próbuje wykonać operację CAS, aby zwiększyć liczbę aktywnych wątków przy użyciu natywnej alokacji. Po wykonaniu potrzebnych czynności zmniejsza liczbę. Jeśli bit zakończenia został ustawiony po zwiększeniu, ale przed zmniejszeniem, a liczba wynosi teraz zero, wątek Looper zostanie wybudzony.

Gdy wątek Looper jest gotowy do zakończenia działania, używa operacji CAS, aby ustawić bit zakończenia w obiekcie atomowym. Jeśli licznik odwołań wynosił 0, można zwolnić przydzielone zasoby natywne. W przeciwnym razie przechodzi w stan uśpienia, wiedząc, że zostanie wybudzony, gdy ostatni użytkownik natywnej alokacji zmniejszy licznik odwołań. Oznacza to, że wątek Looper czeka na postęp innych wątków, ale tylko wtedy, gdy się zamyka. Dzieje się to tylko raz i nie ma wpływu na wydajność, a pozostały kod do korzystania z natywnej alokacji jest w pełni wolny od blokad.

atomicLayout.png

W implementacji jest wiele innych sztuczek i złożoności. Więcej informacji o DeliQueue znajdziesz w kodzie źródłowym.

Optymalizacja: programowanie bez rozgałęzień

Podczas opracowywania i testowania DeliQueue zespół przeprowadził wiele testów porównawczych i dokładnie przeanalizował nowy kod. Jednym z problemów zidentyfikowanych za pomocą narzędzia simpleperf było opróżnianie potoku spowodowane przez kod komparatora Message.

Standardowy komparator używa skoków warunkowych, a warunek decydujący o tym, który z elementów Message jest pierwszy, został uproszczony poniżej:

static int compareMessages(@NonNull Message m1, @NonNull Message m2) {
    if (m1 == m2) {
        return 0;
    }

    // Primary queue order is by when.
    // Messages with an earlier when should come first in the queue.
    final long whenDiff = m1.when - m2.when;
    if (whenDiff > 0) return 1;
    if (whenDiff < 0) return -1;

    // Secondary queue order is by insert sequence.
    // If two messages were inserted with the same `when`, the one inserted
    // first should come first in the queue.
    final long insertSeqDiff = m1.insertSeq - m2.insertSeq;
    if (insertSeqDiff > 0) return 1;
    if (insertSeqDiff < 0) return -1;

    return 0;
}

Ten kod jest kompilowany do skoków warunkowych (instrukcje b.le i cbnz). Gdy procesor napotyka rozgałęzienie warunkowe, nie wie, czy zostanie ono wykonane, dopóki nie zostanie obliczony warunek. Nie wie więc, którą instrukcję odczytać jako następną, i musi zgadywać, korzystając z techniki zwanej przewidywaniem rozgałęzień. W przypadku wyszukiwania binarnego kierunek rozgałęzienia będzie nieprzewidywalnie inny na każdym etapie, więc prawdopodobnie połowa prognoz będzie błędna. W algorytmach wyszukiwania i sortowania (np. w algorytmie używanym w kopcu minimalnym) przewidywanie rozgałęzień jest często nieskuteczne, ponieważ koszt błędnego odgadnięcia jest większy niż korzyść wynikająca z prawidłowego odgadnięcia. Gdy predyktor rozgałęzień się pomyli, musi odrzucić pracę wykonaną po założeniu przewidywanej wartości i zacząć od nowa od ścieżki, która została faktycznie wybrana. Nazywa się to opróżnianiem potoku.

Aby znaleźć ten problem, przeprowadziliśmy profilowanie naszych testów porównawczych za pomocą licznika wydajności branch-misses, który rejestruje ślady stosu, w których predyktor rozgałęzień błędnie przewiduje wynik. Wyniki wizualizowaliśmy za pomocą Google pprof, jak pokazano poniżej:

flame2.png

Przypomnij sobie, że oryginalny kod MessageQueue używał listy jednokierunkowej do kolejki uporządkowanej. Wstawianie będzie polegać na przechodzeniu przez listę w kolejności posortowanej w ramach wyszukiwania liniowego, zatrzymywaniu się na pierwszym elemencie, który znajduje się za punktem wstawienia, i łączeniu nowego węzła Message przed nim. Aby usunąć głowicę, wystarczyło ją odłączyć. DeliQueue używa stogu minimalnego, w którym mutacje wymagają zmiany kolejności niektórych elementów (przesiewania w górę lub w dół) o złożoności logarytmicznej w zrównoważonej strukturze danych, w której każde porównanie ma równe szanse na skierowanie przejścia do lewego lub prawego elementu podrzędnego. Nowy algorytm jest asymptotycznie szybszy, ale ujawnia nowy wąskie gardło, ponieważ kod wyszukiwania zatrzymuje się z powodu błędów rozgałęzienia przez połowę czasu.

Zauważyliśmy, że błędy w przewidywaniu rozgałęzień spowalniają nasz kod sterty, więc zoptymalizowaliśmy go za pomocą programowania bez rozgałęzień:

// Branchless Logic
static int compareMessages(@NonNull Message m1, @NonNull Message m2) {
    final long when1 = m1.when;
    final long when2 = m2.when;
    final long insertSeq1 = m1.insertSeq;
    final long insertSeq2 = m2.insertSeq;

    // signum returns the sign (-1, 0, 1) of the argument,
    // and is implemented as pure arithmetic:
    // ((num >> 63) | (-num >>> 63))
    final int whenSign = Long.signum(when1 - when2);
    final int insertSeqSign = Long.signum(insertSeq1 - insertSeq2);

    // whenSign takes precedence over insertSeqSign,
    // so the formula below is such that insertSeqSign only matters
    // as a tie-breaker if whenSign is 0.
    return whenSign * 2 + insertSeqSign;
}

Aby zrozumieć optymalizację, dezasembluj 2 przykłady w Compiler Explorer i użyj LLVM-MCA, czyli symulatora procesora, który może generować szacowany harmonogram cykli procesora.

The original code:
Index     01234567890123
[0,0]     DeER .    .  .   sub  x0, x2, x3
[0,1]     D=eER.    .  .   cmp  x0, #0
[0,2]     D==eER    .  .   cset w0, ne
[0,3]     .D==eER   .  .   cneg w0, w0, lt
[0,4]     .D===eER  .  .   cmp  w0, #0
[0,5]     .D====eER .  .   b.le #12
[0,6]     . DeE---R .  .   mov  w1, #1
[0,7]     . DeE---R .  .   b    #48
[0,8]     . D==eE-R .  .   tbz  w0, #31, #12
[0,9]     .  DeE--R .  .   mov  w1, #-1
[0,10]    .  DeE--R .  .   b    #36
[0,11]    .  D=eE-R .  .   sub  x0, x4, x5
[0,12]    .   D=eER .  .   cmp  x0, #0
[0,13]    .   D==eER.  .   cset w0, ne
[0,14]    .   D===eER  .   cneg w0, w0, lt
[0,15]    .    D===eER .   cmp  w0, #0
[0,16]    .    D====eER.   csetm        w1, lt
[0,17]    .    D===eE-R.   cmp  w0, #0
[0,18]    .    .D===eER.   csinc        w1, w1, wzr, le
[0,19]    .    .D====eER   mov  x0, x1
[0,20]    .    .DeE----R   ret

Zwróć uwagę na 1 gałąź warunkową, b.le, która pozwala uniknąć porównywania pól insertSeq, jeśli wynik jest już znany z porównania pól when.

The branchless code:
Index     012345678
[0,0]     DeER .  .   sub       x0, x2, x3
[0,1]     DeER .  .   sub       x1, x4, x5
[0,2]     D=eER.  .   cmp       x0, #0
[0,3]     .D=eER  .   cset      w0, ne
[0,4]     .D==eER .   cneg      w0, w0, lt
[0,5]     .DeE--R .   cmp       x1, #0
[0,6]     . DeE-R .   cset      w1, ne
[0,7]     . D=eER .   cneg      w1, w1, lt
[0,8]     . D==eeER   add       w0, w1, w0, lsl #1
[0,9]     .  DeE--R   ret

W tym przypadku implementacja bez rozgałęzień wymaga mniejszej liczby cykli i instrukcji niż nawet najkrótsza ścieżka w kodzie z rozgałęzieniami – jest lepsza we wszystkich przypadkach. Szybsze wdrożenie i wyeliminowanie błędnie przewidzianych rozgałęzień spowodowało 5-krotny wzrost wydajności w niektórych naszych testach porównawczych.


Ta technika nie zawsze ma jednak zastosowanie. Podejścia bez rozgałęzień zwykle wymagają wykonania pracy, która zostanie odrzucona, a jeśli rozgałęzienie jest w większości przypadków przewidywalne, zmarnowana praca może spowolnić działanie kodu. Ponadto usunięcie gałęzi często powoduje zależność danych. Nowoczesne procesory wykonują wiele operacji w jednym cyklu, ale nie mogą wykonać instrukcji, dopóki nie będą gotowe dane wejściowe z poprzedniej instrukcji. Procesor może natomiast spekulować na temat danych w gałęziach i wykonywać pracę z wyprzedzeniem, jeśli gałąź zostanie prawidłowo przewidziana.

Testowanie i weryfikacja

Sprawdzanie poprawności algorytmów bez blokad jest niezwykle trudne.

Oprócz standardowych testów jednostkowych do ciągłej weryfikacji podczas programowania napisaliśmy też rygorystyczne testy obciążeniowe, aby sprawdzić niezmienniki kolejki i spróbować wywołać wyścigi danych, jeśli takie istniały. W naszych laboratoriach testowych możemy uruchamiać miliony instancji testowych na emulowanych urządzeniach i na prawdziwym sprzęcie.

Dzięki instrumentacji Java ThreadSanitizer (JTSan) mogliśmy używać tych samych testów do wykrywania niektórych wyścigów o dane w naszym kodzie. JTSan nie znalazł w DeliQueue żadnych problematycznych wyścigów o dane, ale – co zaskakujące – wykrył 2 błędy współbieżności w platformie Robolectric, które szybko naprawiliśmy.

Aby ulepszyć nasze możliwości debugowania, stworzyliśmy nowe narzędzia analityczne. Poniżej znajduje się przykład problemu w kodzie platformy Android, w którym jeden wątek przeciąża drugi wątek za pomocą Message, co powoduje duże zaległości widoczne w Perfetto dzięki dodanej przez nas funkcji instrumentacji MessageQueue.

workspace.png

Aby włączyć śledzenie MessageQueue w procesie system_server, w konfiguracji Perfetto umieść te informacje:

data_sources {
  config {
    name: "track_event"
    target_buffer: 0  # Change this per your buffers configuration
    track_event_config {
      enabled_categories: "mq"
    }
  }
}

Wpływ

DeliQueue zwiększa wydajność systemu i aplikacji, eliminując blokady z MessageQueue.

  • Testy syntetyczne: wielowątkowe wstawianie do zajętych kolejek jest nawet 5000 razy szybsze niż w przypadku starszego typu MessageQueue dzięki ulepszonej współbieżności (stos Treiber) i szybszemu wstawianiu (kopiec minimalny).
  • W śladach Perfetto uzyskanych od wewnętrznych beta testerów widzimy o 15% krótszy czas, jaki główny wątek aplikacji spędza na rywalizacji o blokadę.
  • Na tych samych urządzeniach testowych zmniejszona rywalizacja o blokady prowadzi do znacznej poprawy wrażeń użytkownika, np.:
    • –4% utraconych klatek w aplikacjach.
    • –7,7% pominiętych klatek w interakcjach z interfejsem systemu i programem uruchamiającym.
    • –9, 1% – czas od uruchomienia aplikacji do narysowania pierwszej klatki (95 percentyl).

Dalsze kroki

DeliQueue jest wdrażana w aplikacjach na Androida 17. Deweloperzy aplikacji powinni zapoznać się z artykułem na blogu dla deweloperów aplikacji na Androida o przygotowywaniu aplikacji do nowego trybu bez blokad MessageQueue, aby dowiedzieć się, jak testować aplikacje.

Źródła

[1] Treiber, R.K., 1986. Programowanie systemowe: radzenie sobie z równoległością. International Business Machines Incorporated, Thomas J. Watson Research Center.

[2] Goetz, B., Peierls, T., Bloch, J., Bowbeer, J., Holmes, D., & Lea, D. (2006). Java Concurrency in Practice. Addison-Wesley Professional.

Autor:

Czytaj dalej