Confronto Complessità : risultato sbalorditivo

[3nigma666]

2 anni fa , avevo creato per l'università un programma che testava e calcolava, su vettori di numeri di numeri, il tempo di esecuzione dei piu famosi algoritmi di ordinamento:
quicksort , heapsort e insertionsort.

Oggi , a distanza di 3 anni ho deciso cosi di ricompilare e provare quel software (di cui andavo parecchio orgoglioso xkè curato anche nei piu piccoli dettagli)

L'ho eseguito ed ho ottenuto dei risulatati.
Dopo di che ho pensato: proviamo a vedere che tempi ho ottenuto 3 anni fa con il mio vecchio pc.
Premetto: ora ho un AMD 64 bit a 4400+ , mentre prima avevo un AMD a 2200+
Inoltre il sistema operativo sul 2200 era Xp, ora è Vista.

ecco che vi posto i risultati (una porzione) fatti prima con il 2200+ e poi con il 4400+

AMD 2200+: e Xp

OS: Win32
ALGORITMO QUICKSORT
Tempo Minimo: 0.300 sec, Tempo Totale Esecuzione: 475.901 sec
Ripetizioni: 97524; Dimensione Input: 200; Campioni: 100;
Media Tempo singolo Ordinamento: 0,000051078543067 sec; Intervallo di Confidenza: +- 0,000000739924645 sec
================================================================



AMD 4400+ e Vista :

OS: Win32
ALGORITMO QUICKSORT
Tempo Minimo: 0.020 sec, Tempo Totale Esecuzione: 36.803 sec
Ripetizioni: 8240; Dimensione Input: 200; Campioni: 100;
Media Tempo singolo Ordinamento: 0.000037430733442 sec; Intervallo di Confidenza: +- 0.000001859233387 sec
================================================================


Come potete vedere , come ci si poteva aspettare, il tempo di esecuzione del 4400 + è LEGGERMENTE PIU VELOCE (di primo acchitto) (Piu veloce di 1,36 volte)

http://www.v4l3rio83.altervista.org/media.jpg


