From 56c1af90999f0a9a55a90f3dd3bf6d04ddda5943 Mon Sep 17 00:00:00 2001 From: Rex Kerr Date: Fri, 13 Feb 2015 16:37:19 -0800 Subject: 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. --- src/library/scala/collection/TraversableOnce.scala | 17 +++++++++++++++-- 1 file changed, 15 insertions(+), 2 deletions(-) (limited to 'src') 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 } -- cgit v1.2.3