Quali sono i motivi di questo risultato di riferimento?

Question

due funzioni che convertono un'immagine rgb un'immagine scala di grigio:

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 

E:

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 

Il primo utilizza cicli, mentre la seconda utilizza vettorizzazione.

Quando li analisi comparativa (con il pacchetto Benchmark) I ottenere i seguenti risultati per le immagini in ingresso di dimensioni diverse (f1 è la versione ad anello, f2 la versione vettorializzare):

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   | 

Mi aspettavo che una funzione fosse più veloce dell'altra (forse f1 a causa della macro inbundi).

Ma non posso spiegare, perché la versione vettoriale diventa più veloce per le immagini più grandi. Perché è quello?

Answer 1

La risposta per i risultati è che gli array multidimensionali in Julia sono memorizzati in ordine di colonna principale.Vedi Julias Memory Order.

fissa Esecuzione in loop, per quanto riguarda column-major-ordine (variabili anello interno ed esterno scambiati):

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 

Nuovi risultati per A = rand(5000,5000,3):

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

ed i risultati per le matrici più piccole:

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

solo speculazione, perché non so Julia-Lang:

Penso che la dichiarazione gray = ... sotto forma vettorizzati crea un nuovo array in cui sono memorizzati tutti i valori calcolati, mentre la vecchia matrice è scartata. In f1 i valori vengono sovrascritti sul posto, quindi non è necessaria alcuna nuova allocazione di memoria. L'allocazione della memoria è piuttosto costosa quindi la versione loop con sovrascritture sul posto è più veloce per i numeri bassi.

Tuttavia, l'allocazione di memoria è in genere un sovraccarico statico (l'allocazione due volte tanto non richiede il doppio del tempo) e la versione vettoriale è più veloce (forse in parallelo?) Quindi se i numeri diventano abbastanza grandi il calcolo più veloce rende più differenza rispetto all'allocazione di memoria.

Answer 3

Non riesco a riprodurre i risultati.

Vedi questo notebook IJulia: http://nbviewer.ipython.org/urls/gist.githubusercontent.com/anonymous/24c17478ae0f5562c449/raw/8d5d32c13209a6443c6d72b31e2459d70607d21b/rgb2gray.ipynb

I numeri che ricevo sono:

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) 

Come previsto, la versione ad anello è più veloce per i grandi ingressi. Si noti inoltre come la versione vettoriale abbia assegnato tre volte più memoria.

Vorrei anche sottolineare che la dichiarazione gray = similar(A,size(A)[1:2]...) è ridondante e può essere omessa. Senza questa allocazione inutili, i risultati per il più grande problema sono:

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

Quindi l'utilizzo della memoria è andato giù, ma la velocità non ha notevolmente migliorare.