[C] - Performance

[clockover]

Supponiamo di avere una funzione molto semplice che mi permette di copiare byte a byte passando come parametro due puntatori e la dimensione.. una cosa del tipo

void mcpy(void *src, void *dst, unsigned size){
int i = 0;
do{
*((char*)dst + i) = *((char*)src + i);
}while(++i < size);
}

questa funziona bene... se la ripeto per parecchie-mila volte ci mette un po troppo tempo....
ad esempio la ripeto per 100000000 volte impiega circa 6.5 secondi su un core due duo da 2GHz
ma comunque non mi interessa tanto questa faccenda, o almeno non mi interessa ora

passo il tutto a Instruments e ho come risultato questo

http://img851.imageshack.us/img851/6295/instr1.png (http://imageshack.us/photo/my-images/851/instr1.png/)

il 22.7% è utilizzato solo per l'incremento e il controllo della variabile..
a me sembra molto... come posso rendere più veloce questa cosa

inoltre se volessi andare sul discorso dei tempi...
la funzione memcpy della libreria string.h sullo stesso input e con lo stesso numero di cicli impiega circa 2 secondi... in che modo copia i valori?

Il tutto ovviamente ha uno scopo didattico, nel senso che non mi importa tanto di quella funzione, ma di come far diventare più efficiente ogni tipo di codice

[sottovento]

Supponiamo di avere una funzione molto semplice che mi permette di copiare byte a byte passando come parametro due puntatori e la dimensione.. una cosa del tipo

void mcpy(void *src, void *dst, unsigned size){
int i = 0;
do{
*((char*)dst + i) = *((char*)src + i);
}while(++i < size);
}

questa funziona bene... se la ripeto per parecchie-mila volte ci mette un po troppo tempo....
ad esempio la ripeto per 100000000 volte impiega circa 6.5 secondi su un core due duo da 2GHz
ma comunque non mi interessa tanto questa faccenda, o almeno non mi interessa ora

passo il tutto a Instruments e ho come risultato questo

http://img851.imageshack.us/img851/6295/instr1.png (http://imageshack.us/photo/my-images/851/instr1.png/)

il 22.7% è utilizzato solo per l'incremento e il controllo della variabile..
a me sembra molto... come posso rendere più veloce questa cosa

inoltre se volessi andare sul discorso dei tempi...
la funzione memcpy della libreria string.h sullo stesso input e con lo stesso numero di cicli impiega circa 2 secondi... in che modo copia i valori?

Il tutto ovviamente ha uno scopo didattico, nel senso che non mi importa tanto di quella funzione, ma di come far diventare più efficiente ogni tipo di codice


Controlla se migliori con
void mcpy(void *src, void *dst, unsigned size){
int i = 0;
do{
*dst++ = *src++;
}while(++i < size);
}

Sui vecchi processori migliorava le prestazioni.

Un altro modo per migliorare e' usare meglio il bus dati... (detto in altri termini: copiare NON un char ma qualcosa di piu' grande di un bytes)

[clockover]

Come mi hai consigliato tu c'è un notevole miglioramento (a livello di tempi),
ora ci impiega meno di 4 secondi per lo stesso numero di operazioni

http://img852.imageshack.us/img852/8483/instr2.png (http://imageshack.us/photo/my-images/852/instr2.png/)

però a maggior ragione adesso è ancora più inaccettabile il consumo di risorse del controllo della variabile.. si può fare di meglio anche li?

[british]

come curiosità didattica, prova a guardare questo:
http://en.wikipedia.org/wiki/Duff%27s_device


ciao!

british

[clockover]

Loop unrolling... quindi è l'unico modo per ridurre al minimo i controlli e l'incremento della variabile.. In effetti ho fatto una cosa del genere (sempre per delle prove) in questo modo

http://img810.imageshack.us/img810/4261/inc3.png (http://imageshack.us/photo/my-images/810/inc3.png/)

