PDA

Visualizza la versione completa : [C] Differenti prestazioni fra % e &


LeleFT
06-02-2004, 16:41
Salve a tutti.
Una curiosità: ho scritto due funzioni del tutto equivalenti in C. Entrambe ricevono in input un valore intero e restituiscono 0 se il valore è dispari o un valore diverso se è pari (una funzione che controlla, insomma, se un numero è pari o meno).
Ho voluto, però, testare l'efficienza delle due funzioni per cui le ho sottoposte a numerosi test cronometrandone il tempo impiegato per l'elaborazione. Secondo le mie teorie la seconda delle funzioni doveva essere più veloce, ma dai risultati ottenuti ho scoperto, invece, che la classica (la prima) risulta essere più performante.

La mia domanda, quindi: i risultati che ho ottenuto sono dovuti al fatto che il compilatore che ho usato (Dev-C++) è un ottimo compilatore che riesce ad accorgersi della divisione per 2 della prima funzione, traducendo, di conseguenza, in modo più efficiente l'operazione tramite un bit-shift?

Oppure dipende da altro?

Posto le due funzioni:


int pari1 (int x) { return !(x % 2); }

int pari2 (int x) { return !(x & 1); }

La prima funzione è la classica: si controlla se il resto della divisione per 2 è 0 oppure no.

La seconda, che ho pensato io, funziona in modo diverso: restituisce, semplicemente, il valore (negato, ovviamente) del bit meno significativo; se è 0, infatti, il numero è pari, altrimenti è dispari.

Secondo le mie teorie, un AND bit a bit dovrebbe essere un'operazione che richiede un solo tic di cloc, mentre il modulo dovrebbe richiederne di più: una divisione per 2 (tradotta in modo efficiente con un bit-shift destro) un prodotto e una differenza.

Qualcuno può illuminarmi su questa faccenda, spiegandomi perchè, invece, la prima viene eseguita più velocemente?


Ciao. :ciauz:

TheGreatWorld
06-02-2004, 23:33
Di sicuro utilizzare un cronometro per questo tipo di test non e' la cosa migliore. Devi basarti su dati oggettivi. Nella discussione premettero' che stiamo parlando di x86.

1) Analizza il codice asm che viene generato dal compilatore; e' quello il vero src da analizzare
2) Nel caso in cui la seconda funzione fosse implementata con un semplice and binario deve essere necessariamente piu' veloce della precedente visto che viene performata una sola operazione piuttosto che piu' operazioni

ciao

iguana13
07-02-2004, 14:25
Io non conosco l'assembler, ma siete sicuri che non esista l'operazione "modulo" direttamente nel processore?
E se magari si può ottenere con qualche semlice operazione binaria?
Comunque è omlto strano! :D

LeleFT
07-02-2004, 15:26
Originariamente inviato da TheGreatWorld
Di sicuro utilizzare un cronometro per questo tipo di test non e' la cosa migliore. Devi basarti su dati oggettivi. Nella discussione premettero' che stiamo parlando di x86.

1) Analizza il codice asm che viene generato dal compilatore; e' quello il vero src da analizzare
2) Nel caso in cui la seconda funzione fosse implementata con un semplice and binario deve essere necessariamente piu' veloce della precedente visto che viene performata una sola operazione piuttosto che piu' operazioni

