Compose SlotTable Internals

SlotTable이란?

Jetpack Compose의 UI 트리를 저장하기 위한 자료구조

처음 이 정의를 접하면 두 가지 의문이 생긴다. UI 트리가 무엇인지? 그리고 왜 이걸 별도로 저장해야 하는지다. 이에 관해 하나씩 알아보자

 

Compose 코드를 작성하면 `Compose Compiler`는 이 코드를 해석해 결과적으로 다음과 같은 계층 구조를 만들어낸다.

Column {
    Text("안녕")
    Row {
        Text("페토")
    }
}

// UI Tree
Column
├── Text("안녕")
└── Row
    └── Text("페토")

Compose는 상태가 바뀌면 해당 컴포저블을 다시 실행해 화면을 업데이트하며 이것을 리컴포지션(Recomposition)이라 한다. 

var count by remember { mutableStateOf(0) }
Text("$count")

만약 위 코드에서 count가 바뀔 때마다 전체 UI를 처음부터 다시 그리면 어떻게 될까? 버튼 하나의 텍스트를 바꾸려고 화면 전체를 재렌더링한다면? 이는 불필요한 연산이 폭발적으로 늘어난다.

 

Compose는 이러한 문제를 해결하기 위해 이전 실행 결과를 어딘가에 저장해두고 다음 리컴포지션 때 "무엇이 바뀌었는지"만 비교하는데, 그 저장소가 바로 SlotTable이다.

2. SlotTable이 기억하는 것

SlotTable은 세 가지를 기억한다.

 

첫 번째, UI 트리 구조를 기억한다. 예를 들어 `Column` 안에 `Text`와 `Row`가 있고, `Row` 안에 `Icon`과 `Text`가 있다는 계층 관계 전체를 저장한다.

두 번째, `remember` API를 사용해 저장한 값을 기억한다.

세 번째, 식별 정보를 기억한다. 각 컴포저블의 순서, 키, 속성 등 리컴포지션 시 동일한 컴포저블을 추적하기 위한 정보가 이에 해당한다.

 

한 가지 주목할 점은 각 컴포저블의 호출 순서를 저장한다는 점인데 이를 위치 기억법(Positional Memoization)이라 한다.

3. 위치 기억법(Positional Memoization)

먼저 메모이제이션(Memoization)이란 함수가 동일한 입력에 대해 결과를 캐싱해 두고 같은 입력이 들어오면 다시 계산하지 않고 캐싱된 결과를 반환하는 기법이다.

 

Compose는 메모이제이션에 소스 코드에서의 호출 위치를 식별자로 사용한다. 이러한 방식덕에 동일한 함수라도 다른 위치에서 호출되면 Compose Runtime은 이를 다른 노드로 취급한다.

@Composable
fun MyComposable() {
    Text("Hello") // id 1
    Text("Hello") // id 2
    Text("Hello") // id 3
}

Text 컴포저블은 모두 동일한 함수에 동일한 입력이지만 호출 위치가 다르기 때문에 트리에서 각각 고유한 노드로 저장되며 이때 사용되는 핵심 메커니즘이 바로 `SlotTable`이다.

 

Compose Runtime은 Composable 함수의 정보를 `SlotTable`에 저장하며 호출 위치를 키로 사용한다. 자세한 내용은 이전글을 참고바란다.

4. 저장 구조

Column {
    Text("안녕")
    Row {
        Text("페토")
    }
}

예시 코드를 토대로 `SlotTable`에 UI 트리가 저장되는 원리에 대해 이해해 보자. Composable들이 `SlotTable`에 실제로 저장되는 형태를 시각화하면 다음과 같다.

위 그림처럼 저장되는 이유는 `SlotTable`의 내부에 두 개의 배열이 존재하기 때문이다.

internal class SlotTable : CompositionData, Iterable<CompositionGroup> {
    /**
     * 그룹 정보를 저장하는 배열
     */
    var groups = IntArray(0)
        private set

