Was sind die Gründe für dieses Benchmark-Ergebnis?

Question

Zwei Funktionen, die ein RGB-Bild in ein Graustufenbild umwandeln:

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 

Und:

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 

Die erste Loops ist, während die zweite Vektorisierung verwendet.

Wenn sie Benchmarking (mit dem Benchmark-Paket) Ich erhalte die folgenden Ergebnisse für unterschiedlich große Eingangsbilder (f1 ist die Schleife Version, f2 die vektorisierte Version):

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   | 

:

Ich erwartete eine Funktion schneller als die andere (vielleicht f1 wegen der inbounds Makro).

Aber ich kann nicht erklären, warum die vektorisierte Version für größere Bilder schneller wird. Warum ist das?

Answer 1

Die Antwort für die Ergebnisse ist, dass mehrdimensionale Arrays in Julia in der Reihenfolge der Reihenfolge der Spalten gespeichert werden.Siehe Julias Memory Order.

geschlungenen Version behoben, in Bezug auf Spalte-major-Ordnung (innere und äußere Schleife Variablen vertauscht):

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 

Neue Ergebnisse für A = rand(5000,5000,3):

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

Und die Ergebnisse für kleinere Arrays:

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

nur Spekulation, weil ich nicht Julia-Lang wissen:

Ich denke, die Aussage gray = ... in der vektorisierten Form ein neues Array erstellt, in der alle berechneten Werte gespeichert werden, während das alte Array verschrottet wird. In f1 werden die Werte an Ort und Stelle überschrieben, sodass keine neue Speicherzuweisung erforderlich ist. Die Speicherzuweisung ist ziemlich teuer, so dass die Loop-Version mit In-Place-Überschreibungen für niedrige Zahlen schneller ist.

Aber Speicherzuweisung ist in der Regel ein statischer Overhead (Zuweisung doppelt so viel dauert nicht doppelt so lange) und die vektorisierte Version ist schneller (vielleicht parallel?), Also, wenn die Zahlen groß genug sind, macht die schnellere Berechnung mehr Unterschied als die Speicherzuweisung.

Answer 3

Ich kann Ihre Ergebnisse nicht reproduzieren.

dieses IJulia Notebook Siehe: http://nbviewer.ipython.org/urls/gist.githubusercontent.com/anonymous/24c17478ae0f5562c449/raw/8d5d32c13209a6443c6d72b31e2459d70607d21b/rgb2gray.ipynb

Die Zahlen, die wir bekommen sind:

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) 

Wie erwartet, die geschlungenen Version ist für große Eingänge schneller. Beachten Sie auch, dass die vektorisierte Version dreimal soviel Speicher zugewiesen hat.

Ich möchte auch darauf hinweisen, dass die Aussage gray = similar(A,size(A)[1:2]...) redundant ist und entfallen kann. Ohne diese unnötige Zuweisung, die Ergebnisse für das größte Problem sind:

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

So die Speicherauslastung ging, aber die Geschwindigkeit verbessert nicht spürbar ist.