Hatena::ブログ(Diary)

scalaとか・・・ このページをアンテナに追加 RSSフィード Twitter

2013-07-09

Scalaにおける細かい最適化のプラクティス

| 09:42 | Scalaにおける細かい最適化のプラクティスを含むブックマーク Scalaにおける細かい最適化のプラクティスのブックマークコメント

列挙順自体はとくに意味ありません。あと「どの最適化がどのくらい速くなるのか?」を詳細に計ったことはないですし、「原理的にこうなってるから(ry」というのを説明するに過ぎません。中には「JITで無意味になるようなどうでもいい細かすぎること」も書いてありますし、最適化のトレードオフとして失うものもあるので、そのあたり自己責任でお願いします。本当に最適化が必要とされる場合は、以下のものを無闇に実行するよりまず計測したほうがいいのは、言うまでもありません。*1


1. private[this]をつかえ

scalaのvalやvarは、private[this]にしたときのみ、直接のフィールドアクセスになります(それ以外ではメソッド呼び出し)。シングルトンのobjectの場合も同様です。private[this]をつけられる場合はできるだけつけましょう



2. なんでもかんでもListをつかうな

最初の入門でListをだす場合が多いことにより(?)明らかにListでないほうがいいのにもかかわらず、Listを使っている初心者向けの解説がかなり多く巷にあふれています。ScalaのListは片方向なLinkedListです。末尾に追加したり、長さを取得したら、O(n)のコストがかかります。また、再帰的構造になっていることにより、Arrayなどに比べたらそれ自体では余計にメモリを消費します。tailの部分をいくつかのListが共有するなどの場合は、全体として逆にメモリ消費は抑えられるかもしれませんが、そういう使い方をする可能性がない場合他のコレクションの使用の検討をしましょう。

この表

http://docs.scala-lang.org/ja/overviews/collections/performance-characteristics.html

をよくみて、適切なコレクション使いましょう。



3. Streamの代わりにIteratorなどの使用の検討

Listと同様Streamも(Iteratorなど他のもので済むのにも関わらず)使われていることが多すぎます。この部分のコード

https://github.com/scala/scala/blob/v2.10.2/src/library/scala/collection/immutable/Stream.scala#L1077-L1090

みればわかると思いますが、スレッドセーフにするためにsynchronizedしていたりして、要素を評価するたびに余計にコストがかかるはずです。また、構造的にはListと同じで片方向LinkedListなので、メモリ消費や性能特性でもListと同じデメリットを持ちます。

「無限に要素を持てる」

というのが、かっこ良く紹介されがちですが、個人的にはIteratorでmethod chainして処理した後、toList、toArray、toVectorなどで評価することが多く、あまりStream使いません。

  • 複数スレッドからのアクセスをしない
  • 本当は遅延評価必要ない(どちらにしろ、結局その後でtoListやtoArrayを呼ぶ。もしくは、すぐ全要素を舐める)

なら、上記のようにIteratorで前処理したあとArrayやVectorなどにすぐ変換でいいと思います。

あと、「全要素を一度しか舐める必要ない(最後にfoldLeftなどを呼んで使い切るだけの場合など)」場合も、わざわざStreamではなくVectorにする必要さえ無く、最初から最後までIteratorのほうがいいはずです。

あと余談として、IteratorをtoSeqすると(現状の実装においては)Streamになるので、注意しましょう



4. 必要ないのにlazy valをつかうな

lazy valも初期化フラグをチェックしてsynchronizedしてるので、ある程度のコストがかかります。「明らかに必要ない場合や、valの並び替え*2で済む場合」は、使わないほうがいいです。ただし、開発途中でclass内にvalが大量にあり、初期化順考えるとか面倒でやってられない場合などは、素直にlazy val(もしくはdef)使いましょう。valの初期化順のバグはかなりわかりにくいバグになるので、この最適はあまり初心者にはオススメできません。あと、traitの継承順により、valではなくlazy valにする必要があったりするので注意が必要です。



5. 高階関数と末尾再帰とwhile

foreachやfoldLeftやmapなどの処理に函数オブジェクトを渡すのと、末尾再帰で独自に書くのでは、末尾再帰はwhile相当(ジャンプ命令)に置き換わるので、Scalaに限っては末尾再帰のほうがはやいかもしれません(?)だた、コードの抽象化やバグの混入率を考えると、一般的には高階関数使ったほうがいいです。

Scalaの標準ライブラリ内でも、おそらくそのあたりを考慮して(高階関数のみですむような場合でも)

「メソッド内メソッドで末尾再帰」もしくは「whileとvarを使用」してる箇所が多くあります



6. メソッド定義の代わりに函数オブジェクトをvalで保持することの検討

例えば以下のように

object A{
  private def foo(i: Int): String = i.toString
 
  def bar = {
    val a = intList.map(foo)
    // その他コード続く
  }
  • def fooはbarから参照されて、函数オブジェクトとしてしか使われない
  • fooが多相でない
  • fooはobject内にあるなど、函数オブジェクトとして保持してもメモリ上ほとんど不都合がない*3

場合は、最初から以下のように

object A{
  private[this] val foo: Int => String =
    (i: Int) => i.toString

としておいたほうが

intList.map(foo)の部分で毎回メソッドから函数オブジェクトが生成される」

というコストが減って、理論上有利なはずです。また、この場合もprivate[this]に出来る場合はそうしましょう。

ただし、valとlazy valのところで書いた初期化順に注意しなくていはいけなくなるデメリットがあります。



7. finalでのインライン化

Scalaにおけるfinalは「オーバーライドさせない」ことを表すだけでなく、「inline化の指定」を表す場合があること知ってましたか?例えば以下のコードにおけるbは

object A{
  final val a = "a"
  val b = a + "b"
}

コンパイル時に"ab"の文字列になります。finalをつけないとなりません。

scala -Xprint:typer -e 'object A{ val a = "a" ; val b = a + "b" }'

scala -Xprint:typer -e 'object A{ final val a = "a" ; val b = a + "b" }'

を実行してみてください



8. ListBufferとArrayBufferとArrayBuilder

Listと同じく、「適していないのにも関わらず必要以上にListBufferが使われている」場面を多く見かけます。ArrayBufferなどのほかのものも検討しましょう。

http://docs.scala-lang.org/ja/overviews/collections/performance-characteristics.html

ArrayBuilderについては以前これ

Scala で Hadoop のjava.lang.Iterable Writable を処理する際の話

のときに言いましたが

そういうことです。



9. プリミティブ型とArray

ArrayBuilderの話と微妙に重複しますが、プリミティブ型の場合はArrayもしくはWrappedArrayで保持したほうが、単体でのメモリ効率に関しては抜群によくなるはずです。List[Int]などでは、boxingやunboxingが発生します。

もちろん、「何度もつなげたり、分割したり」するなら、「構造が共有される」ことによって全体としてVectorやListのほうが効率良くなることもありえますが。ただ、そういう場合は、一旦mutableなArrayBufferやArrayBuilderで構築してから、最後Arrayに変換というやり方もありでしょう。



10. specialized annotation

あまり凝ったライブラリ以外で使ってるの見たこと無いですが*4手軽に使えるので、もうちょっとみんな使用を検討してもいいのでは?

ただし、生成されるバイナリサイズが大きくなるというデメリットはあります。*5



11. コンパイルオプション

あまり使われてるの見たことないですが、optimize というコンパイルオプションあります。*6しかし紹介しておいて無責任ですが、具体的にどのような最適化がされるのかは、詳しく知りません。あと、targetをjvm1.7以降に指定とかもできますが、(Scala2.10においてデフォルトはjvm1.6)、そうすると1.7以降の新機能使って最適化されたバイトコードが生成されたりするんでしょうか?



12. value classの使用

これはもちろん、使える場面があるなら積極的に使いましょう。



13. Tuple3以上でプリミティブ型を保持するとboxingされる

specialized annotationは、Tuple2までしかついていない*7ので、プログラムの読みやすさからの観点からも、パフォーマンスの観点からも、

Tuple3[Int, Long, String]

などの型は使わずに、

case class Foo(a: Int, b: Long, c: String)

というように、独自のcase classを作って使うべきです*8




追記:

「Scalaにおける細かい最適化のプラクティス」への反応

*1:あと、さらに言っておくと、中上級者向けの豆知識的なものであり、初心者は基本的に気にする必要ないし、初心者はもっとほかに先に(最適化以外の面で)知るべきことがたくさんあります

*2:class内のlazyでないvalは上から順に初期化されるという仕様

*3:class内にあって、もしそのclassのインスタンスが大量に生成されることがあるなら、「そのクラスのインスタンスが生成されるたびに函数オブジェクトも生成」されてデメリットが大きいという意味

*4:例えば spire は徹底的に使ってる https://github.com/non/spire

*5:他になにかデメリットあったっけ?

*6:それ以外にも、最適化関連のオプションあります

*7https://github.com/scala/scala/blob/v2.10.2/src/library/scala/Tuple2.scala#L19 https://github.com/scala/scala/blob/v2.10.2/src/library/scala/Tuple3.scala#L20

*8:ただし、2.11からこれ https://twitter.com/xuwei_k/status/324336972250353665 のような例外がありますが