갭 버퍼에서 링크드 리스트로: Compose가 더 빠른 리컴포지션을 위해 SlotTable을 재설계한 방법

Jetpack Compose는 전체 컴포지션(Composition) 트리를 SlotTable이라는 자료구조에 저장합니다. 모든 컴포저블(Composable) 호출, remember로 기억한 값, 모든 키가 이 테이블 안에 그룹(group)과 슬롯(slot)으로 기록됩니다. 그동안 SlotTable은 텍스트 에디터에서 사용하는 것과 동일한 자료구조인 갭 버퍼(gap buffer)를 사용해 왔습니다. 순차적 연산에는 뛰어난 성능을 보여 주었지만, 리스트, 애니메이션, 조건부 콘텐츠 등 동적 요소가 늘어남에 따라 한 가지 한계가 부각되었습니다. 그룹을 이동하거나 재정렬할 때 대량의 메모리 복사가 필요하다는 점이었습니다. Compose 팀은 SlotTable을 링크드 리스트(linked list) 기반으로 재설계했으며, 이를 통해 리스트 리오더링 같은 연산에서 리컴포지션(Recomposition) 속도가 2배 이상 빨라졌습니다.

이 글에서는 이 아키텍처 전환을 깊이 있게 살펴봅니다. 갭 버퍼가 그룹을 연속 배열에 어떻게 저장하는지, 링크 버퍼(link buffer)가 위치 기반 접근을 포인터 기반 탐색으로 어떻게 대체하는지, SlotTableEditor가 O(1) 이동 및 삭제를 어떻게 달성하는지, 프리 리스트(free list)와 슬롯 버퍼링이 메모리를 어떻게 관리하는지, 그리고 GroupHandle이 지연 위치 해석(lazy position resolution)을 어떻게 구현하는지를 하나씩 다루겠습니다. 이 글은 Compose API 사용법을 안내하는 가이드가 아닙니다. 리컴포지션을 근본적으로 더 빠르게 만든 자료구조 재설계에 대한 심층 탐구입니다.

갭 버퍼(Gap Buffer): 텍스트 에디터에서 컴포지션 트리까지

갭 버퍼는 원래 텍스트 편집을 위해 설계된 자료구조입니다. 텍스트 에디터가 직면하는 문제를 떠올려 보겠습니다. 문서는 문자의 시퀀스이고, 사용자는 어느 위치에서든 삽입하거나 삭제할 수 있습니다. 문자를 평탄한 배열에 저장하면, 중간에 삽입할 때 삽입 지점 이후의 모든 문자를 뒤로 밀어야 합니다. 10만 글자짜리 문서에서 시작 부분 근처에 삽입하면, 거의 10만 개의 문자를 이동시켜야 하는 것입니다.

갭 버퍼는 커서 위치에 빈 영역("갭")을 유지함으로써 이 문제를 해결합니다. 커서 위치에서 삽입하면 갭을 채우는 것에 불과하므로 아무것도 밀어낼 필요가 없습니다. 커서 위치에서 삭제하면 갭이 확장됩니다. 대부분의 텍스트 편집은 순차적으로 이루어집니다. 한 곳에서 타이핑하면 갭이 항상 필요한 위치에 있기 때문입니다. Emacs 같은 에디터가 수십 년간 갭 버퍼를 사용해 온 이유도 바로 이러한 특성에 있습니다.

트레이드오프(trade-off)는 멀리 떨어진 위치로 점프할 때 나타납니다. 갭을 새 커서 위치로 슬라이드시켜야 하며, 이전 위치와 새 위치 사이의 모든 요소를 복사해야 합니다. 편집이 하나의 위치 근처에 집중되는 한 갭은 거의 이동하지 않으며 성능은 뛰어나게 유지됩니다. 이것이 갭 버퍼가 텍스트 에디터를 넘어서 다양한 분야에서 효과적으로 작동하는 이유이기도 합니다. 큰 정렬된 데이터셋에서 수정이 순차적으로 발생하는 모든 워크로드가 동일한 원리의 혜택을 받습니다. 데이터가 평탄하고 연속적인 배열에 저장되어 캐시 친화적(cache friendly)이며, 작업 위치에서의 삽입은 O(1)로 처리됩니다.

Compose가 갭 버퍼를 적용한 방식

기존 Compose의 SlotTable은 컴포지션 데이터를 두 개의 평탄한 배열에 저장합니다.

internal class SlotTable : SlotStorage(), CompositionData {
    var groups = IntArray(0)
    var groupsSize = 0
    var slots = Array<Any?>(0) { null }
    var slotsSize = 0
}

groups 배열은 그룹 메타데이터를 각각 5개의 정수로 구성된 인라인 구조체(Group_Fields_Size = 5)로 저장합니다. 각 그룹에는 키, 그룹 크기, 노드 카운트, 부모 앵커(parent anchor), 그리고 slots 배열을 가리키는 데이터 앵커가 포함됩니다. slots 배열에는 실제로 기억된 값, 컴포저블 노드 참조, 그리고 각 그룹에 연관된 기타 데이터가 저장됩니다.

