Scala collections benchmarking: foreach vs. iterator

/** ForeachIteratorShootout.scala
 *  Copyright Rex Kerr 2012; BSD 3-clause license (ask me for others)
 **/

import scala.annotation.tailrec

object ForeachIteratorShootout {
  /***** Random utility stuff *****/

  // We will fill our objects with these, in order to avoid object creations
  // And we will compute the XOR of the contents to make sure no work can be skipped
  sealed trait Bool { def flip: Bool; def ^(b: Bool): Bool }
  object Bool { def apply(i: Int) = if ((i&1)==1) T else F }
  final class True extends Bool { def flip = F; def ^(b: Bool) = b }
  final class False extends Bool { def flip = T; def ^(b: Bool) = b.flip }
  val T = new True
  val F = new False

  // Random container class
  class Box[A] {
    var value: A = _
    def apply() = value
    def update(a: A) { value = a }
  }
  object Box {
    def apply[A]() = new Box[A]
  }

  // Statistics--approximate only, ignoring all -1s (sample SD, etc.)
  case class ErrEst(center: Double, deviation: Double) {
    def variance = deviation*deviation
    def fracErr = deviation/center
    def fracErrSq = fracErr*fracErr
    def lo = center - deviation*ErrEst.ci95 // Low bound for 95% CI (2-tailed)
    def hi = center + deviation*ErrEst.ci95 // High bound for 95% CI (2-tailed)
    def +(ee: ErrEst) = ErrEst(center + ee.center, math.sqrt(variance + ee.variance))
    def -(ee: ErrEst) = ErrEst(center - ee.center, math.sqrt(variance + ee.variance))
    def *(ee: ErrEst) = ErrEst(center * ee.center, deviation*ee.center + ee.deviation*center)
    def /(ee: ErrEst) = ErrEst(center / ee.center, (center/ee.center)*math.sqrt(fracErrSq + ee.fracErrSq))
    def scale(k: Double) = ErrEst(center*k, deviation*k)
  }
  object ErrEst {
    // This is the standard error of the mean, approximately
    final val ci95 = 1.9599639845400538
    def apply(xs: Array[Double]) = {
      val n = xs.length max 1
      val sum = xs.sum
      val sumsq = xs.map(x => x*x).sum
      new ErrEst(sum/n, math.sqrt((sumsq/n - (sum/n)*(sum/n))/n))
    }
  }


  /***** Timing/benchmark utilities *****/

  // How long does something take, in seconds?
  def time[A](a: => A) = {
    var t0 = System.nanoTime
    val ans = a
    (ans , 1e-9*(System.nanoTime - t0))
  }

  // How many iterations do we need to exceed a particular target time?
  @tailrec def timeTarget[A](target: Double, n: Int = 1)(f: () => A): Int = {
    val (_, elapsed) = time{
      val a = Box[A]()
      var i = 0
      while (i<n) {
        a() = f()
        i += 1
      }
      a()
    }
    if (elapsed < target) timeTarget(target, math.ceil(n*math.sqrt(2)).toInt)(f)
    else if (elapsed > 10*target) throw new Exception("Please subdivide the work into smaller units--target time exceeded by more than ten")
    else n
  }

  var maxUID = 0
  case class Benchable(name: String, len: Int, items: Int, alg: String, op: () => Bool, reps: Int = 1, uid: Int = { maxUID += 1; maxUID-1 }) {
    def label = "%-8s %6d".format(name,len)
  }

