Android 17에서 SDK 37 이상을 타깃으로 하는 앱에 적용되는 락 프리 MessageQueue(DeliQueue)의 설계와 성능 개선, Perfetto로 락 경합을 분석하는 방법을 소개한다.
작성자: Shai Barack, Android Platform Performance Lead 및 Charles Munger, Principal Software Engineer
Android 17에서는 SDK 37 이상을 타깃으로 하는 앱이 MessageQueue의 새로운 구현을 받게 되며, 이 구현은 **락 프리(lock-free)**입니다. 새 구현은 성능을 개선하고 프레임 미스(missed frame)를 줄이지만, MessageQueue의 비공개 필드/메서드에 리플렉션(reflection)으로 접근하는 클라이언트는 동작이 깨질 수 있습니다. 동작 변경과 영향 완화 방법을 더 알아보려면 MessageQueue 동작 변경 문서를 확인하세요. 이 기술 블로그 게시물은 MessageQueue 재아키텍처의 개요와 Perfetto를 사용해 락 경합(lock contention) 문제를 분석하는 방법을 제공합니다.
Looper는 모든 Android 애플리케이션의 UI 스레드를 구동합니다. Looper는 MessageQueue에서 작업을 가져와 Handler로 디스패치하고, 이를 반복합니다. 20년 동안 MessageQueue는 상태를 보호하기 위해 단일 모니터 락(즉, synchronized 코드 블록)을 사용해 왔습니다.
Android 17은 이 구성 요소에 대한 중요한 업데이트를 도입합니다. DeliQueue라는 이름의 락 프리 구현입니다.
이 글에서는 락이 UI 성능에 미치는 영향, Perfetto로 이러한 문제를 분석하는 방법, Android 메인 스레드를 개선하기 위해 사용된 구체적인 알고리즘과 최적화를 설명합니다.
기존 MessageQueue는 단일 락으로 보호되는 우선순위 큐(priority queue)로 동작했습니다. 백그라운드 스레드가 메시지를 게시(post)하는 동안 메인 스레드가 큐 유지보수 작업을 수행 중이면, 백그라운드 스레드가 메인 스레드를 막게(block) 됩니다.
둘 이상의 스레드가 동일한 락을 배타적으로 사용하려고 경쟁할 때 이를 **락 경합(lock contention)**이라고 합니다. 이 경합은 **우선순위 역전(priority inversion)**을 유발해 UI 잔크(jank) 및 기타 성능 문제로 이어질 수 있습니다.
우선순위 역전은 높은 우선순위 스레드(예: UI 스레드)가 낮은 우선순위 스레드를 기다리도록 강제될 때 발생할 수 있습니다. 다음 순서를 생각해 보세요.
낮은 우선순위의 백그라운드 스레드가 작업 결과를 게시하기 위해 MessageQueue 락을 획득합니다.
중간 우선순위 스레드가 실행 가능(runnable) 상태가 되고, 커널 스케줄러가 CPU 시간을 할당하면서 낮은 우선순위 스레드를 선점(preempt)합니다.
높은 우선순위 UI 스레드가 현재 작업을 마치고 큐에서 읽으려 하지만, 낮은 우선순위 스레드가 락을 쥐고 있기 때문에 블록됩니다.
결과적으로 낮은 우선순위 스레드가 UI 스레드를 막고, 중간 우선순위 작업이 이를 더 지연시킵니다.
이런 문제는 Perfetto를 사용해 진단할 수 있습니다. 표준 트레이스에서 모니터 락에 의해 블록된 스레드는 sleeping 상태로 들어가며, Perfetto는 락 소유자를 나타내는 슬라이스(slice)를 보여줍니다.
트레이스 데이터를 쿼리할 때는 “monitor contention with …”로 이름 붙은 슬라이스를 찾으세요. 뒤에는 락을 소유한 스레드 이름과 락이 획득된 코드 위치가 이어집니다.
예로, 카메라 앱에서 사진을 찍은 직후 Pixel 폰에서 홈으로 이동할 때 사용자가 잔크를 경험한 트레이스를 분석해 보겠습니다. 아래는 프레임 미스에 이르기까지의 이벤트를 보여주는 Perfetto 스크린샷입니다.
증상: Launcher 메인 스레드가 프레임 마감 시간을 놓쳤습니다. 60Hz 렌더링에 필요한 16ms 마감을 넘는 18ms 동안 블록되었습니다.
진단: Perfetto에서 메인 스레드가 MessageQueue 락에 의해 블록된 것이 보였습니다. “BackgroundExecutor” 스레드가 락을 소유하고 있었습니다.
근본 원인: BackgroundExecutor는 Process.THREAD_PRIORITY_BACKGROUND(매우 낮은 우선순위)로 실행됩니다. 이 스레드는 긴급하지 않은 작업(앱 사용 제한 확인)을 수행하고 있었습니다. 동시에 중간 우선순위 스레드들이 카메라 데이터 처리를 위해 CPU 시간을 사용하고 있었습니다. OS 스케줄러는 카메라 스레드를 실행하기 위해 BackgroundExecutor 스레드를 선점했습니다.
이 순서로 인해 Launcher의 UI 스레드(높은 우선순위)는 카메라 워커 스레드(중간 우선순위)에 의해 간접적으로 블록되었습니다. 카메라 워커가 Launcher의 백그라운드 스레드(낮은 우선순위)가 락을 풀지 못하게 했기 때문입니다.
PerfettoSQL을 사용하면 특정 패턴에 대해 트레이스 데이터를 쿼리할 수 있습니다. 사용자 디바이스나 테스트에서 수집한 대규모 트레이스 뱅크가 있고, 문제를 보여주는 특정 트레이스를 찾고 싶을 때 유용합니다.
예를 들어, 아래 쿼리는 드롭 프레임(잔크)과 동시에 발생한 MessageQueue 경합을 찾습니다.
sqlINCLUDE 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;
더 복잡한 예로, 여러 테이블에 걸친 트레이스 데이터를 조인해 앱 시작 중의 MessageQueue 경합을 식별할 수 있습니다.
sqlINCLUDE 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;
좋아하는 LLM을 사용해 다른 패턴을 찾는 PerfettoSQL 쿼리를 작성할 수도 있습니다.
Google에서는 BigTrace를 사용해 수백만 개의 트레이스에 대해 PerfettoSQL 쿼리를 실행합니다. 그 과정에서 일화적으로 관찰했던 현상이 실제로 시스템 전반의 문제임을 확인했습니다. 데이터는 MessageQueue 락 경합이 전체 생태계의 사용자에게 영향을 주고 있음을 보여주었고, 근본적인 아키텍처 변경이 필요하다는 점을 뒷받침했습니다.
우리는 MessageQueue 경합 문제를 해결하기 위해, 배타적 락 대신 원자적 메모리 연산(atomic memory operations)으로 공유 상태 접근을 동기화하는 락 프리 자료구조를 구현했습니다. 자료구조 또는 알고리즘이 락 프리라는 것은 다른 스레드의 스케줄링 동작과 무관하게 항상 최소 한 스레드는 진행(progress)할 수 있음을 뜻합니다. 이 속성은 일반적으로 달성하기 어렵고, 대부분의 코드에서는 보통 추구할 가치가 없습니다.
락 프리 소프트웨어는 하드웨어가 제공하는 원자적 Read-Modify-Write 프리미티브에 의존하는 경우가 많습니다.
구세대 ARM64 CPU에서는 atomic이 Load-Link/Store-Conditional(LL/SC) 루프를 사용했습니다. CPU가 값을 로드하고 해당 주소를 표시(mark)합니다. 다른 스레드가 그 주소에 쓰기(write)하면 store가 실패하고, 루프는 재시도합니다. 스레드들이 서로를 기다리지 않고 시도와 성공을 반복할 수 있기 때문에 이 연산은 락 프리입니다.
ARM64 LL/SC 루프 재시도 예:
asmretry: 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
더 새로운 ARM 아키텍처(ARMv8.1)는 Large System Extensions(LSE)를 지원하며 Compare-And-Swap(CAS)나 Load-And-Add 같은 명령을 포함합니다(아래에 예시). Android 17에서는 ART 컴파일러가 LSE 지원 여부를 감지해 최적화된 명령을 생성하도록 지원을 추가했습니다.
asm// ARMv8.1 LSE atomic example ldadd x0, x1, [x2] // Atomic load-add. // Faster, no loop required.
벤치마크에서 CAS를 사용하는 고경합(high-contention) 코드는 LL/SC 변형 대비 약 3배의 속도 향상을 보였습니다.
Java 언어는 java.util.concurrent.atomic을 통해 이러한(그리고 기타 특수 CPU 명령에 기반한) 원자적 프리미티브를 제공합니다.
MessageQueue에서 락 경합을 제거하기 위해, 엔지니어들은 DeliQueue라는 새로운 자료구조를 설계했습니다. DeliQueue는 메시지 삽입과 메시지 처리를 분리합니다.
Message 목록(Treiber 스택): 락 프리 스택입니다. 어떤 스레드든 경합 없이 새 Message를 푸시할 수 있습니다.
우선순위 큐(최소 힙, min-heap): 처리할 Message의 힙입니다. Looper 스레드가 독점적으로 소유하므로(따라서 동기화나 락이 필요 없음) 접근합니다.
Message 목록은 Treiber 스택[1]에 저장됩니다. Treiber 스택은 head 포인터를 업데이트하기 위해 CAS 루프를 사용하는 락 프리 스택입니다.
javapublic 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; } }
이 소스 코드는 Java Concurrency in Practice[2]에 기반하며, 온라인으로 제공되고 퍼블릭 도메인으로 공개되었습니다.
어떤 프로듀서라도 언제든 스택에 새 Message를 푸시할 수 있습니다. 이는 델리 카운터에서 번호표를 뽑는 것과 같습니다. 번호는 도착 시점에 따라 정해지지만, 음식을 받는 순서가 반드시 번호 순서와 일치할 필요는 없습니다. 연결 리스트 스택이기 때문에, 모든 Message는 부분 스택(sub-stack)입니다. head를 추적하고 앞으로 순회하면 어느 시점에서의 메시지 큐 상태도 볼 수 있습니다. 순회 중에 위에 새 Message가 추가되더라도, 그 새 Message들은 보이지 않습니다.
다음에 처리할 Message를 찾기 위해 Looper는 Treiber 스택의 새 Message들을 top에서 시작해 아래로 내려가며, 이전에 처리했던 마지막 Message를 찾을 때까지 순회합니다. Looper가 스택을 내려가는 동안, Message들을 마감 시간(deadline) 순으로 정렬되는 최소 힙에 삽입합니다. Looper가 힙을 독점적으로 소유하므로, 락이나 atomic 없이 Message들을 정렬하고 처리할 수 있습니다.
Looper는 스택을 내려가면서 스택에 쌓인 Message들을 그 이전 노드로 가리키는 링크도 생성해 이중 연결 리스트(doubly-linked list)를 형성합니다. 이 연결 리스트 생성은 안전합니다. 스택 아래 방향으로 향하는 링크는 CAS를 사용하는 Treiber 스택 알고리즘으로 추가되고, 스택 위 방향의 링크는 오직 Looper 스레드만 읽고 수정하기 때문입니다. 이 역방향 링크(back link)는 스택의 임의 위치에서 Message를 O(1) 시간에 제거하는 데 사용됩니다.
이 설계는 프로듀서(큐에 작업을 게시하는 스레드)에게 O(1) 삽입을 제공하고, 컨슈머(Looper)에게는 상각(amortized) O(log N) 처리 비용을 제공합니다.
또한 Message를 정렬하기 위해 최소 힙을 사용하면 기존 MessageQueue의 근본적 결함도 해결됩니다. 기존 구현에서는 Message가 단일 연결 리스트(singly-linked list, head에서 시작)로 유지되었습니다. 기존 구현에서 head 제거는 O(1)이지만, 삽입은 최악의 경우 O(N)으로—과부하 큐에서 확장성이 좋지 않았습니다. 반대로 최소 힙에 대한 삽입과 제거는 로그 스케일로 동작하여 경쟁력 있는 평균 성능을 제공하면서도, 특히 꼬리 지연(tail latency)에서 뛰어납니다.
| 기존(락 기반) MessageQueue | DeliQueue | |
|---|---|---|
| 삽입 | O(N) | 호출 스레드 기준 O(1) / Looper 스레드 기준 O(logN) |
| head 제거 | O(1) | O(logN) |
기존 큐 구현에서는 프로듀서와 컨슈머가 락으로 단일 연결 리스트에 대한 배타 접근을 조율했습니다. DeliQueue에서는 Treiber 스택이 동시 접근을 처리하고, 단일 컨슈머가 자신의 작업 큐를 정렬합니다.
DeliQueue는 락 프리 Treiber 스택과 단일 스레드 최소 힙을 결합한 하이브리드 자료구조입니다. 전역 락 없이 두 구조를 동기화하는 것은 독특한 과제를 만듭니다. 즉, 메시지가 스택에는 물리적으로 존재하지만 큐에서는 논리적으로 제거된 상태일 수 있습니다.
이를 해결하기 위해 DeliQueue는 “tombstoning” 기법을 사용합니다. 각 Message는 스택에서의 위치(전/후 포인터), 힙 배열에서의 인덱스, 제거 여부를 나타내는 boolean 플래그를 추적합니다. Message가 실행 준비가 되면 Looper 스레드는 removed 플래그를 CAS로 설정한 후, 힙과 스택에서 제거합니다.
다른 스레드가 Message를 제거해야 할 때는 즉시 자료구조에서 빼지 않습니다. 대신 다음 단계를 수행합니다.
논리적 제거: CAS로 Message의 제거 플래그를 false에서 true로 원자적으로 설정합니다. Message는 제거 예정이라는 증거로 자료구조에 남아 있으며, 이를 “tombstone”이라고 부릅니다. 제거 플래그가 설정된 Message는, 발견되는 즉시 큐에 더 이상 존재하지 않는 것처럼 취급됩니다.
지연 정리: 자료구조에서의 실제 제거는 Looper 스레드가 맡고, 이후로 지연됩니다. 제거 스레드는 스택이나 힙을 수정하는 대신, Message를 또 다른 락 프리 freelist 스택에 추가합니다.
구조적 제거: 오직 Looper만 힙과 상호작용하거나 스택에서 요소를 제거할 수 있습니다. Looper가 깨어나면 freelist를 비우고 그 안의 Message들을 처리합니다. 각 Message는 스택에서 언링크되고 힙에서 제거됩니다.
이 접근은 힙 관리를 완전히 단일 스레드로 유지합니다. 필요한 동시 연산과 메모리 배리어 수를 최소화해, 크리티컬 패스를 더 빠르고 단순하게 만듭니다.
Java 표준 라이브러리의 Future나 Kotlin의 Job/Deferred 같은 대부분의 동시성 API는 작업이 완료되기 전에 취소하는 메커니즘을 포함합니다. 이러한 클래스의 인스턴스는 기본 작업 단위와 1:1로 대응하며, cancel 호출은 해당 객체와 연관된 특정 연산을 취소합니다.
오늘날의 Android 디바이스는 멀티코어 CPU와 동시(concurrent) 세대별 가비지 컬렉션을 갖습니다. 하지만 Android가 처음 개발되던 시기에는 작업 단위마다 객체 하나를 할당하는 비용이 너무 컸습니다. 그 결과 Android의 Handler는 removeMessages의 여러 오버로드를 통한 취소를 지원합니다. 특정 Message 하나를 제거하는 대신, 지정된 조건과 일치하는 모든 Message를 제거합니다. 실무적으로 이는 removeMessages가 호출되기 전에 삽입된 모든 Message를 순회하며 일치하는 것들을 제거해야 한다는 뜻입니다.
전방 순회 시 스레드가 필요로 하는 순서 있는 ordered atomic 연산은 단 하나, 스택 head를 읽는 것입니다. 그 후에는 일반 필드 읽기만으로 다음 Message를 찾습니다. Looper 스레드가 Message를 제거하면서 next 필드를 수정하면, Looper의 쓰기와 다른 스레드의 읽기는 동기화되지 않아 데이터 레이스가 됩니다. 보통 데이터 레이스는 메모리 누수, 무한 루프, 크래시, 프리즈 등 심각한 문제를 일으키는 버그입니다. 하지만 Java 메모리 모델에서는 특정 좁은 조건에서 데이터 레이스가 무해(benign)할 수 있습니다. 예를 들어 다음과 같은 스택이 있다고 합시다.
우리는 head를 원자적으로 읽어 A를 봅니다. A의 next 포인터는 B를 가리킵니다. 동시에 B를 처리하는 동안 Looper가 B와 C를 제거해 A가 C를, 이어서 D를 가리키도록 업데이트할 수도 있습니다.
B와 C는 논리적으로 제거됐더라도, B는 여전히 C를, C는 D를 가리키는 next 포인터를 유지합니다. 읽는 스레드는 분리된 제거 노드들을 계속 순회하다가, 결국 D에서 살아있는 스택에 다시 합류합니다.
순회와 제거 사이의 레이스를 처리하도록 DeliQueue를 설계함으로써, 안전한 락 프리 반복(iteration)을 허용합니다.
Looper는 native 할당에 의해 뒷받침되며, Looper가 종료(quit)되면 수동으로 해제해야 합니다. 다른 스레드가 Looper가 종료하는 동안 Message를 추가하고 있다면, 해제된 native 할당을 사용하게 되어 메모리 안전 위반이 발생할 수 있습니다. 우리는 원자 변수의 한 비트를 Looper 종료 여부를 표시하는 데 사용하는 **태그된 refcount(tagged refcount)**로 이를 방지합니다.
native 할당을 사용하기 전에 스레드는 refcount atomic을 읽습니다. 종료 비트가 설정되어 있으면 Looper가 종료 중이므로 native 할당을 사용하면 안 된다는 값을 반환합니다. 설정되어 있지 않다면 CAS로 native 할당을 사용하는 활성 스레드 수를 증가시키려고 시도합니다. 필요한 작업을 수행한 뒤 카운트를 감소시킵니다. 증가 후 감소 전에 종료 비트가 설정되었고, 감소 결과 카운트가 0이 되면 Looper 스레드를 깨웁니다.
Looper 스레드가 종료할 준비가 되면 CAS로 atomic에 종료 비트를 설정합니다. refcount가 0이면 native 할당을 해제해도 됩니다. 그렇지 않으면, 마지막 사용자가 refcount를 감소시킬 때 깨어날 것을 알고 스스로를 파킹(park)합니다. 이 방식은 Looper 스레드가 다른 스레드의 진행을 기다리도록 만들지만, 이는 종료 시점에만 발생합니다. 종료는 한 번만 일어나고 성능 민감도가 낮으며, 나머지 native 할당 사용 코드 경로를 완전히 락 프리로 유지합니다.
구현에는 이 밖에도 많은 트릭과 복잡성이 있습니다. 더 알아보려면 DeliQueue 소스 코드를 검토해 보세요.
DeliQueue를 개발하고 테스트하는 동안 팀은 많은 벤치마크를 실행하고 새 코드를 신중히 프로파일링했습니다. simpleperf 도구로 확인한 한 가지 문제는 Message 비교기(comparator) 코드로 인해 발생하는 파이프라인 플러시(pipeline flush)였습니다.
표준 비교기는 조건부 점프를 사용하며, 어떤 Message가 먼저 오는지 결정하는 조건을 단순화하면 아래와 같습니다.
javastatic 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; }
이 코드는 조건부 점프(b.le 및 cbnz 명령)로 컴파일됩니다. CPU가 조건 분기를 만나면 조건이 계산될 때까지 분기가 타는지 알 수 없으므로, 다음에 어떤 명령을 읽을지 모른 채로 **분기 예측(branch prediction)**이라는 기법으로 추측해야 합니다. 이진 탐색 같은 경우 각 단계에서 분기 방향이 예측 불가능하게 달라지므로, 절반 정도는 예측이 틀릴 가능성이 큽니다. 분기 예측은 탐색/정렬 알고리즘(예: 최소 힙에서 사용되는 알고리즘)에서 종종 효과가 없습니다. 맞히는 이득보다 틀리는 비용이 더 크기 때문입니다. 분기 예측이 틀리면, CPU는 예측된 경로를 가정해 진행한 작업을 버리고 실제로 선택된 경로에서 다시 시작해야 하는데, 이를 파이프라인 플러시라고 합니다.
이 문제를 찾기 위해, 분기 예측 실패를 기록하는 branch-misses 성능 카운터를 사용해 벤치마크를 프로파일링했고, 스택 트레이스를 수집했습니다. 그런 다음 아래처럼 Google pprof로 결과를 시각화했습니다.
원래 MessageQueue 코드는 정렬된 큐로 단일 연결 리스트를 사용했습니다. 삽입은 선형 검색(linear search)으로 정렬 순서를 따라 리스트를 순회하다가 삽입 지점을 지난 첫 요소에서 멈추고, 새 Message를 그 앞에 링크했습니다. head 제거는 head를 언링크하는 것만 필요했습니다. 반면 DeliQueue는 최소 힙을 사용합니다. 변경(mutation) 시 균형 잡힌 자료구조에서 일부 요소를 재정렬(위/아래로 sift)해야 하며, 복잡도는 로그입니다. 이때 비교는 왼쪽/오른쪽 자식으로 향할 확률이 비슷해, 새로운 알고리즘이 점근적으로는 더 빠르지만 탐색 코드가 절반의 시간 동안 분기 미스로 정체되는 새로운 병목을 드러냅니다.
분기 미스가 힙 코드를 느리게 만든다는 사실을 깨닫고, 우리는 브랜치 없는(branch-free) 프로그래밍으로 코드를 최적화했습니다.
java// 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; }
최적화를 이해하려면 Compiler Explorer에서 두 예제를 디스어셈블하고, CPU 시뮬레이터인 LLVM-MCA를 사용해 추정 CPU 사이클 타임라인을 확인해 보세요.
원래 코드:
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
여기에는 조건부 분기 b.le가 하나 있으며, when 비교 결과로 이미 결론이 나면 insertSeq 비교를 피합니다.
브랜치 없는 코드:
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
여기서는 브랜치 없는 구현이 분기 버전의 가장 짧은 경로보다도 더 적은 사이클과 명령을 사용합니다. 모든 경우에 더 낫습니다. 빠른 구현과 분기 미스 제거로 인해 일부 벤치마크에서는 5배 개선이 있었습니다.
하지만 이 기법이 항상 적용 가능한 것은 아닙니다. 브랜치 없는 접근은 보통 버려질 작업을 수행해야 하며, 분기가 대부분 예측 가능한 경우에는 그 낭비가 코드를 더 느리게 만들 수 있습니다. 또한 분기를 제거하면 데이터 의존성이 추가되는 경우가 많습니다. 현대 CPU는 사이클당 여러 연산을 실행할 수 있지만, 이전 명령의 입력이 준비되기 전에는 다음 명령을 실행할 수 없습니다. 반면 CPU는 분기에서 데이터를 추측(speculate)하여, 분기 예측이 맞으면 앞서 실행할 수 있습니다.
락 프리 알고리즘의 정합성(correctness) 검증은 악명 높을 정도로 어렵습니다.
개발 중 지속 검증을 위한 표준 유닛 테스트 외에도, 큐 불변식(invariant)을 검증하고 데이터 레이스를 유발할 수 있다면 유발하려는 엄격한 스트레스 테스트를 작성했습니다. 테스트 랩에서는 에뮬레이트된 디바이스와 실제 하드웨어에서 수백만 개의 테스트 인스턴스를 실행할 수 있었습니다.
Java ThreadSanitizer(JTSan) 계측을 통해 동일한 테스트를 사용해 코드 내 일부 데이터 레이스도 탐지할 수 있었습니다. JTSan은 DeliQueue에서 문제가 되는 데이터 레이스를 찾지 못했지만, 놀랍게도 Robolectric 프레임워크에서 동시성 버그 두 건을 발견했고, 우리는 즉시 이를 수정했습니다.
디버깅 역량을 높이기 위해 새로운 분석 도구를 만들었습니다. 아래는 Android 플랫폼 코드에서 한 스레드가 다른 스레드에 과도하게 Message를 보내 큰 백로그를 유발하는 문제를 보여주는 예입니다. 우리가 추가한 MessageQueue 계측(instrumentation) 기능 덕분에 Perfetto에서 확인할 수 있습니다.
system_server 프로세스에서 MessageQueue 트레이싱을 활성화하려면 Perfetto 설정에 다음을 포함하세요.
textdata_sources { config { name: "track_event" target_buffer: 0 # Change this per your buffers configuration track_event_config { enabled_categories: "mq" } } }
DeliQueue는 MessageQueue에서 락을 제거함으로써 시스템과 앱 성능을 개선합니다.
합성(synthetic) 벤치마크: 개선된 동시성(Treiber 스택)과 더 빠른 삽입(최소 힙) 덕분에, 바쁜 큐(busy queue)에 대한 멀티 스레드 삽입은 기존 MessageQueue 대비 최대 5,000배 더 빠릅니다.
내부 베타 테스터로부터 수집한 Perfetto 트레이스에서, 앱 메인 스레드가 락 경합에 소비하는 시간이 15% 감소한 것을 확인했습니다.
동일한 테스트 디바이스에서, 락 경합 감소는 다음과 같은 사용자 경험 개선으로 이어졌습니다.
DeliQueue는 Android 17에서 앱에 배포(roll out)되고 있습니다. 앱 개발자는 Android Developers 블로그의 “새로운 락 프리 MessageQueue에 대비해 앱 준비하기”를 검토하여 앱을 테스트하는 방법을 확인해야 합니다.
[1] Treiber, R.K., 1986. Systems programming: Coping with parallelism. 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.
