Slot Table 与 Gap Buffer：Compose 数据结构深度解析

Slot Table 是 Compose Runtime 的核心数据结构，它存储了整个 UI 树的状态信息。本文将深入探索 Slot Table 的内部实现，理解 Gap Buffer 算法如何实现高效的增量更新，以及 Groups 和 Slots 的存储机制。

I. 为什么需要 Slot Table？

1.1 传统方式的问题

如果使用常规的树形数据结构存储 UI 状态，会面临以下问题：

• 内存分散：每个节点是独立对象，内存不连续，缓存效率低
• 更新成本高：插入/删除节点需要调整大量指针
• 遍历慢：需要通过指针跳转，无法利用 CPU 预取

1.2 Slot Table 的设计目标

• 内存紧凑：使用连续数组存储，提高缓存命中率
• 高效更新：使用 Gap Buffer 实现 O(1) 局部插入
• 快速遍历：线性扫描，CPU 预取友好
• 增量更新：只修改变化的部分

II. Gap Buffer 算法详解

2.1 什么是 Gap Buffer

Gap Buffer 是一种专为高效局部编辑设计的数据结构，广泛用于文本编辑器（如 Emacs）。其核心思想是：在数据中维护一个「间隙」(Gap)，插入操作在间隙位置进行，复杂度为 O(1)。

2.2 Gap 的移动

当需要在非 Gap 位置编辑时，需要先移动 Gap：

III. Slot Table 的结构

3.1 双数组设计

Slot Table 使用两个并行的数组：

class SlotTable {
    // Group 信息数组 (每个 Group 占用多个 Int)
    internal var groups: IntArray
    
    // Slot 数据数组 (存储实际的状态值)
    internal var slots: Array<Any?>
    
    // Group Gap 信息
    internal var groupsSize: Int        // 有效 Group 数量
    internal var groupGapStart: Int    // Gap 起始位置
    internal var groupGapLen: Int      // Gap 长度
    
    // Slot Gap 信息
    internal var slotsSize: Int
    internal var slotGapStart: Int
    internal var slotGapLen: Int
}

3.2 Group 的存储格式

每个 Group 在 groups 数组中占用 5 个 Int：

// Group 索引计算
private const val GROUP_FIELDS_SIZE = 5

fun groupIndexToAddress(index: Int): Int = 
    index * GROUP_FIELDS_SIZE

// 读取 Group 信息
fun key(groupIndex: Int): Int = 
    groups[groupIndexToAddress(groupIndex)]

fun groupSize(groupIndex: Int): Int = 
    groups[groupIndexToAddress(groupIndex) + 3]

3.3 Slots 的存储

Slots 数组存储每个 Group 的实际数据：

IV. SlotWriter：写入模式

4.1 写入器的工作原理

组合和重组时，通过 SlotWriter 修改 Slot Table：

class SlotWriter(
    private val table: SlotTable
) {
    // 当前位置（光标）
    private var currentGroup = 0
    private var currentSlot = 0
    
    // 开始一个 Group
    fun startGroup(key: Int) {
        if (inserting) {
            // 初始组合：插入新 Group
            insertGroup(key)
        } else {
            // 重组：验证 key 匹配
            require(key(currentGroup) == key)
        }
        currentGroup++
    }
    
    // 结束 Group
    fun endGroup(): Int {
        // 返回该 Group 的索引
        return currentGroup
    }
    
    // 写入 Slot 数据
    fun update(value: Any?) {
        slots[currentSlot++] = value
    }
    
    // 跳过不变的 Group
    fun skipGroup(): Int {
        val count = groupSize(currentGroup)
        currentGroup += count
        return count
    }
}

4.2 插入操作

private fun insertGroup(key: Int) {
    // 1. 如果 Gap 不在当前位置，移动 Gap
    if (groupGapStart != currentGroup) {
        moveGroupGapTo(currentGroup)
    }
    
    // 2. 检查是否需要扩容
    if (groupGapLen == 0) {
        growGroups()
    }
    
    // 3. 在 Gap 位置写入 Group 信息
    val address = groupIndexToAddress(currentGroup)
    groups[address] = key
    groups[address + 1] = 0  // groupInfo
    groups[address + 2] = parent
    groups[address + 3] = 0  // size (稍后更新)
    groups[address + 4] = currentSlot  // dataAnchor
    
    // 4. 收缩 Gap
    groupGapStart++
    groupGapLen--
}