  // Semi-robust sampling; pick 5th-25th percentile tail as most representative
  def printedBench[A](target: Double = 0.1, samplesize: Int = 100, verbose: Boolean = true)(bs: Seq[Benchable]) {
    if (samplesize/4 == 0) throw new IllegalArgumentException("Can't get statistics off of n="+samplesize)

    if (verbose) println("Warming up.")
    bs.foreach{ b => for (i <- 1 to 10) b.op() }

    if (verbose) println("Estimating needed number of iterations")
    val nbs = bs.grouped(2).flatMap{ gr =>
      val n = gr.map(b => timeTarget(target)(b.op)).max
      gr.map(b =>b.copy(reps = n))
    }.toIndexedSeq

    if (verbose) println("Creating work")
    val many = Vector.fill(samplesize)(nbs).flatten.map(b => (b,scala.util.Random.nextInt)).sortBy(_._2).map(_._1)
    val results = nbs.map(b => b -> Array.fill(samplesize)(0.0)).toMap

    if (verbose) print("Working (not in parallel!): ")
    var i = 0
    var x: Bool = F
    many.foreach{ b =>
      i += 1
      if (verbose && (i%bs.length)==0) print(".")
      val (_,t) = time {
        var i = 0
        while (i < b.reps) {
          x = x ^ b.op()
          i += 1
        }
        x
      }
      val ts = results(b)
      var j = 0
      while (ts(j)!=0.0) j += 1
      ts(j) = t/(b.items*b.reps)
    }
    println

    if (verbose) println("Computing statistics and printing results")
    val stats = results.mapValues(ar => ErrEst(ar.sorted.drop(samplesize/20).take(samplesize/4)))
    Seq(false,true).map{ showTimes =>
      stats.groupBy(_._1.label).toSeq.sortBy(_._1).map(_._2).foreach{ bees =>
        val sorted = bees.toList.sortBy(_._1.alg(1))  // Foreaches first, iterators after
        val missing = ErrEst(Double.NaN, Double.NaN)
        val byAlg = "mfr".toList.map{ c => val x = sorted.filter(_._1.alg(0)==c); if (x.length>0) x.take(2).map(_._2).toList else List(missing,missing) }
        if (byAlg.exists(!_.forall(_.lo.isNaN))) {
          if (showTimes) {
            val List(List(mf,mi), List(ff,fi), List(rf,ri)) = byAlg.map(_.map(_ scale 1e9))
            printf("T %-16s Map:%6.1f/%-6.1f  Filter:%6.1f/%-6.1f  Fold:%6.1f/%-6.1f\n",
                  sorted.head._1.label, mf.center, mi.center, ff.center, fi.center, rf.center, ri.center)
          }
          else {
            val List(mrat, frat, rrat) = byAlg.collect{ case List(fe,it) => fe/it }
            printf("R %-16s Map:%6.3f-%-6.3f  Filter:%6.3f-%-6.3f  Fold:%6.3f-%-6.3f\n",
                  sorted.head._1.label, mrat.lo, mrat.hi, frat.lo, frat.hi, rrat.lo, rrat.hi)
          }
        }
      }
    }
  }


  /***** Tests of map and filter methods using iterator vs. foreach *****/
  /*** WARNING -- serious code duplication ahead!  (Necessary for benchmarking!) ***/

  def mkRng = new scala.util.Random(42)  // This one gives true, then false as first two booleans.  Good for two-element collections.

