Newsgroup: it.comp.hardware.cpu
Titolo: Appello all'intelligenza

Perché dobbiamo inseguire i produttori di hardware sulle frequenze dei
processori, quando la VERA tecnologia è costituita dal software?
E' vero, il processore è un oggetto, lo si tocca, è fisico, ma non è neanche
lontanamente paragonabile come incremento di prestazioni a un algoritmo
decente rispetto che un altro.
Un Athlon 10000 Mhz o Pentium III 10 GhZ alle prese con un algoritmo
insertion sort e con un array da 10 milioni di elementi non faranno meglio
di un Cyrix 133 con un quicksort e lo stesso array da 10 milioni di
elementi.
Anzi! Se il quicksort è randomizzato si avranno delle prestazioni nettamente
superiori con il sistema Cyrix (per quanto vecchissimo).
Meditate gente, meditate!
Il software può migliorare di ordini di grandezza molto superiori rispetto
all'hardware!
Un processore può diventare 100 volte più potente di un altro, ma sarà
sempre dello stesso ordine di grandezza!
Un algoritmo da complessità esponenziale può scendere a polinomiale al
quadrato e si avrebbe un incremento sui grandi numeri che neanche in 100
anni di evoluzione fisica dell'hardware!
Perché non c'è un minimo di ribellione e anche gli sviluppatori seri
preferiscono aspettare l'hardware piuttosto che inventare software
decente???
Ciao a tutti,
giovann...@libero.it

in effetti e' vero.
Ma questa storia l'ho gia' letta sul mio libro di algoritmi I  :)
CIAO!

 wrote in message
0i1o4.95627$C3.10...@news.infostrada.it...


Insomma, pare che non ci sia speranza!!
Non c'e` speranza se si estremizza in questo modo, la virtu` sta nel
mezzo. Ci sono delle cose per le quali e` assolutamente richiesto
l'assembly perche` serve un controllo a basso livello del processore, ad
esempio il codice per il context switching del SO.
Per tutto il resto andare a mano oltre che essere una perdita di tempo
e` praticamente impossibile.
Il vecchio sogno di un assembler object oriented e` ancora lontano.
-- 
Lorenzo
"Given enough eyeballs, all bugs are shallow", Linus'Law
(per rispondere via email fai un rot13 dell'indirizzo)
(apply a rot13 to reply)

Giovanni wrote:
Nulla da eccepire...
Solo un appunto: Amiga Docet! :)
-- 
 _______________________________________________________________
|                                                               |
| Posted By 41 (Marco Casavecchia)                              |
| E-Mail: 
mar...@libero.it
 (Prefisso 071 ;-)                   |
|_______________________________________________________________|

Lorenzo, mi sa che abbiamo sbagliato...
Il msg iniziale non voleva discutere sull'ottimizzazione del codice macchina
da parte dei compilatori. Il thread era partito con un'altra idea, quella di
abbassare la complessità asintotica degli algoritmi. Scegliere gli algoritmi
"giusti", quindi, ed inventarne sempre di migliori, perché se un ordimanento
di un (grande) array viene fatto con un algoritmo non asintoticamente
ottimo, anche un Coppermine 733 + Rambus serviranno a poco.
Sinceramente non so se i programmi commerciali più famosi usino algoritmi
tanto "scandenti". Io credo di no. Insomma, non ci vuole tanto a ordinare
una lista di nominativi con il quick sort! Ci sono anche delle strutture
dati (alberi AVL, heap di Fibonacci) che sono piuttosto complesse ma che
sono molto utili per certe operazioni (in particolare, gli heap di Fibonacci
abbassano la complessità asintotica di alcuni algoritmi sui grafi). Credo
che esistano dei manuali in cui sono descritti in dettaglio sia queste
strutture, sia questi algoritmi sui grafi. Quindi non capisco come dei
programmatori esperti debbano non utilizzarli...
Esistono operazioni che sono comunque "costose"... Se vuoi ordinare un
array, non puoi farlo in meno di logn e se l'array è dannatamente grosso,
c'è poco da fare. Anche per altri algoritmi sono stati trovati dei limiti
inferiori. In questi casi l'unica cosa che ci rimane è abbassare le
costanti: non avremo risultati tanto impressionanti... Ma che volete... !
:-)
Attendo conferme e/o smentite per quanto ho detto!
Marco77

basta vedere quello che puo fare una buona ottimizzazione 3dnow!
(driver voodoo3) o un buon motore grafico (quake3) o un gioco fatto
bene (i vari nukem...giravamo da dio full detail sul mio 486!!)
--
*******************************************************************
"La vanità è il mio peccato preferito" John Milton
visita la mia homepage su Friends:
http://come.to/friendsitaliabis
http://www.geocities.com/pamperoloco
Tutto quello che hanno detto i comunisti sul comunismo è falso
ma tutto quello che hanno detto i comunisti sul capitalismo è vero.
*******************************************************************

Attendo conferme e/o smentite per quanto ho detto!
Confirm.


 Ma questa storia l'ho gia' letta sul mio libro di algoritmi I  :)
