How does Scala's .min avoid the penalty of boxing and unboxing?

Question

Vector.min is implemented as

def min[B >: A](implicit cmp: Ordering[B]): A = {
  if (isEmpty)
    throw new UnsupportedOperationException("empty.min")
  reduceLeft((x, y) => if (cmp.lteq(x, y)) x else y)
}

and when you profile

Vector.fill(1000000)(scala.util.Random.nextLong).min

it's fast and there's no boxing or unboxing going on. If, however, you write the apparently equivalent

val cmp = implicitly[Ordering[Long]]
Vector.fill(1000000)(scala.util.Random.nextLong).reduceLeft((x, y) => if (cmp.lteq(x, y)) x else y)

it runs approximately 10 times slower (ignoring the time in Random, which otherwise dominates this, and yes, I warmed my benchmarks up...).

How is the first version avoiding the performance penalty of the boxing?

Edit: here's my profiling code:

val cmp = implicitly[Ordering[Long]]

def randomLongs = Vector.fill(1000000)(scala.util.Random.nextLong)

def timing[R](f: => R): (Long, R) = {
  val startTime = System.nanoTime
  val result = f
  ((System.nanoTime - startTime) / 1000000, result)
}

def minTiming = { val r = randomLongs; timing(r.min)._1 }
def reduceLeftTiming = { val r = randomLongs; timing(r.reduceLeft((x, y) => if (cmp.lteq(x, y)) x else y))._1 }

while(true) {
  println((minTiming, reduceLeftTiming))
}

and I see times using min of around 20ms, using reduceLeft of ~200ms. I've profiled this code using YourKit; here's a screen grab of the call tree showing that min doesn't result in any boxing.

Answer 1

I think the first version infers java.lang.Long for B. So there still is boxing going on, but only while filling the vector, and afterwards all comparisons are between boxed objects.

In the second version, since type of cmp is given as Ordering[Long], java.lang.Longs in the vector have to be unboxed before being passed to cmp.lteq(x, y).