高性能高安全性的最佳选择：Kotlin Immutable Collection 及纯函数的思考

2024-03-02 约 3325 字预计阅读 7 分钟次阅读

之后文章会全部转到飞书文档发布，此网页可能存在更新不及时的问题，飞书文档首页 zsqw123 Homepage

飞书文档原文：高性能高安全性的最佳选择：Kotlin Immutable Collection 及纯函数的思考

在之前的一篇文章中我提到过纯函数在 kotlin 中的一些运用和纯函数的好处：一个 Kotlin 开发，对于纯函数的思考，简单来说，纯函数为我们带来了可缓存性，并发安全，高度可测性以及清晰的依赖。在这篇文章中我会简单说说可变性是怎样导致程序的不安全性的，也会介绍一种实现纯的方案：kotlin immutable collections，以及我对其的一些思考和优化，还会将其和 guava 做对比。

糟糕的可变性

多线程不安全

众所周知，在多线程的情况下，通常总是无可避免的访问一些在多个线程之间共享的变量，同时为了对多线程数据收集，通常做法也都是多线程同时写入(change var field)或改变(操作 mutable list)同一变量，通常这导致了我们经常需要使用一些线程安全的结构，也需要进行多线程之间的加锁操作。但这对程序员来说很显然就是一种很大的危险性。

Kotlin 的 List 仅仅表示列表，不保证不可变

很多人可能认为只要某个对象的类型是 List 就是不可变的，但实际上这是错误的，尝试运行下面的代码，你会发现即便 kotlin toList 返回的仅仅是个 List<T>，也是能够将其强转后添加元素的。这源于 kotlin 在背后对其的实现是使用 MutableList 来实现的，他实现了 List，但它是可变的。

1
2
3


val originList = arrayOf(1, 2, 3).toList() as MutableList<Int>
originList.add(4)
println(originList) // [1, 2, 3, 4]

列表合并时需要对象拷贝

通常在合并两个列表的时候，在 Kotlin 中我们直接使用 + 运算符即可，背后会创建一个新的列表，并将两个列表的值全都塞入新列表，这其实造成了一些性能开销。

当时我就在想，为什么不直接同时持有两个对象的引用，并用 index 和 offset 实现一个新的 List object 呢？这样就避免了拷贝的开销。原因就是上面提到的，List 无法保证其不可变性，直接持有两个对象引用是危险的，很可能在其中一个列表改动后造成列表访问越界。

危险的生命周期使用

在 Android 开发中，通常总会接触到很多的生命周期事件，类似于 onCreate, onDestory，并且你的代码往往仅能够在这两个生命周期之间进行 UI 关联的操作，这导致了很多的危险。一个常见的例子是你发起了一个网络请求，但在请求结束回来后 activity 已经被销毁了，此时相关方法可能已经无法调用(如 ViewModel)

基于上文这么糟糕的可变性，下文我就来介绍其中的一个解决方案：Immutable collection

Immutable collection

上文中我们说到由于列表合并时，List 无法保证其不可变性，这导致了我们不能直接复用原列表并通过引用建立联系，但如果我们显式用一个类型来保证不可变性，那么问题就能够得到解决，我们也可以直接使用 offset 来对列表进行合并，下文为一个使用 kotlinx immutable collection 的例子，我们直接上测试！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


fun <T> listPlus(payload: List<List<T>>): List<T> {
    var current = emptyList<T>()
    payload.forEach { current = current + it }
    return current
}

fun <T> flatten(payload: List<List<T>>): List<T> = payload.flatten()

fun <T> ktImmutable(input: List<List<T>>): List<T> {
    var current = persistentListOf<T>()
    input.forEach { current += it }
    return current
}

fun <T> guavaImmutable(input: List<List<T>>): List<T> {
    var current: ImmutableList<T> = ImmutableList.of()
    input.forEach { current = ImmutableList.builder<T>().addAll(current).addAll(it).build() }
    return current
}

执行与 payload 的生产代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


fun main() {
    val random = Random(System.currentTimeMillis())
    val payload = List(10000) {
        List(random.nextInt(8, 200)) { random.nextInt() }
    }
    println("listPlus cost ${measureTimeMillis { listPlus(payload) }}ms")
    println("flatten cost ${measureTimeMillis { flatten(payload) }}ms")
    println("kt immutable cost ${measureTimeMillis { ktImmutable(payload) }}ms")
    println("guava immutable cost ${measureTimeMillis { guavaImmutable(payload) }}ms")
}

最终得到的结果如下：

listPlus	5769ms
flatten	7ms
kt immutable	35ms
guava immutable	5758ms

我们能看到 flatten 的效率是最高的，原因是因为其能够直接使用了同一个可变 list 进行操作，其次是 kt immutable，它会通过共享数组来实现即便是多个 immutableList 相加，效率也可以达到类似单个 mutable list 不断 addAll 的效果，这里比 flatten 慢的主要原因在于其创建了大量的 immutableList 对象，并且 mutate 过程也存在一定的性能损耗，当然这个差距会随着列表数量越来越多而逐渐减小。

此外值得一提的是，尽管 guava 提供了 immutable，但是并没有对 immutable 的 addAll 操作进行优化，只能通过 builder 不断 addAll 进行操作，因此相比于 list plus 区别不大。当然可能质疑为什么 payload 不用 guava ImmutableList 呢？但事实上我尝试过，效率没有明显区别。

kt immutable 实现这个这种低损耗列表加法是有额外代价的，效率为 O(log(32)N)，但这个损耗是极小的，在最极端的情况下也只需要 7 次就能够找到对应的元素

能否进一步优化？

