How to properly and simply profile a function in scala?

Question

I am trying to reverse a string containing unicode characters in Scala. I want to find the fastest way to do it. So far I have this code:

import scala.runtime.RichChar

def reverseInPlace(s: String): String = {
   val reverse = new Array[RichChar](s.length)   
   for (i <- (0 to (s.length >> 1))) {
     reverse(i) = s(s.length -i -1)
     reverse(s.length -i -1) = s(i)
   }
   return reverse.mkString
}

def reverseLeft(s: String): String = s.foldLeft("") ( (a,b) => 
    b + a
)

def reverseRight(s: String): String = s.foldRight("") ( (a,b) => 
    b + a
)


def time[R](iterations:Int, block: => R) = {
    val t0 = System.nanoTime()
    for ( i <- 0 to iterations){
       block    // call-by-name
    }
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
}


time(1000, {
    reverseRight("Hello\u0041")
})

time(1000, {
    reverseInPlace("Hello\u0041")
})

time(1000, {
    reverseLeft("Hello\u0041")
})

time(1000, {
    "Hello\u0041".reverse
})

and on my macbook 2013 I get these results:

Elapsed time: 37013000ns
Elapsed time: 23592000ns
Elapsed time: 11647000ns
Elapsed time: 5579000ns

But I feel those numbers are bogus numbers. Who do I properly benchmark the functions using scala, sbt and the JMH library ?

Note: As pointed out from the comments, micro benchmarking in Java is a serious business See (How do I write a correct micro-benchmark in Java?) and https://groups.google.com/d/msg/mechanical-sympathy/m4opvy4xq3U/7lY8x8SvHgwJ. For why you shouldn't try to microbenchmark without using an external library.

Answer 1

Here's a solution using not no framework, but Thyme which I wrote because I wanted a microbenchmarking framework to feel micro, not elephant-like.

scala -cp /jvm/Thyme.jar

is all you need to do to run it in the REPL.

Now we need an implementation that actually works. I'll write two.

First try:

def revStr(s: String): String = {
  val points = for (i <- s.indices if !s(i).isLowSurrogate) yield s.codePointAt(i)
  new String(points.toArray.reverse,0,points.length)
}

Not so hard. Might be slow, though; probably lots of boxing there. Let's try a faster version:

def reverseString(s: String): String = if (s.length < 2) s else {
  import java.lang.Character.{isLowSurrogate => lo, isHighSurrogate => hi}
  val chars = s.toCharArray
  var i = 0
  var j = s.length - 1
  var swapped = false
  while (i < j) {
    swapped = false
    val a = chars(i)
    val b = chars(j)
    if (lo(a) && j+1 < s.length && hi(chars(j+1))) {
      chars(j) = chars(j+1)
      chars(j+1) = a
      swapped = true
    }
    else chars(j) = a
    if (hi(b) && i > 0 && lo(chars(i-1))) {
      chars(i) = chars(i-1)
      chars(i-1) = b
      swapped = true
    }
    else chars(i) = b
    i += 1
    j -= 1
  }
  if (i==j) {
    val c = chars(i)
    if (lo(c) && j+1 < s.length && hi(chars(j+1))) {
      chars(j) = chars(j+1)
      chars(j+1) = c
    }
    else if (hi(c) && i > 0 && lo(chars(i-1))) {
      chars(i) = chars(i-1)
      chars(i-1) = c
    }
  }
  else if (!swapped && hi(chars(i)) && lo(chars(j))) {
    val temp = chars(i)
    chars(i) = chars(j)
    chars(j) = temp
  }
  new String(chars)
}

Ouch. This is written for speed not ease of use, but ouch.

Anyway, let's test these out. I'm not doing full warmups here, but we'll get an idea:

scala> val th = new ichi.bench.Thyme
th: ichi.bench.Thyme = ichi.bench.Thyme@174580e6

scala> val testString = "This is a \ud800\udc00 test!"
testString: String = This is a  test!

scala> val wrong = th.pbench{ testString.reverse }
Benchmark (327660 calls in 115.2 ms)
  Time:    164.8 ns   95% CI 157.4 ns - 172.3 ns   (n=19)
  Garbage: 97.66 ns   (n=2 sweeps measured)
wrong: String = !tset ?? a si sihT

scala> val slow = th.pbench{ revStr(testString) }
Benchmark (163820 calls in 467.2 ms)
  Time:    749.0 ns   95% CI 742.5 ns - 755.5 ns   (n=18)
  Garbage: 2.112 us   (n=2 sweeps measured)
slow: String = !tset  a si sihT

scala> val fast = th.pbench{ reverseString(testString) }
Benchmark (327660 calls in 36.32 ms)
  Time:    58.19 ns   95% CI 58.10 ns - 58.27 ns   (n=18)
  Garbage: 12.21 ns   (n=1 sweeps measured)
fast: String = !tset  a si sihT

scala> val compare = th.pbenchOff(){revStr(testString)}{reverseString(testString)}
Benchmark comparison (in 430.7 ms)
Significantly different (p ~= 0)
  Time ratio:    0.09495   95% CI 0.08061 - 0.10928   (n=20)
    First     777.9 ns   95% CI 756.0 ns - 799.8 ns
    Second    73.86 ns   95% CI 62.90 ns - 84.81 ns
  Individual benchmarks not fully consistent with head-to-head (p ~= 0)
    First     742.9 ns   95% CI 742.0 ns - 743.9 ns
    Second    58.33 ns   95% CI 58.19 ns - 58.46 ns
compare: String = !tset  a si sihT

So, in conclusion, use at least a minimal microbenchmarking tool if you want to do microbenchmarks.

Also, code points are annoying, and direct array manipulations are fast.