[출근길 공부 011] Android 17 MessageQueue 성능 개선

안드로이드 17에서 DeliQueue를 도입함으로써 성능 개선을 이루어냈다는 포스팅이 올라왔습니다.
(https://android-developers.googleblog.com/2026/02/under-hood-android-17s-lock-free.html?m=1)

기존 MessageQueue는 내부적으로 단일 모니터 락으로 상태를 보호하는 priority queue였습니다. 백그라운드 스레드에서 메시지를 enqueue할 때와 메인 스레드(Looper)에서 메시지를 dequeue할 때 동일한 락을 공유했기 때문에, 백그라운드 스레드가 락을 잡고 있는 동안 메인 스레드가 블로킹되는 상황이 발생했습니다.

더 심각한 건 우선순위 역전입니다. 저우선순위 백그라운드 스레드가 MessageQueue에 enqueue하기 위해 락을 잡은 상태에서 os 스케줄러는 더 높은 우선순위를 CPU에 할당하므로, 저우선순위 스레드는 CPU를 빼앗깁니다. 고우선순위 UI 스레드는 락 해제를 기다리지만 정작 락을 가진 저우선순위 스레드는 CPU에 할당되지 못해 jank frame이 발생하곤 했습니다.

Android 17에서는 이 문제를 해결하기 위해 lock-free 자료구조인 DeliQueue를 도입했습니다. DeliQueue는 메시지의 enqueue와 dequeue를 분리하는 것이 핵심입니다.

크게 Treiber Stack과 Min-Heap 두 가지 모듈로 구성됩니다.

Treiber Stack (Lock-Free 삽입 계층)

Treiber Stack은 1986년 R.K. Treiber가 제안한 고전적인 lock-free 스택 자료구조입니다. 내부적으로 AtomicReference를 사용한 CAS(Compare-And-Swap) 루프로 head 포인터를 갱신하여 멀티스레드 안전성을 보장합니다.
동작 원리는 다음과 같습니다:

• Push: 새 노드를 생성하고, 현재 head를 읽어 새 노드의 next로 연결한 뒤, CAS로 head를 새 노드로 교체합니다. CAS가 실패하면(다른 스레드가 먼저 head를 바꿨다면) 성공할 때까지 루프를 돌며 재시도합니다.

• Lock-free 보장: 어떤 스레드가 지연되더라도 다른 스레드는 항상 진행할 수 있습니다. 모니터 락처럼 하나의 스레드가 다른 스레드의 진행을 완전히 차단하는 상황이 원천적으로 발생하지 않습니다.

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;
    }
}

이를 통해 어떤 프로듀서 스레드든 락 경합 없이 O(1)에 메시지를 삽입할 수 있게 됩니다.

추가로 ARM64 아키텍처 레벨에서의 최적화도 적용되었습니다. 구세대 ARM64 CPU에서는 LL/SC(Load-Link/Store-Conditional) 루프로 atomic을 구현했지만, ARMv8.1의 LSE(Large System Extensions)를 지원하는 최신 CPU에서는 하드웨어 수준의 CAS 명령어를 직접 사용하여 고경합 상황에서 ~3배의 성능 향상을 달성했습니다.

// 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
    
// ARMv8.1 LSE atomic example
ldadd   x0, x1, [x2]    // Atomic load-add.
                        // Faster, no loop required.

Local Min Heap

Min-Heap은 배열 기반의 이진 힙(Binary Heap) 자료구조로, 메시지의 실행 시각(when) 기준으로 가장 이른 메시지가 루트(최상위)에 위치하도록 정렬을 보장합니다.

• 독점 소유: 이 Min-Heap 공간은 오직 Looper 스레드(메인 스레드)만 접근할 수 있습니다. 다른 스레드는 절대 이곳을 건드릴 수 없으므로, 원자적 연산이나 락이 전혀 필요 없습니다. 일반적인 단일 스레드 프로그래밍처럼 최고 속도로 동작합니다.

• 자료구조 알고리즘 (Min-Heap): * 기존 MessageQueue는 단일 연결 리스트를 순회하며 메시지를 삽입했기에 최악의 경우 O(N)의 시간 복잡도를 가졌습니다.

  • 새로운 구조는 이진 트리 형태의 Min-heap 배열을 사용합니다. 부모 노드가 항상 자식 노드보다 우선순위가 높도록 유지하는 자료구조로, 삽입과 삭제 모두 O(log N)을 보장하여 큐에 메시지가 수만 개 쌓여도 성능 저하가 없습니다.

• Bulk Transfer (일괄 이동): Looper 스레드가 깨어나면 Treiber Stack의 위에서부터 아래로 쭉 훑으며(순회) 새로 추가된 메시지들을 한 번에 Min-Heap으로 옮겨 담으면서 정렬을 수행합니다.

• branchless programming (branch misprediction 방지): Min-Heap 내부에서 sift-up/sift-down 시 메시지 비교가 빈번하게 발생하는데, 기존의 조건 분기 기반 comparator는 branch misprediction으로 인한 파이프라인 플러시가 빈번하게 발생했습니다. 이를 해결하기 위해 Long.signum()의 순수 산술 연산((num >> 63) | (-num >>> 63))을 활용한 branchless comparator를 도입하여, 조건 분기 없이 비교 결과를 계산합니다. 이 최적화로 일부 벤치마크에서 5배의 성능 향상을 달성했습니다.

// 기존 conditional 로직을 갖고있던 comparator
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;
}

// 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;
}

이러한 두 가지 모듈을 나눠서 구현함으로써 기존의 락경합이 발생하던 문제를 개선할 수 있었던 것으로 보입니다.