Details

      Description

      HashSet does not implement union. That means that creating the union of two sets is very inefficient. Adding a large set to a small set creates the entire set anew.

      scala> val a = Set.empty[Int]
      a: scala.collection.immutable.Set[Int] = Set()
      
      scala> val b = Set(1,2,3,4,5)
      b: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)
      
      scala> val c = a union b
      c: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)
      
      scala> c eq b
      res0: Boolean = false
      

      c is a completely new set even though it contains the exact same elements as b and could therefore be eq b.

      Clearly this is not good. A set should have the most efficient possible implementation for intersection and union. The implementation of filter for set (SI-6196) allows for a fast intersection. The missing operation union is already implemented in HashSet as merge. So all that needs to be done is to adapt the merge algorithm of HashMap to HashSet.

        Issue Links

          Activity

          Hide
          Rüdiger Klaehn added a comment -

          When is scala 2.11 due? I have a week of holiday left this year, so maybe I can work on it then.

          Show
          Rüdiger Klaehn added a comment - When is scala 2.11 due? I have a week of holiday left this year, so maybe I can work on it then.
          Hide
          Rex Kerr added a comment -

          Any significant changes would have to be in (including review and testing) by Friday to make 2.11 without a very compelling argument that we are missing an essential feature.

          Show
          Rex Kerr added a comment - Any significant changes would have to be in (including review and testing) by Friday to make 2.11 without a very compelling argument that we are missing an essential feature.
          Hide
          Rüdiger Klaehn added a comment -

          Damn. Seems that I missed the deadline. Do you anticipate any major collection redesign, or would it be OK to just add a pull request against 2.12?

          Show
          Rüdiger Klaehn added a comment - Damn. Seems that I missed the deadline. Do you anticipate any major collection redesign, or would it be OK to just add a pull request against 2.12?
          Hide
          Rex Kerr added a comment -

          You can add a pull request against 2.11 and I'll evaluate. There's a reasonable chance that it will be fine for M8 (and if not we can just delay it to 2.12).

          Show
          Rex Kerr added a comment - You can add a pull request against 2.11 and I'll evaluate. There's a reasonable chance that it will be fine for M8 (and if not we can just delay it to 2.12).
          Show
          Rex Kerr added a comment - https://github.com/scala/scala/pull/3322

            People

            • Assignee:
              Rüdiger Klaehn
              Reporter:
              Rüdiger Klaehn
            • Votes:
              2 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development