ScalaでtoSetやtoListとかを使うよりはbreakOutした方が少し速い

ScalaにはtoSetやtoListなどのコレクション変換関数が用意されていますが、これを使うよりはbreakOutを使った方が若干速いよ、という話です。

#rpscalaで@xuwei_kさんに教えて頂きました。

toSetやtoListの使い方

まずはおさらいです。

val tmp = Seq(1, 2, 3)

tmp.toSet
tmp.toList
tmp.toVector

tmpみたいなコレクションがあるとき、toXXXXという関数で色々な型に変換できます。

今回対象とする問題

コレクションにはmapとか色々関数が用意されていますが、mapを呼び出した後でコレクションの型を変換する、というシーンが良くあるかと思います。

val tmp = (0 until 3).map(_ + 1).toSet

みたいな感じで。

mapが一旦終わった段階でコレクションが構築されて、その後で別のコレクションに変換されるので、無駄なのでは・・・と思います。これは実際無駄なので、breakOutを使うと少しだけ速くなるよ！という話です。

breakOutを使う

scala.collection.breakOut です。これをimportしてmapの第二引数に指定して、後はmapの右か変数名の右にSet[Int]というように型を指定すればOKです。

import scala.collection._
val tmp = (0 until 3).map(_ + 1)(breakOut) : Set[Int]

breakOutは一体なんなのかというとCanBuildFromのオブジェクトです。CanBuildFromというのは（正直自分も全部把握していませんが）Scalaのコレクションを構築する為のビルダーです。mapなどの中で使われており、このビルダーによって新たなコレクションが作られる訳です。CanBuildFromは型パラメータによって作るコレクションを切り替えているんですね。

つまり上記の場合、:Setによって「Set型のコレクションを作るビルダーをbreakOutで指定している」ため、わざわざtoSetなどをするよりも速くなる、ということです。mapの実装とか見るとなんとなく分かると思います。

実際速いの？　ベンチマーク

rpscalaの勉強会で実演されたときは大体10%速くなっているようでした。ほんとに速いのか自分でも確認してみることにします。結果を言うと確かに10%くらいは速くなっているようです。

ベンチマークの方法はsbt-jmhを利用します。以下のサイトが詳しいです。

sbt-jmhを使って、Scalaでマイクロベンチマーク – CLOVER

class Foo {

  @Benchmark
  def work1() = {
    (0 until 10000).map(_ + 1).toSet
  }

  @Benchmark
  def work2() = {
    (0 until 10000).map(_ + 1)(breakOut): Set[Int]
  }

  @Benchmark
  def work3() = {
    (0 until 10000).view.map(_ + 1).toSet
  }
}

このようなコードを用意してベンチマークを実行してみます。

work1は非効率なコード。

work2はbreakOutを使った効率的なコード。

work3は関数合成を使った効率的なコード。(viewはバグがあるらしいので微妙とかいう話もあるようですが・・・）

sbtで入って以下のベンチマークを実行します。20回繰り返して平均を取っています。JITなどの考慮があるのでウォームアップとして事前に処理を10回行っておき、精度を高めます。

run -i 20 -wi 10 -f1 -t1

以下が結果です。

[info] # Run complete. Total time: 00:01:31
[info] 
[info] Benchmark   Mode  Cnt    Score    Error  Units
[info] Foo.work1  thrpt   20  396.129 ± 25.559  ops/s
[info] Foo.work2  thrpt   20  436.958 ±  6.705  ops/s
[info] Foo.work3  thrpt   20  396.479 ± 10.016  ops/s

Scoreが高いほど速いです。何回か実行してみましたが、breakOutの方が10%ほど速いようです。ここに載せた結果だとview版微妙な感じですが、これも割と速くなっているような印象はありました。

 

breakOutを使うかどうかは悩みどころですが、選択肢の１つとして頭の片隅に入れておくのはどうでしょうか？

以上、breakOutでした。

 - Scala Collection