[C/ASM] Ottimizzazione programma in C

[kalindriv]

Ciao ragazzi, sto ottimizzando un programma in C e pensavo di scrivere dei pezzi in assembler per velocizzarlo un po'. :mc:

Qua sotto riporto un esempio semplificato di una parte di programma: :read:
dovrei fare in pratica l'exor di due vettori che sono lunghi "symbLen" dove questo valore può essere da 1 a svariate migliaia. Se lo implementassi in Assembler avrei tutte le operazioni in parallelo (credo...)

// EX-OR COMPUTATION
for (k=0; k<symbLen; k++){
c[k] = a[k] ^ b[k];
}

Il problema è che non saprei proprio come scriverlo.... qualcuno di voi potrebbe darmi delle dritte?? :help:

Sarebbe piattaforma indipendente...

[recoil]

eh ma se deve essere piattaforma indipendente come fai a scriverlo in assembly?
ti metti a fare le #ifdef e poi codifichi in tutti gli assembly possibili tipo x86, arm, ppc, mips?? è uno sbattimento assurdo

[^TiGeRShArK^]

Ciao ragazzi, sto ottimizzando un programma in C e pensavo di scrivere dei pezzi in assembler per velocizzarlo un po'. :mc:

Qua sotto riporto un esempio semplificato di una parte di programma: :read:
dovrei fare in pratica l'exor di due vettori che sono lunghi "symbLen" dove questo valore può essere da 1 a svariate migliaia. Se lo implementassi in Assembler avrei tutte le operazioni in parallelo (credo...)

// EX-OR COMPUTATION
for (k=0; k<symbLen; k++){
c[k] = a[k] ^ b[k];
}

Il problema è che non saprei proprio come scriverlo.... qualcuno di voi potrebbe darmi delle dritte?? :help:

Sarebbe piattaforma indipendente...

a, b, e c sono array di booleani?
In caso positivo non potresti utilizzare dei long a 64 bit e fare l'XOR tra loro?
Così anzichè ciclare fino a symblen dovresti ciclare fino a (symblen / 64 + symblen % 64) così ad occhio...
...sempre se in C è possibile fare direttamente l'XOR tra due long che sono secoli che non lo tocco.. :stordita:
Altrimenti vai di assembly ed SSE e utilizza i registri a 128 bit per fare direttamente queste operazioni se ne hai la necessità :p

[sottovento]

Ciao ragazzi, sto ottimizzando un programma in C e pensavo di scrivere dei pezzi in assembler per velocizzarlo un po'. :mc:

Qua sotto riporto un esempio semplificato di una parte di programma: :read:
dovrei fare in pratica l'exor di due vettori che sono lunghi "symbLen" dove questo valore può essere da 1 a svariate migliaia. Se lo implementassi in Assembler avrei tutte le operazioni in parallelo (credo...)

// EX-OR COMPUTATION
for (k=0; k<symbLen; k++){
c[k] = a[k] ^ b[k];
}

Il problema è che non saprei proprio come scriverlo.... qualcuno di voi potrebbe darmi delle dritte?? :help:

Sarebbe piattaforma indipendente...

Dubito che su un codice del genere si possa far meglio di quanto riesca a fare il compilatore... otterrai al massimo la stessa velocita'...

[cdimauro]

Potrebbe provare così:
int *x, *y, *z;
x = a; y = b; z = c;
for (k = symbLen; k; k--)
*(z++) = *(x++) ^ *(y++);
ma non so quanto potrebbe guadagnare.

[sottovento]

Potrebbe provare così:
int *x, *y, *z;
x = a; y = b; z = c;
for (k = symbLen; k; k--)
*(z++) = *(x++) ^ *(y++);
ma non so quanto potrebbe guadagnare.

Secondo me e' il modo corretto (e probabilmente il migliore) di ottimizzare il codice in questione. Per esserne sicuri, basta guardare il codice asm generato dal compilatore.

[kalindriv]

