scala - 如何使用范围编写高效的嵌套循环

Question

作为一个 scala 新手，我尝试编写一个在一些二维数据上运行的方法。此方法被多次调用，因此性能很重要。

首先我用理解编码它

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

然后使用while循环：

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
}

我很惊讶范围理解的运行速度有多慢，所以我编写了一个 ScalaMeter 基准测试：

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")
  }
}

结果：

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

此外，对于详细输出，会为 for comprehension 版本报告多个 GC。

我意识到对于每个 x，都会创建新的 Range，这解释了迟缓，

有没有办法修改 for-comprehension 版本以更快地运行（与 while 循环相当）？

// 编辑：我试图对 for 理解进行脱糖：

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

然后拉起yRange：

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

它报告了大约 287 毫秒的运行时间 - 比以前好得多，但仍不能令人满意

标签： scalaperformance

Answer 1

在我相当简单的示例中，我设法用我自己的 Range2D 类解决了这个问题：

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
    }
  }
}

和

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

在我的机器上，它比原始循环慢大约 10 倍，这对我的初始代码来说是一个很好的改进。

编辑

我试着Function1[(Int, Int), Unit]改成Function2[Int, Int, Unit]

• 我不能在理解中使用 Range2D（我收到missing parameter type错误）。
• 我可以使用 foreach：new Range2D(xEnd, yEnd).foreach((_, _) => sum += 1)
• 我的机器上差别不大
• 生成的代码确实看起来更好 - 没有Tuple2创建：

原文Range2D（反编译成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;
}

修改Range2D（反编译成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;
}