SI-7708 - Improve Bitset foreach performance

1. Switched inner for loop for a while loop to enable early exit when bitset
is sparse.

2. Switched outer for loop for while loop for performance.

3. Changed WordLength and friends to final for performance.

New version runs in 60% of time of old on dense bitsets, faster if highly
sparse.  No tests committed (requires performance testing framework).

1 files changed, 17 insertions, 10 deletions

diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala
index f11f3757a6..6592e49429 100644
--- a/src/library/scala/collection/BitSetLike.scala
+++ b/src/library/scala/collection/BitSetLike.scala
@@ -116,14 +116,20 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
   }
 
   override def foreach[B](f: Int => B) {
-    for (i <- 0 until nwords) {
-      val w = word(i)
-      /* NOTE: `until` instead of `to` will not work here because
-         the maximum value of `(i + 1) * WordLength` could be
-         `Int.MaxValue + 1` (i.e. `Int.MinValue`). */
-      for (j <- i * WordLength to (i + 1) * WordLength - 1) {
-        if ((w & (1L << j)) != 0L) f(j)
+    /* NOTE: while loops are significantly faster as of 2.11 and
+       one major use case of bitsets is performance. Also, there
+       is nothing to do when all bits are clear, so use that as
+       the inner loop condition. */
+    var i = 0
+    while (i < nwords) {
+      var w = word(i)
+      var j = i * WordLength
+      while (w != 0L) {
+        if ((w&1L) == 1L) f(j)
+        w = w >>> 1
+        j += 1
       }
+      i += 1
     }
   }
 
@@ -218,9 +224,10 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
 
 /** Companion object for BitSets. Contains private data only */
 object BitSetLike {
-  private[collection] val LogWL = 6
-  private val WordLength = 64
-  private[collection] val MaxSize = (Int.MaxValue >> LogWL) + 1
+  /* Final vals can sometimes be inlined as constants (faster) */
+  private[collection] final val LogWL = 6
+  private final val WordLength = 64
+  private[collection] final val MaxSize = (Int.MaxValue >> LogWL) + 1
 
   private[collection] def updateArray(elems: Array[Long], idx: Int, w: Long): Array[Long] = {
     var len = elems.length