From 04adb53b8d079ea114c5432ca3b3f824c80756a7 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 14 Dec 2016 14:37:13 +0100 Subject: Add benchmarks Benchmark code to compare compilation schemes in different scenarios. See results.md for explanations. --- tests/bench/transactional/Benchmark.scala | 5 ++ tests/bench/transactional/ImplicitMega.scala | 67 +++++++++++++++++++++ tests/bench/transactional/ImplicitMono.scala | 45 ++++++++++++++ tests/bench/transactional/ReaderMonadic.scala | 87 +++++++++++++++++++++++++++ tests/bench/transactional/Runner.scala | 25 ++++++++ tests/bench/transactional/Transaction.scala | 21 +++++++ tests/bench/transactional/results.md | 74 +++++++++++++++++++++++ 7 files changed, 324 insertions(+) create mode 100644 tests/bench/transactional/Benchmark.scala create mode 100644 tests/bench/transactional/ImplicitMega.scala create mode 100644 tests/bench/transactional/ImplicitMono.scala create mode 100644 tests/bench/transactional/ReaderMonadic.scala create mode 100644 tests/bench/transactional/Runner.scala create mode 100644 tests/bench/transactional/Transaction.scala create mode 100644 tests/bench/transactional/results.md (limited to 'tests') 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 -- cgit v1.2.3