ciao
Ti ringrazio per la risposta.
Non penso che non sia oggettivo basarsi sulla velocità d'esecuzione delle due funzioni: io ho generato un array di 1000 elementi interi e ho fatto eseguire le due funzioni 1000 volte su ognuno dei suoi elementi, calcolando il tempo all'inizio dell'elaborazione e alla fine (globalmente, ossia ho rilevato il tempo all'inizio e l'ho rilevato dopo aver fatto eseguire la funzione 1000 volte su ognuno).
Queste due rilevazioni le ho ripetute 1000 volte ed ho notato che nella maggior parte dei casi la differenza di tempo impiegato risulta inferiore (di ben 10 millisecondi) nel primo caso (cosa che anche a me risulta strana).
Purtroppo questo è il procedimento seguito in tutti i test per il calcolo della complessità di un algoritmo (è così che si fa ad Algoritmi e Strutture Dati all'università).
Controllerà anche il codice asm generato, ma dubito di riuscire a trarne qualcosa di utile.

Grazie ancora per la risposta.

Per iguana13: che io sappia non esistono istruzioni asm che calcolino il modulo: specialmente in processori CISC quali Pentium e Athlon; l'operazione di modulo è un'operazione complessa, nel senso che è la combinazione di più operazioni semplici.

Comunque, se tale operazione fosse stata implementata (attraverso, magari, hardware dedicato per migliorarne l'efficienza), questo spiegherebbe molte cose! ;)


Ciao.

iguana13
07-02-2004, 17:36
Usi la GetTickCount per calcolare il tempo?
In questo caso, 10 millisecondi è un normale errore per quella funzione!
Prova con qualcosa coma 30000 elementi o anche più, così la differenza si dovrebbe far vedere!

Comunque forse il compilatore usa chissà che strana ottimizzazione... :dottò:

TheGreatWorld
08-02-2004, 03:13
Se hai problemi con la comprensione dell'asm su x86 pasta qui in lista; se hai problemi con la comprensione dell'asm su SPARC pasta qui in lista; se hai problemi con la comprensione dell'asm su altri processori siamo nella merda :)

scherzi apparte metti il codice online e lo analizzeremo insieme. Soprattutto perche' benche' i beneamati x86 siano CISC hanno un nucleo RISC (quindi le istruzioni fetchate dalla memoria non passano tramite un interprete) che fa l'execute delle istruzioni piu' semplici. L'and dovrebbe essere al 90% una di queste.

ciao

internet
08-02-2004, 12:23
Compilatore CL (VC) su x86

int pari1 (int x) { return !(x % 2); }


mov eax, DWORD PTR _x$[esp-4] ; il parametro x
and eax, -2147483647 ; 80000001H
jns SHORT $L559
dec eax
or eax, -2 ; fffffffeH
inc eax
$L559:
neg eax
sbb eax, eax
inc eax
ret 0


int pari2 (int x) { return !(x & 1); }


mov eax, DWORD PTR _x$[esp-4] ; il parametro x
not eax
and eax, 1
ret 0


Compilatore gcc su x86

int pari1 (int x) { return !(x % 2); }



pushl %ebp
movl %esp,%ebp
movb 8(%ebp),%al
notl %eax
andl $1,%eax
leave
ret


int pari2 (int x) { return !(x & 1); }


pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax
xorb $1,%al
andl $1,%eax
leave
ret


codice di test



#include <stdio.h>
#include <time.h>

#define LOOPS 1000000

int pari1 (int x) { return !(x % 2); }

int pari2 (int x) { return !(x & 1); }

clock_t bench(int (*f)(int), int* tot)
{
int i;
clock_t t0,t1;

t0 = clock();

for (i = 0; i < LOOPS; i++)
*tot += f(i);

t1 = clock();

return t1 - t0;
}

int main()
{
int i, tot1 = 0, tot2 = 0;
double e[2] = {0.0};

for (i = 0; i < 1000; i++)
{
e[0] += (double)(bench(pari1, &tot1)) / CLOCKS_PER_SEC;
e[1] += (double)(bench(pari2, &tot2)) / CLOCKS_PER_SEC;
}

for (i = 0; i < 1000; i++)
{
e[1] += (double)(bench(pari2, &tot2)) / CLOCKS_PER_SEC;
e[0] += (double)(bench(pari1, &tot1)) / CLOCKS_PER_SEC;
}

printf("%% %.3fs %d\n", e[0], tot1);
printf("& %.3fs %d\n", e[1], tot2);

return 0;
}

il codice è stato scritto in modo da forzare il compilatore ad eseguire il loop, altrimenti quando viene attivata l'opzione di ottimizzazione non li eseguirà affatto, il caching può dare fastidio
ecco il perchè dei due loop incrociati.

Test su
CPU: AMD XP 1600+ (1400 Mhz)
RAM: 1 Gbyte DDR 2100 (2 moduli da 512 MB)
OS: win

cl (visual c) modalita Relase
% 5.758s 1000000000
& 5.718s 1000000000

gcc 3.3.2 opzione -O3
% 16.758s 1000000000
& 17.857s 1000000000

devo provarlo su linux.

LeleFT
08-02-2004, 14:49
Sì... effettivamente uso la GetTickCount e avevo anche pensato alla granularità del sistema nell'utilizzo di questa funzione... ma non l'avevo considerato. Può essere che la sua granularità sia di 10 ms però ogni volta c'erano quei 10 ms di scarto sempre in negativo per la seconda funzione...

Osservando il codice ASM postato da internet (Compilatore CL (VC) su x86) mi risulta molto interessante la compattezza di codice della seconda!

Comunque, per TheGreatWorld, ho a che fare con codice x86 non con codice SPARC, anche se a dire il vero potrei provare con uno SPARC a vedere la differenza... ;)


Grazie a tutti per l'interessamento... e visto che internet ha postato un po' di ASM, vediamo che ne esce, se qualcuno vuol mettersi ad analizzarlo!


Ciao. :ciauz:

iguana13
09-02-2004, 17:55
Lele, hai provato con n numero maggiore di cicli?
Con 1000 non dovrebbe metterci neanche un secondo...

LeleFT
09-02-2004, 19:01
Ho appena provato a modificare il numero di cicli (mi sono sbagliato, ho fatto ripetere il test 5000 volte non 1000).

Comunque sono appena passato a 10.000 cicli. Ma il risultato non cambia, anzi peggiora: ora il divario è cresciuto fino a 20 millisecondi.

Credo, comunque, che dipenda anche dalle opzioni di compilazione. Proverò a ricompilare usando gcc con l'opzione -O3 e magari proverò anche altri compilatori! :D


Ciao. :ciauz:

Loading