Scala Programming Language
  1. Scala Programming Language
  2. SI-4647

immutable.BitSet's builder's + has O(N) rather than O(1) runtime

    Details

      Description

      immutable.BitSet's builder uses an immutable.BitSet inside, and every time a new element is added to the builder it copies this BitSet. This makes methods like BitSet.++, which use the builder, run in O(N^2) rather than O(N) time, which makes creating immutable.BitSets with large sets very difficult.

      Here is a new implementation that solves this problem:

        /** A builder that takes advantage of mutable BitSets. */
        def newBuilder: Builder[Int, BitSet] = new Builder[Int, BitSet] with Proxy {
          val self = new mutable.BitSet
          def +=(x: Int): this.type = {self += x; this}
          def clear() = {self.clear}
          def result: BitSet = self.toImmutable
        }
      

        Activity

        Hide
        Daniel Sobral added a comment - - edited

        That doesn't look thread-safe to me. Then again, I'm not sure if a Builder is supposed to be thread-safe or not.

        Show
        Daniel Sobral added a comment - - edited That doesn't look thread-safe to me. Then again, I'm not sure if a Builder is supposed to be thread-safe or not.
        Hide
        Stephen Marsh added a comment -

        It's not thread-safe. But the old builder using SetBuilder relies on updating a var without any synchronization, so it isn't thread-safe either, and neither were any of the other Builders I looked at (for List etc.). If it needs to be thread-safe, only the += method needs to be synchronized.

        def +=(x: Int): this.type = synchronized {self += x; this}
        
        Show
        Stephen Marsh added a comment - It's not thread-safe. But the old builder using SetBuilder relies on updating a var without any synchronization, so it isn't thread-safe either, and neither were any of the other Builders I looked at (for List etc.). If it needs to be thread-safe, only the += method needs to be synchronized. def +=(x: Int): this.type = synchronized {self += x; this}
        Hide
        Simon Ochsenreither added a comment -

        https://github.com/scala/scala/commit/2d0f82898dc6e3998db425dbab571ba297deda41

        Improved BitSet implementations
        [...]

        • immutable.BitSet uses a more efficient Builder, based on
          mutable.BitSet (closes SI-4647)
        Show
        Simon Ochsenreither added a comment - https://github.com/scala/scala/commit/2d0f82898dc6e3998db425dbab571ba297deda41 Improved BitSet implementations [...] immutable.BitSet uses a more efficient Builder, based on mutable.BitSet (closes SI-4647 )

          People

          • Assignee:
            Stefan Zeiger
            Reporter:
            Stephen Marsh
          • Votes:
            1 Vote for this issue
            Watchers:
            7 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development