Perché la moltiplicazione C++ con array dinamico funziona meglio di std :: vector versione

Question

Sto implementando la moltiplicazione C++ per matrici con diverse strutture dati e tecniche (vettori, matrici e OpenMP) e ho trovato una strana situazione ... La mia dinamica versione matrice è lavorare meglio:

volte:

OpenMP mult_1: tempo: 5,882 mila s

matrice mult_2: tempo: 1,478 mila s

mie flag di compilazione sono:

/usr/bin/g ++ -fopenmp -pthread -std = C++ 1A -O3

versione C++ vettore

typedef std::vector<std::vector<float>> matrix_f; 
void mult_1 (const matrix_f & matrixOne, const matrix_f & matrixTwo, matrix_f & result) { 
    const int matrixSize = (int)result.size(); 
    #pragma omp parallel for simd 
    for (int rowResult = 0; rowResult < matrixSize; ++rowResult) { 
     for (int colResult = 0; colResult < matrixSize; ++colResult) { 
      for (int k = 0; k < matrixSize; ++k) { 
       result[rowResult][colResult] += matrixOne[rowResult][k] * matrixTwo[k][colResult]; 
      } 
     } 
    } 
} 

Versione array dinamico

void mult_2 (float * matrixOne, float * matrixTwo, float * result, int size) { 
    for (int row = 0; row < size; ++row) { 
     for (int col = 0; col < size; ++col) { 
      for (int k = 0; k < size; ++k) { 
       (*(result+(size*row)+col)) += (*(matrixOne+(size*row)+k)) * (*(matrixTwo+(size*k)+col)); 
      } 
     } 
    } 
} 

prove:

C++ versione vettore

utils::ChronoTimer timer; 
/* set Up simple matrix */ 
utils::matrix::matrix_f matr1 = std::vector<std::vector<float>>(size,std::vector<float>(size)); 
fillRandomMatrix(matr1); 

utils::matrix::matrix_f matr2 = std::vector<std::vector<float>>(size,std::vector<float>(size)); 
fillRandomMatrix(matr2); 

utils::matrix::matrix_f result = std::vector<std::vector<float>>(size,std::vector<float>(size));  
timer.init(); 
utils::matrix::mult_1(matr1,matr2,result); 
std::printf("openmp mult_1: time: %f ms\n",timer.now()/1000); 

array dinamico versione

utils::ChronoTimer timer; 

float *p_matr1 = new float[size*size]; 
float *p_matr2 = new float[size*size]; 
float *p_result = new float[size*size]; 

fillRandomMatrixArray(p_matr1,size); 
fillRandomMatrixArray(p_matr2,size); 

timer.init(); 
utils::matrix::mult_2(p_matr1,p_matr2,p_result,size); 
std::printf("array mult_2: time: %f ms\n",timer.now()/1000); 

delete [] p_matr1; 
delete [] p_matr2; 
delete [] p_result; 

stavo controllando alcuni post precedenti, ma non riuscivo a trovare tutte le relative attività con il mio problema link, link2, link3:

UPDATE: Ho refactorized test con le risposte, e VectorWorks leggermente migliore:

vettore mult: tempo: 1,194 mila s

serie mult_2: tempo: 1,202 mila s

versione vettoriale C++

void mult (const std::vector<float> & matrixOne, const std::vector<float> & matrixTwo, std::vector<float> & result, int size) { 
    for (int row = 0; row < size; ++row) { 
     for (int col = 0; col < size; ++col) { 
      for (int k = 0; k <size; ++k) { 
       result[(size*row)+col] += matrixOne[(size*row)+k] * matrixTwo[(size*k)+col]; 
      } 
     } 
    } 
} 

array dinamico versione

void mult_2 (float * matrixOne, float * matrixTwo, float * result, int size) { 
    for (int row = 0; row < size; ++row) { 
     for (int col = 0; col < size; ++col) { 
      for (int k = 0; k < size; ++k) { 
       (*(result+(size*row)+col)) += (*(matrixOne+(size*row)+k)) * (*(matrixTwo+(size*k)+col)); 
      } 
     } 
    } 
} 

Inoltre, la versione vettorializzare funziona meglio (0,803 s);

Answer 1

Un vettore di vettori è analogo a un array frastagliato - un array in cui ogni voce è un puntatore, ogni puntatore punta a un'altra matrice di float.

In confronto, la versione dell'array raw è un blocco di memoria, dove si fa matematica per trovare gli elementi.

Utilizzare un vettore singolo, non un vettore di vettori e eseguire manualmente i calcoli matematici. Oppure utilizzare un vettore di dimensioni fisse std::array s. Oppure scrivi un tipo di helper che prende il vettore (unidimensionale) di float e ti offre una vista bidimensionale di esso.

I dati in un buffer contiguo sono più cache e ottimizzati rispetto ai dati in un gruppo di buffer disconnessi.