    /**
     * 각 그룹에 대한 슬롯 데이터를 저장하는 배열
     */
    var slots = Array<Any?>(0) { null }
        private set
    //...
}

• `Groups: IntArray` : UI의 설계도에 해당하며 컴포저블 하나에 대한 메타데이터가 다음과 같이 연속된 5개의 정수로 표현된다.

// 그룹 레이아웃
//  0             | 1             | 2             | 3             | 4             |
//  Key           | Group info    | Parent anchor | Size          | Data anchor   |
private const val Group_Fields_Size = 5

• `slots: Array<Any?>` : 실제 데이터 저장소로 `remember`로 기억한 값, 상태(state) 객체, 람다, UI Node(LayoutNode) 등 컴포저블이 생성한 실제 데이터와 객체를 보관한다.

`groups` 배열은 Compose Runtime이 Slots 배열을 어떻게 해석해야 하는지 알려주는 역할을 한다. 일반적으로 객체에 필요한 상태를 캡슐화해 클래스를 단위로 저장하는 것과는 다르게 배열 안에 직접 펼쳐서 저장한 형태인 점이 특이한데, 이 설계는 객체 지향적인 특징보다 성능을 우선시하는 데이터 지향 설계(data-oriented design) 기법이다.

 

이 구조는 객체 할당을 완전히 배제하고 비트 연산을 수행하는 확장 함수를 통해 접근하므로 속도가 매우 빠르다. 예를 들어 특정 그룹이 UI 노드를 나타내는지 확인하려면 다음과 같이 비트 연산을 활용해 처리한다.

private const val NodeBit_Mask = 0b0100_0000_0000_0000__0000_0000_0000_0000
private inline fun IntArray.isNode(address: Int) =
    this[address * Group_Fields_Size + GroupInfo_Offset] and NodeBit_Mask != 0

이러한 방식으로 Compose는 런타임에 수천 개의 그룹을 순회하더라고 GC 부담 없이 처리할 수 있다. 그룹 하나의 구성 요소를 대략적으로 표현하면 다음과 같다.

groups = [
  ...,
  1823,   // [0] Key        
  0b0100, // [1] Group info
  2,      // [2] Parent anchor
  1,      // [3] Size       
  3,      // [4] Data anchor
  ...
]

• `Key` : 컴파일러가 호출 위치마다 부여한 고유 번호로 위치 메모이제이션을 위한 키
• `Group info` : 나는 노드인가, 특별한 속성이 있는가? 같은 플래그 비트들
• `Parent anchor` : 부모 컴포저블이 groups 배열 몇 번째에 있는지(e.g. 내 부모는 groups 배열 2번 위치에 있다)
• `Size` : 내 자식 그룹의 개수
• `Data anchor` : Slots 배열 내에서 그룹의 슬롯 데이터가 시작되는 위치(e.g. 내가 `remember`로 저장한 값은 slots[3]에 있다)

@Composable
fun SlotTableDemo(modifier: Modifier = Modifier) {
	val message = remember { "정페토" }
	Column(
        modifier = modifier
    ) {
        Text(text = "안녕")
        Text(text = "Hello")
    }
}

`SlotTable`에 대한 정보는 컴파일 타임에 접근하여 출력할 수 없기 때문에 리플렉션을 사용해 런타임에 `SlotTable`의 정보를 구한 뒤 출력해 보면 실제로 다음과 같은 데이터가 나온다. 사용한 코드는 이 저장소에서 확인할 수 있다.

========================================
SlotTable Structure
========================================
D  Total groups: 64
Groups array size: 320
========================================

--- 그룹 0 ---
Key          : 100
Group info   : 1
Parent anchor: -1
Size         : 64
Data anchor  : 0

--- 그룹 1 ---
Key          : -96456358
Group info   : 1
Parent anchor: 0
Size         : 63
Data anchor  : 1

... 

--- 그룹 5 ---
Key          : 125
Group info   : 1073741825
Parent anchor: 3
Size         : 59
Data anchor  : 5

