这个基准测试结果的原因是什么？

Question

将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，因为入站宏）。

但我无法解释，为什么矢量化版本对于较大的图像会变得更快。这是为什么？

Answer 1

只是猜测，因为我不认识 Julia-Lang：

我认为向量化形式中的语句 gray = ... 创建了一个新数组，其中存储了所有计算值，同时废弃了旧数组。在 f1 中，值被原地覆盖，因此不需要新的内存分配。内存分配非常昂贵，因此具有就地覆盖的循环版本对于低数字更快。

但是内存分配通常是静态开销（两倍的分配并不需要两倍的时间）并且矢量化版本计算速度更快（也许是并行的？）所以如果数字足够大，计算速度就会更快比内存分配更多的差异。

Answer 2

我无法重现你的结果。

查看这个 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)

所以内存使用率下降了，但速度没有明显提高。

Answer 3

结果的答案是 Julia 中的多维数组按列优先顺序存储。参见 Julias Memory Order。

固定循环版本，关于列主顺序（交换内部和外部循环变量）：

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         |

这个基准测试结果的原因是什么？

What are the reasons for this benchmark result?

benchmarking

loops

vectorization

julia