Каковы причины этого эталонного результата?

Две функции, которые преобразуют изображение rgb в изображение с серой шкалой:

function rgb2gray_loop{T<:FloatingPoint}(A::Array{T,3})
  r,c = size(A)
  gray = similar(A,r,c)
  for i = 1:r
    for j = 1:c
      @inbounds gray[i,j] = 0.299*A[i,j,1] + 0.587*A[i,j,2] + 0.114 *A[i,j,3]
    end
  end
  return gray
end

function rgb2gray_vec{T<:FloatingPoint}(A::Array{T,3})
  gray = similar(A,size(A)[1:2]...)
  gray = 0.299*A[:,:,1] + 0.587*A[:,:,2] + 0.114 *A[:,:,3]
  return gray
end

Первый использует циклы, а второй - векторизация.

При сравнительном тестировании (с пакетом Benchmark) я получаю следующие результаты для входных изображений различного размера (f1 - версия цикла, f2 векторная версия):

A = rand(50,50,3):

| Row | Function | Average     | Relative | Replications |
|-----|----------|-------------|----------|--------------|
| 1   | "f1"     | 3.23746e-5  | 1.0      | 1000         |
| 2   | "f2"     | 0.000160214 | 4.94875  | 1000         |

A = rand(500,500,3):

| Row | Function | Average    | Relative | Replications |
|-----|----------|------------|----------|--------------|
| 1   | "f1"     | 0.00783007 | 1.0      | 100          |
| 2   | "f2"     | 0.0153099  | 1.95527  | 100          |

A = rand(5000,5000,3):

| Row | Function | Average  | Relative | Replications |
|-----|----------|----------|----------|--------------|
| 1   | "f1"     | 1.60534  | 2.56553  | 10           |
| 2   | "f2"     | 0.625734 | 1.0      | 10           |

Я ожидал, что одна функция будет быстрее другой (возможно, f1 из-за макроса inbounds).

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

Ответ 1

Ответ на результаты заключается в том, что многомерные массивы в Julia хранятся в порядке столбцов. См. Заказ памяти Юлиаса.

Фиксированная петлевая версия, относящаяся к столбцу-главному порядку (внутренние и внешние переменные цикла заменены):

function rgb2gray_loop{T<:FloatingPoint}(A::Array{T,3})
  r,c = size(A)
  gray = similar(A,r,c)
  for j = 1:c
    for i = 1:r
      @inbounds gray[i,j] = 0.299*A[i,j,1] + 0.587*A[i,j,2] + 0.114 *A[i,j,3]
    end
  end
  return gray
end

Новые результаты для A = rand(5000,5000,3):

| Row | Function | Average  | Relative | Replications |
|-----|----------|----------|----------|--------------|
| 1   | "f1"     | 0.107275 | 1.0      | 10           |
| 2   | "f2"     | 0.646872 | 6.03004  | 10           |

И результаты для меньших массивов:

A = rand(500,500,3):

| Row | Function | Average    | Relative | Replications |
|-----|----------|------------|----------|--------------|
| 1   | "f1"     | 0.00236405 | 1.0      | 100          |
| 2   | "f2"     | 0.0207249  | 8.76671  | 100          |

A = rand(50,50,3):

| Row | Function | Average     | Relative | Replications |
|-----|----------|-------------|----------|--------------|
| 1   | "f1"     | 4.29321e-5  | 1.0      | 1000         |
| 2   | "f2"     | 0.000224518 | 5.22961  | 1000         |

Ответ 2

Просто размышление, потому что я не знаю Джулиа-Ланга:

Я думаю, что выражение gray = ... в векторизованной форме создает новый массив, в котором хранятся все вычисленные значения, а старый массив обрывается. В f1 значения перезаписываются на месте, поэтому не требуется новое распределение памяти. Распределение памяти довольно дорого, поэтому версия цикла с перезаписью на месте быстрее для низких чисел.

Но распределение памяти обычно является статическим накладным (распределение в два раза больше, чем в два раза больше), а векторизованная версия вычисляется быстрее (возможно, параллельно?), поэтому, если числа становятся достаточно большими, более быстрый расчет делает большую разницу чем выделение памяти.

Ответ 3

Я не могу воспроизвести ваши результаты.

Смотрите этот блокнот IJulia: http://nbviewer.ipython.org/urls/gist.githubusercontent.com/anonymous/24c17478ae0f5562c449/raw/8d5d32c13209a6443c6d72b31e2459d70607d21b/rgb2gray.ipynb

Я получаю следующие цифры:

In [5]:

@time rgb2gray_loop(rand(50,50,3));
@time rgb2gray_vec(rand(50,50,3));

elapsed time: 7.591e-5 seconds (80344 bytes allocated)
elapsed time: 0.000108785 seconds (241192 bytes allocated)

In [6]:

@time rgb2gray_loop(rand(500,500,3));
@time rgb2gray_vec(rand(500,500,3));

elapsed time: 0.021647914 seconds (8000344 bytes allocated)
elapsed time: 0.012364489 seconds (24001192 bytes allocated)

In [7]:

@time rgb2gray_loop(rand(5000,5000,3));
@time rgb2gray_vec(rand(5000,5000,3));

elapsed time: 0.902367223 seconds (800000440 bytes allocated)
elapsed time: 1.237281103 seconds (2400001592 bytes allocated, 7.61% gc time)

Как и ожидалось, зацикленная версия быстрее для больших входов. Также обратите внимание, как в векторной версии выделено в три раза больше памяти.

Я также хочу указать, что утверждение gray = similar(A,size(A)[1:2]...) является избыточным и может быть опущено. Без этого ненужного выделения результаты для самой большой проблемы:

@time rgb2gray_loop(rand(5000,5000,3));
@time rgb2gray_vec(rand(5000,5000,3));

elapsed time: 0.953746863 seconds (800000488 bytes allocated, 3.06% gc time)
elapsed time: 1.203013639 seconds (2200001200 bytes allocated, 7.28% gc time)

Таким образом, использование памяти снизилось, но скорость не заметно улучшилась.