Почему вертикальный обход быстрее горизонтального, если он должен быть противоположным?

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
  }

Это реализация базового размытия 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 и на Ma c OS 2,2 ГГц Параллельный примитив task возвращает возвращение ForkJoinTask.

Answer 1

Производительность будет зависеть от ряда факторов, включая размер изображения, размер ядра, архитектуру процессора и эффективность компилятора JIT.

В этом случае boxBlurKernel очень неэффективно, поскольку использует не менее 9 циклов, когда вычисления могут быть выполнены за один проход. Он также обрезает координаты каждый раз, а не обрезает границы перед вводом l oop.

. Кажется маловероятным, что различие связано с кэшированием, поскольку такая небольшая часть кода считывает новые данные в кеш. Количество циклов делает JIT-компилятор очень трудным для оптимизации кода, и разница может просто заключаться в том, что он генерирует более эффективный код во втором случае.

Использование нескольких задач усложняет ситуацию, поэтому было бы лучше проверить одну задачу, чтобы увидеть, какая версия на самом деле более эффективна. После этого поработайте над общей эффективностью алгоритма, прежде чем беспокоиться об относительной эффективности двух разных версий.