Scalaの early return は遅いのか？ (追記あり)

## 前書き
Scalaを普段の業務や学習で利用する際に、コードジャンプなどでメソッドの定義を確認したり内部処理を調べたりといったことはままあることかと思います。
私もScalaはまだ初学者レベルなので、主に学習を目的としてライブラリの実装などはよく参考にさせて頂いたりします。

その中で、ひと目見たときからずっと気になっていた実装がありました。それが`TraversableLike`の`exists`メソッドです。※1

```scala
 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](https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/TraversableLike.scala#L351-L358)

最初見たときは、なぜreturnではなくbreakでループを抜ける手法を使っているのだろう？と思いました。
きっと何か事情があるのだとは判りつつもずっと調べず放置していましたが、実践Scala入門の本を読んでようやく理由がわかりました。

> 特に、関数リテラルから作られる関数オブジェクト内でreturnを使用すると、バイトコード上で例外のthrowとcatchとして解釈されるため、あまり効率が良くないことに注意してください。実行頻度の高い場所で、この種のreturnを使用すると性能に悪影響を与えます。
>
> 出典: 瀬良和弘・水島宏太・河内崇・麻植泰輔・青山直紀 (2018)『実践Scala入門』 技術評論社 p274.

どうやらScalaでは、関数オブジェクト内でのearly returnは遅いらしいのです。※2

これで謎は解けました。
でも、やはりreturnとbreakではどれほど差がでるんだろう？と気になってしまいますよね。
というわけで今回、ちょっとだけ検証をしてみました。

## 検証
### 検証用コードの準備
簡単なコードを書いてパフォーマンスを測定してみます。
今回はもともと気になった`exists`と似た処理を、breakとreturnを用いてそれぞれ用意し、JMHでベンチマークをとってみることとします。

大変雑なコードですが、以下のようなコードを用意してみました。

```scala

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を用いてパフォーマンスを計測してみます。

```shell
> jmh:compile
> jmh:run -i 10 -wi 20 -f1 -t1
```
一応JMHの公式ドキュメントに則り、ウォームアップイテレーションは20回、イテレーションは10回で実行してみます。
その結果がコチラ↓

```shell_session
[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を使ってコンパイルされた先程のコードをデコンパイルしてみます。

```java
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で逆アセンブルしてみます。

```java
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](https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/TraversableLike.scala#L351-L358)
※2 瀬良和弘・水島宏太・河内崇・麻植泰輔・青山直紀 (2018)『実践Scala入門』 技術評論社 p274.
※3 上述書同ページに記載.