그룹은 선형으로 정렬되어 있습니다. 부모의 그룹 필드 바로 뒤에 모든 자식의 필드가 배치되어 깊이 우선(depth-first) 레이아웃을 형성합니다. 이러한 구조 덕분에 선형 스캔이 빠르게 수행됩니다. 트리를 처음부터 끝까지 메모리 점프 없이 순차적으로 읽을 수 있기 때문입니다. 그러나 한편으로는 그룹의 정체성이 배열 내 위치에 묶인다는 의미이기도 합니다. 그룹을 이동하려면 데이터를 물리적으로 재배치해야 합니다.

갭 버퍼는 각 배열에 "갭"을 유지합니다. 갭 위치에서의 삽입은 O(1)이지만, 다른 위치에 삽입하려면 먼저 갭을 이동시켜야 하며, 이전 갭 위치와 새 위치 사이의 모든 요소를 복사해야 합니다. 10,000개의 그룹(50,000개의 정수)을 가진 테이블에서 갭을 끝에서 처음으로 이동하면 50,000개의 정수를 모두 복사하게 됩니다.

삭제도 유사하게 동작합니다. 그룹을 제거하면 해당 공간은 갭의 일부가 됩니다. 그러나 갭이 삭제된 그룹에 인접하지 않으면, 먼저 갭을 그곳으로 이동시켜야 합니다. 이 방식은 트리를 순차적으로 탐색하는 최초 컴포지션(initial composition)에서는 잘 동작했습니다. 하지만 리컴포지션은 트리의 어느 부분이든 임의의 순서로 접근할 수 있으며, 리스트 리오더링은 그룹을 먼 거리에 걸쳐 이동시켜야 합니다.

근본적인 문제: 컴포지션 크기에 비례하여 증가하는 배열 복사

1,000개의 아이템을 렌더링하는 Column을 떠올려 보겠습니다. 데이터 소스가 999번째 아이템을 0번 위치로 재정렬한다면, 런타임은 해당 아이템의 그룹(과 모든 슬롯)을 SlotTable의 끝에서 처음으로 이동시켜야 합니다. 갭 버퍼에서는 이 과정이 9단계를 거칩니다.

1. 목적지에 슬롯 공간 삽입: 가장 먼저 수행되는 단계로, 갭을 목적지로 이동시키고 확장하면서 이전 갭 위치와 새 위치 사이의 모든 앵커를 업데이트합니다.
2. 목적지에 그룹 공간 삽입: 그룹 배열에 대해서도 동일한 갭 이동이 필요하며, 역시 요소를 밀어내고 앵커를 업데이트합니다.
3. 그룹 필드를 새 위치로 복사: 그룹의 메타데이터(키, 크기, 노드 카운트, 부모 앵커, 데이터 앵커)가 새로 확보된 공간에 복사됩니다.
4. 슬롯 데이터를 새 위치로 복사: 그룹에 연관된 모든 기억된 값을 새로 확보된 슬롯 공간으로 옮깁니다.
5. 이동된 그룹의 슬롯 위치 앵커 보정: 이동된 블록 내의 모든 그룹이 slots 배열을 가리키는 데이터 앵커를 갖고 있으므로, 슬롯이 이동한 만큼 앵커를 모두 재계산해야 합니다.
6. 이동된 그룹의 외부 앵커 업데이트: 이동된 그룹을 참조하는 외부 Anchor 객체들이 새 배열 위치를 반영하도록 갱신됩니다.
7. 이전 그룹 제거: 원본 그룹 필드(이제 중복된 상태)를 갭으로 덮어씌워 삭제합니다.
8. 부모 앵커 보정: 이전 위치를 참조하던 부모 그룹들이 새 위치를 가리키도록 업데이트되어야 합니다.
9. 이전 슬롯 제거: 원본 슬롯 데이터는 가장 마지막에 삭제됩니다. 이전 위치를 참조하는 그룹들이 먼저 제거되어야 하기 때문입니다.

이 순서가 중요합니다. 슬롯은 그룹보다 먼저 삽입해야 합니다(갭 이동에 유효한 그룹 앵커가 필요하기 때문). 이전 슬롯은 이전 그룹 뒤에 제거해야 합니다(같은 이유). 각 단계는 배열 요소를 밀어내는 작업을 수반하며, 수천 개의 그룹이 있는 테이블에서는 단계마다 수천 번의 정수 복사가 발생합니다. 10개의 아이템만 재정렬해도 수만 번의 복사 연산이 이루어지는 것입니다.

갭 버퍼의 SlotWriter에 구현된 moveGroup 함수를 보면 이 복잡성을 확인할 수 있습니다. 실제 구현을 살펴보겠습니다.

