Add benchmarks

Benchmark code to compare compilation schemes in
different scenarios. See results.md for explanations.

7 files changed, 324 insertions, 0 deletions

diff --git a/tests/bench/transactional/Benchmark.scala b/tests/bench/transactional/Benchmark.scala
new file mode 100644
index 000000000..8af7ebb83
--- /dev/null
+++ b/tests/bench/transactional/Benchmark.scala
@@ -0,0 +1,5 @@
+package transactional
+abstract class Benchmark {
+  def run(): Int
+}
+
diff --git a/tests/bench/transactional/ImplicitMega.scala b/tests/bench/transactional/ImplicitMega.scala
new file mode 100644
index 000000000..80e9c4a43
--- /dev/null
+++ b/tests/bench/transactional/ImplicitMega.scala
@@ -0,0 +1,67 @@
+package transactional
+object MegaBench extends Benchmark {
+  type Transactional[T] = implicit Transaction => T
+
+  def transaction[T](op: Transactional[T]): T = {
+    implicit val trans: Transaction = new Transaction
+    val res = op
+    trans.commit()
+    res
+  }
+
+  def thisTransaction: Transactional[Transaction] = implicitly[Transaction]
+
+  abstract class Op {
+    def f(x: Int): Transactional[Int]
+  }
+
+  class Op0 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("0th step")
+      x
+    }
+  }
+
+  class Op1 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("first step")
+      x + 1
+    }
+  }
+
+  class Op2 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("second step")
+      x + 2
+    }
+  }
+
+  class Op3 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("third step")
+      x + 3
+    }
+  }
+
+  val op = Array[Op](new Op0, new Op1, new Op2, new Op3)
+
+  def f(x: Int, n: Int): Transactional[Int] = {
+    thisTransaction.println("fourth step")
+    if (n > 0) f(op(n % 4).f(x), n - 1)
+    else {
+      if (x % 2 != 0) thisTransaction.abort()
+      x
+    }
+  }
+
+  def run(): Int = {
+    transaction {
+      val res = f(7, 10)
+      assert(!thisTransaction.isAborted)
+      assert(res == 22)
+      res
+    }
+  }
+}
+
+object ImplicitMega extends Runner("megamorphic", MegaBench, 22)
diff --git a/tests/bench/transactional/ImplicitMono.scala b/tests/bench/transactional/ImplicitMono.scala
new file mode 100644
index 000000000..10391f191
--- /dev/null
+++ b/tests/bench/transactional/ImplicitMono.scala
@@ -0,0 +1,45 @@
+package transactional
+object MonoBench extends Benchmark {
+  type Transactional[T] = implicit Transaction => T
+
+  def transaction[T](op: Transactional[T]): T = {
+    implicit val trans: Transaction = new Transaction
+    val res = op
+    trans.commit()
+    res
+  }
+
+  def thisTransaction: Transactional[Transaction] = implicitly[Transaction]
+
+  def f1(x: Int): Transactional[Int] = {
+    thisTransaction.println("first step")
+    f2(x + 1)
+  }
+  def f2(x: Int): Transactional[Int] = {
+    thisTransaction.println("second step")
+    f3(x * x)
+  }
+  def f3(x: Int): Transactional[Int] = {
+    thisTransaction.println("third step")
+    f4(x + 1, 7)
+  }
+  def f4(x: Int, n: Int): Transactional[Int] = {
+    thisTransaction.println("fourth step")
+    if (n > 0) f4(x + 1, n - 1)
+    else {
+      if (x % 2 != 0) thisTransaction.abort()
+      x
+    }
+  }
+
+  def run(): Int = {
+    transaction {
+      val res = f1(7)
+      assert(!thisTransaction.isAborted)
+      assert(res == 72)
+      res
+    }
+  }
+}
+
+object ImplicitMono extends Runner("monomorphic implicits", MonoBench, 72)
diff --git a/tests/bench/transactional/ReaderMonadic.scala b/tests/bench/transactional/ReaderMonadic.scala
new file mode 100644
index 000000000..ce69c35ad
--- /dev/null
+++ b/tests/bench/transactional/ReaderMonadic.scala
@@ -0,0 +1,87 @@
+package transactional
+
+case class Reader[R,A](run: R => A) {
+  def map[B](f: A => B): Reader[R, B] = Reader(r => f(run(r)))
+  def flatMap[B](f: A => Reader[R, B]): Reader[R, B] = Reader(r => f(run(r)).run(r))
+}
+
+object Reader {
+  def ask[R]: Reader[R,R] = Reader(r => r)
+}
+
+object ReaderBench extends Benchmark {
+  type Transactional[T] = Reader[Transaction, T]
+
+  def transaction[T](op: Transactional[T]): T = {
+    implicit val trans: Transaction = new Transaction
+    val res = op.run(trans)
+    trans.commit()
+    res
+  }
+
+  def thisTransaction: Transactional[Transaction] = Reader.ask
+
+  abstract class Op {
+    def f(x: Int): Transactional[Int]
+  }
+
+  class Op0 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("0th step"); x }
+  }
+
+  class Op1 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("first step"); x + 1 }
+  }
+
+  class Op2 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("second step"); x + 2 }
+  }
+
+  class Op3 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("third step"); x + 3 }
+  }
+
+  val op = Array[Op](new Op0, new Op1, new Op2, new Op3)
+
+  def f(x: Int, n: Int): Transactional[Int] = {
+    def rest(trans: Transaction): Transactional[Int] = {
+      trans.println("fourth step")
+      if (n > 0) {
+        for {
+          y <- op(n % 4).f(x)
+          z <- f(y: Int, n - 1)
+        }
+        yield z
+      }
+      else {
+        if (x % 2 != 0)
+          for (trans <- thisTransaction)
+          yield { trans.abort(); () }
+        Reader(_ => x)
+      }
+    }
+    thisTransaction.flatMap(rest)
+  }
+
+  def run(): Int = {
+    transaction {
+      for (res <- f(7, 10))
+      yield {
+        for (trans <- thisTransaction)
+        yield { assert(!trans.isAborted); () }
+        assert(res == 22)
+        res
+      }
+    }
+  }
+}
+
+object ReaderMonadic extends Runner("reader monadic", ReaderBench, 22)
diff --git a/tests/bench/transactional/Runner.scala b/tests/bench/transactional/Runner.scala
new file mode 100644
index 000000000..48da7ff12
--- /dev/null
+++ b/tests/bench/transactional/Runner.scala
@@ -0,0 +1,25 @@
+package transactional
+import System.nanoTime
+
+class Runner(name: String, bench: Benchmark, expected: Int) {
+
+  val numIters = 10000000
+  val numTests = 5
+
+  def run(): Unit = {
+    val start = nanoTime
+    var cnt = 0
+    var i = 0
+    while (i < numIters) {
+      cnt += bench.run()
+      i += 1
+    }
+    assert(cnt == expected * numIters)
+    val duration = nanoTime - start
+    println(s"$name in ${duration / 1000000}ms")
+  }
+
+  def main(args: Array[String]) =
+    for (i <- 0 until numTests)
+      run()
+}
diff --git a/tests/bench/transactional/Transaction.scala b/tests/bench/transactional/Transaction.scala
new file mode 100644
index 000000000..dbb28d452
--- /dev/null
+++ b/tests/bench/transactional/Transaction.scala
@@ -0,0 +1,21 @@
+package transactional
+import collection.mutable.ListBuffer
+
+class Transaction {
+  private val log = new ListBuffer[String]
+  def println(s: String): Unit = log += s
+
+  private var aborted = false
+  private var committed = false
+
+  def abort(): Unit = { aborted = true }
+  def isAborted = aborted
+
+  def commit(): Unit =
+    if (!aborted && !committed) {
+      //Console.println("******* log ********")
+      //log.foreach(Console.println)
+      committed = true
+    }
+}
+
diff --git a/tests/bench/transactional/results.md b/tests/bench/transactional/results.md
new file mode 100644
index 000000000..4a58800ec
--- /dev/null
+++ b/tests/bench/transactional/results.md
@@ -0,0 +1,74 @@
+# Benchmark results for implicit compilation scenarios.
+
+### Setup
+
+Three alternatives:
+
+  1. No implicit shortcuts
+  2. Implicit shortcuts only for possible targets of megamorphic dispatch
+     (`specializeMonoTargets` set to false)
+  3. Implicit shortcuts for all methods returning implicit function types
+     (`specializeMonoTargets` set to true)
+
+Two benchmarks:
+
+ - `ImplicitMono`:  all calls are monomorphic
+ - `IplicitMega` :  about half of the calls are (4-way) megamorphic,
+                    the others are monomorphic.
+
+### Results
+
+| Scheme              | ImplicitMono | ImplicitMega |
+|---------------------|-------------:|-------------:|
+| no shortcuts        | 1354ms       | 3260ms
+|                     | 955ms        | 2906ms
+|                     | 908ms        | 2899ms
+|                     | 906ms        | 2887ms
+|                     | 886ms        | 2872ms
+| only mega shortcuts |        |
+                      | 1243ms | 2472ms
+|                     | 926ms  | 2146ms
+|                     | 925ms  | 2169ms
+|                     | 902ms  | 2136ms
+|                     | 913ms  | 2179ms
+| all shortcuts       |        |
+|                     | 1354ms | 1940ms
+|                     | 1039ms | 1563ms
+|                     | 1031ms | 1593ms
+|                     | 1065ms | 1548ms
+|                     | 1016ms | 1579ms
+
+### Interpretation
+
+In the fully monomorphic benchmark, specializing
+only megamorphic targets has the same performance as
+not spezializing at all (not surprising, since there
+are no megamorphic targets). Specializing everything
+incurs about a 14% performance hit (maybe due to the extra
+code generated; it's hard to pin down what it is).
+
+Note: We compaute relative performance differences by comparing the
+second-best test runs of each series with each other.
+
+In the megamorphic benchmark, it's the other way round.
+Specializing only megamorphic callsites leads to a performance
+improvement of about 36% compared to no specialization. Specializing
+everything leads to another 37% improvement (85% total compared
+to no specialization).
+
+I think we need larger benchmarks to decide whether we should
+specicialize mono-morphic call-targets or not.
+
+### Comparing with the Reader Monad
+
+Translating `ImplicitMega` to the reader monad, gives the following runtimes:
+
+| Reader |
+| 11563ms |
+| 11108ms |
+| 11300ms |
+| 11098ms |
+| 11159ms |
+
+This translates to a 710% slowdown compared to implicit function types
+with full specialization.
\ No newline at end of file