SI-8240 Consider rolling back optimizations for List

Some compiler-specific optimizations turn out to be very helpful for Lists in general.

  * List map can be a lot faster (up to 5x!)
  * List collect can be considerably faster (up to 3x)
  * List flatMap can be a bit faster (2x)
  * List take can be slightly faster (1.1x) and have better structural sharing

These appear to be unqualified wins (tested), even in a scenario with mixed collections.  This is expected: detecting the builder is faster than the otherwise mandatory object creation, and multiple dispatch is mostly a wash since it was already multiple dispatch in getting to the builder.

With -optimize, map is not always such a big win, but is never slower.

Also added @noinline to map to work around an optimizer bug (SI-8334) and added a test to check that the pattern that triggers the optimizer bug does not affect any of the map-like methods.

1 files changed, 92 insertions, 9 deletions

diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index c3728fa02a..930e13a9d3 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -203,17 +203,19 @@ sealed abstract class List[+A] extends AbstractSeq[A]
 
   override def toList: List[A] = this
 
-  override def take(n: Int): List[A] = {
-    val b = new ListBuffer[A]
-    var i = 0
-    var these = this
-    while (!these.isEmpty && i < n) {
+  override def take(n: Int): List[A] = if (isEmpty || n <= 0) Nil else {
+    val h = new ::(head, Nil)
+    var t = h
+    var rest = tail
+    var i = 1
+    while ({if (rest.isEmpty) return this; i < n}) {
       i += 1
-      b += these.head
-      these = these.tail
+      val nx = new ::(rest.head, Nil)
+      t.tl = nx
+      t = nx
+      rest = rest.tail
     }
-    if (these.isEmpty) this
-    else b.toList
+    h
   }
 
   override def drop(n: Int): List[A] = {
@@ -264,6 +266,85 @@ sealed abstract class List[+A] extends AbstractSeq[A]
     }
     (b.toList, these)
   }
+  
+  @noinline // TODO - fix optimizer bug that requires noinline (see SI-8334)
+  final override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That = {
+    if (bf eq List.ReusableCBF) {
+      if (this eq Nil) Nil.asInstanceOf[That] else {
+        val h = new ::[B](f(head), Nil)
+        var t: ::[B] = h
+        var rest = tail
+        while (rest ne Nil) {
+          val nx = new ::(f(rest.head), Nil)
+          t.tl = nx
+          t = nx
+          rest = rest.tail
+        }
+        h.asInstanceOf[That]
+      }
+    }
+    else super.map(f)
+  }
+  
+  @noinline // TODO - fix optimizer bug that requires noinline for map; applied here to be safe (see SI-8334)
+  final override def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[List[A], B, That]): That = {
+    if (bf eq List.ReusableCBF) {
+      if (this eq Nil) Nil.asInstanceOf[That] else {
+        var rest = this
+        var h: ::[B] = null
+        var x: A = null.asInstanceOf[A]
+        // Special case for first element
+        do {
+          val x: Any = pf.applyOrElse(rest.head, List.partialNotApplied)
+          if (x.asInstanceOf[AnyRef] ne List.partialNotApplied) h = new ::(x.asInstanceOf[B], Nil)
+          rest = rest.tail
+          if (rest eq Nil) return (if (h eq null ) Nil else h).asInstanceOf[That]
+        } while (h eq null)
+        var t = h
+        // Remaining elements
+        do {
+          val x: Any = pf.applyOrElse(rest.head, List.partialNotApplied)
+          if (x.asInstanceOf[AnyRef] ne List.partialNotApplied) {
+            val nx = new ::(x.asInstanceOf[B], Nil)
+            t.tl = nx
+            t = nx
+          }
+          rest = rest.tail
+        } while (rest ne Nil)
+        h.asInstanceOf[That]
+      }
+    }
+    else super.collect(pf)
+  }
+  
+  @noinline // TODO - fix optimizer bug that requires noinline for map; applied here to be safe (see SI-8334)
+  final override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = {
+    if (bf eq List.ReusableCBF) {
+      if (this eq Nil) Nil.asInstanceOf[That] else {
+        var rest = this
+        var found = false
+        var h: ::[B] = null
+        var t: ::[B] = null
+        while (rest ne Nil) {
+          f(rest.head).foreach{ b =>
+            if (!found) {
+              h = new ::(b, Nil)
+              t = h
+              found = true
+            }
+            else {
+              val nx = new ::(b, Nil)
+              t.tl = nx
+              t = nx
+            }
+          }
+          rest = rest.tail
+        }
+        (if (!found) Nil else h).asInstanceOf[That]
+      }
+    }
+    else super.flatMap(f)
+  }
 
   @inline final override def takeWhile(p: A => Boolean): List[A] = {
     val b = new ListBuffer[A]
@@ -375,6 +456,8 @@ object List extends SeqFactory[List] {
   override def empty[A]: List[A] = Nil
 
   override def apply[A](xs: A*): List[A] = xs.toList
+  
+  private[collection] val partialNotApplied = new Function1[Any, Any] { def apply(x: Any): Any = this }
 
   @SerialVersionUID(1L)
   private class SerializationProxy[A](@transient private var orig: List[A]) extends Serializable {