a, b, e c sono array di booleani?
In caso positivo non potresti utilizzare dei long a 64 bit e fare l'XOR tra loro?
Così anzichè ciclare fino a symblen dovresti ciclare fino a (symblen / 64 + symblen % 64) così ad occhio...
...sempre se in C è possibile fare direttamente l'XOR tra due long che sono secoli che non lo tocco.. :stordita:
Altrimenti vai di assembly ed SSE e utilizza i registri a 128 bit per fare direttamente queste operazioni se ne hai la necessità :p

Grazie a tutti dei consigli!!
Ora proverò a fare un confronto fra la mia implementazione e quella suggerita da cdimauro con i puntatori per vedere quanto si guadagna... :read:

In realtà userei solo x86... l'idea del multipiattaforma cade quando si tratta di ottimizzare! :)

Mi è stato detto che potrei usare in assebly gli SSE.... :help:
Ah, dimenticavo.... i vettori sono di char.

[cdimauro]

Se i vettori sono di char allora potresti ottenere un notevole aumento prestazionale convertendoli in int per le architetture a 32 bit e in long long per quelle a 64 bit (posto che int e long long corrispondano esattamente a queste dimensioni: il C come linguaggio non te lo garantisce :stordita:).

Il codice sarebbe "qualosa" (notare le virgolette: fai delle prove e adattalo alla situazione reale) tipo questo:
MyInt *x, *y, *z; // MyInt sarà il typedef o la macro che lo definisce come int o long long a seconda dell'architettura.
x = a; y = b; z = c;
for (k = symbLen / sizeof(MyInt); k; k--)
*(z++) = *(x++) ^ *(y++);
Ovviamente dovresti assicurarti che symbLen sia sempre un multiplo di sizeof(MyInt), pena eventuali segmentation fault (intermittenti: i peggiori).

P.S. Sì, puoi usare le SSE, ma ti legheresti alla piattaforma x86, e per di più soltanto ai processori che le hanno in dotazione.

[marko.fatto]

è un po' ot..
ma se un programma è compilato utilizzando delle sse non supportate da un processore che succede? non si avvia e basta? :confused:

[cdimauro]

O non si avvia o va in crash. :D

[marko.fatto]

O non si avvia o va in crash. :D

ah ok.. quindi non ha un comportamento ben definito nemmeno quello!? :asd:

[cdimauro]

Dipende dal compilatore. :stordita:

[marko.fatto]

c'è anche qualcosa che non dipende dal compilatore? :asd:


ironico ovviamente :fagiano:

[^TiGeRShArK^]

c'è anche qualcosa che non dipende dal compilatore? :asd:


ironico ovviamente :fagiano:

beh..potresti anche gestire tutto in fase di avvio testando se sono supportate le SSE.. non mi pare trascendentale.. :stordita:

cmq alla fine col codice del topic non ho detto una cazzata tanto grande :p
(spero :asd: )

[cdimauro]

Azz. Vero. :doh: Non mi sono accorto che l'ultimo pezzo di codice che ho riportato praticamente è l'equivalente di quello che avevi scritto all'inizio. :muro:

[^TiGeRShArK^]

Azz. Vero. :doh: Non mi sono accorto che l'ultimo pezzo di codice che ho riportato praticamente è l'equivalente di quello che avevi scritto all'inizio. :muro:

vabbè.. tu hai postato il codice però :p
io ormai sono allergico al C e avrei scritto sicuramente qualche cazzata :asd:

[cdimauro]

Io non sono sicuro di non averne scritte, visto che pure io sono allergico al C, e da parecchio tempo. :asd:

[Big Bamboo]

Dall'esperienza che ho maturato, è quasi impossibile scrivere codice più ottimizzato di un compilatore. IMHO trova una buona soluzione algoritmica e lascia perdere assembler.

[cdimauro]

Dipende dall'architettura. :cool:

P.S. Si dice "assembly", non "assembler". ;)

[kalindriv]

Grazie ragazzi per l'aiuto che mi state dando!!

In realtà mi sto convincendo che il compilatore sa meglio di me come ottimizzare, quindi devo solo fare alcuni accorgimanti mentre scrivo. Del tipo evitare operazioni troppo complesse e non dipendenti dal ciclo for dentro gli indici di un vettore:

for (i=0; i<100; i++)
a[i] = b[i]+c[d*e+i];

questo ciclo non è ottimizzato per niente perchè richiede di fare 100 volte la moltiplicazione d*e che avrà lo stesso identico risultato.

