Benchmarks

To benchmark the code, we took the Fast Fourier Transform example from Rosetta code and used it as the benchmarking target: value clases vs scala classes:

Complex class:

@value
case class Complex(re: Double, im: Double) {
    def +(x: Complex): Complex = Complex(re + x.re, im + x.im)
    def -(x: Complex): Complex = Complex(re - x.re, im - x.im)
    def *(x: Double): Complex = Complex(re * x, im * x)
    def *(x: Complex): Complex = Complex(re * x.re - im * x.im, re * x.im + im * x.re)
    def /(x: Double): Complex = Complex(re / x, im / x)

    override def toString(): String = {
        val a = "%1.3f" format re
        val b = "%1.3f" format abs(im)
        (a,b) match {
            case (_, "0.000") => a
            case ("0.000", _) => b + "i"
            case (_, _) if im > 0 => a + " + " + b + "i"
            case (_, _) => a + " - " + b + "i"
        }
    }
}

object Complex {
  def exp(c: Complex) : Complex = {
      val r = (cosh(c.re) + sinh(c.re))
      Complex(cos(c.im), sin(c.im)) * r
  }
}

FFT:

import scala.math.{ Pi, cos, sin, cosh, sinh, abs }

object FFT {
  def _fft(cSeq: Seq[Complex], direction: Complex, scalar: Int): Seq[Complex] = {
    if (cSeq.length == 1) {
        cSeq
    } else {
        val n = cSeq.length
        assume(n % 2 == 0, "The Cooley-Tukey FFT algorithm only works when the length of the input is a power of two.")

        val evenOddPairs = cSeq.grouped(2).toSeq
        val evens = _fft(evenOddPairs map (_(0)), direction, scalar)
        val odds = _fft(evenOddPairs map (_(1)), direction, scalar)

        def leftRightPair(k: Int): (Complex, Complex) = {
            val base = evens(k) / scalar
            val offset = Complex.exp(direction * (Pi * k / n)) * odds(k) / scalar
            (base + offset, base - offset)
        }

        val pairs = (0 until n/2) map leftRightPair
        val left = pairs map (_._1)
        val right = pairs map (_._2)
        left ++ right
    }
  }

  def fft(cSeq: Seq[Complex]): Seq[Complex] = _fft(cSeq, Complex(0, 2), 1)
  def rfft(cSeq: Seq[Complex]): Seq[Complex] = _fft(cSeq, Complex(0, -2), 2)
}

Aside from the FFT, we also benchmarked basic operations on arrays of complex numbers:

object Ops {

  def sum(seq: Array[Complex]): Complex = {
    var acc = Complex(0.0, 0.0)
    var i = 0
    while (i < seq.size) {
      acc = acc + seq(i)
      i += 1
    }
    acc
  }

  def prod(seq: Array[Complex]): Complex = {
    var acc = Complex(0.0, 0.0)
    var i = 0
    while (i < seq.size) {
      acc = acc * seq(i)
      i += 1
    }
    acc
  }
}

Finally, the benchmarking code is in ComplexBenchmark.scala.

To run the benchmarking code, you can use sbt in the DRT Virtual Machine:

$ cd Workspace/value-plugin
$ sbt
...
> valium-bench/run
[info] Running valium.bench.complex.ComplexBenchmark
::Benchmark FFT.Scala Complex::
Parameters(data size = 2^ -> 4): 11.9418295

::Benchmark FFT.Valium Complex::
Parameters(data size = 2^ -> 4): 11.818757100000001

::Benchmark Ops.Scala Complex::
Parameters(data size = 2^ -> 14): 0.1461588

::Benchmark Ops.Valium Complex::
Parameters(data size = 2^ -> 14): 0.09300530000000001

While there are speedups visible, they are significantly hindered by the fact that even the value class plugin requires boxing. In the future, we plan to have a different scheme for returning unboxed values, which would go through storing the fields in an object: https://github.com/miniboxing/value-plugin/issues/38.

The [next chapter](Test Suite) shows how to run the project's test suite.