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

Improvements for HashSet #6220

Closed
scabug opened this issue Aug 12, 2012 · 5 comments
Closed

Improvements for HashSet #6220

scabug opened this issue Aug 12, 2012 · 5 comments
Milestone

Comments

@scabug
Copy link

scabug commented Aug 12, 2012

Performance improvements in updated0 (where there are todos in the current version). This will prevent several temporary object creations and have a significant benefit a) with small sets and b) with sets containing collisions

Avoid having to create a temporary HashTrieSet with 0 or 1 elements

Add assertion on HashTrieSet to prevent people from violating invariants

The main point is not the performance improvements, athough there are a nice side benefit, but that it will be possible to prevent violating the assumptions of HashTrieSet with a relatively cheap assertion.

@scabug
Copy link
Author

scabug commented Aug 12, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6220?orig=1
Reporter: @rklaehn
Assignee: @rklaehn
Affected Versions: 2.10.0-M6
Other Milestones: 2.10.0
See #6197

@scabug
Copy link
Author

scabug commented Aug 12, 2012

@rklaehn said:
I wrote a little program that shows all objects of any type being created in a code block using this http://code.google.com/p/java-allocation-instrumenter/ :

import com.google.monitoring.runtime.instrumentation.AllocationRecorder
import com.google.monitoring.runtime.instrumentation.Sampler
import scala.collection.immutable._

object Test extends App {
  @volatile var enabled = false
  val sampler = new Sampler {
    def sampleAllocation(count:Int, desc:String, newObj:AnyRef, size:Long) {
      if(enabled) {
	if(count>=0)
          println("Array["+ desc + "] " + count+ " bytes="+size)        
        else 
	  println(desc + " bytes=" + size)
      }
    }
  }
  val x0 = HashSet.empty[Int] + 1 + 2
  AllocationRecorder.addSampler(sampler)
  enabled = true
  val x = HashSet.empty[Int] + 1 + 2
  enabled = false
}

When running this with the current collections, you get this. A lot of unnecessary object creations, and HashTrieSet gets temporarily created with 0 elements, which does not make sense for a final HashTrieSet and prevents putting a meaningful assert in it.

rudi@ubuntu:~/objectcounting$ java -cp ../projects_git/scala/lib/scala-library.jar:allocation.jar:. -javaagent:allocation.jar Test
scala/collection/immutable/HashSet$HashSet1 bytes=24
Array[scala/collection/immutable/HashSet] 0 bytes=16
scala/collection/immutable/HashSet$HashTrieSet bytes=24
Array[scala/collection/immutable/HashSet] 1 bytes=24
scala/collection/immutable/HashSet$HashSet1 bytes=24
scala/collection/immutable/HashSet$HashTrieSet bytes=24
Array[scala/collection/immutable/HashSet] 2 bytes=24
scala/collection/immutable/HashSet$HashSet1 bytes=24
scala/collection/immutable/HashSet$HashTrieSet bytes=24

When running it with the optimized version of HashSet, you get this:

rudi@ubuntu:~/objectcounting$ java -cp ../projects_git/scala/build/pack/lib/scala-library.jar:allocation.jar:. -javaagent:allocation.jar Test
scala/collection/immutable/HashSet$HashSet1 bytes=24
scala/collection/immutable/HashSet$HashSet1 bytes=24
Array[scala/collection/immutable/HashSet] 2 bytes=24
scala/collection/immutable/HashSet$HashTrieSet bytes=24

@scabug
Copy link
Author

scabug commented Aug 12, 2012

@rklaehn said:
Added pull request
scala/scala#1126

@scabug
Copy link
Author

scabug commented Aug 13, 2012

@rklaehn said:
Implementing #6197 is a prerequisite for enabling the assertion in HashTrieSet

@scabug
Copy link
Author

scabug commented Oct 3, 2012

@adriaanm said:
scala/scala#1160

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

1 participant