  // Standard six methods with List
  def reverseMapListForeach[Q](xs: List[Q])(f: Q => Q) = {
    var ys = List[Q]()
    xs.foreach{x => ys = f(x) :: ys}
    ys
  }
  def reverseMapListIterator[Q](xs: List[Q])(f: Q => Q) = {
    var ys = List[Q]()
    val xi = xs.iterator
    while (xi.hasNext) { ys = f(xi.next) :: ys }
    ys
  }
  def reverseFilterListForeach[Q](xs: List[Q])(f: Q => Boolean) = {
    var ys = List[Q]()
    xs.foreach{ x => if (f(x)) ys = x :: ys }
    ys
  }
  def reverseFilterListIterator[Q](xs: List[Q])(f: Q => Boolean) = {
    var ys = List[Q]()
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) ys = x :: ys
    }
    ys
  }
  def foldListForeach[Q](xs: List[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldListIterator[Q](xs: List[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testLists(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: List[Bool] = List.fill(len){ if (rng.nextBoolean) T else F }
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("List",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = reverseMapListForeach(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = reverseMapListIterator(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="ff", op = () => { var ys = List[Bool](); var i=0; while (i<N) { ys = reverseFilterListForeach(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="fi", op = () => { var ys = List[Bool](); var i=0; while (i<N) { ys = reverseFilterListIterator(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="rf", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldListForeach(xs)(y)(_ ^ _); i += 1 }; y }) ::
    base.copy(alg="ri", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldListIterator(xs)(y)(_ ^ _); i += 1 }; y }) ::
    Nil
  }

  // Standard six methods with Vector
  def mapVectorForeach[Q](xs: Vector[Q])(f: Q => Q) = {
    var yb = Vector.newBuilder[Q]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapVectorIterator[Q](xs: Vector[Q])(f: Q => Q) = {
    var yb = Vector.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterVectorForeach[Q](xs: Vector[Q])(f: Q => Boolean) = {
    var yb = Vector.newBuilder[Q]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterVectorIterator[Q](xs: Vector[Q])(f: Q => Boolean) = {
    var yb = Vector.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldVectorForeach[Q](xs: Vector[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldVectorIterator[Q](xs: Vector[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testVectors(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: Vector[Bool] = Vector.fill(len){ if (rng.nextBoolean) T else F }
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("Vector",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapVectorForeach(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapVectorIterator(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="ff", op = () => { var ys = Vector[Bool](); var i=0; while (i<N) { ys = filterVectorForeach(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="fi", op = () => { var ys = Vector[Bool](); var i=0; while (i<N) { ys = filterVectorIterator(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="rf", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldVectorForeach(xs)(y)(_ ^ _); i += 1 }; y }) ::
    base.copy(alg="ri", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldVectorIterator(xs)(y)(_ ^ _); i += 1 }; y }) ::
    Nil
  }

  // Standard six methods with Set
  def mapSetForeach[Q](xs: Set[Q])(f: Q => Q) = {
    var yb = Set.newBuilder[Q]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapSetIterator[Q](xs: Set[Q])(f: Q => Q) = {
    var yb = Set.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterSetForeach[Q](xs: Set[Q])(f: Q => Boolean) = {
    var yb = Set.newBuilder[Q]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterSetIterator[Q](xs: Set[Q])(f: Q => Boolean) = {
    var yb = Set.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldSetForeach[Q](xs: Set[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldSetIterator[Q](xs: Set[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testSets(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: Set[Int] = List.fill(len){ rng.nextInt }.toSet
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("Set",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapSetForeach(ys)(_+1); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapSetIterator(ys)(_+1); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="ff", op = () => { var ys = Set[Int](); var i=0; while (i<N) { ys = filterSetForeach(xs)(_ >= 0); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="fi", op = () => { var ys = Set[Int](); var i=0; while (i<N) { ys = filterSetIterator(xs)(_ >= 0); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="rf", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldSetForeach(xs)(y)((a,b) => math.min(a,b)); i += 1 }; Bool(y) }) ::
    base.copy(alg="ri", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldSetIterator(xs)(y)((a,b) => math.min(a,b)); i += 1 }; Bool(y) }) ::
    Nil
  }

  // Standard six methods with Map
  def mapMapForeach[Q,Z](xs: Map[Q,Z])(f: ((Q,Z)) => (Q,Z)) = {
    var yb = Map.newBuilder[Q,Z]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapMapIterator[Q,Z](xs: Map[Q,Z])(f: ((Q,Z)) => (Q,Z)) = {
    var yb = Map.newBuilder[Q,Z]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterMapForeach[Q,Z](xs: Map[Q,Z])(f: ((Q,Z)) => Boolean) = {
    var yb = Map.newBuilder[Q,Z]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterMapIterator[Q,Z](xs: Map[Q,Z])(f: ((Q,Z)) => Boolean) = {
    var yb = Map.newBuilder[Q,Z]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldMapForeach[Q,Z,J](xs: Map[Q,Z])(zero: J)(f: (J,(Q,Z)) => J) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldMapIterator[Q,Z,J](xs: Map[Q,Z])(zero: J)(f: (J,(Q,Z)) => J) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testMaps(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: Map[Int,Int] = List.fill(len){ rng.nextInt -> rng.nextInt }.toMap
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("Map",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapMapForeach(ys)(_.swap); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapMapIterator(ys)(_.swap); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="ff", op = () => { var ys = Map[Int,Int](); var i=0; while (i<N) { ys = filterMapForeach(xs)(x => x._1 < x._2); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="fi", op = () => { var ys = Map[Int,Int](); var i=0; while (i<N) { ys = filterMapIterator(xs)(x => x._1 < x._2); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="rf", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldMapForeach(xs)(y)((a,b) => math.min(a,b._1+b._2)); i += 1 }; Bool(y) }) ::
    base.copy(alg="ri", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldMapIterator(xs)(y)((a,b) => math.min(a,b._1+b._2)); i += 1 }; Bool(y) }) ::
    Nil
  }

  // Standard six methods with Array
  def mapArrayForeach[Q: ClassManifest](xs: Array[Q])(f: Q => Q) = {
    var yb = Array.newBuilder[Q]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapArrayIterator[Q: ClassManifest](xs: Array[Q])(f: Q => Q) = {
    var yb = Array.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterArrayForeach[Q: ClassManifest](xs: Array[Q])(f: Q => Boolean) = {
    var yb = Array.newBuilder[Q]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterArrayIterator[Q: ClassManifest](xs: Array[Q])(f: Q => Boolean) = {
    var yb = Array.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldArrayForeach[Q](xs: Array[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldArrayIterator[Q](xs: Array[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testArrays(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: Array[Bool] = Array.fill(len){ if (rng.nextBoolean) T else F }
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("Array",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapArrayForeach(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapArrayIterator(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="ff", op = () => { var ys = Array[Bool](); var i=0; while (i<N) { ys = filterArrayForeach(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="fi", op = () => { var ys = Array[Bool](); var i=0; while (i<N) { ys = filterArrayIterator(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="rf", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldArrayForeach(xs)(y)(_ ^ _); i += 1 }; y }) ::
    base.copy(alg="ri", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldArrayIterator(xs)(y)(_ ^ _); i += 1 }; y }) ::
    Nil
  }

  // Standard six methods with TreeSet
  import scala.collection.immutable.TreeSet
  def mapTreeSetForeach[Q: Ordering](xs: TreeSet[Q])(f: Q => Q) = {
    var yb = TreeSet.newBuilder[Q]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapTreeSetIterator[Q: Ordering](xs: TreeSet[Q])(f: Q => Q) = {
    var yb = TreeSet.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterTreeSetForeach[Q: Ordering](xs: TreeSet[Q])(f: Q => Boolean) = {
    var yb = TreeSet.newBuilder[Q]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterTreeSetIterator[Q: Ordering](xs: TreeSet[Q])(f: Q => Boolean) = {
    var yb = TreeSet.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldTreeSetForeach[Q](xs: TreeSet[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldTreeSetIterator[Q](xs: TreeSet[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testTreeSets(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: TreeSet[Int] = TreeSet[Int]() ++ List.fill(len){ rng.nextInt }
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("TreeSet",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapTreeSetForeach(ys)(_+1); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapTreeSetIterator(ys)(_+1); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="ff", op = () => { var ys = TreeSet[Int](); var i=0; while (i<N) { ys = filterTreeSetForeach(xs)(_ >= 0); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="fi", op = () => { var ys = TreeSet[Int](); var i=0; while (i<N) { ys = filterTreeSetIterator(xs)(_ >= 0); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="rf", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldTreeSetForeach(xs)(y)((a,b) => math.min(a,b)); i += 1 }; Bool(y) }) ::
    base.copy(alg="ri", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldTreeSetIterator(xs)(y)((a,b) => math.min(a,b)); i += 1 }; Bool(y) }) ::
    Nil
  }

  // Standard six methods with mutable.HashMap
  import scala.collection.mutable.HashMap
  def mapHashMapForeach[Q,Z](xs: HashMap[Q,Z])(f: ((Q,Z)) => (Q,Z)) = {
    var yb = HashMap.newBuilder[Q,Z]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapHashMapIterator[Q,Z](xs: HashMap[Q,Z])(f: ((Q,Z)) => (Q,Z)) = {
    var yb = HashMap.newBuilder[Q,Z]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterHashMapForeach[Q,Z](xs: HashMap[Q,Z])(f: ((Q,Z)) => Boolean) = {
    var yb = HashMap.newBuilder[Q,Z]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterHashMapIterator[Q,Z](xs: HashMap[Q,Z])(f: ((Q,Z)) => Boolean) = {
    var yb = HashMap.newBuilder[Q,Z]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldHashMapForeach[Q,Z,J](xs: HashMap[Q,Z])(zero: J)(f: (J,(Q,Z)) => J) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldHashMapIterator[Q,Z,J](xs: HashMap[Q,Z])(zero: J)(f: (J,(Q,Z)) => J) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testHashMaps(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: HashMap[Int,Int] = HashMap[Int,Int]() ++ List.fill(len){ rng.nextInt -> rng.nextInt }
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("mHashMap",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapHashMapForeach(ys)(_.swap); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapHashMapIterator(ys)(_.swap); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="ff", op = () => { var ys = HashMap[Int,Int](); var i=0; while (i<N) { ys = filterHashMapForeach(xs)(x => x._1 < x._2); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="fi", op = () => { var ys = HashMap[Int,Int](); var i=0; while (i<N) { ys = filterHashMapIterator(xs)(x => x._1 < x._2); i += 1 }; Bool(ys.head._1 ^ ys.head._2) }) ::
    base.copy(alg="rf", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldHashMapForeach(xs)(y)((a,b) => math.min(a,b._1+b._2)); i += 1 }; Bool(y) }) ::
    base.copy(alg="ri", op = () => { var y: Int = Int.MaxValue; var i=0; while (i<N) { y = foldHashMapIterator(xs)(y)((a,b) => math.min(a,b._1+b._2)); i += 1 }; Bool(y) }) ::
    Nil
  }

  // Standard six methods with ArrayBuffer
  import scala.collection.mutable.{ArrayBuffer => ArrayBuf}
  def mapArrayBufForeach[Q](xs: ArrayBuf[Q])(f: Q => Q) = {
    var yb = ArrayBuf.newBuilder[Q]
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapArrayBufIterator[Q](xs: ArrayBuf[Q])(f: Q => Q) = {
    var yb = ArrayBuf.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterArrayBufForeach[Q](xs: ArrayBuf[Q])(f: Q => Boolean) = {
    var yb = ArrayBuf.newBuilder[Q]
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterArrayBufIterator[Q](xs: ArrayBuf[Q])(f: Q => Boolean) = {
    var yb = ArrayBuf.newBuilder[Q]
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldArrayBufForeach[Q](xs: ArrayBuf[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldArrayBufIterator[Q](xs: ArrayBuf[Q])(zero: Q)(f: (Q,Q) => Q) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testArrayBufs(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: ArrayBuf[Bool] = ArrayBuf.fill(len){ if (rng.nextBoolean) T else F }
    val N = (if (len/1000 >= 10) 1 else if (len/1000 > 1) 10 else if (len/100 > 1) 100 else 1000)
    val base = Benchable("ArrayBuf",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapArrayBufForeach(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="mi", op = () => { var ys = xs; var i=0; while (i<N) { ys = mapArrayBufIterator(ys)(_.flip); i += 1 }; ys.head }) ::
    base.copy(alg="ff", op = () => { var ys = ArrayBuf[Bool](); var i=0; while (i<N) { ys = filterArrayBufForeach(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="fi", op = () => { var ys = ArrayBuf[Bool](); var i=0; while (i<N) { ys = filterArrayBufIterator(xs)(_ eq F); i += 1 }; ys.head }) ::
    base.copy(alg="rf", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldArrayBufForeach(xs)(y)(_ ^ _); i += 1 }; y }) ::
    base.copy(alg="ri", op = () => { var y: Bool = F; var i=0; while (i<N) { y = foldArrayBufIterator(xs)(y)(_ ^ _); i += 1 }; y }) ::
    Nil
  }

  // Standard six methods with Range
  def mapRangeForeach(xs: Range)(f: Int => Int) = {
    var yb = ArrayBuf[Int]()
    xs.foreach{x => yb += f(x) }
    yb.result
  }
  def mapRangeIterator(xs: Range)(f: Int => Int) = {
    var yb = ArrayBuf[Int]()
    val xi = xs.iterator
    while (xi.hasNext) { yb += f(xi.next) }
    yb.result
  }
  def filterRangeForeach(xs: Range)(f: Int => Boolean) = {
    var yb = ArrayBuf[Int]()
    xs.foreach{ x => if (f(x)) yb += x }
    yb.result
  }
  def filterRangeIterator(xs: Range)(f: Int => Boolean) = {
    var yb = ArrayBuf[Int]()
    val xi = xs.iterator
    while (xi.hasNext) {
      val x = xi.next
      if (f(x)) yb += x
    }
    yb.result
  }
  def foldRangeForeach(xs: Range)(zero: Int)(f: (Int,Int) => Int) = {
    var i = zero
    xs.foreach{ x => i = f(i,x) }
    i
  }
  def foldRangeIterator(xs: Range)(zero: Int)(f: (Int,Int) => Int) = {
    var i = zero
    var xi = xs.iterator
    while (xi.hasNext) { i = f(i,xi.next) }
    i
  }
  def testRanges(len: Int): List[Benchable] = {
    val rng = mkRng
    val xs: Range = Range(0,len)
    val N = (if (len/1000 >= 100) 1 else if (len/1000 > 10) 10 else if (len/1000 > 1) 100 else if (len/100>1) 1000 else 10000)
    val base = Benchable("Range",len,len*N,"",()=>T)

    base.copy(alg="mf", op = () => { var ys = ArrayBuf[Int](); var i=0; while (i<N) { ys = mapRangeForeach(xs)(_+1); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="mi", op = () => { var ys = ArrayBuf[Int](); var i=0; while (i<N) { ys = mapRangeIterator(xs)(_+1); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="ff", op = () => { var ys = ArrayBuf[Int](); var i=0; while (i<N) { ys = filterRangeForeach(xs)(_ >= 0); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="fi", op = () => { var ys = ArrayBuf[Int](); var i=0; while (i<N) { ys = filterRangeIterator(xs)(_ >= 0); i += 1 }; Bool(ys.head) }) ::
    base.copy(alg="rf", op = () => { var y = 0; var i=0; while (i<N) { y = foldRangeForeach(xs)(y)((a,b) => a + b); i += 1 }; Bool(y) }) ::
    base.copy(alg="ri", op = () => { var y = 0; var i=0; while (i<N) { y = foldRangeIterator(xs)(y)((a,b) => a + b); i += 1 }; Bool(y) }) ::
    Nil
  }


  /***** Main *****/

  val availableCollections = Array("List","Vector","Set","Array","TreeSet","Map","mHashMap","ArrayBuf","Range")
  val defaultSizes = Seq(2,50,1250,31250)

  // Run this in the REPL to run the collections and sizes one at a time.
  // Put a link in the current directory to the Scala version you want to use.
  def scriptMe = {
    for (cc <- availableCollections.sorted; sz <- defaultSizes.sorted) println("./scala -J-Xmx6G ForeachIteratorShootout -quiet -collections="+cc+" -n="+sz)
  }

  def main(args: Array[String]) { for (i <- 1 to 2) {
    val isQuiet = args.contains("-quiet")
    val numbers = args.find(_.startsWith("-n=")).map(_.drop(3).split(",").map(_.toInt).toSeq).getOrElse(defaultSizes)
    val algs = args.find(_.startsWith("-alg=")).map(_.drop(5)).getOrElse("mfr").map(_.toString).toSet
    val colls = args.find(_.startsWith("-collections=")).map(_.drop(13).split(",")).getOrElse(availableCollections).toSet
    printedBench(0.05, 40, !isQuiet){
      numbers.flatMap(n => testLists(n) ++ testVectors(n) ++ testSets(n) ++ testArrays(n) ++ testTreeSets(n) ++ testMaps(n) ++ testHashMaps(n) ++ testArrayBufs(n) ++ testRanges(n)).
      filter(colls contains _.name).filter(algs contains _.alg.take(1))
    }
  }}
}