diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2013-09-23 05:27:07 -0700 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2013-09-23 05:27:07 -0700 |
commit | 7d570b54c3c895bc8948adeca2e463d135e38feb (patch) | |
tree | 24d8484361faf4510289e76cd3569bbdc839c1a7 /src/library | |
parent | 8980cdffa3965fe1d3900eeb80a9592c013df718 (diff) | |
parent | 4234b34dd4e6563ba8a9b5080cc6a0da021848d3 (diff) | |
download | scala-7d570b54c3c895bc8948adeca2e463d135e38feb.tar.gz scala-7d570b54c3c895bc8948adeca2e463d135e38feb.tar.bz2 scala-7d570b54c3c895bc8948adeca2e463d135e38feb.zip |
Merge pull request #2938 from Ichoran/issue/7725
SI-7725 - Vector concatenation is unreasonably slow
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/Vector.scala | 29 |
1 files changed, 26 insertions, 3 deletions
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 571e6775c8..0a100578c0 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -24,6 +24,10 @@ object Vector extends IndexedSeqFactory[Vector] { ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] private[immutable] val NIL = new Vector[Nothing](0, 0, 0) override def empty[A]: Vector[A] = NIL + + // Constants governing concat strategy for performance + private final val Log2ConcatFaster = 5 + private final val TinyAppendFaster = 2 } // in principle, most members should be private. however, access privileges must @@ -205,10 +209,29 @@ override def companion: GenericCompanion[Vector] = Vector override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) - // concat (stub) - + // concat (suboptimal but avoids worst performance gotchas) override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = { - super.++(that.seq) + if (bf eq IndexedSeq.ReusableCBF) { + import Vector.{Log2ConcatFaster, TinyAppendFaster} + if (that.isEmpty) this.asInstanceOf[That] + else { + val again = if (!that.isTraversableAgain) that.toVector else that + again.size match { + // Often it's better to append small numbers of elements (or prepend if RHS is a vector) + case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => + var v: Vector[B] = this + for (x <- again) v = v :+ x + v.asInstanceOf[That] + case n if this.size < (n >> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => + var v = again.asInstanceOf[Vector[B]] + val ri = this.reverseIterator + while (ri.hasNext) v = ri.next +: v + v.asInstanceOf[That] + case _ => super.++(that) + } + } + } + else super.++(that.seq) } |