Why is headOption faster

Question

I made a change to some code and it got 4.5x faster. I'm wondering why. It used to be 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 speed boost:

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

What does _* do 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 I see the following methods being called (edited for brevity):

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 compare the length of the collection in a possibly optimized way. For Queue, it creates an iterator and iterates one time. So that should be somewhat fast. On the other hand drop(1) also constructs an iterator, skips one element and adds the rest of the elements to the result queue, so that would be linear in the size of the collection.

The headOption example is more straightforward, it checks if the list is empty (two comparisons), and if not returns a Some(head), which then just has its _1 and _2 assigned to thing and stuff. So no iterators are created and nothing linear in the length of the collection.