Lý do cho kết quả điểm chuẩn này là gì?

Question

Hai chức năng chuyển đổi một hình ảnh rgb đến một hình ảnh thang xám:

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 

Và:

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 

là Người đầu tiên sử dụng các vòng lặp, trong khi cái thứ hai sử dụng vector hóa.

Khi benchmarking họ (với gói Benchmark) tôi nhận được kết quả như sau cho hình ảnh đầu vào có kích thước khác nhau (f1 là phiên bản lặp, f2 phiên bản vectorized):

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   | 

Tôi mong đợi một hàm sẽ nhanh hơn hàm kia (có thể là f1 vì macro cận cảnh).

Nhưng tôi không thể giải thích, tại sao phiên bản vectơ trở nên nhanh hơn cho hình ảnh lớn hơn. Tại sao vậy?

Answer 1

Câu trả lời cho kết quả là các mảng đa chiều trong Julia được lưu trữ theo thứ tự cột lớn.Xem Julias Memory Order.

cố định phiên bản lặp, liên quan đến cột lớn theo đơn đặt hàng (biến vòng lặp bên trong và bên ngoài hoán đổi):

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 

Kết quả mới cho A = rand(5000,5000,3):

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

Và kết quả cho mảng nhỏ:

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   | 

Answer 2

Chỉ cần suy đoán bởi vì tôi không biết Julia-Lang:

Tôi nghĩ rằng tuyên bố gray = ... theo hình thức vectorized tạo ra một mảng mới, nơi tất cả các giá trị tính toán được lưu trữ, trong khi mảng cũ được loại bỏ. Trong f1 các giá trị được ghi đè tại chỗ, do đó không cần phân bổ bộ nhớ mới. Phân bổ bộ nhớ khá tốn kém nên phiên bản vòng lặp với ghi đè tại chỗ nhanh hơn cho số thấp.

Nhưng phân bổ bộ nhớ thường là chi phí tĩnh (phân bổ gấp đôi không mất nhiều gấp đôi) và phiên bản vectơ được tính toán nhanh hơn (có thể song song?) Nên nếu các con số đủ lớn thì phép tính nhanh hơn khác với phân bổ bộ nhớ.

Answer 3

Tôi không thể tạo lại kết quả của bạn.

Xem máy tính xách tay này IJulia: http://nbviewer.ipython.org/urls/gist.githubusercontent.com/anonymous/24c17478ae0f5562c449/raw/8d5d32c13209a6443c6d72b31e2459d70607d21b/rgb2gray.ipynb

Các số liệu mà tôi có được là:

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.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) 

Đúng như dự đoán, phiên bản lặp là nhanh hơn vì những đóng góp lớn. Cũng lưu ý cách phiên bản vectơ phân bổ ba lần bộ nhớ nhiều.

Tôi cũng muốn chỉ ra rằng tuyên bố gray = similar(A,size(A)[1:2]...) là không cần thiết và có thể bỏ qua. Nếu không phân bổ không cần thiết này, các kết quả cho các vấn đề lớn nhất là:

@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) 

Vì vậy, việc sử dụng bộ nhớ đã đi xuống, nhưng tốc độ không cải thiện rõ rệt.