Performance issue removing 1,000,000 items from a mutable list in Compose

Readme.md

This was an idea for tree implementation I came up with to try and play well with the way Compose wants us to do things.

The basic idea:

• Maintain a list of every row which is currently visible/expanded
• When you expand a node, add all its children to the list
• When you collapse a node, remove its children (caveat: and their children) from the list
• Rendering nodes is fairly easy because the only thing that varies is the amount of indent and which icon to show

The idea seems sound - adding a million entries to the list is fast enough as to be unnoticeable.

There's a massive performance issue when you try to collapse the large branch again. LOL... Still, I think it would be viable, if someone made an alternative list implementation which was sufficiently fast at removing a range.

Or maybe there's a way to make a list view for a tree which just does what's needed to make the tree look like a list?

stack-dump.txt

"AWT-EventQueue-0" #20 prio=6 os_prio=1 cpu=47890.62ms elapsed=59.36s tid=0x00000203bb468ba0 nid=0x6764 runnable  [0x0000001d062fc000]
   java.lang.Thread.State: RUNNABLE
	at androidx.compose.runtime.external.kotlinx.collections.immutable.implementations.immutableList.PersistentVectorBuilder.removeFromRootAt(PersistentVectorBuilder.kt:604)
	at androidx.compose.runtime.external.kotlinx.collections.immutable.implementations.immutableList.PersistentVectorBuilder.removeFromRootAt(PersistentVectorBuilder.kt:604)
	at androidx.compose.runtime.external.kotlinx.collections.immutable.implementations.immutableList.PersistentVectorBuilder.removeFromRootAt(PersistentVectorBuilder.kt:604)
	at androidx.compose.runtime.external.kotlinx.collections.immutable.implementations.immutableList.PersistentVectorBuilder.removeAt(PersistentVectorBuilder.kt:549)
	at kotlin.collections.AbstractMutableList.remove(AbstractMutableList.kt:15)
	at androidx.compose.runtime.external.kotlinx.collections.immutable.implementations.immutableList.PersistentVectorMutableIterator.remove(PersistentVectorMutableIterator.kt:110)
	at java.util.AbstractList.removeRange(java.base@17.0.5/AbstractList.java:598)
	at java.util.AbstractList$SubList.removeRange(java.base@17.0.5/AbstractList.java:811)
	at java.util.AbstractList.clear(java.base@17.0.5/AbstractList.java:243)
	at androidx.compose.runtime.snapshots.SnapshotStateList.removeRange(SnapshotStateList.kt:110)
	at TreeScratchKt$CleverTreeView$1$1$1$1$1$1.invoke(TreeScratch.kt:68)

TreeScratch.kt

import androidx.compose.foundation.*
import androidx.compose.foundation.layout.*
import androidx.compose.foundation.lazy.*
import androidx.compose.material.*
import androidx.compose.material.icons.*
import androidx.compose.material.icons.filled.*
import androidx.compose.runtime.*
import androidx.compose.ui.*
import androidx.compose.ui.unit.*
import androidx.compose.ui.window.*

fun main() = singleWindowApplication {
    val rootNode = CommentNode("Hi there", listOf(
        CommentNode("Oh hi, did it work?", listOf(
            CommentNode("Kind of, but a lot of shit is missing")
        )),
        CommentNode("Here, this should break the tree, surely?",
            (1..1_000_000).map { i -> CommentNode("Comment $i") })
    ))

    CleverTreeView(rootNode) { node ->
        Text(node.content)
    }
}

data class CommentNode(
    val content: String,
    val children: List<CommentNode> = emptyList()
)

data class TreeRow(
    val nestingLevel: Int,
    val node: CommentNode,
    val expanded: Boolean = false,
)

@Composable
fun CleverTreeView(
    rootNode: CommentNode,
    content: @Composable (CommentNode) -> Unit
) {
    val treeRows = remember { mutableStateListOf(TreeRow(0, rootNode)) }
    val lazyListState = rememberLazyListState()

    Box(modifier = Modifier.fillMaxWidth()) {
        LazyColumn(state = lazyListState, modifier = Modifier.fillMaxWidth()) {
            items(treeRows.size) { index ->
                val row = treeRows[index]
                Row(
                    verticalAlignment = Alignment.CenterVertically,
                    modifier = Modifier.padding(start = 8.dp * row.nestingLevel)
                ) {
                    IconButton(
                        onClick = {
                            // TODO: It would be super nice if these tree mutations were done in one step
                            if (row.expanded) {
                                println("Collapsing tree node...")
                                treeRows[index] = row.copy(expanded = false)
                                // Scan to find the next sibling to figure out how many rows to remove.
                                // Not the optimal solution, but seems to work.
                                println("Figuring out how many rows to remove...")
                                var descendantCount = treeRows.subList(index + 1, treeRows.size)
                                    .indexOfFirst { r -> r.nestingLevel <= row.nestingLevel  }
                                if (descendantCount < 0) {
                                    descendantCount = treeRows.size - (index + 1)
                                }
                                println("Removing $descendantCount rows from the row list...")
                                treeRows.removeRange(index + 1, index + 1 + descendantCount)
                                println("Done!")
                            } else {
                                println("Expanding tree node...")
                                treeRows[index] = row.copy(expanded = true)
                                println("Adding ${row.node.children.size} rows to the row list...")
                                treeRows.addAll(index + 1, row.node.children.map { child -> TreeRow(row.nestingLevel + 1, child) })
                                println("Done!")
                            }
                        },
                        // TODO: Figure out a sensible row height. Using dp isn't sensible because the text will be in sp.
                        modifier = Modifier.size(24.dp)
                    ) {
                        // TODO: Figure out a sane contentDescription for disclosure triangles
                        Icon(
                            imageVector = if (row.expanded) Icons.Filled.ArrowDropDown else Icons.Filled.ArrowRight,
                            contentDescription = ""
                        )
                    }

                    content(row.node)
                }
            }
        }

        VerticalScrollbar(
            modifier = Modifier.align(Alignment.CenterEnd).fillMaxHeight(),
            adapter = rememberScrollbarAdapter(lazyListState)
        )
    }
}