Newsgroup: it.comp.lang.c++
Titolo: Compilatori moderni (curiosità)...

Ciao, stavo scrivendo una spece di parser e a un certo punto, leggendo un
intero ho trovato una cosa che a me pare abbastanza strana...
Leggendo dei digit da uno stream per risalire al numero intero leggo il
digit, moltiplico il risultato temporaneo per dieci e sommo il digit,
ovviamente, finche ci sono digit.
Ma non è questo il punto, la curiosità è che, se per moltiplicare per 10 uso
qualcosa del tipo
l= l<<3 + l<<1;
ottengo un comportamento a mio avviso anomalo di questa linea... (ma forse
sono io che ho delle aspettative infondate!)
il risultato non è quello che naturalmente ci si potrebbe attendere, cioè se
l fosse ad esempio il primo digit=2 e il secondo=0 dovrebbe essere
entra con l=0, l viene moltiplicato per 10 e da sempre zero, poi l diventa
2, al giro successivo l viene moltiplicato per 10 e diventa 20 quindi viene
sommato zero e il risultato è 20.
invece fa: entra con l=0, legge l e gli somma 3 rilegge l (ancora =0) quindi
shifta il valore di l con quello di l sommato a 3, il risultato viene
moltiplicato per due (shiftato a sinistra di 1), dopo la prima passata l è
ancora a zero, ma poi viene il bello, alla seconda esecuzione della stessa
linea viene caricato il valore 2 (che è corretto perché il primo digit era
due e la moltiplicazione per 10, si fa per dire, ancora deve essere fatta!),
al valore 2 viene sommato 3!!! (e questo non lo capisco) che da 5, viene
riletto il valore 2 che viene shiftato del valore precedentemente ottenuto,
quindi 2<<5 che da 64, poi viene moltiplicato per due che da 128!! Io
onestamente non capisco...
Ecco il codice... (prima viene messo l=0)
        while(isdigit(c)) {
                l=l<<3+l<<1;
                l=l+(c-'0');
                in->get(c);
        }
Per ottenere invece una traduzione corretta di quello che voglio fare devo
passare per la creazione di variabili temporanee, create in modo più o meno
esplicito.
Quindi o creo un'intero j che uso per la moltiplicazione es. j=l<<3; quindi
j+=l<<1; oppure lascio crearla al compilatore forzandolo con due costruttori
d'intero con il codice adattato come sotto...
        while(isdigit(c)) {
                l=int(l<<3)+int(l<<1);
                l=l+(c-'0');
                in->get(c);
        }
Allora, come dice qualcuno... la domanda sorge spontanea...
Quale sarebbe il comportamento che prevede il C++ in un caso simile?
E' giusto che il compilatore con il primo segmento di codice dia il
risultato che ha dato?
Mi sembrava di ricordare che anni fa quando programmavo in C il compilatore
che usavo (in una macchina non Intel compatibile) dava il risultato che mi
aspettavo... e allora volevo sapere se dipende dal compilatore e dalle sue
ottimizzazioni che però qualche volta ingannano (sempre se è così) oppure
c'è una regola...
P.S. il compilatore che sto usando per questo codice è il Borland 5.

 Ciao, stavo scrivendo una spece di parser e a un certo punto, leggendo un
                                           ^^^^^
E' meglio dire specie... meno male che non è un parser per la lingua
italiana... scusate ma scrivo di fretta e "dis-imparo!".

(ma forse sono io che ho delle aspettative infondate!)
Esatto. Il problema e' che lo shift ha una precedenza inferiore
a quella della somma. Quindi se scrivi:
   l<<3 + l<<1
il compilatore interpreta come
   l << (3+l) << 1
HTH
Andrea
PS: 
  ma perche' complicare anche le semplici moltiplicazioni
  per 10 poi ?

   per 10 poi ?
