Performance improvement: collectFirst in TraversableOnce

collectFirst was implemented in TraversableOnce by calling toIterator and then using a non-local return to pull out a Some when the partial function succeeded.  This had two problems:

  1. If the TraversableOnce was Iterator or Iterable, stepping through until pf is happy is much (15x!) faster.
  2. If the TraversableOnce was not, creating an Iterator is a waste of time and memory

This fixes both of these issues by inspecting the self-type and choosing the appropriate implementation.

Further (modest) improvements likely possible in 2.12 by moving specialized implementations to child classes and using `applyOrElse` on the partial function with a package-private object instead of a locally created one.

1 files changed, 15 insertions, 2 deletions

diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala
index 2eab58009c..c5b0d0f085 100644
--- a/src/library/scala/collection/TraversableOnce.scala
+++ b/src/library/scala/collection/TraversableOnce.scala
@@ -128,8 +128,21 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] {
    *  @example    `Seq("a", 1, 5L).collectFirst({ case x: Int => x*10 }) = Some(10)`
    */
   def collectFirst[B](pf: PartialFunction[A, B]): Option[B] = {
-    // make sure to use an iterator or `seq`
-    self.toIterator.foreach(pf.runWith(b => return Some(b)))
+    // TODO 2.12 -- move out alternate implementations into child classes
+    val i: Iterator[A] = self match {
+      case it: Iterator[A] => it
+      case _: GenIterable[_] => self.toIterator   // If it might be parallel, be sure to .seq or use iterator!
+      case _ =>                                   // Not parallel, not iterable--just traverse
+        self.foreach(pf.runWith(b => return Some(b)))
+        return None
+    }
+    // Presumably the fastest way to get in and out of a partial function is for a sentinel function to return itself
+    // (Tested to be lower-overhead than runWith.  Would be better yet to not need to (formally) allocate it--change in 2.12.)
+    val sentinel: Function1[A, Any] = new scala.runtime.AbstractFunction1[A, Any]{ def apply(a: A) = this }
+    while (i.hasNext) {
+      val x = pf.applyOrElse(i.next, sentinel)
+      if (x.asInstanceOf[AnyRef] ne sentinel) return Some(x.asInstanceOf[B])
+    }
     None
   }