[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'.

Qua sotto riporto un esempio semplificato di una parte di programma:
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??

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^]

Originariamente inviato da kalindriv

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

Qua sotto riporto un esempio semplificato di una parte di programma:
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??

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..
Altrimenti vai di assembly ed SSE e utilizza i registri a 128 bit per fare direttamente queste operazioni se ne hai la necessità

[sottovento]

Originariamente inviato da kalindriv

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

Qua sotto riporto un esempio semplificato di una parte di programma:
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??

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]

Originariamente inviato da 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.

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]

Originariamente inviato da ^TiGeRShArK^

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..
Altrimenti vai di assembly ed SSE e utilizza i registri a 128 bit per fare direttamente queste operazioni se ne hai la necessità

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...

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....
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 ).

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?

[cdimauro]

O non si avvia o va in crash.

[marko.fatto]

Originariamente inviato da cdimauro

O non si avvia o va in crash.

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

[cdimauro]

Dipende dal compilatore.

[marko.fatto]

c'è anche qualcosa che non dipende dal compilatore?


ironico ovviamente

[^TiGeRShArK^]

Originariamente inviato da marko.fatto

c'è anche qualcosa che non dipende dal compilatore?


ironico ovviamente

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

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

[cdimauro]

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

[^TiGeRShArK^]

Originariamente inviato da cdimauro

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

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

[cdimauro]

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

[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.

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....