Improve performance of BitSet.size

szeiger · szeiger · commit 989c0d0693e2 · 2011-12-02T12:45:40.000+01:00
Using java.lang.Long.bitCount for the size computation is a lot faster
than the previous Scala implementation. Closes SI-2196.
diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala
@@ -65,7 +65,7 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
     var i = nwords
     while (i > 0) {
       i -= 1
-      s += popCount(word(i))
+      s += java.lang.Long.bitCount(word(i))
     }
     s
   }
@@ -221,15 +221,4 @@ object BitSetLike {
     else assert(w == 0L)
     newelems
   }
-
-  private val pc1: Array[Int] = {
-    def countBits(x: Int): Int = if (x == 0) 0 else x % 2 + countBits(x >>> 1)
-    Array.tabulate(256)(countBits _)
-  }
-
-  private def popCount(w: Long): Int = {
-    def pc2(w: Int) = if (w == 0) 0 else pc1(w & 0xff) + pc1(w >>> 8)
-    def pc4(w: Int) = if (w == 0) 0 else pc2(w & 0xffff) + pc2(w >>> 16)
-    if (w == 0L) 0 else pc4(w.toInt) + pc4((w >>> 32).toInt)
-  }
 }

Original file line number	Diff line number	Diff line change
`@@ -65,7 +65,7 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe`
`65`	`65`	`var i = nwords`
`66`	`66`	`while (i > 0) {`
`67`	`67`	`i -= 1`
`68`		`- s += popCount(word(i))`
	`68`	`+ s += java.lang.Long.bitCount(word(i))`
`69`	`69`	`}`
`70`	`70`	`s`
`71`	`71`	`}`
`@@ -221,15 +221,4 @@ object BitSetLike {`
`221`	`221`	`else assert(w == 0L)`
`222`	`222`	`newelems`
`223`	`223`	`}`
`224`		`-`
`225`		`- private val pc1: Array[Int] = {`
`226`		`- def countBits(x: Int): Int = if (x == 0) 0 else x % 2 + countBits(x >>> 1)`
`227`		`- Array.tabulate(256)(countBits _)`
`228`		`- }`
`229`		`-`
`230`		`- private def popCount(w: Long): Int = {`
`231`		`- def pc2(w: Int) = if (w == 0) 0 else pc1(w & 0xff) + pc1(w >>> 8)`
`232`		`- def pc4(w: Int) = if (w == 0) 0 else pc2(w & 0xffff) + pc2(w >>> 16)`
`233`		`- if (w == 0L) 0 else pc4(w.toInt) + pc4((w >>> 32).toInt)`
`234`		`- }`
`235`	`224`	`}`