Details: SlotTable과 Link Table
Compose Runtime의 SlotTable은 어떻게 변화하고 있나요?
Compose Runtime의 핵심 자료구조인 SlotTable은 갭 버퍼(gap buffer)에서 영감을 받아 설계되었습니다. 그런데 AOSP 코드를 살펴보면, Android 팀이 현재 이 SlotTable의 내부 구현을 갭 버퍼에서 링크 테이블(Link Table) 로 마이그레이션하고 있음을 확인할 수 있습니다.
갭 버퍼(Gap Buffer)
갭 버퍼는 텍스트 에디터에서 문자 시퀀스를 효율적으로 관리하기 위해 고안된 자료구조입니다. 연속된 메모리 블록을 유지하되, 현재 편집 위치에 "갭(빈 공간)"을 두어 해당 위치에서의 삽입과 삭제를 O(1)에 가깝게 처리합니다. 단, 편집 위치가 멀리 이동할 때는 갭을 이동시키는 비용이 발생합니다.
Compose Runtime은 이 구조에서 영감을 받아 Composition 상태를 연속 메모리에 저장하고, 상태를 읽고 쓸 때 슬롯 포인터를 이동하며 효율적으로 접근합니다. SlotTable을 처음 구축하는 과정에는 이 방식이 뛰어난 성능을 발휘합니다.
링크 테이블(Link Table)로의 마이그레이션
링크 테이블은 연결된 노드로 데이터를 구성하는 자료구조로, 요소의 삽입, 삭제, 재배치를 더 효율적으로 처리할 수 있습니다.
이 마이그레이션의 목표는 다음과 같습니다.
SlotTable 편집 성능 향상: 이미 구축된 SlotTable을 수정(편집)하는 과정에서 갭 버퍼의 갭 이동 비용 없이 효율적으로 노드를 조작할 수 있습니다.
현재 구축 효율 유지: 링크 테이블로 변경하면서도 SlotTable을 처음 만들 때의 효율성은 그대로 보존합니다.
두 자료구조 비교
특성 | 갭 버퍼(Gap Buffer) | 링크 테이블(Link Table) |
|---|---|---|
메모리 구조 | 연속 메모리 블록 | 링크로 연결된 노드 |
초기 구축 | 효율적 | 효율적 |
편집(삽입/삭제) | 갭 이동 비용 발생 | 노드 재연결로 효율적 처리 |
임의 접근 | 빠름(인덱스 기반) | 상대적으로 느림(순회 필요) |
Compose Runtime의 SlotTable은 리컴포지션 시 지속적으로 편집되는 자료구조이므로, 편집 효율이 높은 링크 테이블로의 전환은 반복적인 상태 업데이트 성능을 개선하는 데 의미 있는 변화입니다.
요약
- Q) Compose Runtime이 SlotTable에 갭 버퍼 자료구조를 사용한 이유는 무엇이며, 링크 테이블로 마이그레이션하는 이유는 무엇인가요?
갭 버퍼를 사용한 이유:
갭 버퍼는 순차적 읽기/쓰기가 빈번한 상황에서 뛰어난 성능을 발휘합니다. Composition을 처음 구축할 때는
@Composable함수들을 순서대로 실행하며 슬롯 테이블에 상태를 순차적으로 기록하므로, 갭 버퍼의 연속 메모리 특성이 효율적으로 작동합니다.링크 테이블로 마이그레이션하는 이유:
리컴포지션 시에는 이미 구축된 SlotTable에서 특정 부분을 삽입, 삭제, 재배치해야 합니다. 갭 버퍼는 이러한 편집 작업 시 갭을 이동시키는 추가 비용이 발생합니다. 링크 테이블은 노드 간 연결을 재구성하는 방식으로 이 편집 작업을 더 효율적으로 처리할 수 있어, 복잡한 리컴포지션이 많은 앱에서 성능 개선이 기대됩니다.