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

Question

Good day to everyone. I have been trying to improve the execution time of this code in 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
}

My code performs a two-dimensional convolution using the linear convolution of the rows and columns. Note that the input array is not two-dimensional, but the way to access it is linearly. The for loop of k allows you to iterate on each row or column without having to zero pad on edges.

I have also tried to avoid storing intermediate results as much as possible, but as you can see, the result variable, which saves the convolved rows, is necessary to perform the convolution of the columns.

I do not consider myself an expert in Scala and although I have some experience in C/C++, I can not improve the timing even more.

The truth is that I can not think of what else I could do with the few knowledge of functional programming I have.

Some Scala expert could suggest something to me? Thanks in advance to everyone for reading.

Answer 1

One optimization I would suggest would be to optimize the loop with k. You have:

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

However, if k is < 0 || k >= Height, the loop does nothing and you are iterating needlessly.

Perhaps changing to:

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

This eliminates that if statement and ensures no extra iterations are consumed.