4.3 Gap 移动的实现

private fun moveGroupGapTo(index: Int) {
    val gapStart = groupGapStart
    val gapLen = groupGapLen
    
    if (index < gapStart) {
        // Gap 向左移动：将 [index, gapStart) 复制到 Gap 后面
        val count = gapStart - index
        arraycopy(
            src = groups,
            srcPos = groupIndexToAddress(index),
            dst = groups,
            dstPos = groupIndexToAddress(index + gapLen),
            len = count * GROUP_FIELDS_SIZE
        )
    } else {
        // Gap 向右移动：将 [gapStart + gapLen, index) 复制到 Gap 前面
        val count = index - gapStart - gapLen
        arraycopy(
            src = groups,
            srcPos = groupIndexToAddress(gapStart + gapLen),
            dst = groups,
            dstPos = groupIndexToAddress(gapStart),
            len = count * GROUP_FIELDS_SIZE
        )
    }
    groupGapStart = index
}

V. SlotReader：读取模式

5.1 读取器的设计

class SlotReader(
    private val table: SlotTable
) {
    // 当前读取位置
    var currentGroup: Int = 0
        private set
    
    // 读取下一个 Slot 值
    fun next(): Any? = slots[currentSlot++]
    
    // 获取当前 Group 的 key
    fun groupKey(): Int = key(currentGroup)
    
    // 跳过当前 Group 及其所有子 Group
    fun skipGroup(): Int {
        val count = groupSize(currentGroup)
        currentGroup += count
        return count
    }
    
    // 检查是否还有更多 Group
    fun isGroupEnd(): Boolean = 
        currentGroup >= groupsSize
}

5.2 遍历示例

// 遍历所有顶层 Group
fun traverse(table: SlotTable) {
    table.read { reader ->
        while (!reader.isGroupEnd()) {
            val key = reader.groupKey()
            val size = reader.groupSize()
            
            println("Group: key=$key, size=$size")
            
            // 读取该 Group 的所有 Slot 数据
            val slotCount = reader.groupSlotCount()
            for (i in 0 until slotCount) {
                val slot = reader.next()
                println("  Slot: $slot")
            }
            
            // 移动到下一个 Group
            reader.skipToGroupEnd()
        }
    }
}

VI. 实际场景分析

6.1 初始组合

@Composable
fun Counter() {
    var count by remember { mutableStateOf(0) }
    Text("Count: $count")
}

6.2 重组：状态变化

// 点击按钮后 count 变为 1
count = 1

6.3 条件渲染导致结构变化

@Composable
fun ConditionalContent(showExtra: Boolean) {
    Text("Always")
    if (showExtra) {
        Text("Extra")  // 条件显示
    }
    Text("Footer")
}

VII. 性能分析

7.1 时间复杂度

* 假设 Gap 已在正确位置，否则需要 O(k) 移动 Gap（k 是移动距离）

7.2 空间效率

7.3 为什么适合 Compose？

1. 局部性：重组通常只影响局部区域，Gap Buffer 正好优化这种场景
2. 增量更新：大部分重组不改变结构，只更新 Slot 值
3. 有序遍历：组合/重组都是深度优先遍历，线性扫描效率高
4. 批量操作：一次重组中的多个插入/删除可以合并

VIII. 调试与观察

8.1 使用 Layout Inspector

Android Studio 的 Layout Inspector 可以查看 Composition 结构，实际上就是可视化 Slot Table 中的 Groups。

8.2 打印 Slot Table

// 调试：遍历并打印 Slot Table 结构
fun dumpSlotTable(composition: Composition) {
    val table = (composition as CompositionImpl).slotTable
    
    table.read { reader ->
        var indent = 0
        val stack = mutableListOf<Int>()
        
        while (!reader.isGroupEnd()) {
            val key = reader.groupKey()
            val size = reader.groupSize()
            val slots = reader.groupSlotCount()
            
            println("${"  ".repeat(indent)}Group(key=$key, size=$size, slots=$slots)")
            
            reader.startGroup()
            indent++
            stack.add(reader.currentGroup + size)
            
            while (stack.isNotEmpty() && reader.currentGroup >= stack.last()) {
                stack.removeLast()
                indent--
            }
        }
    }
}

IX. 总结

理解 Slot Table 的工作原理，能够帮助你：

• 理解 Compose 的性能特征
• 优化重组范围，减少结构变更
• debug 复杂的状态问题
• 为 Compose 贡献代码