e infatti il tempo perso nel controllo del while è minimo ora... ora provo altre soluzioni

edit
non sto usando nessun livello di ottimizzazione

[WarDuck]

Provo a dire la mia... hai provato a castare i puntatori fuori dal ciclo, anziché farlo ad ogni passo?

[clockover]

Provo a dire la mia... hai provato a castare i puntatori fuori dal ciclo, anziché farlo ad ogni passo?

Grande :D :D e chi ci aveva pensato... ci provo subito

[clockover]

Ho tentato un'altra strada per vedere la situazione come va e ho anche ascoltato il suggerimento di WarDuck

void mcpyF2(void *src, void *dst, unsigned size){
unsigned i = 0;
unsigned max = 0;
unsigned resto = size % 8;
char *Dc = (char*)dst;
char *Sc = (char*)src;
switch (resto) {
case 0:
max = size - 7;
double *Dd = (double*)dst;
double *Sd = (double*)src;
do{
*(Dd++) = *(Sd++);
i += 8;
}while(i < max);
break;
case 4:
max = size - 3;
int *Di = (int*)dst;
int *Si = (int*)src;
do{
*(Di++) = *(Si++);
i += 4;
}while(i < max);
break;
case 2:
max = size - 1;
short *Ds = (short*)dst;
short *Ss = (short*)src;
do{
*(Ds++) = *(Ss++);
i += 2;
}while(i < max);
break;
default:
while(i < size){
*(Dc++) = *(Sc++);
i++;
}
}
}

con risultati
http://img3.imageshack.us/img3/8678/schermata20110510a17244.png (http://imageshack.us/photo/my-images/3/schermata20110510a17244.png/)

in quanto a tempi il vecchio codice è poco più veloce, ma suppone che sia un multiplo di 4 bytes... per quanto riguarda questo diciamo che la lo switch è un vero e proprio vampiro

ecco invece il codice seguendo il suggerimento di Warduck...
http://img717.imageshack.us/img717/570/schermata20110510a17321.png (http://imageshack.us/photo/my-images/717/schermata20110510a17321.png/)

sembra che il cast fuori dal loop non cambi la situazione, ma forse perchè gli passo una parola da 8 bytes, adesso faccio un paio di prove con un pezzettone da 16KB :D :D

[clockover]

E si per molta più memoria da copiare si fa sentire il cast fuori dal loop...

Ma la funzione memcpy come funziona??

[sottovento]

Loop unrolling... quindi è l'unico modo per ridurre al minimo i controlli e l'incremento della variabile.. In effetti ho fatto una cosa del genere (sempre per delle prove) in questo modo

http://img810.imageshack.us/img810/4261/inc3.png (http://imageshack.us/photo/my-images/810/inc3.png/)

e infatti il tempo perso nel controllo del while è minimo ora... ora provo altre soluzioni

edit
non sto usando nessun livello di ottimizzazione

Potresti provare a copiare i byte a 4 a 4 invece che uno alla volta (a 8 a 8 sui 64 bit).
Per semplicita': se parti da un indirizzo allineato a 4 byte e le dimensioni sono multiple di 4:


// Nota: per semplicita', src e dst sono allineate a 4 byte; size e' multiplo di 4
void mcpy(void *src, void *dst, unsigned size) throw()
{
register int i = size/sizeof(int);
register int *p = (int *)src;
register int *q = (int *)dst;
do{
*p++ = *q++;
}while(--i > 0);
}



Ovviamente, se non sei allineato devi aggiungere la copia "a mano" dei primi byte e degli ultimi, fino all'allineamento.

NOTA - il predecremento, su alcuni processori (motorola in particolare) e' piu' efficiente del post decremento.
Il post decremento sugli stessi processori e' piu' efficiente del pre incremento.

Altra nota: hai parlato di C ma magari stai usando un compilatore c++. Per sicurezza potresti usare il throw() per evitare che certe implementazioni introducano un codice per la verifica di eccezioni che in realta' non possono succedere.

