From e3d5314ac13f32cb2dde747bad8f8633f223a2e2 Mon Sep 17 00:00:00 2001 From: Rex Kerr Date: Sun, 30 Nov 2014 13:43:21 -0800 Subject: SI-7981 toSeq on immutable Map and Set return ArrayBuffer Switched to `Vector` for the default `MapLike`/`SetLike`, then back again in `mutable.MapLike`/`mutable.SetLike`. Preliminary performance testing indicates an across-the-board improvement due to cutting out a great deal of indirection. In the case of empty immutable maps or sets, the improvement is enormous: it quickly returns Vector.empty instead of jumping through all sorts of hoops to eventually create an empty `ArrayBuffer`. One possible downside is that `Vector` is pretty memory-hungry for small collections. Need to evalute this; rather than abandoning this change, it's probably better to make `Vector` smarter about small collections. Also fixed test with literal "ArrayBuffer" in output (`s/ArrayBuffer/Vector/g`). --- src/library/scala/collection/MapLike.scala | 15 +++++++++++--- src/library/scala/collection/SetLike.scala | 15 +++++++++++--- src/library/scala/collection/mutable/MapLike.scala | 12 +++++++++++ src/library/scala/collection/mutable/SetLike.scala | 11 ++++++++++ test/files/run/inline-ex-handlers.check | 24 +++++++++++----------- 5 files changed, 59 insertions(+), 18 deletions(-) diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala index 3de30c2c8b..38a598321f 100644 --- a/src/library/scala/collection/MapLike.scala +++ b/src/library/scala/collection/MapLike.scala @@ -323,11 +323,20 @@ self => res } - /* Overridden for efficiency. */ - override def toSeq: Seq[(A, B)] = toBuffer[(A, B)] + override def toSeq: Seq[(A, B)] = { + if (isEmpty) Vector.empty[(A, B)] + else { + // Default appropriate for immutable collections; mutable collections override this + val vb = Vector.newBuilder[(A, B)] + foreach(vb += _) + vb.result + } + } + override def toBuffer[C >: (A, B)]: mutable.Buffer[C] = { val result = new mutable.ArrayBuffer[C](size) - copyToBuffer(result) + // Faster to let the map iterate itself than to defer through copyToBuffer + foreach(result += _) result } diff --git a/src/library/scala/collection/SetLike.scala b/src/library/scala/collection/SetLike.scala index 3e549f72cd..80a344e6a8 100644 --- a/src/library/scala/collection/SetLike.scala +++ b/src/library/scala/collection/SetLike.scala @@ -77,11 +77,20 @@ self => protected[this] override def parCombiner = ParSet.newCombiner[A] - /* Overridden for efficiency. */ - override def toSeq: Seq[A] = toBuffer[A] + // Default collection type appropriate for immutable collections; mutable collections override this + override def toSeq: Seq[A] = { + if (isEmpty) Vector.empty[A] + else { + val vb = Vector.newBuilder[A] + foreach(vb += _) + vb.result + } + } + override def toBuffer[A1 >: A]: mutable.Buffer[A1] = { val result = new mutable.ArrayBuffer[A1](size) - copyToBuffer(result) + // Faster to let the map iterate itself than to defer through copyToBuffer + foreach(result += _) result } diff --git a/src/library/scala/collection/mutable/MapLike.scala b/src/library/scala/collection/mutable/MapLike.scala index 6230fc23aa..8ba31d47b6 100644 --- a/src/library/scala/collection/mutable/MapLike.scala +++ b/src/library/scala/collection/mutable/MapLike.scala @@ -59,6 +59,18 @@ trait MapLike[A, B, +This <: MapLike[A, B, This] with Map[A, B]] override protected[this] def newBuilder: Builder[(A, B), This] = empty protected[this] override def parCombiner = ParMap.newCombiner[A, B] + + /** Converts this $coll to a sequence. + * + * ```Note```: assumes a fast `size` method. Subclasses should override if this is not true. + */ + override def toSeq: collection.Seq[(A, B)] = { + // ArrayBuffer for efficiency, preallocated to the right size. + val result = new ArrayBuffer[(A, B)](size) + foreach(result += _) + result + } + /** Adds a new key/value pair to this map and optionally returns previously bound value. * If the map already contains a diff --git a/src/library/scala/collection/mutable/SetLike.scala b/src/library/scala/collection/mutable/SetLike.scala index a377b03124..cbe7a639dd 100644 --- a/src/library/scala/collection/mutable/SetLike.scala +++ b/src/library/scala/collection/mutable/SetLike.scala @@ -72,6 +72,17 @@ trait SetLike[A, +This <: SetLike[A, This] with Set[A]] protected[this] override def parCombiner = ParSet.newCombiner[A] + /** Converts this $coll to a sequence. + * + * ```Note```: assumes a fast `size` method. Subclasses should override if this is not true. + */ + override def toSeq: collection.Seq[A] = { + // ArrayBuffer for efficiency, preallocated to the right size. + val result = new ArrayBuffer[A](size) + foreach(result += _) + result + } + /** Adds an element to this $coll. * * @param elem the element to be added diff --git a/test/files/run/inline-ex-handlers.check b/test/files/run/inline-ex-handlers.check index 7c885d2cc9..27a277d314 100644 --- a/test/files/run/inline-ex-handlers.check +++ b/test/files/run/inline-ex-handlers.check @@ -123,12 +123,12 @@ 300 RETURN(UNIT) @@ -583,6 +603,6 @@ with finalizer: null -- catch (Throwable) in ArrayBuffer(7, 9, 10) starting at: 6 -+ catch (Throwable) in ArrayBuffer(7, 9, 10, 11) starting at: 6 +- catch (Throwable) in Vector(7, 9, 10) starting at: 6 ++ catch (Throwable) in Vector(7, 9, 10, 11) starting at: 6 consisting of blocks: List(6) with finalizer: null -- catch (Throwable) in ArrayBuffer(4, 6, 7, 9, 10) starting at: 3 -+ catch (Throwable) in ArrayBuffer(4, 6, 7, 9, 10, 11, 12) starting at: 3 +- catch (Throwable) in Vector(4, 6, 7, 9, 10) starting at: 3 ++ catch (Throwable) in Vector(4, 6, 7, 9, 10, 11, 12) starting at: 3 consisting of blocks: List(3) @@ -618,3 +638,3 @@ startBlock: 1 @@ -171,8 +171,8 @@ } @@ -690,3 +730,3 @@ with finalizer: null -- catch () in ArrayBuffer(4, 5, 6, 8) starting at: 3 -+ catch () in ArrayBuffer(4, 5, 6, 8, 10) starting at: 3 +- catch () in Vector(4, 5, 6, 8) starting at: 3 ++ catch () in Vector(4, 5, 6, 8, 10) starting at: 3 consisting of blocks: List(3) @@ -714,5 +754,5 @@ def main(args: Array[String] (ARRAY[REF(class String)])): Unit { @@ -276,12 +276,12 @@ } @@ -852,6 +918,6 @@ with finalizer: null -- catch (Throwable) in ArrayBuffer(13, 14, 15, 18, 20, 21, 23) starting at: 4 -+ catch (Throwable) in ArrayBuffer(13, 14, 15, 18, 20, 21, 23, 25) starting at: 4 +- catch (Throwable) in Vector(13, 14, 15, 18, 20, 21, 23) starting at: 4 ++ catch (Throwable) in Vector(13, 14, 15, 18, 20, 21, 23, 25) starting at: 4 consisting of blocks: List(9, 8, 6, 5, 4) with finalizer: null -- catch () in ArrayBuffer(4, 5, 6, 9, 13, 14, 15, 18, 20, 21, 23) starting at: 3 -+ catch () in ArrayBuffer(4, 5, 6, 9, 13, 14, 15, 18, 20, 21, 23, 25, 26) starting at: 3 +- catch () in Vector(4, 5, 6, 9, 13, 14, 15, 18, 20, 21, 23) starting at: 3 ++ catch () in Vector(4, 5, 6, 9, 13, 14, 15, 18, 20, 21, 23, 25, 26) starting at: 3 consisting of blocks: List(3) @@ -879,5 +945,5 @@ def main(args: Array[String] (ARRAY[REF(class String)])): Unit { @@ -317,8 +317,8 @@ 127 CALL_METHOD scala.Predef.println (dynamic) @@ -964,3 +1034,3 @@ with finalizer: null -- catch (IllegalArgumentException) in ArrayBuffer(6, 7, 8, 11, 13, 14, 16) starting at: 3 -+ catch (IllegalArgumentException) in ArrayBuffer(6, 7, 8, 11, 13, 14, 16, 17) starting at: 3 +- catch (IllegalArgumentException) in Vector(6, 7, 8, 11, 13, 14, 16) starting at: 3 ++ catch (IllegalArgumentException) in Vector(6, 7, 8, 11, 13, 14, 16, 17) starting at: 3 consisting of blocks: List(3) @@ -988,5 +1058,5 @@ def main(args: Array[String] (ARRAY[REF(class String)])): Unit { -- cgit v1.2.3