前書き
Scalaを普段の業務や学習で利用する際に、コードジャンプなどでメソッドの定義を確認したり内部処理を調べたりといったことはままあることかと思います。
私もScalaはまだ初学者レベルなので、主に学習を目的としてライブラリの実装などはよく参考にさせて頂いたりします。
その中で、ひと目見たときからずっと気になっていた実装がありました。それがTraversableLikeのexistsメソッドです。※1
def exists(p: A => Boolean): Boolean = {
var result = false
breakable {
for (x <- this)
if (p(x)) { result = true; break }
}
result
}
※出典: scala/TraversableLike.scala at v2.9.2 · scala/scala
最初見たときは、なぜreturnではなくbreakでループを抜ける手法を使っているのだろう？と思いました。
きっと何か事情があるのだとは判りつつもずっと調べず放置していましたが、実践Scala入門の本を読んでようやく理由がわかりました。
特に、関数リテラルから作られる関数オブジェクト内でreturnを使用すると、バイトコード上で例外のthrowとcatchとして解釈されるため、あまり効率が良くないことに注意してください。実行頻度の高い場所で、この種のreturnを使用すると性能に悪影響を与えます。
出典: 瀬良和弘・水島宏太・河内崇・麻植泰輔・青山直紀 (2018)『実践Scala入門』 技術評論社 p274.
どうやらScalaでは、関数オブジェクト内でのearly returnは遅いらしいのです。※2
これで謎は解けました。
でも、やはりreturnとbreakではどれほど差がでるんだろう？と気になってしまいますよね。
というわけで今回、ちょっとだけ検証をしてみました。
検証
検証用コードの準備
簡単なコードを書いてパフォーマンスを測定してみます。
今回はもともと気になったexistsと似た処理を、breakとreturnを用いてそれぞれ用意し、JMHでベンチマークをとってみることとします。
大変雑なコードですが、以下のようなコードを用意してみました。
package benchmark
import scala.util.control.Breaks
import org.openjdk.jmh.annotations.{ Benchmark, Scope, State }
@State(Scope.Thread)
class EarlyReturnTest {
val numSeq = Seq(1,2,3,4,5)
val b = new Breaks
@Benchmark
def existsWithBreak(): Boolean = {
var result = false
b.breakable {
for (x <- numSeq)
if (x == 5) { result = true; b.break }
}
result
}
@Benchmark
def existsWithReturn(): Boolean = {
for (x <- numSeq)
if (x == 5) { return true }
false
}
}
やっていることは、要素が5つのSeqに対して『5』が含まれているかを判定するだけですが、
見てのとおり、前者がbreakをつかってループを抜ける実装、後者がreturnで処理を終了させる実装にしています。
パフォーマンスの計測
早速JMHを用いてパフォーマンスを計測してみます。
> jmh:compile
> jmh:run -i 10 -wi 20 -f1 -t1
一応JMHの公式ドキュメントに則り、ウォームアップイテレーションは20回、イテレーションは10回で実行してみます。
その結果がコチラ↓
[info] Benchmark Mode Cnt Score Error Units
[info] EarlyReturnTest.existsWithBreak thrpt 10 84887350.071 ± 1249431.724 ops/s
[info] EarlyReturnTest.existsWithReturn thrpt 10 44777889.387 ± 2935297.651 ops/s
[success] Total time: 606 s, completed 2019/06/06 0:04:50
breakで実装したexistsが、returnで実装したexistsと比較して倍に近いスコアを叩き出しました。
この結果から、確かにearly returnを使って実装した処理はbreakをつかって実装した処理よりも遅くなるということが言えそうです。
ほぼ同じ処理を行っているにもかかわらず、これほど差が開くとは思っていなかったので驚きですね。
【追記: breakとreturnのパフォーマンス差について(2019/06/16)】
後述の追記でも記載していますが、**決して『returnは遅くbreakは速い』ということは無く、『どちらも遅い可能性が高いが、当方で検証の結果幾分かパフォーマンス面で差が見られた』**ということだけです。
遅くなる原因を探る
early returnが遅くなってしまう原因は、先程の引用に拠るならば、関数オブジェクト内でのearly returnはバイトコード上では例外のthrowとcatchと解釈されるため、そのせいでオーバーヘッドが生まれてしまっているのが原因とのこと。※3
折角なので、ちょっと詳しく見てみます。
【追記: breakの実装について(2019/06/16)】
こちらコメントにて @xuwei_k さんにご指摘頂いたおかげで判明したのですが、関数リテラル内でのreturnだけでなくbreakableの方も例外を用いた実装になっています。
https://github.com/scala/scala/blob/v2.13.0/src/library/scala/util/control/Breaks.scala#L40-L47
なので上記の『early returnはthrowとcatchと解釈されるので遅い』というのは強ち間違ってはいませんが、決して『breakは早いがreturnは遅い』ということは無く、『どちらも例外を用いた実装でありどちらも遅い』というのが正解のようです。
デコンパイルしてみる
本当に例外を投げているのでしょうか？とりあえずデコンパイルして確認してみます。
Java Decompilerを使ってコンパイルされた先程のコードをデコンパイルしてみます。
public boolean existsWithReturn() {
Object object = new Object(); try {
numSeq().foreach(object::$anonfun$existsWithReturn$1);
}
catch (NonLocalReturnControl ex) {
if (ex.key() == object) {
} else {
throw ex;
}
}
return false;
}
完全には読み解けていませんが、確かにtryとcatchが使われており、NonLocalReturnControlをキャッチしそうな様子が確認できますね！
バイトコードを見てみる
私はJVM等についての知識は皆無ですが、バイトコードの方も見てみます。
先程のEarlyReturnTestをscalacでコンパイルし、javapで逆アセンブルしてみます。
Constant pool:
#4 = Class #3 // java/lang/Object
#73 = Utf8 scala/runtime/NonLocalReturnControl
#74 = Class #73 // scala/runtime/NonLocalReturnControl
#77 = Methodref #4.#76 // java/lang/Object."<init>":()V
#76 = NameAndType #75:#38 // "<init>":()V
#78 = NameAndType #14:#19 // numSeq:()Lscala/collection/immutable/List;
#79 = Methodref #2.#78 // benchmark/EarlyReturnTest.numSeq:()Lscala/collection/immutable/List;
#87 = Utf8 apply$mcVI$sp
#88 = Utf8 (Ljava/lang/Object;)Lscala/runtime/java8/JFunction1$mcVI$sp;
#89 = NameAndType #87:#88 // apply$mcVI$sp:(Ljava/lang/Object;)Lscala/runtime/java8/JFunction1$mcVI$sp;
#90 = InvokeDynamic #1:#89 // #1:apply$mcVI$sp:(Ljava/lang/Object;)Lscala/runtime/java8/JFunction1$mcVI$sp;
#96 = Methodref #92.#95 // scala/collection/immutable/List.foreach:(Lscala/Function1;)V
#100 = Methodref #74.#99 // scala/runtime/NonLocalReturnControl.key:()Ljava/lang/Object;
#101 = Utf8 value$mcZ$sp
#102 = NameAndType #101:#29 // value$mcZ$sp:()Z
#103 = Methodref #74.#102 // scala/runtime/NonLocalReturnControl.value$mcZ$sp:()Z
public boolean existsWithReturn();
descriptor: ()Z
flags: ACC_PUBLIC
Code:
stack=2, locals=3, args_size=1
0: new #4 // class java/lang/Object
3: dup
4: invokespecial #77 // Method java/lang/Object."<init>":()V
7: astore_1
8: aload_0
9: invokevirtual #79 // Method numSeq:()Lscala/collection/immutable/List;
12: aload_1
13: invokedynamic #90, 0 // InvokeDynamic #1:apply$mcVI$sp:(Ljava/lang/Object;)Lscala/runtime/java8/JFunction1$mcVI$sp;
18: invokevirtual #96 // Method scala/collection/immutable/List.foreach:(Lscala/Function1;)V
21: iconst_0
22: goto 46
25: astore_2
26: aload_2
27: invokevirtual #100 // Method scala/runtime/NonLocalReturnControl.key:()Ljava/lang/Object;
30: aload_1
31: if_acmpne 41
34: aload_2
35: invokevirtual #103 // Method scala/runtime/NonLocalReturnControl.value$mcZ$sp:()Z
38: goto 43
41: aload_2
42: athrow
43: goto 46
46: ireturn
Exception table:
from to target type
8 22 25 Class scala/runtime/NonLocalReturnControl
ものすごく長くなったので、なんとな〜く関係ありそうな箇所だけ載せました。
正直こちらもあまり読み解けてはいませんが、30~42がおそらくif (x == 5) { return true }の箇所で、NonLocalReturnControlをthrowしているような雰囲気がありますね。
(間違っていたらすみません。。)
おわりに
今回の検証で、確かにearly returnは遅くなるということが確認できました。
既存の機能がどういった意図からそのような実装になっているのかを確認するのは勉強になりますし、何より楽しいですよね。
普段Scalaでreturn文を記述することはあまりないかもしれませんが、頭の片隅にでも入れておくと良いのかもしれません。
また、今回の実装は以下のリポジトリに格納しておりますので、もし宜しければご参照ください。
https://github.com/atsumine/scala-early-return-test
最後になりますが、もし記事の内容に誤りやミス、また不適切な点などございましたら、お気軽にお申し付けください。
すぐに対応をさせていただきます。
ここまでお読み頂き、ありがとうございました！
参考文献など
※1 scala/TraversableLike.scala at v2.9.2 · scala/scala
※2 瀬良和弘・水島宏太・河内崇・麻植泰輔・青山直紀 (2018)『実践Scala入門』 技術評論社 p274.
※3 上述書同ページに記載.