benchmarks.scala

import scala.collection.mutable.WrappedArray

abstract class Impl(val name: String) {
  val N = 20000
  val R = 100

  def setup(n: Int): Unit = ()
  def run(n: Int): Unit

  def time(n: Int): Long = {
    val start = System.nanoTime
    run(n)
    val end = System.nanoTime
    end - start
  }

  def avgTime(n: Int): Double = {
    System.gc()
    setup(n)
    for (_ <- 0 until N) {
      time(n)
    }
    (0 until N).map(_ => time(n)).sum.toDouble / N / 1000000
  }
}

trait ListSetup {
  self: Impl =>
  var xs: List[Int] = Nil
  override def setup(n: Int) {
    val b = List.newBuilder[Int]
    b ++= (1 to n)
    xs = b.result
  }
}

trait VectorSetup {
  self: Impl =>
  var xs = Vector.empty[Int]
  override def setup(n: Int) {
    val b = Vector.newBuilder[Int]
    b ++= (1 to n)
    xs = b.result
  }
}

trait WrappedArraySetup {
  self: Impl =>
  var xs = WrappedArray.newBuilder[Int].result
  override def setup(n: Int) {
    val b = WrappedArray.newBuilder[Int]
    b ++= (1 to n)
    xs = b.result
  }
}

trait EmptyList {
  val E = Nil
}

trait EmptyVector {
  val E = Vector.empty[Int]
}

trait EmptyWrappedArray {
  val E = WrappedArray.newBuilder[Int].result  
}


trait Append {
  self: Impl =>
  val E: Seq[Int]

  def run(n: Int) {
    var i = 0
    var c = E
    while (i < n) {
      c = c :+ i
      i += 1
    }
  }
}

object ListAppend extends Impl("List append") with Append with EmptyList
object VectorAppend extends Impl("Vector append") with Append with EmptyVector
object WrappedArrayAppend extends Impl("WrappedArray append") with Append with EmptyWrappedArray

trait Prepend {
  self: Impl =>
  val E: Seq[Int]

  def run(n: Int) {
    var i = 0
    var c = E
    while (i < n) {
      c = i +: c
      i += 1
    }
  }
}

object ListPrepend extends Impl("List prepend") with Prepend with EmptyList
object VectorPrepend extends Impl("Vector prepend") with Prepend with EmptyVector
object WrappedArrayPrepend extends Impl("WrappedArray prepend") with Prepend with EmptyWrappedArray

trait Concat {
  self: Impl =>
  def xs: Seq[Int]
  val E: Seq[Int]

  def run(n: Int) {
    var i = 0
    var c = E
    while (i < 10) {
      c = c ++ xs
      i += 1
    }
  }
}


object ListConcat extends Impl("List concat") with Concat with EmptyList with ListSetup
object VectorConcat extends Impl("Vector concat") with Concat with EmptyVector with VectorSetup
object WrappedArrayConcat extends Impl("WrappedArray concat") with Concat with EmptyWrappedArray with WrappedArraySetup

trait Match {
  self: Impl =>
  def xs: Seq[Int]
  val E: Seq[Int]

  def run(n: Int) {
    var i = 0
    while (i < R) {
      xs match {
        case E => 0
        case h +: t => 1
      }
      i += 1
    }
  }
}

object ListMatch extends Impl("List match") with Match with EmptyList with ListSetup
object VectorMatch extends Impl("Vector match") with Match with EmptyVector with VectorSetup
object WrappedArrayMatch extends Impl("WrappedArray match") with Match with EmptyWrappedArray with WrappedArraySetup

trait Length {
  self: Impl =>
  def xs: Seq[Int]
  def run(n: Int) {
    var i = 0
    while (i < R) {
      xs.length
      i += 1
    }
  }
}

object ListLength extends Impl("List length") with Length with ListSetup
object VectorLength extends Impl("Vector length") with Length with VectorSetup
object WrappedArrayLength extends Impl("WrappedArray length") with Length with WrappedArraySetup


trait Map {
  self: Impl =>
  def xs: Seq[Int]
  def run(n: Int) {
    xs.map(x => x+1)
  }
}

object ListMap extends Impl("List map") with Map with ListSetup
object VectorMap extends Impl("Vector map") with Map with VectorSetup
object WrappedArrayMap extends Impl("WrappedArray map") with Map with WrappedArraySetup

trait FlatMap {
  self: Impl =>
  def xs: Seq[Int]
  val ys: Seq[Int]
  def run(n: Int) {
    xs.flatMap(x => ys)
  }
}

object ListFlatMap extends Impl("List flatMap") with FlatMap with ListSetup {
  val ys = List.fill(20)(1)
}

object VectorFlatMap extends Impl("Vector flatMap") with FlatMap with VectorSetup {
  val ys = Vector.fill(20)(1)
}

object WrappedArrayFlatMap extends Impl("WrappedArray flatMap") with FlatMap with WrappedArraySetup {
  val b = WrappedArray.newBuilder[Int]
  b ++= (1 to 20)
  val ys = b.result
}

trait Foreach {
  self: Impl =>
  def xs: Seq[Int]
  def run(n: Int) {
    xs.foreach(x => ())
  }  
}

object ListForeach extends Impl("List foreach") with Foreach with ListSetup
object VectorForeach extends Impl("Vector foreach") with Foreach with VectorSetup
object WrappedArrayForeach extends Impl("WrappedArray foreach") with Foreach with WrappedArraySetup

trait Filter {
  self: Impl =>
  def xs: Seq[Int]
  def run(n: Int) {
    xs.filter(x => x % 2 == 0)
  }
}

object ListFilter extends Impl("List filter") with Filter with ListSetup
object VectorFilter extends Impl("Vector filter") with Filter with VectorSetup
object WrappedArrayFilter extends Impl("WrappedArray filter") with Filter with WrappedArraySetup



class Benchmark(impls: List[Impl]) {
  def this(impls: Impl*) = this(impls.toList)

  val df = new java.text.DecimalFormat("#.####")
  val sizes = List(3, 10, 30, 100, 300, 1000, 3000)

  def eval() {
    println(("size" +: impls.map(_.name)).mkString("\t"))
    for (size <- sizes) {
      val times = impls.map(_.avgTime(size))
      println((size +: times.map(df.format)).mkString("\t"))
    }
    println()
  }
}

object Benchmarks {
  val append = new Benchmark(ListAppend, VectorAppend, WrappedArrayAppend)
  val prepend = new Benchmark(ListPrepend, VectorPrepend, WrappedArrayPrepend)
  val concat = new Benchmark(ListConcat, VectorConcat, WrappedArrayConcat)
  val matcher = new Benchmark(ListMatch, VectorMatch, WrappedArrayMatch)
  val length = new Benchmark(ListLength, VectorLength, WrappedArrayLength)
  val map = new Benchmark(ListMap, VectorMap, WrappedArrayMap)
  val flatMap = new Benchmark(ListFlatMap, VectorFlatMap, WrappedArrayFlatMap)
  val foreach = new Benchmark(ListForeach, VectorForeach, WrappedArrayForeach)
  val filter = new Benchmark(ListFilter, VectorFilter, WrappedArrayFilter)

  val all = List(append, prepend, concat, matcher, length, map, flatMap, foreach, filter)

  def main(args: Array[String]) {
    for (b <- all) {
      b.eval()
    }
  }
}