Su questa scia di pensiero mi sto chiedendo come posso trovare in maniera intelligente la somma dei valori di un vettore e come trovare la cumulativa di una distribuzione di probabilità:

for (i=0; i<100; i++)
sum += a[i];

cum[0] = dist[0];
for (i=1; i<100; i++)
cum[i] = cum[i-1] + dist[i];

A me sembra che una scrittura così sia lenta.... :muro:

[Big Bamboo]

Sarebbe interessante fare una prova cronometrata tra la versione iniziale del programma (ottimizzata solo dal compilatore) e una versione ottimizzata da te (senza utilizzare il "codice macchina")
Così ad occhio, a meno di grandi porcherie nel codice iniziale, dico che le prestazioni saranno quasi identiche.

[cdimauro]

Grazie ragazzi per l'aiuto che mi state dando!!

In realtà mi sto convincendo che il compilatore sa meglio di me come ottimizzare, quindi devo solo fare alcuni accorgimanti mentre scrivo. Del tipo evitare operazioni troppo complesse e non dipendenti dal ciclo for dentro gli indici di un vettore:

for (i=0; i<100; i++)
a[i] = b[i]+c[d*e+i];

questo ciclo non è ottimizzato per niente perchè richiede di fare 100 volte la moltiplicazione d*e che avrà lo stesso identico risultato.
Hum... Non credo: quello di recuperare gli "invarianti" in un ciclo e portarli fuori da esso è un lavoro piuttosto semplice che i compilatori dovrebbero fare già automaticamente da soli da un bel pezzo.
Su questa scia di pensiero mi sto chiedendo come posso trovare in maniera intelligente la somma dei valori di un vettore e come trovare la cumulativa di una distribuzione di probabilità:

for (i=0; i<100; i++)
sum += a[i];

cum[0] = dist[0];
for (i=1; i<100; i++)
cum[i] = cum[i-1] + dist[i];

A me sembra che una scrittura così sia lenta.... :muro:
Riscrivendolo usando i puntatori:
float *p = a;

for(; i; i--)
sum += *(p++);

float *c = cum
float *c_prev = cum;
float *d = dist;

*(c++) = *(d++);

for(i--; i; i--)
*(c++) = *(c_prev++) + *(dist++);
Vedi un po' come ti va. ;)

x Big Bamboo: concordo. Cronometriamo la versione originale e quella ottimizzata.

[sottovento]

Hum... Non credo: quello di recuperare gli "invarianti" in un ciclo e portarli fuori da esso è un lavoro piuttosto semplice che i compilatori dovrebbero fare già automaticamente da soli da un bel pezzo.

:mbe: Veramente non sono "invarianti". Infatti il tuo primo codice sfruttava proprio i puntatori per evitare questi conti. E sono ancora convinto che e' il modo migliore per ottimizzare questo codice (ammesso, ovviamente, che sia questo il codice da ottimizzare


<cut>

x Big Bamboo: concordo. Cronometriamo la versione originale e quella ottimizzata.
Fermo restando che anch'io concordo con Big Bamboo, cercando di ottimizzare il codice C si arriva alla versione che avevi scritto in partenza.

Fra l'altro, su molti processori verra' effettuata un'ottimizzazione "spinta" in quanto sono presenti istruzioni di "usa il valore puntato ed incrementa il puntatore" pertanto istruzioni come
*p++
verranno tradotte in una sola istruzione macchina

[cdimauro]

:mbe: Veramente non sono "invarianti". Infatti il tuo primo codice sfruttava proprio i puntatori per evitare questi conti. E sono ancora convinto che e' il modo migliore per ottimizzare questo codice (ammesso, ovviamente, che sia questo il codice da ottimizzare
Veramente parlavo di questo:
for (i=0; i<100; i++)
a[i] = b[i]+c[d*e+i];
In questo caso d ed e non variano per cui un buon compilatore internamente dovrebbe essere capace di "tirare fuori" d * e, generando un codice simile a questo:
float temp = d * e;
for (i=0; i<100; i++)
a[i] = b[i]+c[temp + i];
Fermo restando che anch'io concordo con Big Bamboo, cercando di ottimizzare il codice C si arriva alla versione che avevi scritto in partenza.
Vero, ma al giorno d'oggi mi aspetto che codice del genere venga generato automaticamente dal compilatore.

