Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
scabug opened this issue May 25, 2011 · 4 comments
Closed

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

scabug opened this issue May 25, 2011 · 4 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented May 25, 2011

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
  }
@scabug
Copy link
Author

scabug commented May 25, 2011

Imported From: https://issues.scala-lang.org/browse/SI-4647?orig=1
Reporter: Stephen Marsh (smarsh)
Affected Versions: 2.8.1

@scabug
Copy link
Author

scabug commented May 25, 2011

@dcsobral said (edited on May 25, 2011 8:02:09 PM UTC):
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.

@scabug
Copy link
Author

scabug commented May 25, 2011

Stephen Marsh (smarsh) said:
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}

@scabug
Copy link
Author

scabug commented Dec 1, 2011

@soc said:
scala/scala@2d0f828

Improved BitSet implementations
[...]

  • immutable.BitSet uses a more efficient Builder, based on
    mutable.BitSet (closes SI-4647)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants