ベンチマーク

Scala で処理時間を計測する Benchmark trait があったので
試しに 1から100万の整数要素を持つリストの各要素を合計する計算処理の時間を、
末尾再帰関数、forループ、whileループ、List の sum で計測してみた。

Benchmark の runBenchmarkメソッドは引数の times で計測の回数を指定し、
計測回数分の計測結果が入った List[Long]をかえしてくれる。計測結果の時間の単位はミリ秒。
Benchmark には multiplier フィールドがあり 1回の計測で計測対象の処理を
何回実行するかを指定できる。デフォルト値は 1 が指定されている。
ここで multiplier はデフォルト値 1 のままで実行。times はデフォルト引数で 10 回を指定。

import scala.annotation.tailrec
import scala.testing.Benchmark

object Test {
  def main(args: Array[String]) = {
    val list = (1 to 1000000).toList
    test("Test1", sum(list.head, list.tail))
    test("Test2", sum2(list))
    test("Test3", sum3(list))
    test("Test4", list.sum)
  }

  final def test(name: String, f: => Any, times: Int = 10) = {
    val result = new Benchmark { def run() = f }.runBenchmark(times)
    println(name + ": " + (result.sum / result.size) + " " + result)
  }

  @tailrec
  final def sum(acc: Int, list: List[Int]): Int = {
    if (list.isEmpty) acc else sum(acc + list.head, list.tail)
  }

  final def sum2(list: List[Int]): Int = {
    var cnt = 0;
    for (i <- list) { cnt += i }
    cnt
  }

  final def sum3(list: List[Int]): Int = {
    var cnt = 0;
    var tmp = list
    while (!tmp.isEmpty) {
      cnt += tmp.head
      tmp = tmp.tail
    }
    cnt
  }
}

[実行結果]
処理10回の計測テストを4回やってみた。
結果は10回の計測結果の平均値と各10回の計測結果のリストの内容を表示。
Test1:末尾再帰 Test2:for Test3:while Test4:list.sum
最適化された末尾再帰関数と while ループは、ほぼ同じくらいで最も早く、
以外にも Scala の List に元からある list.sum が一番遅かった。
for は while よりは遅く list.sum よりは早かった。

$ scala -version
Scala code runner version 2.9.1 -- Copyright 2002-2011, LAMP/EPFL
$ scala Test
Test1: 44 List(33, 51, 26, 44, 46, 44, 45, 64, 44, 44)
Test2: 53 List(57, 53, 53, 53, 53, 53, 53, 53, 52, 53)
Test3: 42 List(31, 47, 25, 44, 45, 44, 45, 48, 45, 48)
Test4: 72 List(59, 101, 50, 73, 73, 74, 73, 73, 76, 73)
$ scala Test
Test1: 41 List(32, 48, 25, 44, 44, 44, 44, 44, 44, 47)
Test2: 56 List(58, 53, 55, 53, 54, 53, 79, 53, 53, 54)
Test3: 45 List(31, 50, 25, 71, 45, 46, 47, 45, 47, 45)
Test4: 71 List(83, 71, 42, 76, 76, 78, 76, 78, 66, 66)
$ scala Test
Test1: 41 List(32, 48, 25, 45, 44, 44, 44, 44, 45, 45)
Test2: 52 List(55, 53, 52, 53, 53, 52, 53, 52, 52, 52)
Test3: 41 List(31, 49, 24, 45, 44, 44, 45, 45, 45, 44)
Test4: 64 List(53, 70, 41, 65, 77, 65, 73, 66, 66, 66)

Benchmark.scala のソースファイル

Benchmark.scala の runBenchmarkメソッドの実装をみてみると

計測の開始時の時刻と終了時の時刻を Platform.currentTime *1 で計測
1回の計測後にPlatform.collectGarbage *2 を呼び出している。

Platform object の各メソッドには @inline アノテーションが指定されていたが、
これは C の inline と同じようなものかな ?

..snip..
  def runBenchmark(noTimes: Int): List[Long] =
    for (i <- List.range(1, noTimes + 1)) yield {
      setUp
      val startTime = Platform.currentTime
      var i = 0; while (i < multiplier) {
        run()
        i += 1
      }
      val stopTime = Platform.currentTime
      tearDown
      Platform.collectGarbage

      stopTime - startTime
    }
..snip..

[参考]
hishidamaさんの Scala Benchmark ページ

*1:Platform.currentTime は java の System.currentTimeMillis()

*2:Platform.collectGarbage は java の System.gc()