Jetpack Compose 내부에 숨겨진 다섯 가지 알고리즘과 자료구조

Jetpack Compose는 겉으로 보기에 UI 툴킷에 불과하지만, 내부적으로는 수십 년에 걸친 컴퓨터 과학 연구 성과를 적극적으로 활용하고 있습니다. 런타임은 텍스트 에디터에서 차용한 자료구조를 사용하여 컴포지션(Composition) 상태를 저장하며, Modifier 시스템은 버전 관리 도구에서 사용하는 알고리즘을 적용하여 노드 체인의 변경점을 비교합니다. 또한 상태 관리 계층은 데이터베이스 엔진에서 사용하는 동시성 모델을 구현합니다. 이러한 기법들은 단순한 이론적 연습이 아니라, Compose가 매 프레임마다 실제로 해결해야 하는 문제에 대한 실용적인 해법입니다.

이 글에서는 Compose 내부에 적용된 다섯 가지 알고리즘과 자료구조를 살펴봅니다. 슬롯 테이블(slot table)을 구동하는 갭 버퍼(gap buffer), Modifier 체인 비교에 적용되는 Myers diff 알고리즘, 데이터베이스 MVCC에서 차용한 스냅샷 격리(snapshot isolation), 플래그와 매개변수를 압축하는 비트 패킹(bit packing), 그리고 명시적 키 없이 remember를 동작하게 해주는 위치 기반 메모이제이션(positional memoization)까지 하나씩 깊이 있게 다루겠습니다.

갭 버퍼(Gap Buffer): 슬롯 테이블 내부의 텍스트 에디터 기법

텍스트 에디터에서 글자를 입력할 때, 커서 위치에 문자를 삽입해야 합니다. 가장 단순한 방식은 삽입 지점 이후의 모든 문자를 한 칸씩 오른쪽으로 밀어내는 것인데, 이 경우 키 입력 한 번에 O(n)의 비용이 듭니다. 텍스트 에디터는 이 문제를 수십 년 전에 갭 버퍼로 해결했습니다. 갭 버퍼란, 배열 내에 커서 위치에 빈 공간("갭")을 유지하는 자료구조입니다. 문자를 삽입하면 갭의 한 슬롯을 채우는 것에 불과하므로 O(1)의 비용으로 처리할 수 있습니다. 커서를 이동하면 갭도 새로운 위치로 옮겨야 하지만, 인접한 위치에서 연속적으로 편집할 때에는 갭이 이미 그 자리에 있으므로 매우 빠릅니다.

Compose의 슬롯 테이블도 본질적으로 동일한 문제에 직면합니다. 컴포지션 과정에서 런타임은 컴포저블 함수가 실행될 때마다 그룹(group)과 관련 데이터 슬롯을 삽입해야 합니다. SlotWriter는 두 개의 병렬 갭 버퍼를 유지합니다. 하나는 그룹(구조적 메타데이터)용이고, 다른 하나는 슬롯(기억된 상태 등 저장 값)용입니다. 각 버퍼는 gapStart 위치와 gapLen 크기를 추적합니다.

현재 갭 위치에서 벗어난 지점에 삽입해야 할 경우, 먼저 갭을 해당 위치로 이동시킵니다. 이 연산은 배열 요소를 이동시켜 빈 공간의 위치를 재배치합니다. 다음은 간소화된 코드입니다.

private fun moveGroupGapTo(index: Int) {
    if (groupGapStart == index) return

    if (index < groupGapStart) {
        // 갭을 왼쪽(뒤쪽)으로 이동: 대상 위치부터 기존 갭까지의 요소를 오른쪽으로 복사
        groups.copyInto(
            destination = groups,
            destinationOffset = index + groupGapLen,
            startIndex = index,
            endIndex = groupGapStart,
        )
    } else {
        // 갭을 오른쪽(앞쪽)으로 이동: 기존 갭 이후 요소를 왼쪽으로 복사
        groups.copyInto(
            destination = groups,
            destinationOffset = groupGapStart,
            startIndex = groupGapStart + groupGapLen,
            endIndex = index + groupGapLen,
        )
    }
    this.groupGapStart = index
}

index < gapStart인 경우, 갭이 뒤쪽으로 이동합니다. 대상 위치와 기존 갭 사이의 요소들이 오른쪽으로 밀려나면서 빈 공간이 확보됩니다. 반대로 index > gapStart인 경우에는 갭이 앞쪽으로 이동하며, 기존 갭 이후의 요소들이 왼쪽으로 이동합니다. 갭이 원하는 위치에 자리를 잡고 나면, 이후의 삽입 연산은 빈 공간을 채우는 것이므로 각각 O(1)로 처리됩니다.

이러한 원리 덕분에 최초 컴포지션(initial composition)이 빠르게 수행됩니다. 런타임이 처음부터 끝까지 순차적으로 그룹을 삽입하므로, 갭이 항상 삽입 지점에 위치해 있어 이동할 필요가 없기 때문입니다. 리컴포지션(Recomposition) 과정에서는 변경된 구간으로 갭을 한 번만 이동시킨 뒤, 해당 구간 내의 모든 업데이트를 O(1)로 처리할 수 있습니다. 즉, 갭 버퍼는 순차적 접근에 최적화된 자료구조이며, Compose의 트리 구조 순회 패턴에 매우 잘 맞는 설계라고 할 수 있습니다.

Myers Diff: Modifier 체인을 위한 최소 편집 스크립트

git diff를 실행할 때 내부적으로 동작하는 알고리즘은 Eugene Myers가 1986년에 발표한 diff 알고리즘입니다. 두 시퀀스가 주어졌을 때, 하나를 다른 하나로 변환하는 데 필요한 최소한의 삽입과 삭제 횟수를 찾아냅니다. Compose는 리컴포지션 과정에서 Modifier가 변경될 때 Modifier.Node 체인을 비교하여 어떤 노드를 삽입하고, 어떤 노드를 제거하고, 어떤 노드를 재사용할지 결정하는 데 바로 이 알고리즘을 활용합니다.

이 알고리즘은 문제를 편집 그래프(edit graph)에서의 최단 경로 탐색으로 모델링합니다. x축이 기존 Modifier 리스트, y축이 새 Modifier 리스트를 나타내는 격자(grid)를 떠올려 보시기 바랍니다. 오른쪽으로 이동하면 기존 요소를 삭제하는 것이고, 아래로 이동하면 새 요소를 삽입하는 것입니다. 대각선으로 이동하면 두 요소가 일치하는 것이므로 비용 없이 유지할 수 있습니다. 좌측 상단에서 우측 하단까지의 최단 경로가 바로 최소 편집 스크립트(minimum edit script)를 의미합니다.