【Kotlin】ローカル関数の利用はパフォーマンス低下につながる

TL;DR

• ローカル関数を利用するとパフォーマンスが低下する
• このため、パフォーマンスが重要な場面ではローカル関数を利用すべきでない

文脈

日頃からお世話になっているintellij-rainbow-bracketsのコードを読んでいた所、以下のコードを見つけました。

github.com

このコードはローカル関数（関数内に定義する関数）を多用する書き方をしていますが、これがパフォーマンスに影響を与えないのか気になったため確認を行いました。

パフォーマンス低下を推測する根拠

上記のコードをJavaへデコンパイルすると、以下のような表現になっています。

   public final void annotateUtil(/* */) {
      <undefinedtype> $fun$getBracketLevel$1 = new Function1() {
         public final int invoke(@NotNull LeafPsiElement element) {
            <undefinedtype> $fun$iterateParents$1 = new Function1() {
               public final void invoke(@NotNull final PsiElement currentNode) {
                  while(true) {
                     <undefinedtype> $fun$iterateChildren$1 = new Function1() {
                        public final void invoke(@NotNull PsiElement currentChild) {
                        }
                     };
                  }
               }
            };
         };
      };
   }

かなり要約していますが、ここからは以下のような問題点が見えます。

• 関数呼び出し毎にローカル関数のnewが行われている
• ループ（tailrec）内では、繰り返しローカル関数のnewが行われている

検証

検証のため、分割を行っていない状態と、分割後の状態とを再現し、それらに対するJMHベンチマークを作成しました。
コードは以下の通りです。

import org.openjdk.jmh.annotations.Benchmark
import org.openjdk.jmh.annotations.Scope
import org.openjdk.jmh.annotations.State

// ベンチマーク対象（分割後）
object Separated {
    private tailrec fun inner(i: Int, limit: Int): Int =
        if (i == limit) i else inner(i + 1, limit)

    private tailrec fun outer(i: Int, limit: Int): Int =
        if (i == limit) inner(i, limit) else outer(i + 1, limit)

    private fun caller(limit: Int) = outer(0, limit)

    // limit must be an integer greater than or equal to 1.
    fun target(limit: Int) = caller(limit)
}

// ベンチマーク対象（分割前）
object Combined {
    // limit must be an integer greater than or equal to 1.
    fun target(limit: Int): Int {
        fun caller(): Int {
            tailrec fun outer(i: Int): Int {
                tailrec fun inner(i: Int): Int =
                    if (i == limit) i else inner(i + 1)

                return if (i == limit) inner(i) else outer(i + 1)
            }
            return outer(0)
        }

        return caller()
    }
}

// ベンチマーク
@State(Scope.Benchmark)
open class Measurement {
    private val limit = 10

    @Benchmark
    open fun combined() = Combined.target(limit)

    @Benchmark
    open fun separated() = Separated.target(limit)
}

構築は下記を利用しています。

qiita.com

検証結果

build.gradle.ktsに以下の設定を入れてベンチマークを行いました。

jmh {
    warmupForks = 2
    warmupBatchSize = 3
    warmupIterations = 3
    warmup = "1s"

    fork = 2
    batchSize = 3
    iterations = 2
    timeOnIteration = "1500ms"

    failOnError = true
    isIncludeTests = false

    resultFormat = "CSV"
}

自分のPCで実行した結果は以下の通りです。
combinedが旧来のコードの再現で、separatedが分割後の想定です。
スコアは高いほど良いです。

Benchmark               Mode  Cnt         Score         Error  Units
Measurement.combined   thrpt    4  12430932.298 ±  581801.766  ops/s
Measurement.separated  thrpt    4  80820942.692 ± 2977174.695  ops/s

考察

推測通り、ローカル関数の利用によってパフォーマンスの問題が発生するようでした。
ベンチマーク内容について現実的な想定だと言い張るつもりは有りませんが、少なくともそれなりの影響は有ると言えます。

combinedのinner関数を外に出すだけでもスコアが倍以上改善する様子も有りました。

まとめ

この記事ではintellij-rainbow-bracketsのコードを例にローカル関数の利用がパフォーマンス低下につながることを確認しました。
ローカル関数は便利な機能であるものの、パフォーマンスが重要な場面で利用することは避けた方が良いと思います。

終わりに

intellij-rainbow-bracketsのパフォーマンス改善も取り組もうと思っています。

最後に、intellij-rainbow-bracketsが継続的にやっていけるよう、スター・スポンサーもよろしくお願いします。

github.com

追記

改善やりました。
ソースを読んだ限りですが、C#とHaskellは高速化すると思います。

github.com