Scala：有没有办法提高这个卷积码的时序性能？

Question

大家好。我一直在尝试改善这段代码在 Scala 中的执行时间：

def TwoDimensionalConvolution(Input: => Array[Int], Height: => Int, Width: => Int, Kernel: => Array[Int]): Array[Int] = {
  val R = (Kernel.length - 1) >> 1

  val result = Array.ofDim[Int](Input.length)
  for (i <- 0 until Height) {
    for (j <- 0 until Width) {
      var acc = 0
      for (k <- j - R to j + R)
        if (k >= 0 && k < Width)
          acc += Input(i * Width + k) * Kernel(k + R - j)
      result(j * Height + i) = acc >> 8
    }
  }

  val Output = Array.ofDim[Int](Input.length)
  for (i <- 0 until Width) {
    for (j <- 0 until Height) {
      var acc = 0
      for (k <- j - R to j + R)
        if (k >= 0 && k < Height)
          acc += result(i * Height + k) * Kernel(k + R - j)
      Output(j * Width + i) = acc >> 8
    }
  }
  Output
}

我的代码使用行和列的线性卷积执行二维卷积。请注意，输入数组不是二维的，但访问它的方式是线性的。 k 的 for 循环允许您在每一行或每一列上进行迭代，而无需在边缘上进行零填充。

我也尽量避免存储中间结果，但如您所见，保存卷积行的 result 变量是执行列卷积所必需的。

我不认为自己是 Scala 专家，虽然我在 C/C++ 方面有一些经验，但我无法进一步改进计时。

事实是，我想不出我还能用我所掌握的少量函数式编程知识做些什么。

Scala 专家可以给我一些建议吗？在此先感谢大家的阅读。

Answer 1

一定要从删除别名参数开始 (: => ...)。它们成为函数，在方法中的每次使用时都会对其进行评估，即使您只是将变量和文字传递给方法调用，仍然会有不小的开销。

尝试用 while 替换 for 循环。这将产生多少影响将取决于 Scala 版本以及您是否将优化标志传递给编译器。参见例如http://dynamicsofprogramming.blogspot.com/2017/01/performance-of-scala-for-loops.html 用于比较，包括 Scala 2.12。

您在衡量性能时也需要小心：使用Scalameter or JMH。

Answer 2

我建议的一个优化是用 k 优化循环。你有：

for (k <- j - R to j + R)
    if (k >= 0 && k < Height)
      acc += result(i * Height + k) * Kernel(k + R - j)

但是，如果 k is < 0 || k >= Height，则循环不执行任何操作并且您在进行不必要的迭代。

也许更改为：

for (k <- (j - R max 0) to (j + R min Height - 1))
     acc += result(i * Height + k) * Kernel(k + R - j)

这消除了 if 语句并确保不会消耗额外的迭代。

Scala：有没有办法提高这个卷积码的时序性能？

Scala: Is there a way to improve the timing performance of this convolution code?

performance

scala

timing

convolution