つかびーの技術日記

情報系修士卒のWeb系技術日記です。現在のフォーカス分野はアドテクです。

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

      2015/03/22

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

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

toSetやtoListの使い方

まずはおさらいです。

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

今回対象とする問題

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

みたいな感じで。

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

breakOutを使う

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

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

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

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

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

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

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

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

work1は非効率なコード。

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

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

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

以下が結果です。

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

 

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

以上、breakOutでした。

 - Scala