SI-9043 ArrayBuffer.insert and insertAll are very slow

insert and insertAll were slower than their java equivalents by factors
of 5 and 10 respectively.

Benchmark code was provided here:
https://gist.github.com/rklaehn/3e9290118fcf63d1feae

We are using a toList to the source Traversable
Then doing a length and a copy on that collection.

By using an array, we can make use of faster methods.
Managed to get the ratios down to 1.5 and 1.5 respectively.

In addition to this, I think we should consider breaking insert into 2
separate methods, one for a single item and one for a collection.  The
varags version is very expensive when a single item is being inserted.

@phaller @axel22

1 files changed, 7 insertions, 6 deletions

diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala
index 8f77114746..011fd415ee 100644
--- a/src/library/scala/collection/mutable/ArrayBuffer.scala
+++ b/src/library/scala/collection/mutable/ArrayBuffer.scala
@@ -128,7 +128,7 @@ class ArrayBuffer[A](override protected val initialSize: Int)
   override def ++=:(xs: TraversableOnce[A]): this.type = { insertAll(0, xs.toTraversable); this }
 
   /** Inserts new elements at the index `n`. Opposed to method
-   *  `update`, this method will not replace an element with a
+   *  `update`, this method will not replace an element with a new
    *  one. Instead, it will insert a new element at index `n`.
    *
    *  @param n     the index where a new element will be inserted.
@@ -137,12 +137,13 @@ class ArrayBuffer[A](override protected val initialSize: Int)
    */
   def insertAll(n: Int, seq: Traversable[A]) {
     if (n < 0 || n > size0) throw new IndexOutOfBoundsException(n.toString)
-    val xs = seq.toList
-    val len = xs.length
-    ensureSize(size0 + len)
+    val len = seq.size
+    val newSize = size0 + len
+    ensureSize(newSize)
+
     copy(n, n + len, size0 - n)
-    xs.copyToArray(array.asInstanceOf[scala.Array[Any]], n)
-    size0 += len
+    seq.copyToArray(array.asInstanceOf[Array[Any]], n)
+    size0 = newSize
   }
 
   /** Removes the element on a given index position. It takes time linear in