Vedremo coi benchmark se sarà così oppure se l'analisi e relativa ottimizzazione del codice è ancora scarsa nei moderni compilatori.
Fra l'altro, su molti processori verra' effettuata un'ottimizzazione "spinta" in quanto sono presenti istruzioni di "usa il valore puntato ed incrementa il puntatore" pertanto istruzioni come
*p++
verranno tradotte in una sola istruzione macchina
Chessò, i 68000? :fiufiu: :cool:

[sottovento]

Veramente parlavo di questo:
for (i=0; i<100; i++)
a[i] = b[i]+c[d*e+i];
In questo caso d ed e non variano per cui un buon compilatore internamente dovrebbe essere capace di "tirare fuori" d * e, generando un codice simile a questo:
float temp = d * e;
for (i=0; i<100; i++)
a[i] = b[i]+c[temp + i];

Vero, ma al giorno d'oggi mi aspetto che codice del genere venga generato automaticamente dal compilatore.

Ok, ma si puo' fare di meglio... capisco il tuo punto di vista, cmq.

Ad ogni modo, in questo codice, il compilatore deve comunque accedere ad un elemento del vettore prendendo il suo indirizzo di partenza (che si spera sia stato assegnato ad un registro), calcolando lo spiazzamento (i.e. la somma al suo interno), moltiplicarlo per la dimensione del tipo contenuto nel vettore e finalmente aggiungere questo spiazzamento all'indirizzo di partenza.

Ovviamente il codice che hai postato all'inizio non deve fare questo lavoro: per accedere all'elemento successivo deve fare semplicemente +1 :D



Chessò, i 68000? :fiufiu: :cool:

Potrebbe essere, ma se mi dai 5/6 anni di tempo mi viene in mente qualche altra famiglia di processori ;)

[cdimauro]

Ok, ma si puo' fare di meglio... capisco il tuo punto di vista, cmq.

Ad ogni modo, in questo codice, il compilatore deve comunque accedere ad un elemento del vettore prendendo il suo indirizzo di partenza (che si spera sia stato assegnato ad un registro), calcolando lo spiazzamento (i.e. la somma al suo interno), moltiplicarlo per la dimensione del tipo contenuto nel vettore e finalmente aggiungere questo spiazzamento all'indirizzo di partenza.

Ovviamente il codice che hai postato all'inizio non deve fare questo lavoro: per accedere all'elemento successivo deve fare semplicemente +1 :D
Ma infatti son d'accordo con te. Il codice iniziale è un pattern "standard": mi aspetto che un buon compilatore lo traduca nella forma con cui l'ho espresso io. :)

Quindi non soltanto d * e, che è veramente banale come ottimizzazione. :p
Potrebbe essere, ma se mi dai 5/6 anni di tempo mi viene in mente qualche altra famiglia di processori ;)
National 32000, PDP-11, e roba simile.

Con x86 hai soltanto uno "stream" in lettura e un altro in scrittura, per cui per operazioni che coinvolgano più di due stream si deve ricorrere necessariamente all'incremento manuale successivamente al load e/o allo store per gli altri "stream".

[Big Bamboo]

x Big Bamboo: concordo. Cronometriamo la versione originale e quella ottimizzata.

Si riesce a scrivere un programma la cui esecuzione sia abbastanza lunga per poter apprezzare eventuali differenze di prestazioni?

[sanford]

Si riesce a scrivere un programma la cui esecuzione sia abbastanza lunga per poter apprezzare eventuali differenze di prestazioni?

beh, se proprio ci fosse qualcuno che ne ha voglia, in questo caso la differenza di prestazioni sarebbe enorme:

http://www.hwupgrade.it/forum/showthread.php?t=1790186

...io ci provo, non si sa mai...:D

[^TiGeRShArK^]

Si riesce a scrivere un programma la cui esecuzione sia abbastanza lunga per poter apprezzare eventuali differenze di prestazioni?