Beh su questo non sarei molto daccordo... c'è un esempio nelle letteratura
Borland (di Saching Garg, How to Optimize C++ Source) che parla proprio di
questo tipo d'ottimizzazione (solo che loro non hanno fatto il mio errore,
hanno messo le parentesi)... il punto è che dopo una giornata di lavoro sono
stato io ad aver dato i numeri e a dimenticarmi addirittura delle basi...
comunque spesso c'è molta differenza in termini di prestazioni, infatti il
più delle volte sono gli stessi compilatori a introdurre di questi
trucchetti (solo che loro a differenza mia si ricordano di farlo sempre
bene...).
Anche se forse in quest'applicazione la velocità non conta tanto cerco di
evitare moltiplicazioni inutili, per abitudine, questa volta ho toppato io
però come linea di condotta non si può dire che sia sbagliata (e poi se
metti le parentesi funziona)...
Ciao.

 evitare moltiplicazioni inutili, per abitudine
Tempo perso al giorno d'oggi. Ci pensano i compilatori e il tuo codice 
risulta più leggibile.
-- 
Luc.

> Beh su questo non sarei molto daccordo... c'č un esempio nelle letteratura
                                                 ^^^^^^^^
E' meglio dire d'accordo... meno male che non č un parser per la lingua
italiana... probabilmente scrivevi di fretta.... ;-)
Scusa se mi son permessa...

 wrote in message
news:b0ho9n$2it$1...@lacerta.tiscalinet.it...

Ottimizzazione si', ma... beh, facciamo un discorso semplice^^;
La moltiplicazione, gia' sui vecchi Pentium 1, portava via tipo 30-35 cicli
di clock, mentre uno shift un ciclo solo, e un'addizione anche.
L'ottimizzazione c'e', e basta. Nessuno lo nega. Io meno che mai.
Solo che... un processore (vecchio) come un 486-66 Mhz riesce a fare
qualcosa come 66 milioni di cicli al secondo. Se consideri un vantaggio di
20 cicli (arrotondo), 66.000.000 / 20 = 3.300.000.
Non mi viene in mente nessun vantaggio significativo nel guadagnare un
tremilionietrecentomillesimo di secondo (su un 486-66, non voglio parlare
dei P4 a 1700 Mhz, in cui il vantaggio e' ancora piu' piccolo - e poi anche
la velocita' delle istruzioni e' stata ridotta) ^^;
Certo, poi dipende dalla frequenza con cui viene chiamata la funzione, ma
cmq...
L'ottimizzazione non ha piu' senso a livello di codice "codice", queste
piccole cose, salvo eccezioni. Certo, se non ti costa niente, non ha senso
scrivere del codice "non ottimizzato" di proposito, ma non vale la pena
"sbattersi" per queste piccole cose a ogni pie' sospinto, altrimenti ci si
impiega una vita a finire anche solo un progettino semplice^^;
Vale invece la pena ottimizzare delle sezioni di codice chiamate spesso.
Piuttosto, per avere un programma veloce, e' importante strutturare bene gli
algoritmi (IMO).

...

Il tuo mi pare un esempio perfetto di come *non* si ottimizza il
codice. Gli errori sono diversi:
- Non misuri le prestazioni prima di decidere dove ottimizzare;
- Sostituisci un'espressione semplicissima con una piu' difficile
  da capire, tanto che persino tu hai perso parecchio tempo per
  scriverla giusta, figuriamoci poi cosa puo' succedere se qualcuno
  deve mantenere il tuo codice;
- Intervieni su un istruzione di peso estremamente limitato
  (una moltiplicazione tra interi), quando uno dei dati su cui questa
  opera e' ottenuto con un'operazione di svariati ordini di grandezza
  piu' onerosa (la lettura da file).
Penso che dovresti cercare di perdere le cattive abitudini.
Ciao,
Nicola

"Nicola Musatti" <Nicola....@ObjectWay.it> wrote in message
news:a327cf48.03012...@posting.google.com...

