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
Labels
Milestone

Comments

@scabug
Copy link

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 12, 2012

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

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 13, 2012

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

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Oct 3, 2012

@scabug scabug closed this Oct 3, 2012
@scabug scabug added this to the 2.10.0-M6 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant
You can’t perform that action at this time.