为什么垂直遍历比水平遍历快，而它应该相反?

Question

所以我正在做scala并行编程课程，它挑战我们使用不同的实现来实现盒子模糊。

其中之一是按行对图像进行分块，另一种是按列对图像进行分块。图像存储为(行主顺序(：

type RGBA = Int  
/** Image is a two-dimensional matrix of pixel values. */
class Img(val width: Int, val height: Int, private val data: Array[RGBA]) {
def this(w: Int, h: Int) = this(w, h, new Array(w * h))
def apply(x: Int, y: Int): RGBA = {
data(y * width + x)
}
def update(x: Int, y: Int, c: RGBA): Unit = data(y * width + x) = c
}

这是基本模糊的实现，在所有实现中都是相同的。

def boxBlurKernel(src: Img, x: Int, y: Int, radius: Int): RGBA = {
val pixels = for {
j <- (y - radius to y + radius)
i <- (x - radius to x + radius)
if (i > 0 && i < src.width && j > 0 && j < src.height)
} yield src(i,j)
val reds = pixels.map(red)
val greens = pixels.map(green)
val blues = pixels.map(blue)
val alphas = pixels.map(alpha)
val redComponent = reds.sum / pixels.size
val greenComponent = greens.sum / pixels.size
val blueComponent = blues.sum / pixels.size
val alphaComponent = alphas.sum / pixels.size
rgba(redComponent,greenComponent,blueComponent,alphaComponent)
}

现在我们实现垂直模糊实现 -

def blur(src: Img, dst: Img, from: Int, end: Int, radius: Int): Unit = {
val imageHeight = src.height
val xCoordinates: Seq[Int] = from until end
val yCoordinates: Seq[Int] = 0 until imageHeight
for {
xCoordinate <- xCoordinates
yCoordinate <- yCoordinates
} yield dst.update(xCoordinate, yCoordinate, boxBlurKernel(src, xCoordinate, yCoordinate, radius))
}
def parBlur(src: Img, dst: Img, numTasks: Int, radius: Int): Unit = {
val imageWidth = src.width
val boundaries = linspace(0, imageWidth, numTasks + 1).map(_.toInt).toScalaVector.sliding(2)
val tasks = boundaries.toList.map { case Seq(from, end) => task {
blur(src, dst, from, end, radius)
}
}
tasks.foreach(_.join())
}

然后我们实现水平模糊

def blur(src: Img, dst: Img, from: Int, end: Int, radius: Int): Unit = {
val imageWidth = src.width
val xCoordinates = 0 until imageWidth
val yCoordinates = from until end
for {
yCoordinate <- yCoordinates
xCoordinate <- xCoordinates
} yield dst.update(xCoordinate, yCoordinate, boxBlurKernel(src, xCoordinate, yCoordinate, radius))
}
def parBlur(src: Img, dst: Img, numTasks: Int, radius: Int): Unit = {
val imageHeight = src.height
val boundaries = linspace(0, imageHeight, numTasks + 1).map(_.toInt).toScalaVector.sliding(2)
boundaries.toList.map {
case Seq(from: Int, end: Int) => task(from, end, blur(src, dst, from, end, radius))
}.foreach(_.join())
}

现在，由于图像以行主要格式存储，因此预计水平模糊会更有效地利用处理器缓存，并且应该比垂直模糊计时快一些。 但是，我发现了相反的结果。

垂直框模糊时间 -

[info] Running (fork) scalashop.VerticalBoxBlurRunner 
fork/join blur time: 2281.5884644 ms

水平框模糊时间 -

[info] Running (fork) scalashop.HorizontalBoxBlurRunner 
fork/join blur time with number of tasks = 32: 2680.8516574 ms

我正在使用scalameter和Mac OS 2.2 GHz上运行这些基准测试task并行原语返回 ForkJoinTask inturn。

Answer 1

性能取决于一系列因素，包括图像的大小、内核的大小、处理器的体系结构以及 JIT 编译器的效率。

在这种情况下，boxBlurKernel效率非常低，因为它至少使用 9 个循环，而计算可以在一次传递中完成。它还每次都修剪坐标，而不是在进入循环之前裁剪边界。

这种差异似乎不太可能是由于缓存造成的，因为如此小的一部分代码正在将新数据读入缓存。循环的数量使 JIT 编译器很难优化代码，区别可能只是它在第二种情况下生成更有效的代码。

使用多个任务会使事情复杂化，因此最好使用单个任务进行测试，以查看哪个版本实际上更有效率。之后，在担心两个不同版本的相对效率之前，先研究算法的整体效率。