그룹 0의 `Parent anchor`가 -1이라는 것은 부모가 없다는 뜻이다. 즉 가장 루트에 있는 컴포저블을 의미하며 `Size`는 64개로 총 그룹 수와 동일하다. 

 

그룹 5의 `Group Info`인 1073741825를 이진수로 변환한 뒤 `NodeBit_Mask`와 AND 연산을 수행하면 결과가 0이 아니므로 그룹 5에 저장된 데이터는 Node임을 알 수 있다.

// Group5의 Group Info
1073741825 = 01000000_00000000_00000000_00000001

// SlotTable의 NodeBit_Mask
1073741824 = 01000000_00000000_00000000_00000000

AND 연산 (두 비트가 모두 1일 때만 1)
  01000000_00000000_00000000_00000001
& 01000000_00000000_00000000_00000000
= 01000000_00000000_00000000_00000000
= 1073741824

`Data anchor`는 해당 그룹의 슬롯 데이터가 시작되는 위치를 가리킨다. 그룹 5의 경우 `slots[5]`부터 시작하며 `LayoutNode`와 `remember`값 등 여러 데이터가 순서대로 저장된다. 실제로 Slot 배열 정보를 출력해 본 결과 `slots[5]`부터 `LayoutNode`가 들어있고 `remember`에 저장한 변수는 `slots[15]`에 있는 것을 확인할 수 있다. 

SlotTable Read/Write

앞서 `SlotTable` 내부에 `groups`와 `slots` 배열이 있다는 걸 살펴봤다. 그런데 두 배열 모두 private set으로 선언되어 있다.

var groups = IntArray(0)
    private set
var slots = Array<Any?>(0) { null }
    private set

그렇다면 Compose Runtime은 SlotTable을 어떻게 읽고 쓰는 걸까? 여기서 등장하는 것이 SlotReader와 SlotWriter다.

`SlotReader`

`SlotReader`는 `SlotTable`을 읽기 위한 커서다. Compose가 리컴포지션을 수행할 때 이전 상태를 확인하기 위해 사용하며 속도를 위해 배열에 대한 직접 참조를 보유하는 경량 객체다.

internal class SlotReader(internal val table: SlotTable) {
    private val groups: IntArray = table.groups
    private var slots: Array<Any?> = table.slots
    // ...
}

Reader는 여러 개가 동시에 열려 있어도 된다. 읽기만 하기 때문에 데이터가 변경될 위험이 없어 동시 접근이 안전하다.

`SlotWriter`

`SlotWriter`는 `SlotTable`을 읽기 쓰기 할 때 사용하는 커서다. 최초 컴포지션이나 변경사항을 적용할 때 동작한다.

internal class SlotWriter(internal val table: SlotTable) {
    private var groups: IntArray = table.groups
    private var slots: Array<Any?> = table.slots
}

한 번에 하나의 Writer만 활성화할 수 있으며, Writer가 활성화된 동안에는 Reader도 사용할 수 없다. 이러한 제약을 통해 트랜잭션 안전성(transactional safety)을 보장한다.

잠금 메커니즘

SlotTable은 openReader()와 openWriter() 메서드를 통해 접근을 직접 관리한다.

fun openReader(): SlotReader {
    if (writer) error("Cannot read while a writer is pending")
    readers++
    return SlotReader(table = this)
}

fun openWriter(): SlotWriter {
    runtimeCheck(!writer) { "Cannot start a writer when another writer is pending" }
    runtimeCheck(readers <= 0) { "Cannot start a writer when a reader is pending" }
    writer = true
    return SlotWriter(table = this)
}

Writer가 열려 있으면 Reader를 열 수 없고, Reader가 열려 있으면 Writer를 열 수 없다. 이 단순한 잠금 메커니즘 덕분에 `SlotTable`의 멀티 스레드 환경에서 데이터 정합성을 유지할 수 있다.

성능의 비결: 갭 버퍼(Gap Buffer) 

`SlotWriter`의 성능은 갭 버퍼(Gap Buffer) 덕분이다. Gap Buffer는 원래 텍스트 에디터에서 고안된 자료구조로 배열에서 삽입과 삭제를 효율적으로 수행하기 위해 설계되었다.