Hai ragione, il mitico Cormen, Leiserson, Rivest :)
Ciao
Paolo

 Lorenzo

Perchè è più facile e comodo acquistare una cpu più potente che scervellarsi
per inventare qualcosa di nuovo.
Ecco perchè i giochini per Playstation sono così geniali e hanno prestazioni
incredibili e quelli per PC invece pur avendo un hardware 20 volte più
potente non sono proporzionalmente migliori.
Più andiamo avanti con le cpu e più il software sarà fatto con i piedi !
Belli in tempi in cui si riusciva a fare un programma eccellente nello
spazio di pochissimi Kb !
Adesso sembrano pochi 64 Mb.... se fossero ottimizzati ne basterebbero 16
!!!
Ciao

asintotico inferiore per l'ordinamento di array non è logn ma nlogn!!
Beh dipende, si puo` fare anche in O(n).


 Beh dipende, si puo` fare anche in O(n).
Uh?
Ordinare un array in O(n)? Come?
Se e` gia` ordinato? (O(n) serve per vedere che e` ordinato).
La cosa mi interessa particolarmente.
bye,
--
  Piergiorgio Sartor

La cosa mi interessa particolarmente.
Do you know counting sort? radix sort?
Se e` noto il range degli elementi da ordinare (es: valori a 32 bit)
si puo` ordinarli in O(n).
Pero` in pratica non conviene perche` hanno una costante molto elevata
dovuta a numerosi accessi alla memoria, molti di piu` del qsort.


Ringrazio tutti per le vostre opinioni al riguardo ma non intendevo
scatenare un flame.
Ritenevo erroneamente che su questo newsgroup ci fosse un 90% di
tecnologicisti, invece noto con piacere che siete tutti
molto preparati (molto più di me sicuramente) sia sugli aspetti hardware che
su quelli software.
C'è da dire, comunque, a favore dei tecnologicisti che certi giochi tipo
Quake, Unreal, Urban Chaos etc... non sarebbero stati neanche immaginabili
come disegno di copertina delle scatole o quasi come scene statiche di
caricamento fino a un po' di anni fa... E ritengo che tutto ciò non sia
dovuto solo ad un miglioramento delle tecniche programmatorie (comunque i
vari motori grafici sono tecnologia pura secondo me) ma sicuramente su tutto
ciò incide l'incremento delle prestazioni di cpu e ammenicoli vari.
Ciao a tutti e continuate a tenervi informati come ora, magari cercate anzi
di informare tutta la gente "sprovveduta" che trovate in giro perché
purtroppo l'informatica è un mondo che si è talmente recentemente aperto al
vastissimo pubblico che le fregature sono dietro ogni angolo.
giovann...@libero.it

 dovuta a numerosi accessi alla memoria, molti di piu` del qsort.
Alt, O(x) include gli accessi in memoria.
Diciamo che con O(n) intendo TUTTE le operazioni necessarie.
Mi sa che radix sort ritorna O(n^2), in questo caso, ma non
sono sicuro.
bye,
--
  Piergiorgio Sartor


Tutte le operazioni sono O(n) comprese gli accessi alla memoria.
Forse intendevi O(k*n) ?


 Forse intendevi O(k*n) ?
Forse hai ragione, e` O(k*n).
Il problema e` il seguente e le soluzioni della letteratura
non comprendono il radix-sort:
Ho una lista (array o quello che si preferisce) di byte
(8 bit, quindi), devo trovare quello che sta "in mezzo".
Cioe` devo ordinare la lista, che sara` sempre di 2n+1
elementi, e prendere il n+1-esimo.
In letteratura si usa qsort, per "n" grande e bubblesort
per "n" piccolo.
Naturalmente "potando" le scelte ormai inutili, quindi
riducendo la complessita`.
Esistono soluzioni "ottimizzate" per esempio per n=4
(9 elementi), che sono derivate dal bubblesort, in fin
dei conti, ma mai ho letto di radix-sort per questo problema.
Ho letto di insertion-sort (!), pero`.
Ora mi chiedevo se per n=7 o n=9 vi fossero soluzioni
interessanti, anche a discapito della memoria, ma non
della velocita`.
bye,
--
  Piergiorgio Sartor


Non saprei, comunque se n e` piccolo (7 o 9) credo che convenga
analizzare i casi con dei if-then-else uno dentro l'altro, tanto
n e` piccolo.
E` una soluzione "brutta" ed ad hoc ma credo sia la piu` veloce.
Ok, siamo un tantino off topic qui, o ci spostiamo o continuiamo
in privato.


decente???
perche' in genere non lo fanno, mi pare semplice.
microsoft a parte, tutti i produttori di soft fanno dei programmi quanto
piu' efficienti possibili nelle loro capacita', e' nel loro interesse....
---
    (iao!!oai)                                    (ICQ: 10860566)
    //.aurizio
    I bimbi buoni vanno in paradiso.
    I bimbi cattivi vanno dove gli pare!

Mai sentito parlare di portabilita` del codice?
e l'ottimizzazione allora dove finisce?
o hai l'una o hai l'altra.
Java e' (relativamente) lentissimo perche e' (relativamente) portabile.
e, appunto, la portabilita' e' molto piu' importante, che me ne faccio di
aver passato gli ultimi due mesi ad ottimizzare il mio gioco per farlo
girare su una macchina con PII400 e TNT quando su tutte le altre macchine
non gira?


Solo un appunto: Amiga Docet! :)
di fatti e' fallita.
e dico questo da amighista convinto, dopo anni ed anni passati a combattere
l'hardware bashing e la programmazione system-killer.
ma non ti pare assurda una macchina in cui nel passaggio dal s.o. 1.2 al
1.3 il 70% del software ha smesso di funzionare? (quello scritto secondo
specifiche Commodore ovviamente non dava problemi)
che per piantare un gioco basti avere mezzo mega di ram in piu'? 
oppure un 68020 invece del 68000?
oppure un chipset appena lievemente diverso? (ecs, figuriamoci con l'aga)
proprio per questo l'amiga e' morta (gestione economica assurda a
parte...), perche' nessuno dei videogiocatori (che sono sempre stati la
maggior parte degli utenti, noi smanettoni coprivamo si e no il 2% del
mercato Amiga) voleva comprarne versioni nuove, sapendo che avrebbero avuto
problemi di compatibilita' enormi, e se nessuno compra computer, chi li
vende fallisce.
ora quello era il mercato amiga, dove venivano usati quattro tipi diversi
di cpu (68000, 68020, 68030, 68040 (contando solo le offerte ufficiali
commodore), tre tipi di chipset (ocs, ecs, aga) e quattro versioni del s.o
(1.2, 1.3, 2.0, 3.0 (identica alla 2.0 apparte il supporto aga) neppure poi
tanto differenti fra di loro.
passiamo al mercato x86, quanti processori dobbiamo considerare? dall'8088
ai k7, ovviamente. quante schede grafiche? dal video monocromatico dei "pc"
ibm (antecedente alle cga di parecchio....) alle schede professionali di
Evans&Southerland, quanti s.o.? quante configurazioni audio? quante
configurazioni di memoria?
bene, scrivi il tuo bel programma in hardware bashing e OTTIMIZZAMELO PER
TUTTE LE COMBINAZIONI POSSIBILI, quando avrai finito vediamo quali sono i
risultati e riparliamone.... (sette o ottomila anni dovrebbero bastarti
cosi' ad occhio....)


Java e' (relativamente) lentissimo perche e' (relativamente) portabile.
Java e` bytecompilato, io parlavo di C/C++.
Se il programmatore e` bravo scrive una sola versione che poi puo`
essere compilata con pochissime modifiche su altri SO.


 !!!
Beh, dai tieni presente che la memoria non e' occupata poi piu' di tanto dal
codice, in un gioco, ma dalle textures (e quelle non le posso
ridurre,se le comprimo poi le dovro' decompattare...sprecando potenza di
calcolo), dal sonoro 16bit 44khz ecc...
Il codice -voglio sperare- e' ancora realtivamente poco ingobrante.
--
ByE,
Kvochur
*************************************
ICQ                       16656093
E-Mail          
kvoc...@yahoo.com
Homepage 
http://highflight.cjb.net/
*************************************

 Il codice -voglio sperare- e' ancora realtivamente poco ingobrante.
Vero, ma in mem codice non ne finisce, il probl sono le variabli.

 Lorenzo

 in privato.
In effetti, anche se tempo fa, mi pare, ci sia stata una
discussione sugli scacchi e persino una sui numeri
transfiniti...
bye,
--
  Piergiorgio Sartor


A beh allora :-)