Un po' dura, come risposta, ma non ho niente da dire per mitigarla - nel
senso, quanto dici e' vero.
A parte che cmq, non e' detto che arrivi da file - uno stream non e' un
file, anche cin e' uno stream - ma e' anche vero che la conversione da
char[] a int cmq non e' "gratuita", per cui poco cambia...
Riguardo al mantenere il codice sarei svenuto anch'io^^;


 cmq...
Allora ecco il solito test:
<CODE>
#include<stdio.h>
#include<time.h>
#include<windows.h>
int main()
{
    int x,y,z,w;
    int i;
    int sum;
    DWORD start, end;
    srand(time(NULL));
    start=GetTickCount();
    sum=0;
    x=0;
    for(i=0;i<500000000;++i){
        (x<100)?(++x):(x=0);
        y=x*5;
        z=x*13;
        w=x*18;
        sum+=y+z;
        sum-=w;
    }
    end=GetTickCount();
    printf("*:\nRisultato:%d\nTempo:%d\n",sum,end-start);
    start=GetTickCount();
    sum=0;
    x=0;
    for(i=0;i<500000000;++i){
        (x<100)?(++x):(x=0);
        y=(x<<2)+(x);   // y=x*5;
        z=(x<<3)+(x<<2)+(x); // z=x*13;
        w=(x<<4)+(x<<1);  // w=x*18;
        sum+=y+z;
        sum-=w;
    }
    end=GetTickCount();
    printf("<<:\nRisultato:%d\nTempo:%d\n",sum,end-start);
    return 0;
}
</CODE>
<OUTPUT>
*:
Risultato:0
Tempo:1234
<<:
Risultato:0
Tempo:1295
Press any key to continue
</OUTPUT>
I tempi cambiano di qualche decina di volta in volta, ma sono praticamente
identici!
Oooppsss! Vediamo cosa succede...
Il primo ciclo viene tradotto cosi:
<ASM>
cmp eax, 00000064
jge 0040102B
inc eax
jmp 0040102D
</ASM>
Il secondo cosi' invece:
<ASM>
cmp eax, 00000064
jge 00401057
inc eax
jmp 00401059
</ASM>
Se li guardate sono identici e non c'e' traccia ne di shift ne di
moltiplicazione!
Alla faccia dell'optimiser! Ha capito che non servivano a NULLA !!!!! (ed
evita cosi' di farle!)
Proviamo con un altro:
<CODE>
#include<stdio.h>
int main()
{
    int x=10,y,z;
    y=x*5;   // moltiplico * 5
    z=(x<<2)+(x); // moltiplico * 5
    printf("%d e %d\n",y,z);
    return 0;
}
</CODE>
Beh, qua l'optimiser fa di peggio:
push 00000032
push 00000032
e poi chiama printf!!! Butta su il valore 50 direttamente senza
calcolarlo!!!! Lo calcola at compile time e NON at run-time!!!
BRAVO !!!
Ora freghiamolo chiedendo input da tastiera!!!
<CODE>
#include<stdio.h>
int main()
{
    int x,y,z;
    scanf("%d",&x);
    y=x*7;   // moltiplico * 7
    scanf("%d",&x);
    z=(x<<3)+(x); // moltiplico * 9
    printf("%d e %d\n",y,z);
    return 0;
}
</CODE>
Ma ancora una volta il caro optimiser si fa prendere da manie di
protagonismo:
Ecco come moltiplica per 7 (y=x*7):
# lea esi, dword[8*eax+00000000]
# sub esi, eax
In pratica moltiplica x*8 e poi fa - x
Ecco come moltiplica per 9 (z=(x<<3)+(x)):
# lea edx, dword[eax+8*eax]
In pratica fa la stessa cosa!!!
Se metto 7 anche nella seconda parte (o vice versa) il codice diventa lo
stesso!!!
Non gli interessa che sia << o * ! E' piu' furbo di noi!
In pratica il mio compilatore VC++6 con maximize speed non si interessa del
fatto che sia uno uno shft o meno, ottimizza sempre e comunque allo stesso
modo.
La morale di questo lungo post deve essere che oggi giorno i compilatori
fanno un lavoro cosi' buono che non c'e' piu' bisogno di fare questi
trucchetti, specialmente in C/C++ !! Se uno vuole, ed e' in grado, puo' al
limite farlo direttamente in assembly.
In pratica conludo con cio' che ha detto Genjuro e che condivido:
"Piuttosto, per avere un programma veloce, e' importante strutturare bene
gli
algoritmi (IMO)."
Non condivido le sue motivazioni, ma certamente sono concorde al 100% con
questa frase!
Basta giochetti del tipo << e >> invece che * e / e xor invece che swap
etc...... !!!
Tommy

 wrote in message