fun moveGroup(offset: Int) {
    val current = currentGroup
    var count = offset
    var groupToMove = current
    while (count > 0) {
        groupToMove += groups.groupSize(
            address = groupIndexToAddress(groupToMove)
        )
        count--
    }

    val moveLen = groups.groupSize(
        address = groupIndexToAddress(groupToMove)
    )
    val dataStart = groups.dataIndex(groupIndexToAddress(groupToMove))
    val dataEnd = groups.dataIndex(
        address = groupIndexToAddress(index = groupToMove + moveLen)
    )
    val moveDataLen = dataEnd - dataStart

    // 1) 목적지에 슬롯 공간 삽입
    insertSlots(moveDataLen, max(currentGroup - 1, 0))

    // 2) 목적지에 그룹 공간 삽입
    insertGroups(moveLen)

    // 3) 그룹을 새 위치로 복사
    groups.copyInto(
        destination = groups,
        destinationOffset = currentAddress * Group_Fields_Size,
        startIndex = moveLocationOffset,
        endIndex = moveLocationOffset + moveLen * Group_Fields_Size,
    )

    // ... 4~9단계가 이어집니다
}

소스 코드의 주석에서 이 순서가 왜 중요한지 설명하고 있습니다. 슬롯 삽입이 먼저 이루어져야 하는 이유는 갭 이동에 유효한 그룹 앵커가 필요하기 때문이고, 슬롯 제거가 마지막에 이루어져야 하는 이유는 이전 위치를 참조하는 그룹들이 먼저 제거되어야 하기 때문입니다. 이러한 종속성의 연쇄 구조 때문에 연산이 본질적으로 순차적이면서 비용이 높을 수밖에 없습니다.

링크 버퍼 SlotTable: 위치 대신 포인터

새로운 SlotTable은 근본적으로 다른 접근 방식을 취합니다. 그룹이 배열에서 어디에 위치하느냐로 트리 내 위치를 결정하는 대신, 각 그룹이 이웃을 가리키는 명시적인 포인터를 갖습니다. 이를 비유하자면 책꽂이(책의 물리적 위치가 순서를 결정)와 클립 체인(각 클립이 테이블 어디에 있든 상관없이 다음 클립에 물리적으로 연결되어 있음)의 차이와 같습니다.

각 그룹은 6개의 정수를 저장합니다. 키, 다음 형제(sibling) 포인터, 부모 포인터, 첫 번째 자식 포인터, 플래그 필드, 슬롯 범위가 그것입니다.

const val SLOT_TABLE_GROUP_SIZE = 6
const val SLOT_TABLE_GROUP_KEY_OFFSET = 0    // 키
const val SLOT_TABLE_GROUP_NEXT_OFFSET = 1   // 다음 형제(sibling)
const val SLOT_TABLE_GROUP_PARENT_OFFSET = 2 // 부모
const val SLOT_TABLE_GROUP_CHILD_OFFSET = 3  // 첫 번째 자식
const val SLOT_TABLE_GROUP_FLAGS_OFFSET = 4  // 플래그
const val SLOT_TABLE_GROUP_SLOTS_OFFSET = 5  // 슬롯 범위

개념적으로 각 그룹은 링크드 리스트의 노드에 해당합니다.

data class Group(
    val key: Int,
    val next: GroupAddress,      // 자식 리스트 내 다음 형제
    val parent: GroupAddress,    // 부모 그룹
    val child: GroupAddress,     // 첫 번째 자식 그룹
    val flags: GroupFlags,       // 비트 패킹된 메타데이터
    val slotRange: SlotRange,    // 기억된 값에 대한 참조
)

핵심적인 차이는 그룹의 트리 내 위치가 배열 내 위치가 아닌 포인터에 의해 결정된다는 점입니다. 42번 그룹이 1,000번 그룹의 자식일 수 있고, 6번 그룹이 42번 그룹의 자식일 수 있습니다. 배열 위치는 무관합니다. 중요한 것은 next, parent, child 필드가 가리키는 대상입니다. 트리에서 그룹을 이동해도 배열 내 데이터를 이동시킬 필요가 없습니다. 포인터만 변경하면 됩니다.

이 그룹들은 에디터와 리더 모두가 사용하는 핵심 데이터 저장소인 SlotTableAddressSpace 안에 존재합니다.

internal class SlotTableAddressSpace(
    var groups: IntArray = newArray(SLOT_TABLE_INITIAL_GROUPS_SIZE),
    var slots: Array<Any?> =
        arrayOfNulls<Any?>(SLOT_TABLE_INITIAL_SLOTS_SIZE),
)

여전히 두 개의 배열을 사용합니다. groups 배열은 6개의 연속된 정수가 하나의 그룹을 구성하는 IntArray이고, slots 배열은 기억된 값을 저장합니다. 그러나 그룹 간의 관계 표현 방식이 근본적으로 달라졌습니다. 갭 버퍼에서는 배열 내 인접성이 부모/자식 관계를 암시했지만, 링크 버퍼에서는 관계가 명시적 포인터로 표현됩니다.