Java e` bytecompilato, io parlavo di C/C++.
che sono portabili solo sulla carta - per scriverci programmi veramente
portabili devi rinunciare a tutti i trucchetti che ti danno velocita'.


 portabili devi rinunciare a tutti i trucchetti che ti danno velocita'.
A meno che tu non faccia una bella analisi isolando le ottimizzazioni e
riscrivendo solo quelle Linux docet.
Cmq basta compilare java.

 portabili devi rinunciare a tutti i trucchetti che ti danno velocita'.
Più che altro per avere una buona portbilità sei costretto a usare solo
librerie standard/ISO... e i grossi problemi si vedono quando devi creare
l'interfaccia con l'utente.
Prova a disegnare una tabella a forza di puts(), printf(), ecc...
--
________________________________
Togliete NoSpaM per rispondermi
bye Brain

 Dove posso trovarne?
Prova sul sito della Intel: sono anni che produce merda!
Più biologiche di così! ^_^
m[a]v @ AzzurraNet || 
mav...@yahoo.com
 || ICQ UIN# 22579106
*****************************************************

 neppure Java Script e' portabile senza fare i salti mortali, figuriamoci...
(Con un minimo di accortezza non ci sono probl, certo che se vuoi frae una
cosa molto dinamica, tutta a run time ...)

 *****************************************************
ma io non dimentichero mai certi giochi fantastici del mio commodore 64...... ;-)
SAluti
Makarenko