diff options
author | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2013-09-11 12:09:52 -0700 |
---|---|---|
committer | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2013-09-11 12:09:52 -0700 |
commit | 9788e7a1f1809491154c2bcb47d3061b11c1d8a8 (patch) | |
tree | 78d5a6bea262ce658ed6645212deb930eab2fb6e /src/library | |
parent | 54666c987ae680de79a1fab1dbeb355d8156f31f (diff) | |
parent | f812a4c1ecef008107a1a824baea5a3889dad344 (diff) | |
download | scala-9788e7a1f1809491154c2bcb47d3061b11c1d8a8.tar.gz scala-9788e7a1f1809491154c2bcb47d3061b11c1d8a8.tar.bz2 scala-9788e7a1f1809491154c2bcb47d3061b11c1d8a8.zip |
Merge pull request #2927 from Ichoran/issue/7708
SI-7708 - Improve Bitset foreach performance
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/BitSetLike.scala | 27 |
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 |