Kotlin の Range.forEach は遅いのか?

少し前に、「Kotlinの隠れたコストについてのベンチマーク(原文: Kotlin's hidden costs - Benchmarks)」という記事が話題になりました。

その中で、Kotlin の Range を使った for ループと forEach() の比較があり、forEach() は「絶対に避けた方がよい(should absolutely be avoided)」と結論づけていました。この点と、それに対するはてぶなどの反応が気になりました。

そこで、今回は Range に対する for ループに対象を絞って調べてみました。

記事を見直してみる

元記事にはベンチマーク結果が書かれており、数値は以下のようになっています。

Benchmark                                                                             Mode   Samples         Mean   Mean error    Units
c.a.k.part3.KotlinBenchmarkPart3.kotlinRangeForEachFunction                          thrpt       200   108382.188      561.632   ops/ms
c.a.k.part3.KotlinBenchmarkPart3.kotlinRangeForEachLoop                              thrpt       200   331558.172      494.281   ops/ms
c.a.k.part3.KotlinBenchmarkPart3.kotlinRangeForEachLoopWithStep1                     thrpt       200   331250.339      545.200   ops/ms

確かに forEach を使用したベンチマーク (kotlinRangeForEachFunction) は他と比べ 3 倍かかっています。しかしこれだけで本当に「絶対に避けた方が良い」と言えるほどの差なのでしょうか。

結果を良くみてみましょう。単位は全て ops/ms とあります。これを元に「一回の処理に秒かかったか」を計算すると以下のようになります。

名称	内容	スコア
kotlinRangeForEachFunction	forEach()呼び出し	9.227(ns/op)
kotlinRangeForEachLoop	for … in ループ	3.016(ns/op)
kotlinRangeForEachLoopWithStep1	for … in … by ループ	3.019(ns/op)

ここで行なっている処理は 1..10 に対する処理です。つまりこの「3倍の差」というのは 10 回のループに 9 ナノ秒かかるか 3 ナノ秒かかるかの違いです。

ちなみに元のベンチマークでは Core i7 の MacBook Pro を使っているようですが、Android 7.1.2 上の Pixel によるベンチマークを試した方もいるようです。for ループが 170 ナノ秒程度なのに対し、forEach() を使った場合は約3倍の 500 ナノ秒程度かかるようです。

果たしてこの差はどれくらいの影響を与えるのでしょうか。

他の処理と比較してみる

ナノ秒レベルの数字を出されてもいまいち実感がないかもしれません。そこで少し処理を変えながら比較してみました。

なお計測対象のマシンは以下の通りです。

• 機種 … Nexus5x
• CPU … Qualcomm Snapdragon 808 1.8GHz (2コア)+ 1.4GHz (4コア)
• メモリ … 2GB
• OS … Android の 8.0.0

Kotlin の Range ループ

元のベンチマークでも行われている Range の for ループと forEach() 関数を使った処理を呼び出しました。

forEach() 呼び出し(t0_range_forEachFunction)

fun rangeForEachMethod(blackHole: BlackHole) {
    (1..10).forEach {
        blackHole.consume(it)
    }
}

for　… in ループ(t0_range_forEachLoop)

fun rangeForEachLoop(blackHole: BlackHole) {
    for (it in 1..10) {
        blackHole.consume(it)
    }
}

結果

やはり forEach() 呼び出しを使うと遅く、 6〜7 倍の時間がかかっています。しかし先ほどの Android ベンチマークと比べて 100 ナノ秒ほど速くなっています(これはプログラムを修正したためで、詳細は後述します)

ループの中で他の処理を行う

現実的には空の処理を行う事は無いでしょうから、他の処理を含めてみました。

1要素の Int 配列の生成 (t1_rangeForEachLoop_withArrayCreation)

fun rangeForEachLoopWithArrayCreation(blackHole: BlackHole) {
    for (it in 1..10) {
        blackHole.consumeArray(intArrayOf(it))
    }
}

Int? へのキャスト (t1_rangeForEachLoop_withBoxing)

fun rangeForEachLoopWithBoxing(blackHole: BlackHole) {
    for (it in 1..10) {
        blackHole.consume(it as Int?)
    }
}

Optional に変換すると、遅いと言われる Auto Boxing が行われます

大きな数字の Int? へのキャスト(t1_rangeForEachLoop_withBoxingLargeNum)

fun rangeForEachLoopWithBoxingLargeNum(blackHole: BlackHole) {
    for (it in 1001..1010) {
        blackHole.consume(it as Int?)
    }
}

Java では 127 までの int の Auto Boxing は最適化されています。それより大きな数は毎回 Integer が生成されるようになり、さらに遅くなります。

配列へのランダムなアクセス (t1_rangeForEachLoop_withRandomAccess)

fun rangeForEachLoopWithRandomAccess(blackHole: BlackHole, ra: RandomAccessor) {
    for (it in 1..10) {
        blackHole.consume(ra.next(it))
    }
}

ra.next() 呼び出しを行うと、配列の要素へのアクセスが1回だけ行われます。何番目にアクセスするかはランダムです。配列は100万要素と大きめになっていて、これによって CPU のキャッシュアクセスができないようになっています。

結果

注目すべきはランダムアクセスにかかる時間でしょう。元の for ループよりも約 35 倍もの時間がかかっています。Auto Boxing や配列の生成と比べても何倍も時間がかかっています。

これは、メモリが CPU のキャッシュに乗ってない事が原因と言えるでしょう。一般にキャッシュに乗らない場合に 100 倍遅くなる事は珍しい事ではありません。それでも遅延時間は 1 回のアクセスにつき 200 ナノ秒程度である事は注目に値する所です。

Auto Boxing や配列の生成がある場合も forEach() と同等の時間がかかるようですので、forEach() の最適化の前にオブジェクトを生成していないかを確認した方が良いでしょう。

Java の for ループ

元のベンチマークには Java のループのベンチマークはありません。参考までに Java のループを追加し、他の処理(forEach()関数と Range に対する for ループ)と比較追加してみました。

結果

多少小さくなっていますが、10回のループで数十ナノ秒程度の差であり、誤差の範囲です。

インライン展開

以上の処理には、ループ自体のコストの時間の他に、blackHole.consume(…) という呼び出しの時間が含まれています。この関数は、過剰な最適化を防ぐためのダミーの処理が書かれています(この処理が無いと空のループなどはループ自体が削除されてしまって計測できなくなります)。

このダミーの処理がどれくらいかかっているかを見るために、10回のループを展開して計測してみました。また、1回/2回/4回のループも追加しています。

結果

かかった時間は for ループと大きく変わりません。つまり、今まで行ったベンチマークのうち、50ナノ秒程度は blackHole.consume(…) 呼び出しにかかっていると思われます。特に for ループを使った処理の大半はこの処理で占められている事が想定されます。

まとめ

例のベンチマークの記事が出て「forEach() は絶対に避けるべき」と書かれているのを見て「そんなわけあるか！」とつっこみたくなったのは僕だけではないでしょう。

Kotlin の Range を使った for ループは極めて速く、ボトルネックとなる事はまずないと言えるのではないでしょうか。また Kotlin の forEach() ループは相対的に遅いと言えますが、「ループ内の処理が極めてシンプル」でかつ「大量に呼び出される」場合を除き、その影響が顕在化する事は無いと思われます。

またこの種のマイクロベンチマークはもちろん有効ではありますが、鵜呑みにするのも危険でしょう。今回の例だと、計測対象とは関係のない blackHole.consume(…) という処理がベンチマーク結果に大きな影響を与えていました。(なお元の Android 向けのベンチマークでは blackHole が不正確な結果をもたらしているように思われたので、大きく修正しています。今回のベンチマーク結果が多少速くなっているのはそのためです)

ちなみに、今回のベンチマークにしようしたプログラムは以下に公開しています。

最後に、多少の演算処理や関数呼び出しよりもメモリアクセスの方がはるかに時間がかかると言えると思います。ちなみに少し前に参考になるツイートや資料が話題になりましたので、リンクを貼っておきます。

この表いいな。HDDが遅いことがよくわかる(大陸またぐのと一桁しか違わない)。https://t.co/w5W0bLTyge pic.twitter.com/e2TccGVp7q

— TT@北海道 (@edy555) 2017年8月11日

ソースと思われる資料(英語)
https://gist.github.com/jboner/2841832