scala.collection.mutable.ArrayOpsの遅さ

昨日作った、noboxというライブラリ
https://github.com/xuwei-k/nobox
ベンチマークしたら、巨大な配列の場合は思ったよりそれなりに効果でる、という話


ArrayOpsがなんなのか知らない人は、このあたり
http://docs.scala-lang.org/ja/overviews/collections/arrays.html
まず読みましょう。


ベンチマーク条件

  • version 0.1.1
  • Scala 2.10.3
  • 40000000( 四千万 )の要素のInt配列
  • 比べる対象は、Arrayからのメソッド呼び出しなので、ArrayOpsに暗黙変換されて、そのメソッド呼び出し
  • 前後にGCくらいはしてる
  • それぞれ一回しかやってないので、ちょっと雑*1
  • くわしくは、ソース読んで https://github.com/xuwei-k/nobox/blob/v0.1.1/src/test/scala/Benchmark.scala

https://travis-ci.org/xuwei-k/nobox/jobs/13017641#L305
結果(ArrayOpsとの差が大きかった順から、上位いくつか) *2

  • contains 29.5 倍速い
  • exists 22.8
  • updated 24.7
  • sum 24.0 *3
  • find 21.6
  • map 16.9 *4
  • slice 14.4
  • takeWhile 13.8
  • sorted 13.8 *5
  • drop 11.8
  • splitAt 11.3
  • dropRight 11.4
  • takeRight 11.0

少なくとも、四千万という巨大な配列の場合は、わりと簡単に10倍〜20倍くらいの差がでるんですね。*6ArrayOpsが遅い原因として考えられるのは

  • Boxing、Unboxing
  • 「1要素アクセス毎にメソッド呼び出しになる場合がある?」 vs 「whileループ」
  • Arrayに特化すれば、System.arraycopyなどを使ったほうが、builder*7より速い?
  • その他?

でしょうか。
あと、全部のメソッドが10倍くらい速くなったわけではなく、2〜3倍しか速くならなかったものもあります。


ただ、繰り返しますが、実際そんな巨大な配列扱うことは稀でしょうし、パフォーマンスチューニングするなら、まずは計測しましょう・・・。


もうちょっとライブラリいじって、またなにかあれば書きます。 → 書きました http://d.hatena.ne.jp/xuwei/20131029/1383012766

*1:普通は、何回もやって、平均とる?

*2:引数の条件によって、差が出る、逆に差がでない可能性があるものは、"わざと差がでそうな引数選んでる"場合がある。

*3:Numeric指定できなく、足す方法が固定されてて柔軟性なくなってるので、ちょっとインチキだけど

*4:IntからIntへmapする場合

*5:sumと同じく、柔軟性なくなってるので、ちょっとインチキ

*6:1000とか10000程度でやると、全体的に2〜3倍しか速くならないですが、遅くなることも(ほとんど)ないです

*7:内部的には、scala.collection.mutable.ArrayBuilder使っている箇所は多いのだろうが、builderの+=や++=を呼ぶ際に、一旦boxingとunboxingされてしまってる箇所がある気がする