Questi valori sono abb. coerenti. Infatti se eseguo un algoritmo prima su un computer e poi su un spercomputer, l'incremento prestazionale non è evidentissimo.(come in questo caso)
Se io invece eseguo un algoritmo (che calcola la stessa cosa, nel nostro caso l'ordinamento di un vettore) con complessità migliorata (tipo passo da un algoritmo di complessità O(n^2) a O(n) nel caso peggiore ) allora il tempo di esecuzione avrà un miglioramento DECISAMENTE MAGGIORE CHE NON NEL PASSAGGIO DA COMPUTER A SUPERCOMPUTER ..


Quello che mi ha sbalordito è ben altro...

Il tempo minimo calcolabile è passato da 0.300 sec di Windows Xp a
0.020 di Vista . Questo significa che l'orologio interno di vista ha una precisione migliore..
Nonostante questo l'Intervallo di confidenza di Xp è nettamente inferiore rispetto a Vista!

http://www.v4l3rio83.altervista.org/intervallo.jpg

Questo cosa vuol dire ?
Significa che Vista è risultato molto piu impreciso come orologio nella computazione. Infatti l'intervallo di confidenza indica l'errore (medio)che può esser commesso sulla misurazione del tempo necessario per fare un singolo ordinamento (sia in positivo che in negavito).
TRADOTTO, se al valore Medio per ogni singolo ordinamento io aggiungo (quindi considero il caso peggiore) il suo intervallo di confidenza, ottengo un tempo molto simile a quello ottenuto con l'AMD 2200+ !! :eek:


http://www.v4l3rio83.altervista.org/media.jpg
http://www.v4l3rio83.altervista.org/intervallo.jpg



Questo significa che esser passati da un 2200 a un 4400 non ha portato nessun vero significativo VANTAGGIO!


Nasco spontanea la mia domanda: PERCHE' COSTRUIRE PROCESSORI STRAVELOCI, quando alla fin fine , è risaputo che non apportano nessuna miglioria effettiva ! è solo business!?!?!
Perche non pensiamo ad ottimizzare gli algoritmi ?!?! solo in questa maniera si ottengono veri risultati..

[^TiGeRShArK^]

2 anni fa , avevo creato per l'università un programma che testava e calcolava, su vettori di numeri di numeri, il tempo di esecuzione dei piu famosi algoritmi di ordinamento:
quicksort , heapsort e insertionsort.

Oggi , a distanza di 3 anni ho deciso cosi di ricompilare e provare quel software (di cui andavo parecchio orgoglioso xkè curato anche nei piu piccoli dettagli)

L'ho eseguito ed ho ottenuto dei risulatati.
Dopo di che ho pensato: proviamo a vedere che tempi ho ottenuto 3 anni fa con il mio vecchio pc.
Premetto: ora ho un AMD 64 bit a 4400+ , mentre prima avevo un AMD a 2200+
Inoltre il sistema operativo sul 2200 era Xp, ora è Vista.

ecco che vi posto i risultati (una porzione) fatti prima con il 2200+ e poi con il 4400+

AMD 2200+: e Xp

OS: Win32
ALGORITMO QUICKSORT
Tempo Minimo: 0.300 sec, Tempo Totale Esecuzione: 475.901 sec
Ripetizioni: 97524; Dimensione Input: 200; Campioni: 100;
Media Tempo singolo Ordinamento: 0,000051078543067 sec; Intervallo di Confidenza: +- 0,000000739924645 sec
================================================================



AMD 4400+ e Vista :

OS: Win32
ALGORITMO QUICKSORT
Tempo Minimo: 0.020 sec, Tempo Totale Esecuzione: 36.803 sec
Ripetizioni: 8240; Dimensione Input: 200; Campioni: 100;
Media Tempo singolo Ordinamento: 0.000037430733442 sec; Intervallo di Confidenza: +- 0.000001859233387 sec
================================================================


Come potete vedere , come ci si poteva aspettare, il tempo di esecuzione del 4400 + è LEGGERMENTE PIU VELOCE (di primo acchitto) (Piu veloce di 1,36 volte)

http://www.v4l3rio83.altervista.org/media.jpg


Questi valori sono abb. coerenti. Infatti se eseguo un algoritmo prima su un computer e poi su un spercomputer, l'incremento prestazionale non è evidentissimo.(come in questo caso)
Se io invece eseguo un algoritmo (che calcola la stessa cosa, nel nostro caso l'ordinamento di un vettore) con complessità migliorata (tipo passo da un algoritmo di complessità O(n^2) a O(n) nel caso peggiore ) allora il tempo di esecuzione avrà un miglioramento DECISAMENTE MAGGIORE CHE NON NEL PASSAGGIO DA COMPUTER A SUPERCOMPUTER ..


Quello che mi ha sbalordito è ben altro...

Il tempo minimo calcolabile è passato da 0.300 sec di Windows Xp a
0.020 di Vista . Questo significa che l'orologio interno di vista ha una precisione migliore..
Nonostante questo l'Intervallo di confidenza di Xp è nettamente inferiore rispetto a Vista!

http://www.v4l3rio83.altervista.org/intervallo.jpg

Questo cosa vuol dire ?
Significa che Vista è risultato molto piu impreciso come orologio nella computazione. Infatti l'intervallo di confidenza indica l'errore (medio)che può esser commesso sulla misurazione del tempo necessario per fare un singolo ordinamento (sia in positivo che in negavito).
TRADOTTO, se al valore Medio per ogni singolo ordinamento io aggiungo (quindi considero il caso peggiore) il suo intervallo di confidenza, ottengo un tempo molto simile a quello ottenuto con l'AMD 2200+ !! :eek:


http://www.v4l3rio83.altervista.org/media.jpg
http://www.v4l3rio83.altervista.org/intervallo.jpg



Questo significa che esser passati da un 2200 a un 4400 non ha portato nessun vero significativo VANTAGGIO!


Nasco spontanea la mia domanda: PERCHE' COSTRUIRE PROCESSORI STRAVELOCI, quando alla fin fine , è risaputo che non apportano nessuna miglioria effettiva ! è solo business!?!?!
Perche non pensiamo ad ottimizzare gli algoritmi ?!?! solo in questa maniera si ottengono veri risultati..
:mbe:
veramente se adeguatamente ottimizzato per sfruttare il multi-threading il tuo programma col processore nuove avrebbe prestazioni + ke doppie.
E seguendo il tuo ragionamento a quest'ora saremmo ancora con macchine dalla potenza computazionale di un Intel 4004 :fagiano:
Ben venga l'innovazione nei processori :O

[3nigma666]

:mbe:
veramente se adeguatamente ottimizzato per sfruttare il multi-threading il tuo programma col processore nuove avrebbe prestazioni + ke doppie.
E seguendo il tuo ragionamento a quest'ora saremmo ancora con macchine dalla potenza computazionale di un Intel 4004 :fagiano:
Ben venga l'innovazione nei processori :O

Il multi-threading è una ottimizzazione SOFTWARE
parli esattamernte di ciò che dico io: miglioramento di algoritmo!
Quindi è ovvio l'incremento prestazionale!
Ma in termini di Mhz , l'ìaumento di essi cambia pochissimo ! anzi è quasi ininfluente !

[jappilas]

Il tempo minimo calcolabile è passato da 0.300 sec di Windows Xp a
0.020 di Vista . Questo significa che l'orologio interno di vista ha una precisione migliore.. veramente io sapevo di funzioni per misurare una differenza temporale tra due eventi, aventi precisione dell' ordine del decimo di microsecondo e implementate tramite l' utilizzo del time stamp counter della cpu , presenti in windows e altri OS già da molto prima di XP...
Questo significa che esser passati da un 2200 a un 4400 non ha portato nessun vero significativo VANTAGGIO! come benchmark non credo sia molto attendibile...
per dire, non hai fatto la prova di XP sul 4400... quindi non hai un' indicazione (almeno spannometrica) di quanto l' algoritmo scali con il numero di core in funzione del sistema operativo (e quindi dei suoi vincoli temporali)
Nasco spontanea la mia domanda: PERCHE' COSTRUIRE PROCESSORI STRAVELOCI, quando alla fin fine , è risaputo che non apportano nessuna miglioria effettivadi solito, per accelerare il software di cui si ha bisogno (che ovviamente è un sottoinsieme di tutto quello esistente ):O
Perche non pensiamo ad ottimizzare gli algoritmi ?!?!perchè ottimizzare non sempre conviene, questo in dipendenza di vari fattori
- non tutti i problemi computabili possono essere scomposti in thread di esecuzione multipli
- il tuo programma dipende quasi sempre da delle funzioni di sistema o di libreria, accedute tramite una API - l' implementazione di tali funzioni che l' interfaccia maschera, è spesso strutturata secondo una stratificazione inaggirabile (a meno di non usare una diversa interfaccia - a volte più ostica, quasi sicuramente non portabile), che può aggiungere overhead ma che comunque toglie al programmatore , il controllo sull' implementazione su cosa sta al di sotto di essa
(questo non tanto per l' annosa questione di codice aperto vs chiuso, quanto per il fatto che una interfaccia programmatica sia a tutti gli effetti un contratto in termin idi funzionalità e specifiche supportate)
- se ottimizzare significa ottenere prestazioni numeriche massime in senso assoluto, l' unica cosa da fare allora è eliminare i layer intermedi, eventualmente programmando in linguaggio assembly e ottimizzando direttamente la sequenza operativa, l' ordine e il numero dei salti, la località a livello sia di dati che di codice)
questo dovrebbe farti intuire che l' ottimizzazione "totale" è una chimera, inapplicabile laddove lo scopo è realizzare programmi sempre più funzionali, quindi sofisticati e complessi, nonchè sempre più interoperanti (quindi basati su standard e api comuni) che dovranno prima di tutto essere curati nel design complessivo e dopo, eventualmente, ottimizzati a livello di singoli sottosistemi
Il multi-threading è una ottimizzazione SOFTWARE
parli esattamernte di ciò che dico io: miglioramento di algoritmo!
Quindi è ovvio l'incremento prestazionale!portare delle strutture dati aventi complessità computazione O(n^2) a operare (a partità di funzione) con complessità O(n) o O(1) è un' ottimizzazione algoritmica
il multithreading non è una ottimizzazione ma un accorgimento strutturale, - tanto è vero che un sistema o un' applicazione intrinsecamente multithread prevede un maggior overhead di runtime (oltre a una difficoltà superiore di design e sviluppo)
overhead che è inerente dovuto alla sincronizzazione tra thread concorrenti e compensato in parte dalla scalabilità ottenuta
Ma in termini di Mhz , l'ìaumento di essi cambia pochissimo ! anzi è quasi ininfluente !invece, l' incremento nella frequenza di funzionamento beneficia l' esecuzione di qualsiasi tipo di applicazioni, a meno che queste non si trovino a raggiungere uno sweet spot dato da vincoli temporali interni o esterni (in tal caso e solo in tal caso i cicli macchina in più saranno cicli idle)
lo sweet spot però andrà determinato tramite profiling per la singola applicazione , quindi non ha senso generalizzare sulla base di una singola sull' evoluzione delle CPU general purpose...