Altra nota ancora: sui compilatori per processori a 32 bits (quali Visual Studio), il double ha dimensione doppia (i.e. 64 bit) i quali non possono ovviamente passare tutti insieme su un bus largo la meta', ma e' probabile che si impieghi di meno a trasferire un valore 64 bit che non due botte da 32 bit. Potresti quindi provare con i puntatori double *. Ovviamente l'allineamento deve essere a 8, altrimenti il giochetto non funziona :D

[clockover]

E si infatti per ora sto facendo delle prove per rendermi conto di come alcune scelte influenzano il codice! Infatti ho creato varie versioni del codice.

Quella dell'efficienza del predecremento o del postdecremento non la sapevo.. tocca sperimentare

Intanto ho trovato questo
http://www.student.cs.uwaterloo.ca/~cs350/common/os161-src-html/memcpy_8c-source.html

molto molto semplice.... ma efficiente

[sottovento]

E si infatti per ora sto facendo delle prove per rendermi conto di come alcune scelte influenzano il codice! Infatti ho creato varie versioni del codice.

Quella dell'efficienza del predecremento o del postdecremento non la sapevo.. tocca sperimentare

Intanto ho trovato questo
http://www.student.cs.uwaterloo.ca/~cs350/common/os161-src-html/memcpy_8c-source.html

molto molto semplice.... ma efficiente

Ho guardato il link e ci sono cose che non riesco a capire, probabilmente perche' sono rimasto un po' indietro:


for (i=0; i<len/sizeof(long); i++) {

Il controllo di ciclo ( i < len/sizeof(long) ) deve essere effettuato ad ogni iterazione, pertanto sarebbe logico aspettarsi che rimpiazzandolo con una variabile locale:


int sz = len/sizeof(long);
for (i = 0; i < sz; i++)

vi siano dei benefici. Immagino che l'abbiano pensato e se non l'hanno fatto e' perche' non hanno ottenuto dei benefici. Come mai? Lo fa il compilatore per noi?

Altra cosa: subito dopo c'e' scritto:


d[i] = s[i];


Anche questo mi lascia perplesso. Sui vecchi processori, con i vecchi compilatori, questo risultava SICURAMENTE piu' lento di


*d++ = *s++;


in quanto nel primo caso si doveva prendere l'indirizzo di base del vettore, calcolare lo spiazzamento in base alla dimensione del tipo ed aggiungerlo all'indirizzo di base per accedere alla locazione corretta.
Nel secondo caso si trattava di referenziare una locazione ed effettuare il post incremento. Fra l'altro, alcuni processori (es. Motorola) hanno una operazione simile nel loro set di istruzioni, quindi quest'assegnamento risultava velocissimo.

Ora non sembra piu' cosi', ma non capisco il motivo....

Infine: la memcpy() presentata all'indirizzo che hai fornito, va solo a controllare se l'allineamento e' rispettato. Se lo e', copia word a word, altrimenti byte a byte. Immagino che potrebbe essere piu' efficiente modificando il caso di non allineamento: nel caso non siano allineati, si potrebbero distinguere alcuni casi e, quando possibile, ricopiare i primi byte dopo di che procedere a word....

[clockover]

Colpa mia... questa è la memcpy di
http://www.eecs.harvard.edu/~syrah/os161/
:D :D

molto sicuramente non c'entra nulla

me lo sono meritato uno schiaffettino :doh:

[marco.r]

non sto usando nessun livello di ottimizzazione
Non ha molto senso far paragoni senza almeno un minimo di ottimizzazione.
Basta far ottimizzare l'agoritmo piu' lento presentato e andra' piu' veloce di quello "migliore" non ottimizzato.

[clockover]

Penso che un buon algoritmo creato al meglio dal programmatore sarà molto efficiente anche senza ottimizzazione da parte del compilatore, figuriamoci poi ottimizzato... anche perchè il compilatore non può fare sempre dei miracoli :D

comunque ora sto cominciando a lavorare con livello di ottimizzazione massimo (uso GCC)

molto interessanti queste cosine... si può limare sempre qualcosina da quello che uno credeva essere un buon algoritmo (non intendo a quelli che ho postato :D :D erano solo delle prove)

[WarDuck]

Penso che un buon algoritmo creato al meglio dal programmatore sarà molto efficiente anche senza ottimizzazione da parte del compilatore, figuriamoci poi ottimizzato... anche perchè il compilatore non può fare sempre dei miracoli :D

comunque ora sto cominciando a lavorare con livello di ottimizzazione massimo (uso GCC)

molto interessanti queste cosine... si può limare sempre qualcosina da quello che uno credeva essere un buon algoritmo (non intendo a quelli che ho postato :D :D erano solo delle prove)

Non ti credere, il compilatore spesso analizzando il codice può produrre ottimizzazioni che il programmatore magari neanche contemplava ;).

