読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

foreachとwhileの速度差

って、関数を呼び出す事によるオーバーヘッドよりも値型<->参照型のboxing/unboxingによるものが大きいのではないかとふと思いついたので、以下のような簡単なベンチマークによって、その思いつきが正しいかどうか調べてみた。内容は簡単で、0〜10000000までの和を計算して出力するのにかかった時間を調べるというもの。念のため、最適化によって計算自体が消去されてしまわないように、計算した和を最後に出力している。bench1〜bench3はそれぞれ

  • bench1: fromからtoまで、1ずつ増加させながら、関数f(型はInt => Unit)を呼び出すメソッドupto_1を使って計算を行う
  • bench2: fromからtoまで、1ずつ増加させながら、IntAction(Int => Unitを継承している)のインスタンスのapply()を呼び出すメソッドupto_2を使って計算を行う
  • bench3: whileを使って直接計算を行う

というものになっている。ポイントは、IntActionが(Int => Unit)を継承しつつ、applyを再宣言しているところで、このようにすることで、不要なboxing/unboxingを行わないバージョンのapplyが生成される。

実行環境は、以下の通り。

  • CPU: AMD Athlon 64 3000+(2.0GHz)
  • RAM: 1.5GB
  • OS: Windows XP Professional(SP3)
  • JVM: jdk1.6.0(client VM)
  • Scala: Scala 2.7.5 final
abstract class IntAction extends (Int => Unit) {
  def apply(x: Int): Unit
}
def upto_1(from: Int, to: Int)(f: Int => Unit) {
  var i = from
  while(i <= to) { f(i); i += 1 }
}
def upto_2(from: Int, to: Int)(f: IntAction) {
  var i = from
  while(i <= to) { f(i); i += 1 }
}
val MAX = 10000000
object bench1 extends scala.testing.Benchmark {
  def run {
    var sum = 0L
    upto_1(0, MAX){i =>
      sum += i
    }
    println("sum = " + sum)
  }
}
object bench2 extends scala.testing.Benchmark {
  def run {
    var sum = 0L
    upto_2(0, MAX)(new IntAction {
      def apply(i: Int) { sum += i; }
    })
    println("sum = " + sum)
  }
}
object bench3 extends scala.testing.Benchmark {
  def run {
    var sum = 0L
    var i = 0
    while(i <= MAX) { sum += i; i += 1 }
    println("sum = " + sum)
  }
}
println(bench1.runBenchmark(10))
println(bench2.runBenchmark(10))
println(bench3.runBenchmark(10))

その結果、以下の出力が得られた(sum = の部分は余分なので省略。リストの各要素が合計値を計算するのにかかった1回の時間を表している)。

(snip)
List(406, 391, 391, 375, 391, 375, 391, 391, 360, 359)
(snip)
List(109, 93, 93, 94, 110, 94, 79, 94, 94, 94)
(snip)
List(31, 32, 32, 31, 31, 16, 15, 31, 31, 31)

見ればわかるように、IntActionを使ったbench2の結果(whileループを直に書いたbench3に比べて3倍程度遅い)は、bench1(bench3に比べて10倍程度遅い)に比べてかなり改善している。さらに、-serverオプションを付けて、server VMで実験してみると、以下の出力が得られた。server VMではbench2とbench3の差がほぼ無くなっているのが面白い。

(snip)
List(360, 313, 296, 313, 313, 313, 313, 312, 437, 312)
(snip)
List(31, 16, 15, 31, 15, 16, 16, 31, 16, 15)
(snip)
List(31, 31, 15, 16, 16, 16, 16, 15, 94, 16)

補足:
upto_1に渡される無名関数について、scalac(2.7.5 final)では、次のような二つのapplyメソッドが生成されるが、upto_1の定義側では、後者(void apply(int))のapplyの存在を知り得ないため、無駄にboxing/unboxingを行う前者のバージョンを呼び出さざるを得ない。

public final java.lang.Object apply(java.lang.Object);
  Code:
   0:   aload_0
   1:   aload_1
   2:   invokestatic    #36; //Method scala/runtime/BoxesRunTime.unboxToInt:(Lja
va/lang/Object;)I
   5:   invokevirtual   #39; //Method apply:(I)V
   8:   getstatic       #45; //Field scala/runtime/BoxedUnit.UNIT:Lscala/runtime
/BoxedUnit;
   11:  areturn

public final void apply(int);
  Code:
   0:   aload_0
   1:   getfield        #12; //Field sum$1:Lscala/runtime/LongRef;
   4:   aload_0
   5:   getfield        #12; //Field sum$1:Lscala/runtime/LongRef;
   8:   getfield        #53; //Field scala/runtime/LongRef.elem:J
   11:  iload_1
   12:  i2l
   13:  ladd
   14:  putfield        #53; //Field scala/runtime/LongRef.elem:J
   17:  return

一方、upto_2に渡されるIntActionの無名サブクラスについても同様に、以下のような二つのapply()が生成されるが、upto_2の定義側では、渡されるのがIntActionのインスタンスであることがわかっているため、オーバーヘッドが少ない後者のapplyを呼び出すことができる。

public java.lang.Object apply(java.lang.Object);
  Code:
   0:   aload_0
   1:   aload_1
   2:   invokestatic    #36; //Method scala/runtime/BoxesRunTime.unboxToInt:(Lja
va/lang/Object;)I
   5:   invokevirtual   #39; //Method apply:(I)V
   8:   getstatic       #45; //Field scala/runtime/BoxedUnit.UNIT:Lscala/runtime
/BoxedUnit;
   11:  areturn

public void apply(int);
  Code:
   0:   aload_0
   1:   getfield        #12; //Field sum$2:Lscala/runtime/LongRef;
   4:   aload_0
   5:   getfield        #12; //Field sum$2:Lscala/runtime/LongRef;
   8:   getfield        #53; //Field scala/runtime/LongRef.elem:J
   11:  iload_1
   12:  i2l
   13:  ladd
   14:  putfield        #53; //Field scala/runtime/LongRef.elem:J
   17:  return

}

追記:
間抜けなことに、upto_1とupto_2の定義で、iをfromではなく0で初期化していたので修正。結果は変わらないはずだけど、念のため結果もベンチマークを取り直したものに差し替え。