Kotlin 的 ImmutableList 本质会在 builder 中存储可变的 Array 引用，并在每个 ImmutableList 中储存和 root Array 的 offset，其列表合并效率最高也只能与直接创建 mutable 打平，但事实上由于其是不可变的，我们完全可以通过引用链构建更高性能的数据结构。

先看效果

先直接看我们优化之后的效果，这是每个列表的创建方式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


private fun <T> flatten(payload: List<List<T>>): List<T> = payload.flatten()

private fun <T> ktImmutable(input: List<List<T>>): List<T> {
    var current = persistentListOf<T>()
    input.forEach { current += it }
    return current
}

private fun <T> myImmutable(input: List<List<T>>): List<T> {
    var current: PersistentList<T> = MyPersistentList.of()
    input.forEach { current += it }
    return current
}

这是我们的启动程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


fun main() {
    val random = Random(System.currentTimeMillis())
    val payload = List(20000) {
        List(1200) { random.nextInt() }
    }
    val ktPayload = payload.map { it.toPersistentList() }
    val myPayload = payload.map { MyPersistentList.copyOf(it) }
    var flattenData: List<Int>
    var myData: List<Int>
    println("flatten cost ${measureTimeMillis { flattenData = flatten(payload) }}ms")
    println("kt immutable cost ${measureTimeMillis { ktImmutable(ktPayload) }}ms")
    println("myImmutable cost ${measureTimeMillis { myData = myImmutable(myPayload) }}ms")
    println("equals: ${flattenData.toList() == myData.toList()}")
}

最终结果是如下，equals 是我为了检验数据正确性而做的操作，返回 true 代表我的列表合并不存在问题。可以看到我们的列表展现出了极为优异的性能，仅需要 14ms：

flatten	165ms
kt immutable	197ms
myImmutable	14ms
equals	true

Kotlin PersistentList

我们先来看看 kotlin persistentList (immutable list 的默认实现) 的数据结构，其数据结构为 Tire，中文可能叫做 “字典树” 或 “前缀树”，kotlin 便是用其实现了 persistentList。

先看 get 操作，这里我们直接使用了 React.js Conf 2015 中的图片，kotlin 与其设计结构事实上是一样的（但默认 shift 为 5）。

shift 是对 index 的分割块大小，以 141 举例，shift 为 2 代表每两个一组分割这个数字：10 00 11 01，也就是图中的高亮节点
这里为了简便，使用了一个 shift 为 2 的字典树，这样每个节点就具有了 4 个元素
所有的元素都存在叶子节点上，获取元素的所需的查找次数为 log(shift)N

然后我们看 set 操作，set 会返回一个全新的数组（图中绿色部分），对于未改变的部分则继续使用原有的节点，而对于需要改变的部分则改变对应的叶子节点及其全部父节点，返回一个新的 list 对象。

当然，add/remove 等操作也会返回全新的对象，不过可能会改变叶子节点列表的大小，kotlin persistentList 中叶子节点是由大小为 32 的 buffer 来储存的，并且会根据实际使用情况来增大叶子节点 buffer 的大小。同时 buffer 结构是在各各个创建出来的 List 之间共享的，不会因为是一个新列表对象就完全拷贝一份原有的 buffers（众所周知 Java 的 ArrayList 增加元素如果需要扩容是需要进行数据拷贝的）

MyPersistentList

Kotlin 使用了经典的字典树结构，但我认为列表合并的时候，如果是不可变的列表，那么完全可以直接持有两个源对象的引用而不必进行数组拷贝创建新数组来做这件事情。

在 MyPersistentList 中，每个列表持有两个数据结构：references 和 indices

reference 存储对所有不可变数组的引用，indices 存储每个数组的偏移量，每个 reference 对应的 index 加上他们在各自节点中的偏移量，就能够得到他们在数组中的具体位置。接下来我们考虑对列表的各种操作：

查找和修改：

因为 indices 是高度有序的，因此我们可以通过二分查找轻松的找到 index 对应的 reference，并通过 index - offset 得到在数组中的具体位置，这个操作时间复杂度约 O(log(2)N)

而对于修改，与 kotlin PersistentList 类似，我们也是创建对一个 buffer 的拷贝并进行修改，对应到我们的结构体中就是对其中的一个 reference 替换，复杂度约为 O(log(2)N + M)，M 为 reference 的大小，但其实耗时位于 reference 新创建对象上，因此实际取决于 reference 修改的速度，全部拷贝的情况下为 M

对于添加或删除元素/列表：

根据 index，找到对应的 reference 执行添加列表并替换原有列表（不是修改原有引用，而是创建新引用），并对之后的全部 indices 进行更新。时间复杂度为 O(log(2)N + M + I)，M 为 reference 列表的大小，但取决于其 addAll 的具体实现，I 为 indices 的大小，最差情况下需要更新整个 indices 列表

对于直接 addAll 操作，我进行了一些简单的优化，直接在 references 和 indices 列表最后添加新元素即可，效率取决于 references 和 indices 具体用的什么样的 PersistentList

最后

在纯函数中，我们会非常频繁的使用 Immutable collection 的特性，也会非常频繁的使用 + 或其他操作来合并两个列表，通过 MyPersistentList，我们便能够做到通过持有引用来实现一个伪 List，而不需要真的拷贝一个新数组，这种方式能够较好提高程序的运行效率，也能减少内存拷贝情况的发生，以至于 MyPersistentList 的合并性能可以超越原生 list 使用可变性做到的的 flatten 操作。

不过在 kotlin 中创建对象进行抽象是具有代价的，如果换做 rust 之类的具有 0 抽象 struct 的语言，能够让性能更上一步。

目录