From Gap Buffer to Linked List: How Compose Rewrote Its SlotTable for Faster Recomposition

Jetpack Compose stores your entire composition tree in a data structure called the SlotTable. Every composable call, every remembered value, every key is recorded as groups and slots in this table. For years, the SlotTable used a gap buffer, the same data structure that powers text editors. It worked well for sequential operations, but as applications grew more dynamic with lists, animations, and conditional content, one limitation became painful: moving or reordering groups required copying large portions of memory. The Compose team rewrote the SlotTable as a linked list, and operations like list reordering now recompose over twice as fast.

In this article, you'll dive deep into this architectural shift, exploring how the gap buffer stores groups in contiguous arrays, how the link buffer replaces positions with pointer based navigation, how the SlotTableEditor achieves O(1) moves and deletes, how the free list and slot buffering manage memory, and how GroupHandle enables lazy position resolution. This isn't a guide on using Compose's APIs. It's an exploration of the data structure rewrite that makes recomposition fundamentally faster.

The gap buffer: From text editors to composition trees

A gap buffer is a data structure originally designed for text editing. Consider the problem a text editor faces: a document is a sequence of characters, and the user can insert or delete at any position. Storing characters in a flat array means inserting in the middle requires shifting every character after the insertion point. For a 100,000 character document, inserting near the beginning means moving nearly 100,000 characters.

The gap buffer solves this by keeping an empty region (the "gap") right at the cursor position. Inserting at the cursor fills in the gap without shifting anything. Deleting at the cursor expands the gap. Most text editing is sequential: you type at one spot, and the gap stays right where you need it. Editors like Emacs have used gap buffers for decades because of this property.

The trade off appears when you jump to a distant position. The gap must slide to the new cursor, copying every element between the old and new positions. As long as edits cluster near one location, the gap rarely moves and performance stays excellent. This is why gap buffers work well beyond text editors too: any workload where modifications happen sequentially in a large, ordered data set benefits from the same principle. The data stays in a flat, contiguous array (which is cache friendly), and insertions at the working position are O(1).

How Compose applied the gap buffer

The original Compose SlotTable stores composition data in two flat arrays:

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

The groups array stores group metadata as inline structs of 5 integers each (Group_Fields_Size = 5). Each group contains a key, group size, node count, parent anchor, and a data anchor pointing into the slots array. The slots array holds the actual remembered values, composable node references, and other data associated with each group.

The groups are ordered linearly: a parent's group fields are followed immediately by all its children's fields, forming a depth first layout. This makes linear scanning fast because you can read the tree from start to finish without jumping around. But it also means that a group's identity is tied to its position in the array. If you want to move a group, you have to physically relocate its data.

The gap buffer maintains its "gap" in each array. Insertions at the gap are O(1). But insertions elsewhere require moving the gap first, which copies every element between the old gap position and the new one. For a table with 10,000 groups (50,000 integers), moving the gap from the end to the beginning copies all 50,000 integers.

Deletions work similarly. When you remove a group, its space becomes part of the gap. But if the gap isn't adjacent to the deleted group, it must be moved there first. This worked well for initial composition, which proceeds sequentially through the tree. But recomposition can touch any part of the tree in any order, and list reordering moves groups across large distances.

The fundamental problem: Array copies that scale with composition size

Imagine a LazyColumn with 1,000 items, and the user drags item 999 to position 0. The runtime must move that item's group (and all its slots) from the end of the SlotTable to the beginning. In the gap buffer, this requires a 9 step process:

1. Insert space for the slots at the destination: This must happen first. The gap is moved to the destination and expanded, which requires updating every anchor between the old gap position and the new one.
2. Insert space for the groups at the destination: Same gap movement for the groups array, again shifting elements and updating anchors.
3. Copy the group fields to the new location: The group's metadata (key, size, node count, parent anchor, data anchor) is copied into the newly opened space.
4. Copy the slot data to the new location: All remembered values associated with the group are copied into the newly opened slot space.
5. Fix up moved group anchors for slot locations: Every group in the moved block has a data anchor pointing into the slots array. These anchors must all be recalculated because the slots moved.
6. Update any anchors in the moved group: External Anchor objects that reference the moved group must be updated to reflect the new array position.
7. Remove the old groups: The original group fields (now duplicated) are deleted by collapsing the gap over them.
8. Fix parent anchors: Parent groups that referenced the old position must be updated to point to the new position.
9. Remove the old slots: The original slot data is deleted last, because the groups referencing the old locations had to be removed first.

The ordering matters: slots must be inserted before groups (because gap movement requires valid group anchors), and old slots must be removed after old groups (for the same reason). Each step involves shifting array elements, and for a table with thousands of groups, this means thousands of integer copies per step. Reorder 10 items and you're doing tens of thousands of copies.

The gap buffer's moveGroup function in SlotWriter reveals this complexity. Looking at the actual implementation:

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) insert space for the slots at the destination
    insertSlots(moveDataLen, max(currentGroup - 1, 0))

    // 2) insert space for the groups at the destination
    insertGroups(moveLen)

    // 3) copy the groups to their new location
    groups.copyInto(
        destination = groups,
        destinationOffset = currentAddress * Group_Fields_Size,
        startIndex = moveLocationOffset,
        endIndex = moveLocationOffset + moveLen * Group_Fields_Size,
    )

    // ... steps 4 through 9 follow
}

The comments in the source code explain why the ordering matters: inserting slots must happen first because moving the gap requires valid group anchors, and removing slots must happen last because the groups that reference the old locations must be removed first. This cascade of dependencies makes the operation inherently sequential and expensive.

The link buffer SlotTable: Pointers instead of positions

The new SlotTable takes a fundamentally different approach. Instead of determining a group's place in the tree by where it sits in the array, each group carries explicit pointers to its neighbors. Think of it like the difference between a bookshelf (where a book's position determines its order) and a chain of paperclips (where each clip is physically connected to the next one regardless of where it is on the table).

Each group stores 6 integers: its key, a pointer to the next sibling, a pointer to its parent, a pointer to its first child, a flags field, and a slot range:

const val SLOT_TABLE_GROUP_SIZE = 6
const val SLOT_TABLE_GROUP_KEY_OFFSET = 0    // key
const val SLOT_TABLE_GROUP_NEXT_OFFSET = 1   // next sibling
const val SLOT_TABLE_GROUP_PARENT_OFFSET = 2 // parent
const val SLOT_TABLE_GROUP_CHILD_OFFSET = 3  // first child
const val SLOT_TABLE_GROUP_FLAGS_OFFSET = 4  // flags
const val SLOT_TABLE_GROUP_SLOTS_OFFSET = 5  // slot range

Conceptually, each group is a node in a linked list:

data class Group(
    val key: Int,
    val next: GroupAddress,      // next sibling in the child list
    val parent: GroupAddress,    // parent group
    val child: GroupAddress,     // first child group
    val flags: GroupFlags,       // bit packed metadata
    val slotRange: SlotRange,    // reference to remembered values
)

The key insight is that a group's position in the tree is defined by its pointers, not by its position in the array. Group 42 might be a child of group 1000, and group 6 might be a child of group 42. The array position is irrelevant. What matters is what the next, parent, and child fields point to. Moving a group in the tree doesn't require moving any data in the array. You just change the pointers.

These groups live inside the SlotTableAddressSpace, the core data store that both the editor and reader operate on: