Why headOption is faster

Question

I made some code changes and it got 4.5 times faster. I wonder why. It was essentially:

def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = queue match { case Queue((thing, stuff), _*) => doThing(queue.tail) case _ => queue } 

and I changed it to this to get a huge speedup:

 def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = queue.headOption match { case Some((thing, stuff)) => doThing(queue.tail) case _ => queue } 

What does _* and why is it so expensive compared to headOption?

Answer 1

My guess after running scalac with -Xprint:all is that at the end of patmat in the queue match { case Queue((thing, stuff), _*) => doThing(queue.tail) } example queue match { case Queue((thing, stuff), _*) => doThing(queue.tail) } I see the following calls (edited to be short):

 val o9 = scala.collection.immutable.Queue.unapplySeq[(String, String)](x1); if (o9.isEmpty.unary_!) if (o9.get.!=(null).&&(o9.get.lengthCompare(1).>=(0))) { val p2: (String, String) = o9.get.apply(0); val p3: Seq[(String, String)] = o9.get.drop(1); 

So lengthCompare comparing the length of the collection is possible in an optimized way. For Queue it creates an iterator and iterates once. So it should be somewhat quick. On the other hand, drop(1) also creates an iterator, skips one element and adds the remaining elements to the result queue, so that it will be linear in size of the collection.

The headOption example is simpler, it checks if the list is empty (two comparisons), and if it does not return a Some(head) , which then only has _1 and _2 assigned to thing and stuff . Thus, no iterators are created and nothing is linear along the length of the collection.

Answer 2

There should be no significant difference between your code samples.

case Queue((thing, stuff), _*) actually translated by the compiler to a call to the head ( apply(0) ) method. You can use scalac -Xprint:patmat to examine this:

 <synthetic> val p2: (String, String) = o9.get.apply(0); if (p2.ne(null)) matchEnd6(doThing(queue.tail)) 

The cost of head and the cost of headOption almost the same.

The head , tail and dequeue can call reverce in the internal List Queue (with a cost of O(n) ). In both code samples there will be no more than 2 reverce calls. You should use dequeue like this to get at most one reverce call:

 def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = if (queue.isEmpty) queue else queue.dequeue match { case (e, q) => doThing(q) } 

You can also replace (thing, stuff) with _ . In this case, the compiler will only generate a call to lengthCompare without head or tail :

 if (o9.get != null && o9.get.lengthCompare(1) >= 0) 

Answer 3

_* used to specify varargs arguments, so what you do in the first version deconstructs the queue into a couple of lines and the corresponding number of additional pairs of lines - that is, you deconstruct the entire Queue even though you only care about the first element.

If you just remove the asterisk by specifying

 def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = queue match { case Queue((thing, stuff), _) => doThing(queue.tail) case _ => queue } 

then you only deconstruct the queue into a couple of lines and the remainder (which, therefore, does not need to be completely deconstructed). This should be done at a comparable time with your second version (although not confined to this one itself).