Details

      Description

      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.

        Issue Links

          Activity

          Hide
          Rüdiger Klaehn added a comment -

          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
          
          Show
          Rüdiger Klaehn added a comment - 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
          Hide
          Rüdiger Klaehn added a comment -
          Show
          Rüdiger Klaehn added a comment - Added pull request https://github.com/scala/scala/pull/1126
          Hide
          Rüdiger Klaehn added a comment -

          Implementing SI-6197 is a prerequisite for enabling the assertion in HashTrieSet

          Show
          Rüdiger Klaehn added a comment - Implementing SI-6197 is a prerequisite for enabling the assertion in HashTrieSet
          Show
          Adriaan Moors added a comment - https://github.com/scala/scala/pull/1160

            People

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

              Dates

              • Created:
                Updated:
                Resolved:

                Development