Io non mi ci metto proprio...
Ieri dopo due ore appresso all'assembly iniziavo a vedere gli elefantini rosa della birra duff nella stanza...:fagiano:

[cdimauro]

Si riesce a scrivere un programma la cui esecuzione sia abbastanza lunga per poter apprezzare eventuali differenze di prestazioni?
Stiamo parlando di vettori: basta "allungarli" opportunamente. :p

[^TiGeRShArK^]

Stiamo parlando di vettori: basta "allungarli" opportunamente. :p

Si, ma ti tocca anche smazzarti la versione in assembly per fare il paragone :p

[cdimauro]

Visto che c'hai lavorato di recente, lascio l'onore a te. :asd:

[marco.r]

ne vale la pena ?
giusto per fare un esempio:
ho provato il codice nella forma originale

for ( int n=0 ; n<1000000; ++n )
{
for ( int i=0 ; i<size ; ++i )
{
a[i] = b[i]+c[d*e+i];
b[i] = a[i];
}
}

(il secondo assegnamento mi serve per forzare l'elaborazione... un compilatore intelligente si accorge che ripeti gli stessi conti e ti taglia il loop esterno)
e con forma "furba"

for ( int n=0 ; n<1000000; ++n )
{
int *x = a;
int *y = b;
int *z = c+d*e;
int i=size;
while( i-- )
{
*(x++) = *(y++) + *(z++);
*y = *x;
}
}

(la dimensione degli array e' di circa 10000 elementi)
Con g++, compilando con -O3 si passa da circa 21 sec. a 18 sec.
Con icc, compilando con -fast -parallel -axP (ottimizza per Core 2 Duo e usa le sse3) ottengo 6.7 sec. nel primo caso e 21 nel secondo. Le ottimizzazioni manuali probabilmente mandano in confusione l'ottimizzatore del compilatore, che non riesce piu' a capire bene le interdipendenze e a parallelizzare automaticamente il codice.
(Per inciso, non me lo aspettavo, pensavo che rimanessero uguali...)

[cdimauro]

:eek: Idem. Non mi aspettavo un risultato del genere. :|

EDIT: avevo commesso un errore nell'ottimizzazione di d * e. :(

[^TiGeRShArK^]

Visto che c'hai lavorato di recente, lascio l'onore a te. :asd:

io l'ho solo letto, non l'ho scritto :fiufiu:

[Big Bamboo]

Le ottimizzazioni manuali probabilmente mandano in confusione l'ottimizzatore del compilatore, che non riesce piu' a capire bene le interdipendenze e a parallelizzare automaticamente il codice.
(Per inciso, non me lo aspettavo, pensavo che rimanessero uguali...)

Come volevasi dimostrare il compilatore ce l'ha più lungo :sofico:

[cdimauro]

ne vale la pena ?
giusto per fare un esempio:
ho provato il codice nella forma originale

for ( int n=0 ; n<1000000; ++n )
{
for ( int i=0 ; i<size ; ++i )
{
a[i] = b[i]+c[d*e+i];
b[i] = a[i];
}
}

(il secondo assegnamento mi serve per forzare l'elaborazione... un compilatore intelligente si accorge che ripeti gli stessi conti e ti taglia il loop esterno)
e con forma "furba"

for ( int n=0 ; n<1000000; ++n )
{
int *x = a;
int *y = b;
int *z = c+d*e;
int i=size;
while( i-- )
{
*(x++) = *(y++) + *(z++);
*y = *x;
}
}

(la dimensione degli array e' di circa 10000 elementi)
Con g++, compilando con -O3 si passa da circa 21 sec. a 18 sec.
Con icc, compilando con -fast -parallel -axP (ottimizza per Core 2 Duo e usa le sse3) ottengo 6.7 sec. nel primo caso e 21 nel secondo. Le ottimizzazioni manuali probabilmente mandano in confusione l'ottimizzatore del compilatore, che non riesce piu' a capire bene le interdipendenze e a parallelizzare automaticamente il codice.
(Per inciso, non me lo aspettavo, pensavo che rimanessero uguali...)
Se ti è possibile e se non chiedo troppo, potresti effettuare dei test compilando con ICC con e senza SSE3, e con e senza parallelizzazione del codice? :)
Come volevasi dimostrare il compilatore ce l'ha più lungo :sofico:
Io ho ottimizzato soltanto il caso generale.

Posso benissimo sfruttare le SSE3 e parallelizzare il codice, se voglio (ma con C e C++ non ne ho proprio voglia :asd:). ;)

[sottovento]

:eek: Idem. Non mi aspettavo un risultato del genere. :|

EDIT: avevo commesso un errore nell'ottimizzazione di d * e. :(

:eek: Idem. Mi aggiungo alla lista dei sorpresi da questi risultati. Per la cronaca, ho appena avuto la stessa sorpresa riguardo all'altro thread, quello del contest 4.

Sembra che aggiungendo operazioni inutili da fare, la velocita' aumenti! :eek:

Sarebbe bello trovare della documentazione che spieghi questa cosa, perche' francamente e' difficile da capire.

[marco.r]

Se ti è possibile e se non chiedo troppo, potresti effettuare dei test compilando con ICC con e senza SSE3, e con e senza parallelizzazione del codice? :)

Sto usando la versione a 64 che non mi permette come quella a 32 di specificare molte opzioni a riguardo. O vettorizza con SSE3 o non lo fa.
La versione "nuda e cruda" (ovvero senza alcun parametro) ci mette circa dieci secondi. A naso pero' vettorizza comunque qualcosa perche' mettendo output verboso mi dice che lo fa. Nel caso vi interessi allego l'assembly ottenuto compilato con -s, forse qualcuno ne capisce piu' di me :p.
Non allego quello della versione superottimizzata, che peraltro e' piu' di 3 mega (:eek: :confused:).


Posso benissimo sfruttare le SSE3 e parallelizzare il codice, se voglio (ma con C e C++ non ne ho proprio voglia :asd:). ;)
Immagino :D. Il vantaggio di farlo fare al compilatore e' che comunque ti genera una versione "di default" nel caso le SSE non siano presenti (se vuoi).

