Scala Generic Type slow

Question

I do need to create a method for comparison for either Int or String or Char. Using AnyVal was not make it possible as there were no method's for <, > comparison.

However Typing it into Ordered shows a significant slowness. Are there better ways to achieve this? The plan is to do a generic binary sorting, and found Generic typing decreases the performance.

def sample1[T <% Ordered[T]](x:T) = { x < (x) }
def sample2(x:Ordered[Int]) = { x < 1 }
def sample3(x:Int) = { x < 1 }

val start1 = System.nanoTime
sample1(5)
println(System.nanoTime - start1)
val start2 = System.nanoTime
sample2(5)
println(System.nanoTime - start2)
val start3 = System.nanoTime
sample3(5)
println(System.nanoTime - start3)
val start4 = System.nanoTime
sample3(5)
println(System.nanoTime - start4)
val start5 = System.nanoTime
sample2(5)
println(System.nanoTime - start5)
val start6 = System.nanoTime
sample1(5)
println(System.nanoTime - start6)

The results shows:

Sample1:696122

Sample2:45123

Sample3:13947

Sample3:5332

Sample2:194438

Sample1:497992

Am I doing the incorrect way of handling Generics? Or should I be doing the old Java method of using Comparator in this case, sample as in:

object C extends Comparator[Int] {
  override def compare(a:Int, b:Int):Int = {
    a - b
  }
}
def sample4[T](a:T, b:T, x:Comparator[T]) {x.compare(a,b)}

Answer 1

Do not do micro-tests in such way if you want to get results somehow similar you will have in production env. First of all you need to warm-up jvm. And after that do your test as average of many iterations. Also, you need to prevent possible jvm optimizations because of const data. E.g.

def sample1[T <% Ordered[T]](x:T) = { x < (x) }
def sample2(x:Ordered[Int]) = { x < 1 }
def sample3(x:Int) = { x < 1 }
val r = new Random()


def measure(f: => Unit): Long = {
  val start1 = System.nanoTime
  f
  System.nanoTime - start1
}
val n = 1000000

(1 to n).map(_ => measure {val k = r.nextInt();sample1(k)})
(1 to n).map(_ => measure {val k = r.nextInt();sample2(k)})
(1 to n).map(_ => measure {val k = r.nextInt();sample3(k)})

val avg1 = (1 to n).map(_ => measure {val k = r.nextInt();sample1(k)}).sum / n
println(avg1)
val avg2 = (1 to n).map(_ => measure {val k = r.nextInt();sample2(k)}).sum / n
println(avg2)
val avg3 = (1 to n).map(_ => measure {val k = r.nextInt();sample3(k)}).sum / n
println(avg3)

I got results, which look more fare for me:

134
92
83

This book could give some light on performance tests.

Answer 2

The Scala equivalent of Java Comparator is Ordering. One of the main differences is that, if you don't provide one manually, a suitable Ordering can be injected implicitly by the compiler. By default, this will be done for Byte, Int, Float and other primitives, for any subclass of Ordered or Comparable, and for some other obvious cases.

Also, Ordering provides method definitions for all the main comparison methods as extension methods, so you can write the following:

import Ordering.Implicits._

def sample5[T : Ordering](a: T, b: T) = a < b

def run() = sample5(1, 2)

As of Scala 2.12, those extension operations (i.e., a < b) invoke wrapping in a temporary object Ordering#Ops, so the code will be slower than with a Comparator. Not much in most real cases, but still significant if you care about micro-optimisations.

But you can use an alternative syntax to define an implicit Ordering[T] parameter and invoke methods on the Ordering object directly. Actually even the generated bytecode for the following two methods will be identical (except for the type of the third argument, and potentially the implementation of the respective compare methods):

def withOrdering[T](x: T, y: T)(implicit cmp: Ordering[T]) = {
  cmp.compare(x, y) // also supports other methods, like `cmp.lt(x, y)`
}

def withComparator[T](x: T, y: T, cmp: Comparator[T]) = {
  cmp.compare(x, y)
}

In practice the runtime on my machine is the same, when invoking these methods with Int arguments.

So, if you want to compare types generically in Scala, you should usually use Ordering.