diff options
author | Paul Phillips <paulp@improving.org> | 2011-12-12 13:48:08 -0800 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2011-12-12 13:48:08 -0800 |
commit | c6dedf91dc02079914160b87dabb4e0ef640b049 (patch) | |
tree | be04f58400cfe7afcf5b6f94f8d2f6547fc0d9aa | |
parent | 6bbc8d2436b553d610f6a75f18455a2549e92605 (diff) | |
parent | 23687eb2e2e4b7e0e8f4b5386320c539664e3542 (diff) | |
download | scala-c6dedf91dc02079914160b87dabb4e0ef640b049.tar.gz scala-c6dedf91dc02079914160b87dabb4e0ef640b049.tar.bz2 scala-c6dedf91dc02079914160b87dabb4e0ef640b049.zip |
Merge branch 'dec10-checkin'
3 files changed, 139 insertions, 13 deletions
diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index e891f8bec8..16d7e68dee 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -71,18 +71,6 @@ extends collection.AbstractSeq[Int] def isInclusive = false - @inline final override def foreach[@specialized(Unit) U](f: Int => U) { - if (length > 0) { - val last = this.last - var i = start - while (i != last) { - f(i) - i += step - } - f(i) - } - } - override def length: Int = numRangeElements override lazy val last: Int = if (length == 0) Nil.last @@ -95,6 +83,83 @@ extends collection.AbstractSeq[Int] if (idx < 0 || idx >= length) throw new IndexOutOfBoundsException(idx.toString) locationAfterN(idx) } + + /** @note Making foreach run as fast as a while loop is a challenge. + * The key elements which I can observe making a difference are: + * + * - the inner loop should be as small as possible + * - the inner loop should be monomorphic + * - the inner loop should perform no boxing and no avoidable tests + * + * This is achieved by: + * + * - keeping initialization logic out of the inner loop + * - dispatching to custom variations based on initial conditions + * - tricking the compiler into always calling Function1#apply$mcVI$sp + * + * The last one is important and less than obvious. Even when foreach + * was specialized on Unit, only Int => Unit arguments benefited from it. + * Other function types would be accepted, but in the absence of full + * specialization the integer argument was boxed on every call. For example: + * + class A { + final def f(x: Int): Int = x + 1 + // Calls Range.foreach, which calls Function1.apply + def g1 = 1 until 100 foreach { x => f(x) } + // Calls Range.foreach$mVc$sp, which calls Function1.apply$mcVI$sp + def g2 = 1 until 100 foreach { x => f(x) ; () } + } + * + * However! Since the result of the closure is always discarded, we + * simply cast it to Int => Unit, thereby executing the fast version. + * The seemingly looming ClassCastException can never arrive. + */ + @inline final override def foreach[U](f: Int => U) { + if (step < 0) { + if (isInclusive) foreachDownIn(f.asInstanceOf[Int => Unit]) + else foreachDownEx(f.asInstanceOf[Int => Unit]) + } + else { + if (isInclusive) foreachUpIn(f.asInstanceOf[Int => Unit]) + else foreachUpEx(f.asInstanceOf[Int => Unit]) + } + } + + /** !!! These methods must be public or they will not be inlined. + * But they are certainly not intended to be part of the API. + * This collision between inlining requirements and access semantics + * is highly unfortunate and must be resolved. + * + * Proposed band-aid: an @internal annotation. + */ + @inline final def foreachDownIn(f: Int => Unit) { + var i = start + while (i >= end) { + f(i) + i += step + } + } + @inline final def foreachUpIn(f: Int => Unit) { + var i = start + while (i <= end) { + f(i) + i += step + } + } + @inline final def foreachDownEx(f: Int => Unit) { + var i = start + while (i > end) { + f(i) + i += step + } + } + @inline final def foreachUpEx(f: Int => Unit) { + var i = start + while (i < end) { + f(i) + i += step + } + } /** Creates a new range containing the first `n` elements of this range. * diff --git a/src/library/scala/collection/parallel/immutable/ParRange.scala b/src/library/scala/collection/parallel/immutable/ParRange.scala index 2a10458457..350e64739f 100644 --- a/src/library/scala/collection/parallel/immutable/ParRange.scala +++ b/src/library/scala/collection/parallel/immutable/ParRange.scala @@ -88,7 +88,7 @@ self => /* accessors */ override def foreach[U](f: Int => U): Unit = { - rangeleft.foreach(f) + rangeleft.foreach(f.asInstanceOf[Int => Unit]) ind = len } diff --git a/test/benchmarks/src/scala/collection/immutable/range-bench.scala b/test/benchmarks/src/scala/collection/immutable/range-bench.scala new file mode 100644 index 0000000000..e167ff04e8 --- /dev/null +++ b/test/benchmarks/src/scala/collection/immutable/range-bench.scala @@ -0,0 +1,61 @@ +package scala.collection.immutable +package benchmarks + +object RangeTest { + // not inlined any more, needs investigation + // + // class XXS { + // private val array = Array.range(0, 100) + // def tst = { var sum = 0; for (i <- 0 until array.length) sum += array(i); sum } + // } + + var x: Int = 0 + + def foreachSum(max: Int): Int = { + var sum = 0 + 1 to max foreach (sum += _) + sum + } + def whileSum(max: Int) = { + var sum = 0 + var num = 1 + while (num <= max) { + sum += num + num += 1 + } + sum + } + + def show(max: Int, foreachNanos: Long, whileNanos: Long) { + val winner = if (foreachNanos < whileNanos) "foreachSum" else "whileSum" + val ratio = if (foreachNanos < whileNanos) foreachNanos.toDouble / whileNanos else whileNanos.toDouble / foreachNanos + println("1 to %d:, %12s wins, %.3f: foreach %.3f while %.3f".format( + max, winner, ratio, + foreachNanos.toDouble / 1000000L, + whileNanos.toDouble / 1000000L) + ) + } + + def run(max: Int) = { + val foreachFirst = util.Random.nextBoolean + val t1 = System.nanoTime + x = if (foreachFirst) foreachSum(max) else whileSum(max) + val t2 = System.nanoTime + x = if (foreachFirst) whileSum(max) else foreachSum(max) + val t3 = System.nanoTime + + val foreachNanos = if (foreachFirst) t2 - t1 else t3 - t2 + val whileNanos = if (foreachFirst) t3 - t2 else t2 - t1 + show(max, foreachNanos, whileNanos) + } + + def main(args: Array[String]): Unit = { + var max = if (args.isEmpty) 100 else args(0).toInt + while (max > 0) { + run(max) + run(max) + run(max) + max += (max / 7) + } + } +} |