Kotlin: Update Immutable List Element
Kotlin beginner here. How do I take a list and without mutating it, create a second (immutable) list with one updated element at a specific index?
I'm thinking of two ways, both of which seem like they may incur performance hits, mutate the underlying object, or both.
data class Player(val name: String, val score: Int = 0)
val players: List<Player> = ...
// Do I do this?
val updatedPlayers1 = players.mapIndexed { i, player ->
if (i == 2) player.copy(score = 100)
else player
}
// Or this?
val updatedPlayer = players[2].copy(score = 100)
val mutable = players.toMutableList()
mutable.set(2, updatedPlayer)
val updatedPlayers2 = mutable.toList()
If there is no performant way to do this, is there a more appropriate data structure in the Kotlin stdlib or other library? Kotlin doesn't seem to have vectors.
Answer
For me obvious that second way should be faster, but how much?
So I wrote some benchmarks here
@State(Scope.Thread)
open class ModifyingImmutableList {
@Param("10", "100", "10000", "1000000")
var size: Int = 0
lateinit var players: List<Player>
@Setup
fun setup() {
players = generatePlayers(size)
}
@Benchmark fun iterative(): List<Player> {
return players.mapIndexed { i, player ->
if (i == 2) player.copy(score = 100)
else player
}
}
@Benchmark fun toMutable(): List<Player> {
val updatedPlayer = players[2].copy(score = 100)
val mutable = players.toMutableList()
mutable.set(2, updatedPlayer)
return mutable.toList()
}
@Benchmark fun toArrayList(): List<Player> {
val updatedPlayer = players[2].copy(score = 100)
return players.set(2, updatedPlayer)
}
}
And got following results:
$ java -jar target/benchmarks.jar -f 5 -wi 5 ModifyingImmutableList
Benchmark (size) Mode Cnt Score Error Units
ModifyingImmutableList.iterative 10 thrpt 100 6885018.769 ± 189148.764 ops/s
ModifyingImmutableList.iterative 100 thrpt 100 877403.066 ± 20792.117 ops/s
ModifyingImmutableList.iterative 10000 thrpt 100 10456.272 ± 382.177 ops/s
ModifyingImmutableList.iterative 1000000 thrpt 100 108.167 ± 3.506 ops/s
ModifyingImmutableList.toArrayList 10 thrpt 100 33278431.127 ± 560577.516 ops/s
ModifyingImmutableList.toArrayList 100 thrpt 100 11009646.095 ± 180549.177 ops/s
ModifyingImmutableList.toArrayList 10000 thrpt 100 129167.033 ± 2532.945 ops/s
ModifyingImmutableList.toArrayList 1000000 thrpt 100 528.502 ± 16.451 ops/s
ModifyingImmutableList.toMutable 10 thrpt 100 19679357.039 ± 338925.701 ops/s
ModifyingImmutableList.toMutable 100 thrpt 100 5504388.388 ± 102757.671 ops/s
ModifyingImmutableList.toMutable 10000 thrpt 100 62809.131 ± 1070.111 ops/s
ModifyingImmutableList.toMutable 1000000 thrpt 100 258.013 ± 8.076 ops/s
So this tests shows that iterating over collection about 3~6 times slower, that copying. Also I provide my implementation: toArray, which looks like more performant.
On 10 element, toArray method has throughput 33278431.127 ± 560577.516 operations per second. Is it slow? Or it's extremely fast? I write "baseline" test, which shows cost of copying Players and mutating array. Results interesting:
@Benchmark fun baseline(): List<Player> {
val updatedPlayer = players[2].copy(score = 100)
mutable[2] = updatedPlayer;
return mutable
}
Where mutable - just MutableList, which is ArrayList.
$ java -jar target/benchmarks.jar -f 5 -wi 5 ModifyingImmutableList
Benchmark (size) Mode Cnt Score Error Units
ModifyingImmutableList.baseline 10 thrpt 100 81026110.043 ± 1076989.958 ops/s
ModifyingImmutableList.baseline 100 thrpt 100 81299168.496 ± 910200.124 ops/s
ModifyingImmutableList.baseline 10000 thrpt 100 81854190.779 ± 1010264.620 ops/s
ModifyingImmutableList.baseline 1000000 thrpt 100 83906022.547 ± 615205.008 ops/s
ModifyingImmutableList.toArrayList 10 thrpt 100 33090236.757 ± 518459.863 ops/s
ModifyingImmutableList.toArrayList 100 thrpt 100 11074338.763 ± 138272.711 ops/s
ModifyingImmutableList.toArrayList 10000 thrpt 100 131486.634 ± 1188.045 ops/s
ModifyingImmutableList.toArrayList 1000000 thrpt 100 531.425 ± 18.513 ops/s
On 10 elements we have 2x regression, and on 1 million about 150000x!
So looks like ArrayList not the best choice for immutable data structures. But there are a lot other collections, one of them is pcollections. Let's see what they got in our scenario:
@Benchmark fun pcollections(): List<Player> {
val updatedPlayer = players[2].copy(score = 100)
return pvector.with(2, updatedPlayer)
}
Where pvector is pvector:PVector<Player> = TreePVector.from(players).
$ java -jar target/benchmarks.jar -f 5 -wi 5 ModifyingImmutableList
Benchmark (size) Mode Cnt Score Error Units
ModifyingImmutableList.baseline 10 thrpt 100 79462416.691 ± 1391446.159 ops/s
ModifyingImmutableList.baseline 100 thrpt 100 79991447.499 ± 1328008.619 ops/s
ModifyingImmutableList.baseline 10000 thrpt 100 80017095.482 ± 1385143.058 ops/s
ModifyingImmutableList.baseline 1000000 thrpt 100 81358696.411 ± 1308714.098 ops/s
ModifyingImmutableList.pcollections 10 thrpt 100 15665979.142 ± 371910.991 ops/s
ModifyingImmutableList.pcollections 100 thrpt 100 9419433.113 ± 161562.675 ops/s
ModifyingImmutableList.pcollections 10000 thrpt 100 4747628.815 ± 81192.752 ops/s
ModifyingImmutableList.pcollections 1000000 thrpt 100 3011819.457 ± 45548.403 ops/s
Nice results! On 1 million case we have only 27x slower execution, which is pretty cool, but on small collections pcollections little bit slower that ArrayList implementation.
Update: as @mfulton26 mentioned, in toMutable benchmark toList is unnecessary, so I deleted it and reran tests. Also I added benchmark on cost of creation TreePVector from existing array:
$ java -jar target/benchmarks.jar ModifyingImmutableList
Benchmark (size) Mode Cnt Score Error Units
ModifyingImmutableList.baseline 10 thrpt 200 77639718.988 ± 1384171.128 ops/s
ModifyingImmutableList.baseline 100 thrpt 200 75978576.147 ± 1528533.332 ops/s
ModifyingImmutableList.baseline 10000 thrpt 200 79041238.378 ± 1137107.301 ops/s
ModifyingImmutableList.baseline 1000000 thrpt 200 84739641.265 ± 557334.317 ops/s
ModifyingImmutableList.iterative 10 thrpt 200 7389762.016 ± 72981.918 ops/s
ModifyingImmutableList.iterative 100 thrpt 200 956362.269 ± 11642.808 ops/s
ModifyingImmutableList.iterative 10000 thrpt 200 10953.451 ± 121.175 ops/s
ModifyingImmutableList.iterative 1000000 thrpt 200 115.379 ± 1.301 ops/s
ModifyingImmutableList.pcollections 10 thrpt 200 15984856.119 ± 162075.427 ops/s
ModifyingImmutableList.pcollections 100 thrpt 200 9322011.769 ± 176301.745 ops/s
ModifyingImmutableList.pcollections 10000 thrpt 200 4854742.140 ± 69066.751 ops/s
ModifyingImmutableList.pcollections 1000000 thrpt 200 3064251.812 ± 35972.244 ops/s
ModifyingImmutableList.pcollectionsFrom 10 thrpt 200 1585762.689 ± 20972.881 ops/s
ModifyingImmutableList.pcollectionsFrom 100 thrpt 200 67107.504 ± 808.308 ops/s
ModifyingImmutableList.pcollectionsFrom 10000 thrpt 200 268.268 ± 2.901 ops/s
ModifyingImmutableList.pcollectionsFrom 1000000 thrpt 200 1.406 ± 0.015 ops/s
ModifyingImmutableList.toArrayList 10 thrpt 200 34567833.775 ± 423910.463 ops/s
ModifyingImmutableList.toArrayList 100 thrpt 200 11395084.257 ± 76689.517 ops/s
ModifyingImmutableList.toArrayList 10000 thrpt 200 134299.055 ± 602.848 ops/s
ModifyingImmutableList.toArrayList 1000000 thrpt 200 549.064 ± 15.317 ops/s
ModifyingImmutableList.toMutable 10 thrpt 200 32441627.735 ± 391890.514 ops/s
ModifyingImmutableList.toMutable 100 thrpt 200 11505955.564 ± 71394.457 ops/s
ModifyingImmutableList.toMutable 10000 thrpt 200 134819.741 ± 526.830 ops/s
ModifyingImmutableList.toMutable 1000000 thrpt 200 561.031 ± 8.117 ops/s