Fidati che può cambiare di molto il risultato.

Inoltre IMHO è meglio fare profiling sul programma già ottimizzato, così da individuare realmente quali siano i colli di bottiglia.

[clockover]

Non ti credere, il compilatore spesso analizzando il codice può produrre ottimizzazioni che il programmatore magari neanche contemplava ;).

Fidati che può cambiare di molto il risultato.

Inoltre IMHO è meglio fare profiling sul programma già ottimizzato, così da individuare realmente quali siano i colli di bottiglia.


si più vado avanti e più mi convinco a lavorare su quello ottimizzato...

ot
forte il debugger di XCode

[Tommo]

sembra che il cast fuori dal loop non cambi la situazione, ma forse perchè gli passo una parola da 8 bytes, adesso faccio un paio di prove con un pezzettone da 16KB :D :D

E' perchè al 99% lo stava già spostando fuori dal ciclo il compilatore :read:

Comunque, se l'obiettivo sono gli x86 un modo eccellente per ottimizzare le prestazioni è TOGLIERE qualsiasi operazione aritmetica e usare il loop unrolling, per trarre vantaggio dalle pipeline multiple di caricamento dalla memoria:

a[i] = b[i] è una operazione svolta interamente dalla pipeline load mentre
*a++ = *b++ deve attendere il risultato delle operazioni ++ svolte dalla pipeline aritmetica e serializza il flusso.

Anche copiare parole a 64 bit potrebbe migliorare le prestazioni su processori a 64 bits:

void mcpy( void* src, void* dst, unsigned size )
{
long* a = (long*)src;
long* b = (long*)dst;
long* end;

size = size/sizeof( long )+1;

end = a + size % 8;

//resto
while( a!= end )
*a++ = *b++;

end = src + size / 8;

for( ; a != end; a += 8, b+= 8 )
{
//copia 64 byte per ogni ciclo
a[0] = b[0];
a[1] = b[1];
a[2] = b[2];
a[3] = b[3];
a[4] = b[4];
a[5] = b[5];
a[6] = b[6];
a[7] = b[7];
}
}


Non so se funziona, però l'idea è quella.

[clockover]

Lo vedo un po strano però quel codice :mbe: non è che si alluppa al ciclo while?? E poi nel ciclo for mi copi 64 bytes non 64 bit... rischi di sforare

Comunque a parte il codice ho capito quello che intendi :)

[Tommo]

Corretto, in effetti non sarebbe mai uscito dal while :D

I 64 byte sono voluti, per massimizzare la banda:
-ogni pipeline estrae al massimo 8 byte con una singola operazione, quindi 8 byte massimizza i byte per istruzione
-allo stesso tempo ci sono diverse pipeline che lavorano in parallelo, quindi 8 trasferimenti dovrebbe riempirle tutte.

E cmq si, il codice sfora perchè copia tutta l'ultima qword, anche se avanza solo un byte :D
Potrebbe creare problemi in caso di sovrascritture di roba adiacente, bisognerebbe considerare pure quello nel resto.