[C] Ottimizzazione spinta

[Unrue]

Ciao ragazzi,
avrei bisogno di ultraottimizzare questo spezzone di codice:

register float32 * punt;
register float32 sample_r,sample_i;

punt = &trdiff[4*i_idx1];

for(m = 0; m < *ntot; m++)
 for( k = 0; k < i_idx2-i_idx1+1 ; k++) {

          sample_r = *punt + up_interp* *(punt+1);
          sample_i = *(punt + 2) +up_interp* *(punt + 3);

          punt +=4;

          numm[ m][k].r += sample_r;
          numm[ m][k].i += sample_i;
          denom[m]      += sample_r * sample_r + sample_i * sample_i;
        }

Secondo voi si può migliorare utilizzando l'aritmetica dei puntatori o richiamando direttamenre istruzioni assembly?( denom e trdiff sono float32, numm è complex32)

Grazie

[Ikon O'Cluster]

Secondo me oltre un certo punto ogni ottimizzazione "sintattica" apporta vantaggi trascurabili... ad un certo punto bisogna considerare l'ottimizzazione "semantica". Ad esempio il tuo codice ha complessità O(N*M) dove:

N = max(*ntot)
M = max(i_idx2-i_idx1+1)

Puoi fare di meglio?

P.S.: Se vuoi ottimizzare (sintatticamente) al max devi avere una grande conoscenza del compilatore. Non so quale usi, ma cmq non sono espertissimo in questo campo. Prova a studiare le tecniche di ottimizzazione che usa il tuo compilatore e cerca di scrivere il codice che le sfrutti al meglio. Ma il gioco non vale la candela... almeno per la maggior parte delle applicazioni che riesco ad immaginare!

[Unrue]

Ciao,
grazie per la risposta. Dunque, sto utilizzando il compilatore Intel. Diciamo che questa applicazione non dove girare su molte macchine ma più o meno sempre sulla stessa ( AMD Opteron)

Riguardo il tuo consiglio, purtroppo non posso eliminare il doppio ciclo.

[Ikon O'Cluster]

Eh... su quello non avevo dubbi! Non intendevo eliminarlo, ma se per esempio da O(N*M) riesci a passare a O(N*log(M)) soprattutto se M >> N allora può essere conveniente... se poi quella è già la soluzione più efficiente pace! Cmq io penso che una ottimizzazione spinta del codice non ti permetta di guadagnare poi tanto... voglio esagerare e dico un 7% (sul tempo di esecuzione).

[Ikon O'Cluster]

Ma forse ho esagerato troppo...

[^TiGeRShArK^]

se hai + di un core a disposizione sulla tua macchina puoi usare i thread, altrimenti credo che la cosa migliore sarebbe ottimizzare l'algoritmo come ha già detto ikon'cluster....
cmq è una matrice completa?
o magari è sparsa o diagonale?
Negli ultimi due casi dovresti poter guadagnare molto a livello algoritmico.....

[Tommo]

Dato che lo stride di punt è 4 elementi, dovrebbe essere possibile usare le SIMD... forse

Oppure potresti spezzare il for interno su tutti i cores con threads che lo eseguirebbero più o meno parallelamente.

L'unica ottimizzazione che mi viene in mente in quel codice è salvarsi i_idx2-i_idx1+1 invece che ricalcolarlo N*M volte... ed anche usare ++k e ++m invece che k++ e m++... dovrebbe risparmiare un paio di istruzioni asm.

[banryu79]

Originariamente inviato da Tommo

ed anche usare ++k e ++m invece che k++ e m++... dovrebbe risparmiare un paio di istruzioni asm.

[OT]Il preincremento è più "economico" del postincremento in termini di assembly? Nel senso, lo è sempre? Non conosco niente di assembly...[/OT]

[^TiGeRShArK^]

con i compilatori moderni utilizzare a++ o ++a dovrebbe essere la stessa cosa.
Anche il fatto di salvarsi la sottrazione in una variabile locale *dovrebbe* essere già fatto dal compilatore...

[Tommo]

Originariamente inviato da banryu79

[OT]Il preincremento è più "economico" del postincremento in termini di assembly? Nel senso, lo è sempre? Non conosco niente di assembly...[/OT]

teoricamente (da quello che mi hanno detto) il posticremento prende il valore dell'espressione ci aggiunge 1 e lo rimette al suo posto... invece il preincremento aggiunge direttamente 1 al valore.

quindi si dovrebbe risparmiare una creazione ed un'assegnazione.
Ma non so niente di assembly
Cmq io lo uso sempre perchè non costa niente, se funziona meglio

In ogni caso il compilatore *dovrebbe* farle da solo ste cose, ma dato che qua si parla di ottimizzazione massima il *dovrebbe* non è ammesso...

[Ikon O'Cluster]

Originariamente inviato da ^TiGeRShArK^

se hai + di un core a disposizione sulla tua macchina puoi usare i thread, altrimenti credo che la cosa migliore sarebbe ottimizzare l'algoritmo come ha già detto ikon'cluster....
cmq è una matrice completa?
o magari è sparsa o diagonale?
Negli ultimi due casi dovresti poter guadagnare molto a livello algoritmico.....

C'è da dire che ottimizzare in sè x sè non dice niente... bisogna sapere se uno ha vincoli stretti su memoria o processore e in quale proporzione...

[Unrue]

Originariamente inviato da Ikon O'Cluster

C'è da dire che ottimizzare in sè x sè non dice niente... bisogna sapere se uno ha vincoli stretti su memoria o processore e in quale proporzione...

Intendo ottimizzare il tempo di esecuzione.

[wingman87]

Potresti anche salvare il valore di *ntot in una variabile per evitare la dereferenziazione, risparmieresti un accesso alla memoria. Ma temo che tutte le ottimizzazioni che stiamo proponendo siano già attuate dal compilatore...

[cionci]

Allora...io proverei così:

sample_r = A + K * B;
sample_i = C + K * D;

Quindi

denom[m] += A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB

N = i_idx2 - i_idx1

denom[m] = somma per K che va da 0 a N(A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB) = NA^2 + NC^2 + (B^2 + D^2)*somma(K^2) + (AB + CD)*somma(K)

somma(K) = (N*(N+1))/2
somma(K^2) = N(N+1)(2N+1)/6

Da numm[m][k] ci passi solo una volta, cosa c'è prima dentro la struct ?

[Unrue]

Originariamente inviato da cionci

Allora...io proverei così:

sample_r = A + K * B;
sample_i = C + K * D;

Quindi

denom[m] += A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB

N = i_idx2 - i_idx1

denom[m] = somma per K che va da 0 a N(A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB) = NA^2 + NC^2 + (B^2 + D^2)*somma(K^2) + (AB + CD)*somma(K)

somma(K) = (N*(N+1))/2
somma(K^2) = N(N+1)(2N+1)/6

Da numm[m][k] ci passi solo una volta, cosa c'è prima dentro la struct ?

Ciao cionci. In numm[m][k] non c'è nulla prima, sono inizializzate a 0.0.

[cionci]

Aspetta, non avevo visto che punt viene incrementato di 4...cancella tutto quello che ho scritto

[Ikon O'Cluster]

Originariamente inviato da cionci

Aspetta, non avevo visto che punt viene incrementato di 4...cancella tutto quello che ho scritto

AUAUHAUHAUH Grandissima sola...

[fracarro]

Originariamente inviato da Unrue

Intendo ottimizzare il tempo di esecuzione.

Potresti provare a compilare con il gcc insieme all'opzione -O3 e vedere come va l'eseguibile rispetto a quello compilato con l'intel.
Da quello che ho letto in giro il compilatore intel dovrebbe generare codici più performanti a patto di compilare con i flag giusti che sfruttano l'architettura. Fai il confronto tra i due eseguibili e se va meglio quello prodotto dal gcc allora forse devi usare qualche altro flag sul compilatore intel.

P.S. Anche se sono poche righe di codice, potresti analizzarle sfruttando il valgrind come profiler e il kcachegrind per vedere ogni istruzione e ogni ciclo quando tempo di cpu impiega (è il modo migliore per trovare i colli di bottiglia).

[Ikon O'Cluster]

fracarro x esempio è uno furbo...

[banryu79]

Magari può interessarti Acovea