diff options
author | Rex Kerr <ichoran@gmail.com> | 2015-08-29 18:10:26 -0700 |
---|---|---|
committer | Rex Kerr <ichoran@gmail.com> | 2016-02-17 15:29:44 -0800 |
commit | 3db50837cca2f92aee48fe44bc38106dbc5f4c59 (patch) | |
tree | 9a5170650d0cc42fff40637450a11f3f6679b79b /src/library/scala/collection/immutable/BitSet.scala | |
parent | 1564f28fe594da85b53b403346636adadbb4b8db (diff) | |
download | scala-3db50837cca2f92aee48fe44bc38106dbc5f4c59.tar.gz scala-3db50837cca2f92aee48fe44bc38106dbc5f4c59.tar.bz2 scala-3db50837cca2f92aee48fe44bc38106dbc5f4c59.zip |
SI-9347 Efficient head/tail, if possible, for immutable maps & sets
Most immutable collections, including sets and maps, have a better-than-O(n) method for removing an element. In those cases, tail and possibly head were overridden so the head/tail pattern can be used with less of a performance penalty.
Speed improvements on head/tail pattern are
(for sets/maps of size 1024, unless otherwise specified):
```
BitSet 190x
HashSet 250x
Set 400x
Set2 9x
Set4 12x
HashMap 430x
ListMap 2500x // size 128
Map 430x
```
Note: `ListMap` is actually `init`/`last` because it's maintained in reverse order.
Altered ListMap docs to explain that reverse traversal is the fast way to do it.
All tested sets/maps that were already fast are still fast.
Test code is reproduced below, except it does ListSet with head/tail which
doesn't show the improvement:
```scala
object BenchTailSetMap {
val th = new ichi.bench.Thyme
val standard = 1 to 1024
val sets = Map[String, Set[Int]](
"Set" -> (Set.empty[Int] ++ standard),
"Set4"-> Set(4, 7, 2, 1),
"Set2"-> Set(3, 4),
"HashSet" -> (collection.immutable.HashSet.empty[Int] ++ standard),
"BitSet" -> (collection.immutable.BitSet.empty ++ standard),
"SortedSet" -> (collection.immutable.SortedSet.empty[Int] ++ standard),
"ListSet" -> (collection.immutable.ListSet.empty[Int] ++ standard)
)
val pairs = standard.map(i => i -> i.toString)
// ListMap implementation is HORRIBLE, O(n^3) tail! Cut down size.
val maps = Map[String, Map[Int, String]](
"Map" -> (Map.empty[Int, String] ++ pairs),
"HashMap" -> (collection.immutable.HashMap.empty[Int, String] ++ pairs),
"SortedMap" -> (collection.immutable.SortedMap.empty[Int, String] ++ pairs),
"ListMap" -> (collection.immutable.ListMap.empty[Int, String] ++ pairs.take(128))
)
def hts(s: Set[Int]) = {
var si = s
var x = 0
while (si.nonEmpty) {
x += si.head
si = si.tail
}
x
}
def htm(m: Map[Int, String]) = {
var mi = m
var x = 0
while (mi.nonEmpty) {
x += mi.head._2.length
mi = mi.tail
}
x
}
def run() {
sets.toList.sortBy(_._1).foreach{ case (name, s) => th.pbench(hts(s), s.size, name) }
maps.toList.sortBy(_._1).foreach{ case (name, m) => th.pbench(htm(m), m.size, name) }
}
}
```
Diffstat (limited to 'src/library/scala/collection/immutable/BitSet.scala')
-rw-r--r-- | src/library/scala/collection/immutable/BitSet.scala | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index 846bc22182..6bb1f116fe 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -103,6 +103,7 @@ object BitSet extends BitSetFactory[BitSet] { else new BitSetN(elems) } + @SerialVersionUID(2260107458435649300L) class BitSet1(val elems: Long) extends BitSet { protected def nwords = 1 protected def word(idx: Int) = if (idx == 0) elems else 0L @@ -110,6 +111,12 @@ object BitSet extends BitSetFactory[BitSet] { if (idx == 0) new BitSet1(w) else if (idx == 1) new BitSet2(elems, w) else fromBitMaskNoCopy(updateArray(Array(elems), idx, w)) + override def head: Int = + if (elems == 0L) throw new NoSuchElementException("Empty BitSet") + else java.lang.Long.numberOfTrailingZeros(elems) + override def tail: BitSet = + if (elems == 0L) throw new NoSuchElementException("Empty BitSet") + else new BitSet1(elems - java.lang.Long.lowestOneBit(elems)) } class BitSet2(val elems0: Long, elems1: Long) extends BitSet { @@ -119,6 +126,18 @@ object BitSet extends BitSetFactory[BitSet] { if (idx == 0) new BitSet2(w, elems1) else if (idx == 1) new BitSet2(elems0, w) else fromBitMaskNoCopy(updateArray(Array(elems0, elems1), idx, w)) + override def head: Int = + if (elems0 == 0L) { + if (elems1 == 0) throw new NoSuchElementException("Empty BitSet") + 64 + java.lang.Long.numberOfTrailingZeros(elems1) + } + else java.lang.Long.numberOfTrailingZeros(elems0) + override def tail: BitSet = + if (elems0 == 0L) { + if (elems1 == 0L) throw new NoSuchElementException("Empty BitSet") + new BitSet2(elems0, elems1 - java.lang.Long.lowestOneBit(elems1)) + } + else new BitSet2(elems0 - java.lang.Long.lowestOneBit(elems0), elems1) } /** The implementing class for bit sets with elements >= 128 (exceeding @@ -131,5 +150,15 @@ object BitSet extends BitSetFactory[BitSet] { protected def nwords = elems.length protected def word(idx: Int) = if (idx < nwords) elems(idx) else 0L protected def updateWord(idx: Int, w: Long): BitSet = fromBitMaskNoCopy(updateArray(elems, idx, w)) + override def tail: BitSet = { + val n = nwords + var i = 0 + while (i < n) { + val wi = word(i) + if (wi != 0L) return fromBitMaskNoCopy(updateArray(elems, i, wi - java.lang.Long.lowestOneBit(wi))) + i += 1 + } + throw new NoSuchElementException("Empty BitSet") + } } } |