Howto write efficient nested loop using ranges

Question

As a scala newbie, I tried to write a method running over some 2-dimentional data. This method is called multiple times, so performance matters.

First I coded it with for comprehension

private def sumWithRange(xEnd: Int, yEnd: Int) = {
  var sum = 0
  for {
    x <- 0 until xEnd
    y <- 0 until yEnd
  } sum += 1
  sum
}

And then with while loop:

private def sumWithWhileLoop(xEnd: Int, yEnd: Int) = {
  var sum = 0
  var x = 0
  while (x < xEnd) {
    var y = 0
    while (y < yEnd) {
      sum += 1
      y += 1
    }
    x += 1
  }
  sum
}

I was surprised how slowly the range-comprehension runs, so I wrote a ScalaMeter benchmark:

object TestDoubleLoopPerformance {
  val standardConfig = config(
    Key.exec.minWarmupRuns -> 5,
    Key.exec.maxWarmupRuns -> 10,
    Key.exec.benchRuns -> 10,
    // Key.verbose -> true
  ) withWarmer(new Warmer.Default)


  def main(args: Array[String]): Unit = {
    val whileLoopTime = standardConfig measure {
      for (iter <- 0 to 1000) {
        sumWithWhileLoop(1000, 2000)
      }
    }
    println(s"while loop time: $whileLoopTime")

    val rangeLoopTime = standardConfig measure {
      for (iter <- 0 to 1000) {
        sumWithRange(1000, 2000)
      }
    }
    println(s"range loop time: $rangeLoopTime")
  }
}

The results:

while loop time: 0.3065984 ms
range loop time: 2585.5892847 ms

In addition, with verbose output, multiple GCs are reported for the for comprehension version.

I realize that for each x, new Range is created, which explains the sluggishness,

Is there a way to modify the for-comprehension version to run faster (on par with the while loop)?

// EDIT: I tried to desugar the for comprehension:

var sum = 0
(0 until xEnd).foreach(x => {
  val yRange = 0 until yEnd
  yRange.foreach(y => sum += 1)
})

and then pull up the yRange:

var sum = 0
val yRange = 0 until yEnd
(0 until xEnd).foreach(x => {
  yRange.foreach(y => sum += 1)
})

It reports running time of circa 287ms - much better than before, but still not satisfactory

user_1570854 · Answer

In my, rather simplistic example, I managed to get around the problem with my own Range2D class:

class Range2D(a0: Int, a1: Int) {
  def foreach(f: ((Int, Int)) => Unit): Unit = {
    var i0 = 0
    while (i0 < a0) {
      var i1 = 0
      while (i1 < a1) {
        f(i0, i1)
        i1 += 1
      }
      i0 += 1
    }
  }
}

and

private def sumWithRange(xEnd: Int, yEnd: Int) = {
  var sum = 0
  for {
    xy <- new Range2D(xEnd, yEnd)
  } sum += 1
  sum
}

On my machine, it is circa 10X slower than a raw loop, which is a good improvement over my initial code.

Edit

I tried changing Function1[(Int, Int), Unit] to Function2[Int, Int, Unit]

I cannot use Range2D in for comprehension (I get missing parameter type error).
I can use foreach: new Range2D(xEnd, yEnd).foreach((_, _) => sum += 1)
there is little difference on my machine
generated code indeed looks better - no Tuple2 are created:

Original Range2D (decompiled to java)

private int sumWithRange(final int xEnd, final int yEnd) {
    IntRef sum = IntRef.create(0);
    (new Range2D(xEnd, yEnd)).foreach((xy) -> {
        $anonfun$sumWithRange$1(sum, xy);
        return BoxedUnit.UNIT;
    });
    return sum.elem;
}

Modified Range2D (decompiled to java)

private int sumWithRange(final int xEnd, final int yEnd) {
    IntRef sum = IntRef.create(0);
    (new Range2D(xEnd, yEnd)).foreach((x$1, x$2) -> {
        ++sum.elem;
    });
    return sum.elem;
}

Howto write efficient nested loop using ranges

1 Answers