[marco.r]

ah, la parallelizzazione invece non viene proprio usata, nel senso che non divide il carico tra i due core. Da quel che mi sembra capire non parallelizza mai pezzi dello stesso codice man pezzi diversi che capisce che possono andare in parallelo. Non mi riesce facile fare un esempio che funzioni,perche' non capisco quando il compilatore ottimizza bene e quando invece "fa il furbo" e (giustamente) taglia il codice inutile.
Ad esempio, il seguente codice (con size=100000 stavolta, ovvero dieci volte il precedente)

for ( int n=0 ; n<1000000; ++n )
{
for ( int i=0 ; i<size ; ++i )
{
a[i] += b[i] + c[d*e + i ];
}
}

Mi ci mette circa 190 secondi con g++ -O3, 90 secondi con parametri di default di ICC, e 13 con -fast -axP :eek: :mbe:

[cdimauro]

Sto usando la versione a 64 che non mi permette come quella a 32 di specificare molte opzioni a riguardo. O vettorizza con SSE3 o non lo fa.
La versione "nuda e cruda" (ovvero senza alcun parametro) ci mette circa dieci secondi. A naso pero' vettorizza comunque qualcosa perche' mettendo output verboso mi dice che lo fa. Nel caso vi interessi allego l'assembly ottenuto compilato con -s, forse qualcuno ne capisce piu' di me :p.
Se non è troppo lungo il listato, posta pure, grazie. :)
Non allego quello della versione superottimizzata, che peraltro e' piu' di 3 mega (:eek: :confused:).
Se la possono tenere gli ingegneri Intel. :D
Immagino :D. Il vantaggio di farlo fare al compilatore e' che comunque ti genera una versione "di default" nel caso le SSE non siano presenti (se vuoi).
Sì, lo so (è tipico di Intel di inserire di code path diversi a seconda dell'architettura).

Io avrei operato similmente, ma a manina, aggiungendo i necessari controlli della CPUID e smistando poi la chiamata al codice per l'architettura.
ah, la parallelizzazione invece non viene proprio usata, nel senso che non divide il carico tra i due core. Da quel che mi sembra capire non parallelizza mai pezzi dello stesso codice man pezzi diversi che capisce che possono andare in parallelo.
Ho capito. E mi sembrava strano, infatti. Anche per questo ti avevo chiesto di fare dei test disabilitando la parallelizzazione. :D
Non mi riesce facile fare un esempio che funzioni,perche' non capisco quando il compilatore ottimizza bene e quando invece "fa il furbo" e (giustamente) taglia il codice inutile.
Ad esempio, il seguente codice (con size=100000 stavolta, ovvero dieci volte il precedente)

for ( int n=0 ; n<1000000; ++n )
{
for ( int i=0 ; i<size ; ++i )
{
a[i] += b[i] + c[d*e + i ];
}
}

Mi ci mette circa 190 secondi con g++ -O3, 90 secondi con parametri di default di ICC, e 13 con -fast -axP :eek: :mbe:
Sono risultati incredibili.

E dimostrano, tra l'altro, che quelli che hanno sviluppato g++ possono andare a zappare la terra, che è meglio. :asd:

[marco.r]

sorry, ero convinto di averlo gia' fatto :p
c'e' tutto il programma dentro, spero ci capiate qualcosa :D

[cdimauro]

Odio la sintassi AT&T: non la posso sopportare. Ma per quale assurdo motivo Intel non supporta la SUA sintassi?!? :muro:

Il pezzo di codice che esegue i calcoli è questo:
..B1.16: # Preds ..B1.15
xorl %eax, %eax #38.5
# LOE rbp r12 r13 r14 r15 eax
..B1.17: # Preds ..B1.19 ..B1.16
xorl %r9d, %r9d #
movl $48, %r8d #
movl $32, %edi #
movl $16, %esi #
movl $b, %ebx #54.20
movl $b+16, %ecx #
movl $b+40048, %edx #
# LOE rdx rcx rbx rbp rsi rdi r8 r9 r12 r13 r14 r15 eax
..B1.18: # Preds ..B1.18 ..B1.17
movdqa (%rbx), %xmm0 #54.20
paddd 20000+c(%r9), %xmm0 #54.27
movdqa %xmm0, (%rbx) #55.13
movdqa (%rcx), %xmm1 #54.20
paddd 20016+c(%r9), %xmm1 #54.27
movdqa 16(%rcx), %xmm2 #54.20
paddd 20032+c(%r9), %xmm2 #54.27
movdqa 32(%rcx), %xmm3 #54.20
paddd 20048+c(%r9), %xmm3 #54.27
movdqa %xmm1, (%rcx) #55.13
movdqa %xmm2, 16(%rcx) #55.13
movdqa %xmm0, a(%r9) #54.13
movdqa %xmm1, a(%rsi) #54.13
movdqa %xmm2, a(%rdi) #54.13
movdqa %xmm3, 32(%rcx) #55.13
movdqa %xmm3, a(%r8) #54.13
addq $64, %r8 #52.9
addq $64, %rdi #52.9
addq $64, %rcx #52.9
addq $64, %rsi #52.9
addq $64, %rbx #52.9
addq $64, %r9 #52.9
lea 32(%rcx), %r10 #52.9
cmpq %r10, %rdx #52.9
jg ..B1.18 # Prob 50% #52.9
# LOE rdx rcx rbx rbp rsi rdi r8 r9 r12 r13 r14 r15 eax
..B1.19: # Preds ..B1.18
addl $1, %eax #38.5
cmpl $1000000, %eax #38.5
jb ..B1.17 # Prob 50% #38.5
# LOE rbp r12 r13 r14 r15 eax
Ed usa estensivamente l'architettura x86-64 e le SSE2 (per le SSE3 ci sono 13 istruzioni, di cui 10 per la parte SIMD, ma al momento non ricordo quali sono e se vengono usate in questo pezzo di codice).

Una curiosità: ovviamente anche g++ generava codice a 64 bit, vero?

[kalindriv]

Che bello vedere che la mia domanda stupida ha portato a una riflessione intelligente!!:D

Per la cronaca, un mio amico mi ha aiutato e abbiamo trovato su internet un qualcosa che ci ha aiutato a raddoppiare la velocità delle operazioni.

Posto la prima parte della fuznione degli exor, per SSE2:

void calcXOR(void *src, void *dst, size_t n, XorType type) {

unsigned int long_size, op_cnt;
unsigned long t;
char *src_p, *dst_p;
unsigned long *src_lp, *dst_lp;
void *aligned_dst;
unsigned long gap;

src_p=(char *)(src);
dst_p=(char *)(dst);

#ifndef non_x86

if(n>=32 && type==SSE2){
// SSE2$BL?Na$rMQ$$$F(B128bit$B$:$D(BXOR$B$r7W;;$9$k(B

//printf("Using SSE2.\n");

aligned_dst=(void *)(((unsigned int)dst+(16-1))&~(16-1));
gap=(unsigned int)aligned_dst - (unsigned int)dst;

//printf("%x, %x, %d\n", aligned_dst, dst, gap);

for(t=0; t<gap; t++){
dst_p[t] ^= src_p[t];
}

op_cnt=(int)((n-gap)/16);

asm volatile ("\n"
" mov %2, %%eax\n"
" calc1:\n"
" movdqu (%%esi),%%xmm0\n"
" movdqa (%%edi),%%xmm1\n"
" pxor %%xmm1,%%xmm0\n"
" movdqa %%xmm0,(%%edi)\n"

" sub $1, %%eax\n"
" cmp $0, %%eax\n"
" je end1\n"

" add $16, %%esi\n"
" add $16, %%edi\n"
" jmp calc1\n"

" end1:\n"
" emms" :: "S" ((unsigned int)src+gap), "D" ((unsigned int)dst+gap), "r" (op_cnt) : "%eax"
);

// $B;D$C$?J,$r(B1$B%P%$%H$:$D7W;;(B
for(t=gap+op_cnt*16; t<n; t++){
dst_p[t] ^= src_p[t];
}

return;
}
...

[kalindriv]

float *c = cum
float *c_prev = cum;
float *d = dist;

*(c++) = *(d++);

for(i--; i; i--)
*(c++) = *(c_prev++) + *(dist++);


Scusate la mia ignoranza, che a sto punto ritengo cosmica.... ma come mai il ciclo for comincia con i--? E dist all'interno del ciclo sarebbe d?
E' opportuno copiare fare le assegnazioni sui puntatori all'inizio? :help:

[marco.r]

Una curiosità: ovviamente anche g++ generava codice a 64 bit, vero?
Si'.
Allego il .s generato da g++ -O3 -msse3 e quello generato nel caso ottimale da ICC, dove pero' ho tolto circa 3 mega di "blob" binario che non so cosa possa voler dire :mbe: (una sequenza infinita di .byte)

[marco.r]

parte seconda

[Big Bamboo]

Non allego quello della versione superottimizzata, che peraltro e' piu' di 3 mega (:eek: :confused:).

Molto probabilmente il compilatore per evitare jump e test condition ha "trasformato" il ciclo for in una serie lunghissima di istruzioni.

[cdimauro]

Scusate la mia ignoranza, che a sto punto ritengo cosmica.... ma come mai il ciclo for comincia con i--?
Perché il primo lo deve saltare, visto che l'ho già copiato.
E dist all'interno del ciclo sarebbe d?
Sì.
E' opportuno copiare fare le assegnazioni sui puntatori all'inizio? :help:
Sì, perché non vado a toccare i puntatori ai vettori, visto che dovrei modificarli. Ne faccio una copia e lavoro su quelli.
Si'.
Allego il .s generato da g++ -O3 -msse3 e quello generato nel caso ottimale da ICC, dove pero' ho tolto circa 3 mega di "blob" binario che non so cosa possa voler dire :mbe: (una sequenza infinita di .byte)
Appena posso controllo.
parte seconda
OK grazie :)
Molto probabilmente il compilatore per evitare jump e test condition ha "trasformato" il ciclo for in una serie lunghissima di istruzioni.
All'inizio lo pensavo anch'io, ma se sono .byte dovrebbero essere dati e non codice.

Se il compilatore avesse eseguito l'unrolling del loop, avrebbe dovuto creare dei blocchi di codice ripetendo le istruzioni, ma non pare sia questo il caso (devo ancora dare un'occhiata al codice; oggi sono di matrimonio, per cui nel forum sono velocemente di passaggio :D).