Dimensioni di passaggio ottimali della matrice di dimensioni fisse in julia

Question

Voglio scrivere una funzione che accetta una matrice come input. Questa è una frequente chiamata di basso livello in un progetto complicato, quindi rendere questa funzione il più veloce possibile ha implicazioni potenzialmente serie. Poiché la velocità è così importante per me, sto utilizzando i tipi in FixedSizeArrays perché so che ciò farà risparmiare sull'utilizzo della memoria. Ma conosco spesso certe proprietà della matrice di input, e non sono certo che ne sto facendo un uso ottimale.

Ecco un semplice esempio. Immaginate che la funzione voglio fare quanto segue il più velocemente possibile:

using FixedSizeArrays 

function foo(input::Mat) 
# NB: Mat is the FixedSizeArrays matrix type 
    return 2 * input 
end 

Ovviamente questo è un esempio banale, ma non è questo il punto. Il punto è che so qualcosa sulle dimensioni della matrice input: ha sempre solo due colonne e posso sempre specificare il numero di righe in fase di esecuzione. Mi sembra un'informazione che potrebbe essere passata al compilatore per rendere più veloce il mio codice. Potrei passarlo come argomento che definisce la dimensione di input in qualche modo? Ecco un esempio che non funziona, ma dovrebbe darti un'idea di cosa sto cercando di fare.

function bar(int::N, thismat::Mat{N,2,Float64}) 
    return 2 * thismat 
end 

C'è qualcosa del genere che posso fare? Funzionerebbe anche se potessi? Forse FixedSizeArrays fa già tutto ciò che può essere fatto. Grazie per i tuoi pensieri!

Answer 1

Gli array di dimensioni fisse sono già specializzati sulle dimensioni. Questi array non sono appropriati per quando il numero di righe, N nel tuo caso, può variare. Eventuali problemi di prestazioni che si notano sono probabilmente a causa della overspecialization .

Vorrei essere un po 'più specifico.

Il compilatore Julia è in grado di ottenere un'astrazione a costo zero attraverso una specializzazione aggressiva sui tipi di argomenti. Quindi in generale (vale a dire, in tutti i casi tranne alcuni in cui la specializzazione sarebbe troppo costosa, o esplicitamente disabilitata), se una funzione viene chiamata con due diversi tipi di firme, verranno compilate due versioni di questa funzione.

Poiché la dimensione di un Mat è parte del suo tipo, ciò significa che una versione verrà compilata per ogni dimensione possibile di Mat. Quindi la specializzazione che cerchi è già fatta.

La specializzazione, tuttavia, non è gratuita. Ci sono due costi associati:

• La prima volta che viene chiamata una funzione su una particolare firma, la memoria verrà allocata e il compilatore dovrà essere eseguito.
• Quando un parametro il cui tipo non può essere dedotto viene passato a una funzione, esiste un "tipo instabilità" e la spedizione dinamica è richiesta. La spedizione dinamica implica ricerche di runtime.

Così se i vostri matrici sono di dimensioni (2, N), dove N varia e non è noto al momento della compilazione, saranno sostenuti i costi delle prestazioni di spedizione dinamica. Questo costo delle prestazioni può essere limitato utilizzando la tecnica della barriera funzionale: il costo è pari a una volta per ogni chiamata instabile, pertanto limitare il numero di tali chiamate migliora le prestazioni.

Ma ciò che aumenterebbe ancora di più le prestazioni sarebbe evitare completamente questa spedizione dinamica.È possibile costruire un tipo di matrice che codifica solo il numero di colonne nel tipo e ha il numero di righe come campo in fase di esecuzione. Cioè, è possibile che il tuo problema di prestazioni sia dovuto alla overspecialization, e devi creare i tuoi tipi per ridurre la quantità di specializzazione.

Trovare il giusto equilibrio è fondamentale per spremere il più possibile le prestazioni di un'applicazione. La specializzazione sulle dimensioni di un array è infatti utile molto raramente, anche il codice C e C++, ad esempio, tende a passare le dimensioni dell'array come parametri di runtime, invece di specializzarsi su una particolare dimensione di array. Questo non è così costoso. In altri casi no, FixedSizeArrays.jl non migliorerà le prestazioni, ma piuttosto danneggerà. Ci sono certamente situazioni in cui aiuterà, ma il tuo potrebbe non essere uno di questi.

---

Nel tuo caso, per le prestazioni massime, ho il sospetto che un tipo come questo sarebbe più veloce:

immutable TwoColumnMatrix{T, BaseType} <: AbstractArray{T, 2} 
    height::Int 
    base::BaseType 
end 

function TwoColumnMatrix(A::Matrix) 
    size(A, 2) == 2 || throw(ArgumentError("must be two columns")) 
    TwoColumnMatrix{eltype(A), typeof(A)}(size(A, 1), A) 
end 

Base.@propagate_inbounds function getindex(M::TwoColumnMatrix, n::Int) 
    M.base[n] 
end 

size(M::TwoColumnMatrix) = (M.height, 2) 

Potrebbe essere necessario definire i metodi aggiuntivi per il massimo delle prestazioni, e come sempre, punto di riferimento. È possibile che il sovraccarico del wrapper non valga la pena che il compilatore conosca le dimensioni.