`Gap Buffer`

텍스트 에디터에서 고안한 자료구조로 문서에 글자를 입력하면 커서 위치에 글자가 삽입되는데 만약 이를 배열로 구현한다면 중간에 글자를 삽입할 때마다 뒷자리에 있는 모든 글자를 한 칸씩 밀어야 한다. 만약 100만 글자짜리 문서의 맨 앞에 글자를 추가하면 100만번 복사가 일어나는 셈이다.

 

`Gap Buffer`는 이를 해결하고자 배열 내부에 커서 위치에 맞춰 빈 공간을 추가한다. 다음 그림처럼 `Gap Buffer`는 커서 위치에 빈 공간을 두고 삽입이 발생하면 그 공간을 채우는 방식으로 동작한다.

Compose의 Gap Buffer 활용

`SlotWriter`는 `groups`와 `slots` 두 배열 각각에 Gap Buffer를 적용한다. Gap의 현재 위치는 두 쌍의 변수로 관리된다.

private const val Group_Fields_Size = 5
private var groupGapStart: Int = table.groupsSize
private var groupGapLen: Int = groups.size / Group_Fields_Size - table.groupsSize

private var slotsGapStart: Int = table.slotsSize
private var slotsGapLen: Int = slots.size - table.slotsSize

`groupGapStart`는 Gap이 시작하는 위치, `groupGapLen`은 Gap의 크기다. 새 그룹을 삽입하면 `groupGapStart` 위치에 데이터를 쓰고 `groupGapLen`을 줄인다. 배열을 밀어낼 필요가 없으므로 O(1)이다.

최초 컴포지션이 빠른 이유 

최초 컴포지션에서는 컴포저블이 항상 순차적으로 실행된다. 하향식으로 순차적으로 실행되기 때문에 Gap이 항상 다음 삽입 위치 바로 앞에 있다. 때문에 Gap을 이동시킬 필요가 없으므로 삽입 비용이 사실상 0에 가깝다.

Column {        // 1번째 실행
    Text("안녕") // 2번째 실행
    Row {        // 3번째 실행
        Text("페토") // 4번째 실행
    }
}

Gap 이동 비용

문제는 Gap이 있는 위치가 아닌 다른 위치에 삽입을 해야 할 때다. Gap을 목표 위치까지 먼저 이동 시키고 그 경로에 있는 모든 요소가 복사해야 하는데, 그룹이 1,000개인 컴포지션에서 500번째 위치에 삽입하면 500번의 복사가 발생한다.

 

이는 컴포지션이 커질수록 이 비용이 선형적으로 증가하는 구조적 한계가 있다. 참고로 이 역할은 `moveGroupGapTo()` 함수가 담당한다.

 

이것이 최근 `SlotTable`이 `Gap Buffer`에서 `LinkBuffer`로 교체된 이유다. 드래그 앤 드롭, 조건부 렌더링처럼 트리 중간을 자주 변경하는 동적 UI에서는 Gap 이동 비용이 계속 누적된다.

 

Compose는 이 문제를 해결하기 위해 연결 리스트 기반의 `LinkBuffer`를 도입했으며 이에 대한 자세한 내용은 다음 글에서 다루겠다.

마무리

오늘은 `SlotTable`의 내부 구조에 대해 알아봤다. 그 동안 내가 생각하던 구현 방식과는 다른 새로운 관점들이 많이 보였다. 특히 객체 지향의 이점을 버리고 원시타입 그대로 오직 "5개의 그룹"이라는 규칙을 통해 원시 타입을 그대로 사용함으로써 객체 생성 비용과 GC 오버헤드 같은 문제들을 최적화할 수 있다는 것도 처음 배우게 되었다.

 

Jetpack Compose라는 도구를 사용해 단순히 화면을 그리는 것만이 아닌 새로운 설계 관점의 철학을 배울 수 있어 매우 값진 시간이었다.