compose.ui.utilにあるfastXXXのリスト操作のAPIを見てみる

`androidx.compose.ui.util` のライブラリに `fastXXX` というリストを操作する拡張関数が用意されています。ライブラリに依存することでアプリの実装でも使うことはできます。  

https://developer.android.com/reference/kotlin/androidx/compose/ui/util/package-summary#extension-functions-summary

これらの API は通常の `forXXX` と何が違うのか調べてみました。


## コードから見る forXXX との違い

### `forEach` との違い
`fastForEach` のコードを見てみます。

```kotlin
@Suppress("BanInlineOptIn")
@OptIn(ExperimentalContracts::class)
inline fun <T> List<T>.fastForEach(action: (T) -> Unit) {
    contract { callsInPlace(action) }
    for (index in indices) {
        val item = get(index)
        action(item)
    }
}
```

https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:compose/ui/ui-util/src/commonMain/kotlin/androidx/compose/ui/util/ListUtils.kt;l=30-38

通常の `forEach` はこのようになっています。

```kotlin
@kotlin.internal.HidesMembers
public inline fun <T> Iterable<T>.forEach(action: (T) -> Unit): Unit {
    for (element in this) action(element)
}
```


https://github.com/JetBrains/kotlin/blob/530725c6bfbc6b392c6d53f34d82efe30383a03e/libraries/stdlib/common/src/generated/_Collections.kt#L1853-L1856


ぱっと実装を見ただけでは違いが分かりにくいので、コンパイルされたコードも見てみましょう。
以下のようなコードを試しに見比べてみます。

```kotlin
val list = ...
list.fastForEach {
    val s = it.toString()
}
list.forEach {
    val s = it.toString()
}
```

`fastForEach` は inline 関数なので以下のように展開されます。
```java
List $this$fastForEach$iv = list;
int $i$f$forEach = false;
index$iv = 0;

for(int var7 = list.size(); index$iv < var7; ++index$iv) {
 Object item$iv = $this$fastForEach$iv.get(index$iv);
 int it = ((Number)item$iv).intValue();
 int var10 = false;
 String var11 = String.valueOf(it);
}
```

`forEach` も inline 関数なので以下のように展開されます。
```java
Iterable $this$forEach$iv = (Iterable)list;
$i$f$forEach = false;

int it;
String var21;
for(Iterator var17 = $this$forEach$iv.iterator(); var17.hasNext(); var21 = String.valueOf(it)) {
 Object element$iv = var17.next();
 it = ((Number)element$iv).intValue();
 var9 = false;
}
```

`fastForEach`　と `forEach` の違いは Iterator を使うか否かのみの差になっています。  
この Iterator を使わないという背景には Iterator の割り当てや GC の回収を減らすことによるパフォーマンス改善といった背景があるそうです。  


https://twitter.com/JimSproch/status/1654027545157988352?s=20

### `map` との違い
`fastMap` のコードを見てみます。

```kotlin
@Suppress("BanInlineOptIn")
@OptIn(ExperimentalContracts::class)
inline fun <T, R> List<T>.fastMap(transform: (T) -> R): List<R> {
    contract { callsInPlace(transform) }
    val target = ArrayList<R>(size)
    fastForEach {
        target += transform(it)
    }
    return target
}
```

https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:compose/runtime/runtime/src/commonMain/kotlin/androidx/compose/runtime/snapshots/ListUtils.kt;l=79-88

通常の `map` はこのようになっています。

```kotlin
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
    return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}

public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
    for (item in this)
        destination.add(transform(item))
    return destination
}
```

https://github.com/JetBrains/kotlin/blob/530725c6bfbc6b392c6d53f34d82efe30383a03e/libraries/stdlib/common/src/generated/_Collections.kt#L1548-L1550

https://github.com/JetBrains/kotlin/blob/530725c6bfbc6b392c6d53f34d82efe30383a03e/libraries/stdlib/common/src/generated/_Collections.kt#L1619-L1623


`fastMap` は内部で `fastForEach` を使用していたり、変換後に格納する ArrayList の配列を List のサイズ分確保していたりといった差が見られます。
コンパイルされたコードも見てみましょう。
以下のようなコードを試しに見比べてみます。

```kotlin
val list = ...
list.fastMap {
    it.toString()
}
list.map {
    it.toString()
}
```

`fastMap` は以下のようになります。
```java
int $i$f$map = false;
ArrayList target$iv = new ArrayList(list.size());
List $this$fastForEach$iv$iv = list;
int $i$f$mapTo = false;
int index$iv$iv = 0;

String var27;
for(int var10 = list.size(); index$iv$iv < var10; ++index$iv$iv) {
 Object item$iv$iv = $this$fastForEach$iv$iv.get(index$iv$iv);
 int var13 = false;
 Collection var10000 = (Collection)target$iv;
 int it = ((Number)item$iv$iv).intValue();
 Collection var16 = var10000;
 int var15 = false;
 var27 = String.valueOf(it);
 var16.add(var27);
}
```

次に `map` は以下のようになります。  
```java
Iterable $this$map$iv = (Iterable)list;
int $i$f$map = false;
Collection destination$iv$iv = (Collection)(new ArrayList(CollectionsKt.collectionSizeOrDefault($this$map$iv, 10)));
int $i$f$mapTo = false;
Iterator var26 = $this$map$iv.iterator();

while(var26.hasNext()) {
 item$iv$iv = var26.next();
 int it = ((Number)item$iv$iv).intValue();
 var14 = false;
 var27 = String.valueOf(it);
 destination$iv$iv.add(var27);
}
```

`fastMap` と `map` の違いは `fastForEach` の Iterator を使うか否かであったり、配列の確保あたりが異なっています。  

## fastXXX の API はいつ使うのか

`fastXXX` の API はドキュメントに以下のように書いています。

>Do not use for collections that come from public APIs, since they may not support random access in an efficient way, and this method may actually be a lot slower. Only use for collections that are created by code we control and are known to support random access.

これらの `fastXXX` の API は Compose のライブラリ内で使用されており、ライブラリ提供者のユーザに公開しない内部でのみパフォーマンスで改善が見込める条件で使うことが想定されています。  


`fastXXX` の API は基本的にアプリを開発する上では使うことはなく、パフォーマンスを改善したいとなった場合に使うことを検討するくらいでしょう。  

## まとめ
- `fastXXX` は Iterator を使わないことで割り当てや GC を回避してパフォーマンスを改善できる API
- 基本的にアプリを開発する上では使うことはなく、ライブラリ提供者が API として公開されない部分で使用することが想定されている