[C++] Ottimizzare una funzione

[Pirelli72]

Ho scritto una funzione molto semplice che prende in ingresso una matrice bidimensionale, due interi e che restituisce un'array di valori. In pratica fa la media dei valori nelle colonne della matrice in ingresso e restituisce i risultati nell'array. La funzione svolge il suo lavoro egregiamente ma mi chiedevo, visto che la matrice in ingresso è molto grande se è possibile renderla più performante.

__declspec(dllexport) void MatrixMean(unsigned char* matrix, unsigned char esito[],int width,int height)
  {
	  int x=0;	 	     
	  int somma=0;
	  	  for(x=0;x<=width;x++)
		  {		 
	             int y=0;	
		     for(y=0;y<=height;matrix++)
		    {	 
		     somma+=*matrix;
		     y++;
		    }
		  *(esito+x)= (somma / (height +1));
		  somma=0;
		 }
  }

[MItaly]

Non credo si possa ottimizzare molto, l'ottimizzazione grossa che si può fare in questi casi è leggere la matrice nell'ordine in cui è in memoria invece di saltare (leggerla per colonne e non per righe) per sfruttare la cache locality, ma vedo che già lo fai.

[deleted_29]

se la matrice è densa, ma veramente grande, ed hai una macchina multicore, puoi fare più thread.
bisogna far attenzione però sia alla sincronizzazione, sia al partizionare opportunamente l'area di memoria per evitare races

[MItaly]

Già, in questo caso però credo che la cosa sia particolarmente semplice: dato che la matrice multidimensionale di fatto è "spalmata" e gestita come fosse una matrice monodimensionale, dovrebbe bastare spezzarla logicamente in più pezzi e richiamare la funzione che già esiste da thread separati (avendo cura ovviamente che i vari pezzi e i pezzi della matrice di output non si sovrappongano).

[Pirelli72]

Non so cosa tu intenda per veramente grande ma l'ordine di grandezza della mia matrice potrebbe essere di 3000 righe x 2500 colonne.

.....ed hai una macchina multicore, puoi fare più thread.
bisogna far attenzione però sia alla sincronizzazione, sia al partizionare opportunamente l'area di memoria per evitare races.

Si la CPU è un dualcore ma in C++ non sarei in grado di farlo.....
Potrei spezzare la matrice in VB.NET e passare le due funzioni su core separati.

[MItaly]

2500x3000 unsigned char sono le dimensioni di una foto, te la puoi passare tutta in una frazione di secondo.

Originariamente inviato da Pirelli72
Potrei spezzare la matrice in VB.NET e passare le due funzioni su core separati.

Non mi pare una buona idea, in .NET dovresti spezzarla in due array separati per davvero, in C++ invece puoi semplicemente passare ad una istanza il puntatore all'inizio dicendogli di fare metà delle colonne, e alla seconda istanza un puntatore al punto dove inizia la colonna di metà dell'array. Tutto questo naturalmente se il tuo array multidimensionale è, come appunto sembra, in memoria in ordine column-major, altrimenti le cose diventano un pelo più complicate.

[Pirelli72]

Originariamente inviato da MItaly
2500x3000 unsigned char sono le dimensioni di una foto, te la puoi passare tutta in una frazione di secondo.

Si, il problema è che lo deve fare almeno 15 volte al secondo e non c'è solo di mezzo quella funzione.

[MItaly]

Il mio consiglio è di iniziare a scrivere gli algoritmi "giusti" (possibilmente disaccoppiando interfaccia ed implementazione, in modo da poterli cambiare internamente in un secondo tempo senza impazzire), quindi effettuare un profiling del programma, in modo che spuntino fuori i veri colli di bottiglia su cui ti devi concentrare per migliorare globalmente le prestazioni.

[MacApp]

sicuro che quei "<=" non debbano essere dei "<"?

In ogni modo perché reinventare ogni volta l'acqua calda?
Ad esempio (assumendo che il "<=" sia corretto):

	             int y=0;	
		     for(y=0;y<=height;matrix++)
		    {	 
		     somma+=*matrix;
		     y++;
		    }

dovrebbe essere equivalente a:

#include <numeric>
...

// il +1 ci va assumendo che il tuo "<=" sia valido
const int somma = std::accumulate (matrix, matrix + height +1, 0);
matrix += height +1;

(dico dovrebbe perché non l'ho provato in questo caso: molto probabilmente va adattato perché gli elementi sono dei "char" e la somma un int);

Osserva anche come nel tuo codice quanta fatica tu debba fare per mantenere la variabile somma; ti basterebbe spostarne la definizione all'interno del primo for e ti eviteresti di doverla reinizializzare alla fine del for; nel mio addirittura è una costante!
;-)

poi ovvio come ti hanno già detto puoi sfruttare i core parallelizzando, ad esempio con:
http://en.wikipedia.org/wiki/OpenMP

considera che per compiere operazioni algebriche sulle matrici si può sfruttare anche la scheda grafica, ad esempio con:
http://en.wikipedia.org/wiki/OpenCL

[deleted_29]

a memoria non ci sono istruzioni SSE che ti possano aiutare, quindi la domanda da porsi è: come viene popolata la matrice?

Puoi calcolare direttamente le somme nel momento in cui viene scritta?