news:b0j93c$do3$1...@sparta.btinternet.com...


 il tempo finale era minore di quello iniziale -_-
<QUOTE>
MSDN:
The GetTickCount function retrieves the number of milliseconds that have
elapsed since the system was started. It is limited to the resolution of the
system timer. If you need a higher resolution timer, use a multimedia timer
or a high-resolution timer.
</QUOTE>
Penso che per rendere l'idea GetTickCount() bastasse.
E poi per essere sincero non mi ha mai dato problemi. Ma cmq terro'
presente, grazie.
Ad ogni modo il tempo ottenuto non e' poi tanto importante nel mio esempio
visto che il codice assembly prodotto e' esattamente identico! Ovvio che
anche il tempo lo sara' ;-) sia usando GetTickCount() che qualsiasi altra
funzione.
Tommy

 wrote in message
news:b0ja7c$la2$1...@knossos.btinternet.com...


 Tommy
[OT]: mi ricordate come si fa lo swap con lo XOR, pliz?
Grazie,
    Rony
--
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 Scusa se mi son permessa...
No, anzi, ti ringrazio... diciamo la fretta... va... è un buon alibi...
Fortunatamente il mio programma "tenterà" di comprendere l'output generato
da un'altro programma che usa un linguaggio formale e non l'italiano...
Ciao.

 algoritmi (IMO).
Io sono --->>> d'accordo <<<--- (visto Marta che ho imparato???) sul tuo
ragionamento.
Io non ho perso tempo ad aggiungere una linea in più, semplicemente la prima
volta che ho testato la mia funzione avevo notato un risultato inatteso (che
invece poi era corretto... sbagliavo io!).
Mi è bastato aggiungere due parentesi per avere il vantaggio
dell'ottimizzazione (anche se praticamente ininfluente come hai dimostrato)
perdendo solo pochi secondi in più.
Io penso che le ottimizzazioni più importanti vadano fatte sull'algoritmo e
generalmente non perdo mai troppo tempo in fase di stesura
nell'ottimizzazione del codice.
Non penso che sia di grande difficoltà evitare una moltiplicazione tra
numeri interi, se poi anche dimentico una parentesi ho l'abitudine di
testare singolarmente tutte le funzioni che scrivo quindi me ne accorgo
subito se qualcosa non va, non aspetto di vedere il programma che non
funziona, intervengo prima.
Quindi se posso certe cose le sistemo subito, senza però perdere tempo
perché poi, l'attenzione per l'ottimizzazione (una volta che il programma è
terminato e funzionante) viene fatta su quel 5% di codice che impiega il 90%
del tempo dell'esecuzione.
Quindi o mi viene in mente un codice più veloce immediatamente mentre lo
scrivo oppure ci penserò eventualmente dopo... (spesso non li ottimizzo
nemmeno se l'applicazione non ha criticità riguardo la velocità o
l'occupazione in memoria).
Ciao.


Mi interessava questa parte in quanto, ricordo che una volta era possibile
utilizzare il profiler (forse quando ancora usavo il TurboC della Borland?).
Adesso come si fa a capire dove sta quel 5% di codice famigerato?
Ad esempio il VisualC++ o il DevC++ ti permettono di utilizzare un profiler?
Maurus

 Nicola
Ciao.

> Riguardo al mantenere il codice sarei svenuto anch'io^^;
Per cosě poco?? Allora non hai visto niente!
:)))))

 Maurus
