diff options
author | Rex Kerr <ichoran@gmail.com> | 2014-02-10 02:17:27 -0800 |
---|---|---|
committer | Rex Kerr <ichoran@gmail.com> | 2014-02-25 05:39:13 -0800 |
commit | c5962b1871f8093fe200fe0c47cd9c202b07a8f9 (patch) | |
tree | 8ca06a81c39c11c44f10dabd23499b63506dbda7 /src/library | |
parent | 1ea43ffb2286d63e133839c1ea0b09449b0ac168 (diff) | |
download | scala-c5962b1871f8093fe200fe0c47cd9c202b07a8f9.tar.gz scala-c5962b1871f8093fe200fe0c47cd9c202b07a8f9.tar.bz2 scala-c5962b1871f8093fe200fe0c47cd9c202b07a8f9.zip |
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.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/List.scala | 101 |
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 { |