From fe6886eb0ec9c02fa666e9e7af09bab92b985d05 Mon Sep 17 00:00:00 2001 From: Rui Gonçalves Date: Sun, 17 Apr 2016 17:51:17 +0100 Subject: Improve performance and behavior of ListMap and ListSet Makes the immutable `ListMap` and `ListSet` collections more alike one another, both in their semantics and in their performance. In terms of semantics, makes the `ListSet` iterator return the elements in their insertion order, as `ListMap` already does. While, as mentioned in SI-8985, `ListMap` and `ListSet` doesn't seem to make any guarantees in terms of iteration order, I believe users expect `ListSet` and `ListMap` to behave in the same way, particularly when they are implemented in the exact same way. In terms of performance, `ListSet` has a custom builder that avoids creation in O(N^2) time. However, this significantly reduces its performance in the creation of small sets, as its requires the instantiation and usage of an auxilliary HashSet. As `ListMap` and `ListSet` are only suitable for small sizes do to their performance characteristics, the builder is removed, the default `SetBuilder` being used instead. --- test/files/jvm/serialization-new.check | 4 ++-- test/files/jvm/serialization.check | 4 ++-- test/files/run/t3822.scala | 19 ------------------- test/files/run/t6198.scala | 7 ------- test/files/run/t7445.scala | 6 ------ 5 files changed, 4 insertions(+), 36 deletions(-) delete mode 100644 test/files/run/t3822.scala delete mode 100644 test/files/run/t7445.scala (limited to 'test/files') diff --git a/test/files/jvm/serialization-new.check b/test/files/jvm/serialization-new.check index cb26446f40..91248320d4 100644 --- a/test/files/jvm/serialization-new.check +++ b/test/files/jvm/serialization-new.check @@ -89,8 +89,8 @@ x = Map(buffers -> 20, layers -> 2, title -> 3) y = Map(buffers -> 20, layers -> 2, title -> 3) x equals y: true, y equals x: true -x = ListSet(5, 3) -y = ListSet(5, 3) +x = ListSet(3, 5) +y = ListSet(3, 5) x equals y: true, y equals x: true x = Queue(a, b, c) diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check index cb26446f40..91248320d4 100644 --- a/test/files/jvm/serialization.check +++ b/test/files/jvm/serialization.check @@ -89,8 +89,8 @@ x = Map(buffers -> 20, layers -> 2, title -> 3) y = Map(buffers -> 20, layers -> 2, title -> 3) x equals y: true, y equals x: true -x = ListSet(5, 3) -y = ListSet(5, 3) +x = ListSet(3, 5) +y = ListSet(3, 5) x equals y: true, y equals x: true x = Queue(a, b, c) diff --git a/test/files/run/t3822.scala b/test/files/run/t3822.scala deleted file mode 100644 index c35804035e..0000000000 --- a/test/files/run/t3822.scala +++ /dev/null @@ -1,19 +0,0 @@ -import scala.collection.{ mutable, immutable, generic } -import immutable.ListSet - -object Test { - def main(args: Array[String]): Unit = { - val xs = ListSet(-100000 to 100001: _*) - - assert(xs.size == 200002) - assert(xs.sum == 100001) - - val ys = ListSet[Int]() - val ys1 = (1 to 12).grouped(3).foldLeft(ys)(_ ++ _) - val ys2 = (1 to 12).foldLeft(ys)(_ + _) - - assert(ys1 == ys2) - } -} - - diff --git a/test/files/run/t6198.scala b/test/files/run/t6198.scala index 5aa8f1c1cf..65dbaf8160 100644 --- a/test/files/run/t6198.scala +++ b/test/files/run/t6198.scala @@ -1,13 +1,6 @@ import scala.collection.immutable._ object Test extends App { - // test that ListSet.tail does not use a builder - // we can't test for O(1) behavior, so the best we can do is to - // check that ls.tail always returns the same instance - val ls = ListSet.empty[Int] + 1 + 2 - - if(ls.tail ne ls.tail) - println("ListSet.tail should not use a builder!") // class that always causes hash collisions case class Collision(value:Int) { override def hashCode = 0 } diff --git a/test/files/run/t7445.scala b/test/files/run/t7445.scala deleted file mode 100644 index e4ffeb8e1a..0000000000 --- a/test/files/run/t7445.scala +++ /dev/null @@ -1,6 +0,0 @@ -import scala.collection.immutable.ListMap - -object Test extends App { - val a = ListMap(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5); - require(a.tail == ListMap(2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)); -} -- cgit v1.2.3