Ciao!
Io l'ultima volta che ho usato il profile è stato tanti anni fa col mitico
Lattice C compiler (roba d'altri tempi... ma fantastico!), quando la vita
non era comoda come oggi, paradossalmente.
Adesso cerco d'andare a "naso", ovvero se l'algoritmo non è particolarmente
complesso lo intuisco con molta esperienza, altrimenti aiuto il naso con
qualche trucchetto (faccio una versione particolare, con le istruzioni del
pre-processore e aggiorno "statistiche" con del codice, che rallenta ma
"traccia" l'applicazione... poi basta una #define e la versione "speciale"
sparisce! Forse non è precisissimo però ti fai un'idea abbastanza
verosimile), immagino che ci siano strumenti appositi per i compilatori
commerciali blasonati ma onestamente non li ho mai nemmeno cercati.
Devo dire che dai tempi in cui programmavo su calcolatori con lo Z80 o con
il 6502 il profiler serve per fortuna meno però per certe, pochissime,
applicazioni effettivamente potrebbe di vitale importanza (penso a certi
driver o grafica ad altissimo livello e realismo).
Paolo Ferraresi.

hanno messo le parentesi)... 
Ho provato a cercare quell'articolo, e una volta trovato
gli ho dato una rapida occhiata. Secondo me si tratta di
spazzatura: quando non dice cose banali dice cose errate...
HTH
Andrea

> Io sono --->>> d'accordo <<<--- (visto Marta che ho imparato???)
Bravo Paolo!!!!!
;-)))))

 essere sbagliata ma spero che sia rispettabile e rispettata.
Il fatto che io esprima la mia opinione con decisione non vuol dire
che ritenga di aver sempre ragione a priori. In fondo il mio scopo non
e' convincerti della mia opinione, quanto convincerti a porti il
dubbio, e mi sembra di esserci riuscito ;-)
Ciao,
Nicola

 evitare moltiplicazioni inutili, per abitudine,
Abitudine abbastanza inutile.  Con i compilatori moderni serve solo a
rendere meno leggibile il codice.
Per esempio ecco il codice generato dal gcc 3.1:
Sorgente:
  int mul1(int x) { return x * 10; }
  int mul2(int x) { return (x << 3) + (x << 1); }
Assembly:
mul1:
	movl	4(%esp), %eax           // eax <- x
	leal	(%eax,%eax,4), %eax     // eax <- eax + eax*4    
	addl	%eax, %eax              // eax <- eax + eax      
	ret
mul2:
	movl	4(%esp), %eax           // eax <- x
	leal	(%eax,%eax), %ecx       // ecx <- eax + eax      
	leal	(%ecx,%eax,8), %eax     // eax <- ecx + eax*8
	ret
In nessuna delle due c'e` traccia di moltiplicazione e di shift.
"leal" e` un'istruzione pensata per calcolare l'indirizzo effettivo
partendo da base, offset e indice, e viene "riciclata" dal gcc par
fare i conti.
I tempi di esecuzione sono gli stessi in entrambi i casi.
        Mauro

 risulta più leggibile.
Non solo... Nei P4 il barrel shift register non esiste piu' (grazie Intel),
quindi quel codice costa PIU' cicli di quello che esegue la normale
moltiplicazione.
Ciaotutti,
*

 Poi, chiaro, del tempo preciso, nella discussione, chissene.
Il quote.
Grazie.
Prego.
*

 
uhm uhm...
a = a xor b
b = b xor a
a = a xor b
se ben ricordo.
Ciaotutti,
*