Ottimizzazione di array C ++ 2-D

Question

Ho bisogno di un modo per rappresentare un array 2-D (una matrice densa) di doppi in C ++, con un overhead di accesso minimo assoluto.

Ho fatto qualche tempistica su varie macchine linux / unix e versioni gcc. Un vettore di vettori STL, dichiarato come:

vector<vector<double> > matrix(n,vector<double>(n));

e l'accesso tramite matrix[i][j] è tra il 5% e il 100% più lento rispetto a un array dichiarato come:

double *matrix = new double[n*n];

accessibile tramite una funzione indice incorporata matrix[index(i,j)], dove index(i,j) restituisce i + n * j. Altri modi di organizzare un array 2-D senza STL - un array di n puntatori all'inizio di ogni riga, o definire l'intera cosa nello stack come una dimensione costante matrix[n][n] - funzionano quasi esattamente alla stessa velocità dell'indice metodo di funzione.

Le recenti versioni di GCC (> 4.0) sembrano essere in grado di compilare il vettore di vettori STL con la stessa efficienza del codice non-STL quando sono attivate le ottimizzazioni, ma questo è in qualche modo macchina- dipendente.

Vorrei usare STL se possibile, ma dovrò scegliere la soluzione più veloce. Qualcuno ha esperienza nell'ottimizzazione di STL con GCC?

Answer 1

Se si utilizza GCC, il compilatore può analizzare gli accessi alla matrice e modificare l'ordine in memoria in alcuni casi. Il flag del compilatore magico è definito come:

-fipa-matrix-reorg

  

Esegue l'appiattimento della matrice e   trasposizione. Tentativi di appiattimento della matrice   per sostituire una matrice m-dimensionale con   la sua matrice n-dimensionale equivalente,   dove n < m. Questo riduce il livello di   riferimento indiretto necessario per accedere a   elementi della matrice. Il secondo   l'ottimizzazione sta trasponendo la matrice   che tenta di cambiare l'ordine di   le dimensioni della matrice per   migliorare la localizzazione della cache. Tutti e due   le ottimizzazioni necessitano di tutto il programma   bandiera. La trasposizione è abilitata solo se   le informazioni di profilazione sono disponibili.

Nota che questa opzione non è abilitata da -O2 o -O3. Devi passarlo da solo.

Answer 2

La mia ipotesi sarebbe il più veloce è, per una matrice, utilizzare l'array 1D STL e sovrascrivere l'operatore () per usarlo come matrice 2D.

Tuttavia, STL definisce anche un tipo specifico per array numerici non ridimensionabili: valarray. Hai anche varie ottimizzazioni per le operazioni sul posto.

valarray accetta come argomento un tipo numerico:

valarray<double> a;

Quindi, puoi usare slice, array indiretti, ... e, naturalmente, puoi ereditare il valarray e definire il tuo operatore () (int i, int j) per array 2D ...

Answer 3

Molto probabilmente si tratta di un problema di località di riferimento. vector utilizza new per allocare il suo array interno, quindi ogni riga sarà almeno un po 'separata nella memoria a causa dell'intestazione di ogni blocco; potrebbe essere molto distante se la memoria è già frammentata quando le allocate. È probabile che righe diverse dell'array generino almeno un errore della riga della cache e potrebbero causare un errore della pagina; se sei davvero sfortunato, due file adiacenti potrebbero trovarsi su linee di memoria che condividono uno slot TLB e accedendo a uno sfratterà l'altro.

Al contrario, le altre soluzioni garantiscono che tutti i dati siano adiacenti. Potrebbe aiutare le tue prestazioni se allinei la struttura in modo che attraversi il minor numero possibile di righe della cache.

<=> è progettato per matrici ridimensionabili . Se non è necessario ridimensionare gli array, utilizzare un normale array C ++. Le operazioni STL possono generalmente operare su array C ++.

Assicurarsi di percorrere l'array nella direzione corretta, ovvero attraverso (indirizzi di memoria consecutivi) anziché verso il basso. Ciò ridurrà i guasti della cache.

Answer 4

La mia raccomandazione sarebbe di usare Boost.UBLAS, che fornisce classi veloci di matrice / vettore.

Answer 5

Ad essere onesti dipende dagli algoritmi che stai usando sulla matrice.

Il formato con doppio nome [n * m] è molto veloce quando si accede ai dati per righe sia perché non ha quasi alcun sovraccarico oltre a una moltiplicazione e aggiunta sia perché le righe sono dati compressi che saranno coerenti nella cache.

Se i tuoi algoritmi accedono ai dati ordinati della colonna, altri layout potrebbero avere una coerenza della cache molto migliore. Se il tuo algoritmo accede ai dati nei quadranti della matrice, anche altri layout potrebbero essere migliori.

Prova a fare alcune ricerche dirette al tipo di utilizzo e agli algoritmi che stai utilizzando. Ciò è particolarmente importante se la matrice è molto grande, poiché i mancati errori nella cache possono danneggiare le tue prestazioni molto più che la necessità di 1 o 2 operazioni matematiche extra per accedere a ciascun indirizzo.

Answer 6

Potresti fare altrettanto facilmente < double > (n * m);

Answer 7

Puoi consultare la libreria di modelli Eigen C ++ su http://eigen.tuxfamily.org/. Genera codice AltiVec o sse2 per ottimizzare i calcoli vettoriale / matrice.

Answer 8

Esiste l'implementazione di uBLAS in Boost. Vale la pena dare un'occhiata.

http: //www.boost .org / doc / libs / 1_36_0 / libs / numerico / uBLAS / doc / matrix.htm

Answer 9

Un'altra libreria correlata è Blitz ++: http://www.oonumerics.org/blitz /docs/blitz.html

Blitz ++ è progettato per ottimizzare la manipolazione dell'array.

Answer 10

L'ho fatto qualche tempo fa per le immagini non elaborate dichiarando le mie classi di array bidimensionali.

In un normale array 2D, si accede a elementi come:

array [2] [3]. Ora per ottenere questo effetto, avresti un array di classi con un sovraccarico [] accessor di array. Ma ciò restituirebbe essenzialmente un altro array, dando così tu la seconda dimensione.

Il problema con questo approccio è che ha un overhead di chiamata a doppia funzione.

Il modo in cui l'ho fatto è stato usare il sovraccarico di stile ().

Quindi invece di array [2] [3], modifica L'ho fatto fare questo stile array (2,3).

Quella funzione () era molto piccola e mi sono assicurato che fosse inline.

Vedi questo link per il concetto generale di ciò: http://www.learncpp.com/cpp-tutorial / 99-sovraccarico-the-parentesi di operatore /

È possibile modellare il tipo se necessario.
La differenza che ho avuto è stata che il mio array era dinamico. Avevo un blocco di memoria char che dichiarerei. E ho impiegato una cache di colonna, quindi sapevo da dove nella mia sequenza di byte è iniziata la riga successiva. L'accesso è stato ottimizzato per l'accesso ai valori vicini, perché lo stavo usando per l'elaborazione delle immagini.

È difficile da spiegare senza il codice ma essenzialmente il risultato è stato veloce come C e molto più facile da capire e usare.