template<std::size_t Dim, class T> 
struct multi_dim_array_view_helper { 
    std::size_t const* dims; 
    T* t; 
    std::size_t stride() const { 
    return 
     multi_dim_array_view_helper<Dim-1, T>{dims+1, nullptr}.stride() 
     * *dims; 
    } 
    multi_dim_array_view_helper<Dim-1, T> operator[](std::size_t i)const{ 
    return {dims+1, t+i*stride()}; 
    } 
}; 
template<class T> 
struct multi_dim_array_view_helper<1, T> { 
    std::size_t stride() const{ return 1; } 
    T* t; 
    T& operator[](std::size_t i)const{ 
    return t[i]; 
    } 
    multi_dim_array_view_helper(std::size_t const*, T* p):t(p) {} 
}; 
template<std::size_t Dims> 
using dims_t = std::array<std::size_t, Dims-1>; 
template<std::size_t Dims, class T> 
struct multi_dim_array_view_storage 
{ 
    dims_t<Dims> storage; 
}; 
template<std::size_t Dims, class T> 
struct multi_dim_array_view: 
    multi_dim_array_view_storage<Dims, T>, 
    multi_dim_array_view_helper<Dims, T> 
{ 
    multi_dim_array_view(dims_t<Dims> d, T* t): 
    multi_dim_array_view_storage<Dims, T>{std::move(d)}, 
    multi_dim_array_view_helper<Dims, T>{ 
     this->storage.data(), t 
    } 
    {} 
}; 

ora si può fare questo:

std::vector<float> blah = { 
    01.f, 02.f, 03.f, 
    11.f, 12.f, 13.f, 
    21.f, 22.f, 23.f, 
}; 

multi_dim_array_view<2, float> view = { {3}, blah.data() }; 
for (std::size_t i = 0; i < 3; ++i) 
{ 
    std::cout << "["; 
    for (std::size_t j = 0; j < 3; ++j) 
    std::cout << view[i][j] << ","; 
    std::cout << "]\n"; 
} 

live example

Nessun dato viene copiato nella classe di visualizzazione. Fornisce solo una vista dell'array piatto che è una matrice multidimensionale.

Answer 2

tuoi approcci sono molto diversi:

• Nella versione "matrice dinamica" si allocano un singolo blocco di memoria per ogni matrice e mappa le righe delle matrici su quella intervallo di memoria dimensionale.

• Nella versione "vettoriale" si utilizzano vettori di vettori che sono significati bidimensionali "reali" e "dinamicamente" che la posizione di memorizzazione di ciascuna riga delle matrici non è correlata rispetto alle altre righe.

Quello che probabilmente vuole fare è:

• Usa vector<float>(size*size) ed eseguire la stessa mappatura si sta facendo nella "matrice dinamica" esempio a mano o

• Write una classe che gestisce internamente la mappatura per te e fornisce un'interfaccia di accesso bidimensionale (T& operator()(size_t, size_t) o un tipo di row_proxy operator[](size_t) dove row_proxy a sua volta ha T& operator[](size_t))

Answer 3

Questo è solo per rafforzare la teoria (in pratica) sulla memoria contigua.

Dopo aver fatto qualche analisi sul codice generato con g ++ (-O2) la fonte può essere trovato alla: https://gist.github.com/42be237af8e3e2b1ca03

Il relativo codice generato per la versione array è:

.L3: 
    lea r9, [r13+0+rbx]    ; <-------- KEEPS THE ADDRESS 
    lea r11, [r12+rbx] 
    xor edx, edx 
.L7: 
    lea r8, [rsi+rdx] 
    movss xmm1, DWORD PTR [r9] 
    xor eax, eax 
.L6: 
    movss xmm0, DWORD PTR [r11+rax*4] 
    add rax, 1 
    mulss xmm0, DWORD PTR [r8] 
    add r8, r10 
    cmp ecx, eax 
    addss xmm1, xmm0 
    movss DWORD PTR [r9], xmm1  ; <------------ ADDRESS IS USED 
    jg .L6 
    add rdx, 4 
    add r9, 4      ; <--- ADDRESS INCREMENTED WITH SIZE OF FLOAT 
    cmp rdx, rdi 
    jne .L7 
    add ebp, 1 
    add rbx, r10 
    cmp ebp, ecx 
    jne .L3 

vedere come l'uso del valore di r9 sta riflettendo la memoria contigua per l'array di destinazione e r8 per uno degli array di input.

Dall'altra parte, il vettore di vettori genera codice come:

.L12: 
    mov r9, QWORD PTR [r12+r11] 
    mov rdi, QWORD PTR [rbx+r11] 
    xor ecx, ecx 
.L16: 
    movss xmm1, DWORD PTR [rdi+rcx] 
    mov rdx, r10 
    xor eax, eax 
    jmp .L15 
.L13: 
    movaps xmm1, xmm0 
.L15: 
    mov rsi, QWORD PTR [rdx] 
    movss xmm0, DWORD PTR [r9+rax] 
    add rax, 4 
    add rdx, 24 
    cmp r8, rax 
    mulss xmm0, DWORD PTR [rsi+rcx] 
    addss xmm0, xmm1 
    movss DWORD PTR [rdi+rcx], xmm0 ; <------------ HERE 
    jne .L13 
    add rcx, 4 
    cmp rcx, r8 
    jne .L16 
    add r11, 24 
    cmp r11, rbp 
    jne .L12 

Non a caso, il compilatore è abbastanza intelligente per non generare il codice per tutti i operator [] chiamate, e fa un buon lavoro di messa in linea loro, ma vedi come deve tenere traccia di diversi indirizzi tramite rdi + rcx quando memorizza il valore sul vettore risultato, e anche gli accessi extra alla memoria per i vari sotto-vettori (mov rsi, QWORD PTR [rdx]) che generano tutti un sovraccarico.