よく、素朴に List を返す関数を書いてメモリーリーク¹が発生することがあります。これを Kotlin の Seqeunce に書き換えて改善する方法を紹介します。

性能測定に Flight Recorder を使います。JDK 17 で実行しました。

メモリーリーク発生

次の例を考えます。

CartesianProduct1.kt

import java.io.OutputStream
import java.io.PrintStream

object CartesianProduct1 {
    private val list1 = (1..300).toList()
    private val list2 = (1..300).toList()
    private val list3 = (1..300).toList()

    private fun <T> cartesianProduct(list1: List<T>, list2: List<T>, list3: List<T>): List<List<T>> {
        return list1.flatMap { elem1 ->
            list2.flatMap { elem2 ->
                list3.map { elem3 ->
                    listOf(elem1, elem2, elem3)
                }
            }
        }
    }

    @JvmStatic
    fun main(vararg args: String) {
        for (product in cartesianProduct(list1, list2, list3)) {
            System.setOut(PrintStream(OutputStream.nullOutputStream()))
            println(product)
        }
    }
}

System.setOut(PrintStream(OutputStream.nullOutputStream())) は、println での大量の出力を抑制するために使っています。

以下のVM オプションを付けて実行すると、プロファイルを取ることができます²。

-XX:StartFlightRecording=filename=CartesianProduct1.jfr,settings=profile

JDK Mission Control (ここでは Azul Mission Control) に読み込ませ、アウトラインから「メモリー」を選択肢、グラフの「メモリー使用状況」をクリックすると、次のような情報が表示されました。

最大で 2 GiB のメモリーを消費し、その後は最低でも 1.5 GiB 程度のオブジェクトがコミットされていることがわかります。「スレッド」を選択すると開始時刻と終了時刻が表示されるのですが、そこから計算すると実行時間は40秒ほどだったようです。

char[] や byte[] の割当量が多いですが、println のためのすぐに開放可能な一時的なメモリー使用なので気にしなくて大丈夫そうです。ArrayList の割当量が 1.12 GiB で、処理の流れを見てもリストがメモリーを使いそうですし、量的にもグラフの最低ラインの使用量に近く、疑わしいところです。詳しい調査が必要な場合はヒープダンプを取りたいところですが、あたりをつけるには十分な情報が得られました。

「最大ライブ・サイズ」などの列が空欄になっていますが、これはウィンドウ > フライト記録テンプレート・マネージャで $JAVA_HOME\lib\jfr\profile.jfc をロードして複製し、Memory Profiling を All に編集し、エクスポートして settings=edited.jfc のようにすると出力されるようです。今回は設定しませんでしたが、開発環境でのメモリーリークの調査では設定したほうが良さそうですね。

Sequence で改善

.asSequence で Sequence にしても良いのですが、使える場面が多い sequence と yield を使った改善例を紹介します。

CartesianProduct2.kt

import java.io.OutputStream
import java.io.PrintStream

object CartesianProduct2 {
    private val list1 = (1..300).toList()
    private val list2 = (1..300).toList()
    private val list3 = (1..300).toList()

    private fun <T> cartesianProduct(list1: List<T>, list2: List<T>, list3: List<T>): Sequence<List<T>> {
        return sequence {
            list1.flatMap { elem1 ->
                list2.flatMap { elem2 ->
                    list3.map { elem3 ->
                        yield(listOf(elem1, elem2, elem3))
                    }
                }
            }
        }
    }

    @JvmStatic
    fun main(vararg args: String) {
        for (product in cartesianProduct(list1, list2, list3)) {
            System.setOut(PrintStream(OutputStream.nullOutputStream()))
            println(product)
        }
    }
}

同様に JDK Mission Control にプロファイルを読み込ませると、次のような情報を得ることができました。

最大で 868 GiB のメモリーを消費し、その後は最低ラインがじわじわ上昇し、多いときには最低で 280 MiB 程度がコミットされていることがわかります³。実行時間は33秒ほどだったようです。

最低ラインがじわじわ上昇していることからメモリーリークが完全には解消されていないことがわかりますが、こんなに簡単な修正でここまで改善するなら許容範囲ではないでしょうか。2次元目までのリストの構築分でメモリーを消費しているものと思われます。flatMap や map を for に直すか、.asSequence() で書き換えたところ完全に解消されたので、この例ではそれらへの書き換えがおすすめです。

おまけ: Guava で解消

Guava による Cartesian product の実装も使ってみました。Set を返しますが、Set のインターフェースを通して返しているだけで Set の中身はメモリ上に展開されないのでメモリーリークが起きないという、すごい実装です。

CartesianProduct3.kt

import com.google.common.collect.Sets.cartesianProduct
import java.io.OutputStream
import java.io.PrintStream

object CartesianProduct3 {
    private val list1 = (1..300).toSet()
    private val list2 = (1..300).toSet()
    private val list3 = (1..300).toSet()

    @JvmStatic
    fun main(vararg args: String) {
        for (product in cartesianProduct(list1, list2, list3)) {
            System.setOut(PrintStream(OutputStream.nullOutputStream()))
            println(product)
        }
    }
}

同様に JDK Mission Control にプロファイルを読み込ませると、次のような情報を得ることができました。

左下のプロパティー欄を見ると最大で 846 MiB のメモリーを消費していますが、グラフを見る限り 512 MiB 程度までに収まっているようです。最低ラインは 5.17 MiB 程度にとどまっています。完全にメモリーリークが解消されたことがわかります。実行時間は32秒ほどでした。

厳密にはメモリーリークではない気がしますが、そう呼ばれます。 ↩
JDK 8 では -XX:+UnlockCommercialFeatures も必要です。 ↩
最低ラインは、JVM 内部 > ガベージ・コレクションの Heap Post GC からも確認できます。 ↩