Moved five methods from LinearSeqOptimized to List

Curiously, profiling showed that these methods (in particular map) got slower when specialized in LinearSeqOptimized from their generic impl in TraversableLike.
I speculate that the virtual calls to head/tail/nonEmpty are more expensive than the closure creation which we save (Note that foreach IS specialized in List,
so head/tail are monomorphic, even though isEmpty still has two implementations.

If we confirm a speedup in this commit it would make sense to specialize more methods in LinearSeqOptimized again in List.

2 files changed, 56 insertions, 58 deletions

diff --git a/src/library/scala/collection/LinearSeqOptimized.scala b/src/library/scala/collection/LinearSeqOptimized.scala
index 2a06b9d0bd..188e0e8afd 100755
--- a/src/library/scala/collection/LinearSeqOptimized.scala
+++ b/src/library/scala/collection/LinearSeqOptimized.scala
@@ -82,17 +82,6 @@ trait LinearSeqOptimized[+A, +Repr <: LinearSeqOptimized[A, Repr]] extends Linea
     false
   }
 
-  override /*TraversableLike*/
-  def count(p: A => Boolean): Int = {
-    var these = this
-    var cnt = 0
-    while (!these.isEmpty) {
-      if (p(these.head)) cnt += 1
-      these = these.tail
-    }
-    cnt
-  }
-
   override /*SeqLike*/
   def contains(elem: Any): Boolean = {
     var these = this
@@ -124,53 +113,6 @@ trait LinearSeqOptimized[+A, +Repr <: LinearSeqOptimized[A, Repr]] extends Linea
     acc
   }
   
-  override /*TraversableLike*/
-  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
-    val b = bf(repr)
-    b.sizeHint(this)
-    var these = this
-    while (!these.isEmpty) {
-      b += f(these.head)
-      these = these.tail
-    }
-    b.result
-  }
-  
-  override /*TraversableLike*/
-  def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
-    val b = bf(repr)
-    var these = this
-    while (!these.isEmpty) {
-      b ++= f(these.head).seq
-      these = these.tail
-    }
-    b.result
-  }
-  
-  override /*TraversableLike*/
-  def filter(p: A => Boolean): Repr = {
-    val b = newBuilder
-    var these = this
-    while (!these.isEmpty) {
-      val x = these.head
-      if (p(x)) b += x
-      these = these.tail
-    }
-    b.result
-  }  
-  
-  override /*TraversableLike*/
-  def filterNot(p: A => Boolean): Repr = {
-    val b = newBuilder
-    var these = this
-    while (!these.isEmpty) {
-      val x = these.head
-      if (!p(x)) b += x
-      these = these.tail
-    }
-    b.result
-  }  
-  
   override /*IterableLike*/
   def foldRight[B](z: B)(f: (A, B) => B): B =
     if (this.isEmpty) z
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index 87b58005cf..d9e98b56c1 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -310,6 +310,62 @@ sealed abstract class List[+A] extends AbstractSeq[A]
       these = these.tail
     }
   }
+  
+  @inline override /*TraversableLike*/
+  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That = {
+    val b = bf(repr)
+    var these = this
+    while (!these.isEmpty) {
+      b += f(these.head)
+      these = these.tail
+    }
+    b.result
+  }
+  
+  @inline override /*TraversableLike*/
+  def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = {
+    val b = bf(repr)
+    var these = this
+    while (!these.isEmpty) {
+      b ++= f(these.head).seq
+      these = these.tail
+    }
+    b.result
+  }
+  
+  @inline override /*TraversableLike*/
+  def filter(p: A => Boolean): List[A] = {
+    val b = newBuilder
+    var these = this
+    while (!these.isEmpty) {
+      val x = these.head
+      if (p(x)) b += x
+      these = these.tail
+    }
+    b.result
+  }  
+  
+  @inline override /*TraversableLike*/
+  def filterNot(p: A => Boolean): List[A] = {
+    val b = newBuilder
+    var these = this
+    while (!these.isEmpty) {
+      val x = these.head
+      if (!p(x)) b += x
+      these = these.tail
+    }
+    b.result
+  }  
+
+  @inline override /*SeqLike*/
+  def contains(elem: Any): Boolean = {
+    var these = this
+    while (!these.isEmpty) {
+      if (these.head == elem) return true
+      these = these.tail
+    }
+    false
+  }
 
   @deprecated("use `distinct` instead", "2.8.0")
   def removeDuplicates: List[A] = distinct