scala · mkeskells · Oct 17, 2016
diff --git a/src/library/scala/collection/immutable/FilteredTraversableInternal.scala b/src/library/scala/collection/immutable/FilteredTraversableInternal.scala
@@ -0,0 +1,104 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package scala
+package collection
+package immutable
+
+import scala.annotation.tailrec
+
+/**
+  * Optimised filter functions for List
+  * n.b. this is an internal class to help maintain compatibility and should not be used directly.
+  */
+private[immutable] trait FilteredTraversableInternal[+A, +Repr <: AnyRef with TraversableLike[A, Repr]] extends TraversableLike[A, Repr] {
+
+  // Optimized for List
+
+  override def filter(p: A => Boolean): Self = filterImpl(p, isFlipped = false)
+
+  override def filterNot(p: A => Boolean): Self = filterImpl(p, isFlipped = true)
+
+  private[this] def filterImpl(p: A => Boolean, isFlipped: Boolean): Self = {
+
+    // everything seen so far so far is not included
+    @tailrec def noneIn(l: Repr): Repr = {
+      if (l.isEmpty)
+        Nil.asInstanceOf[Repr]
+      else {
+        val h = l.head
+        val t = l.tail
+        if (p(h) != isFlipped)
+          allIn(l, t)
+        else
+          noneIn(t)
+      }
+    }
+
+    // everything from 'start' is included, if everything from this point is in we can return the origin
+    // start otherwise if we discover an element that is out we must create a new partial list.
+    @tailrec def allIn(start: Repr, remaining: Repr): Repr = {
+      if (remaining.isEmpty)
+        start
+      else {
+        val x = remaining.head
+        if (p(x) != isFlipped)
+          allIn(start, remaining.tail)
+        else
+          partialFill(start, remaining)
+      }
+    }
+
+    // we have seen elements that should be included then one that should be excluded, start building
+    def partialFill(origStart: Repr, firstMiss: Repr): Repr = {
+      val newHead = new ::(origStart.head, Nil)
+      var toProcess = origStart.tail
+      var currentLast = newHead
+
+      // we know that all elements are :: until at least firstMiss.tail
+      while (!(toProcess eq firstMiss)) {
+        val newElem = new ::(toProcess.head, Nil)
+        currentLast.tl = newElem
+        currentLast = newElem
+        toProcess = toProcess.tail
+      }
+
+      // at this point newHead points to a list which is a duplicate of all the 'in' elements up to the first miss.
+      // currentLast is the last element in that list.
+
+      // now we are going to try and share as much of the tail as we can, only moving elements across when we have to.
+      var next = firstMiss.tail
+      var nextToCopy = next // the next element we would need to copy to our list if we cant share.
+      while (!next.isEmpty) {
+        // generally recommended is next.isNonEmpty but this incurs an extra method call.
+        val head: A = next.head
+        if (p(head) != isFlipped) {
+          next = next.tail
+        } else {
+          // its not a match - do we have outstanding elements?
+          while (!(nextToCopy eq next)) {
+            val newElem = new ::(nextToCopy.head, Nil)
+            currentLast.tl = newElem
+            currentLast = newElem
+            nextToCopy = nextToCopy.tail
+          }
+          nextToCopy = next.tail
+          next = next.tail
+        }
+      }
+
+      // we have remaining elements - they are unchanged attach them to the end
+      if (!nextToCopy.isEmpty)
+        currentLast.tl = nextToCopy.asInstanceOf[List[A]]
+
+      newHead.asInstanceOf[Repr]
+    }
+
+    noneIn(repr)
+  }
+}
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
@@ -86,6 +86,7 @@ sealed abstract class List[+A] extends AbstractSeq[A]
                                   with Product
                                   with GenericTraversableTemplate[A, List]
                                   with LinearSeqOptimized[A, List[A]]
+                                  with FilteredTraversableInternal[A, List[A]]
                                   with Serializable {
   override def companion: GenericCompanion[List] = List
 
@@ -405,6 +406,7 @@ sealed abstract class List[+A] extends AbstractSeq[A]
   // Create a proxy for Java serialization that allows us to avoid mutation
   // during de-serialization.  This is the Serialization Proxy Pattern.
   protected final def writeReplace(): AnyRef = new List.SerializationProxy(this)
+
 }
 
 /** The empty list.

diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala
@@ -0,0 +1,57 @@
+package scala.collection.immutable
+
+import java.util.concurrent.TimeUnit
+
+import org.openjdk.jmh.annotations._
+
+object ListBenchmark {
+  case class Content(value: Int)
+}
+
+@BenchmarkMode(Array(Mode.AverageTime))
+@Fork(2)
+@Threads(1)
+@Warmup(iterations = 10)
+@Measurement(iterations = 10)
+@OutputTimeUnit(TimeUnit.NANOSECONDS)
+@State(Scope.Benchmark)
+class ListBenchmark {
+  import ListBenchmark._
+  @Param(Array("0", "1", "10", "100", "1000"))
+  var size: Int = _
+
+  var values: List[Content] = _
+  var mid: Content = _
+  var last: Content = _
+
+
+  @Setup(Level.Trial) def initKeys(): Unit = {
+    values = List.tabulate(size)(v => Content(v))
+    mid = Content(size / 2)
+    last = Content(Math.max(0,size -1))
+  }
+
+  @Benchmark def filter_includeAll: Any = {
+    values.filter(v => true)
+  }
+
+  @Benchmark def filter_excludeAll: Any = {
+    values.filter(_ => false)
+  }
+
+  @Benchmark def filter_exc_mid: Any = {
+    values.filter(v => v.value != mid.value)
+  }
+
+  @Benchmark def filter_from_mid: Any = {
+    values.filter(v => v.value <= mid.value)
+  }
+
+  @Benchmark def filter_exc_last: Any = {
+    values.filter(v => v.value != last.value)
+  }
+
+  @Benchmark def filter_only_last: Any = {
+    values.filter(v => v.value == last.value)
+  }
+}