Analisi e Confronto dei Generatori di Codice C/C++ dei Compilatori GCC, SAS/C e StormC di Bernardo Innocenti Lo scopo di questo articolo non e' determinare quale tra i compilatori C/C++ per Amiga sia il migliore in assoluto o il piu' adatto ad un certo tipo di sviluppo. Paragoni di questo tipo vengono fatti da sempre nei newsgroups ed e' mio parere che queste discussioni siano del tutto superflue, in quanto finiscono quasi sempre per sfociare in interminabili guerre sante. Come per la maggior parte delle scelte personali, quella del compilatore preferito non e' meno soggetta al gusto e all'esperienza personale di quanto non lo sia la scelta di un paio di scarpe. In questa analisi ci concentreremo esclusivamente sul funzionamento interno dei compilatori e sulla qualita' del codice da essi generato, tralasciando tutte le altre caratteristiche che contraddistinguono questi prodotti: comodita' e integrazione dell'ambiente di sviluppo, qualita' della documentazione, prezzo al pubblico e cosi' via. Attualmente esistono tre compilatori C/C++ per Amiga tuttora in fase di sviluppo e altrettanti non piu' sviluppati. Riassumiamone brevemente le caratteristiche. o SAS/C E' di gran lunga il piu' antico compilatore per Amiga. Il SAS/C e' erede del piu' antico Lattice C, che a sua volta deriva dal primordiale Amiga C, il compilatore che fu utilizzato per sviluppare le prime versioni di AmigaOS. Questo compilatore fu poi acquistato dal SAS Institute, che lo aggiorno' rilasciando le versioni 6.0 e 6.50. Qualche anno dopo, in seguito al drammatico fallimento di Commodore, SAS decise di interrompere lo sviluppo della versione Amiga. Fortunatamente i tre programmatori che se ne occupavano chiesero ed ottennero il permesso di continuare a rilasciare aggiornamenti gratuiti in favore degli utenti, giungendo cosi' all'attuale versione 6.58. Recentemente, mossi dalla vivace capacita' degli sviluppatori Amiga nel riportare i problemi presenti nel compilatore, i dirigenti della SAS sembrano voler ritornare sulle proprie decisioni. Intanto Steve Krueger continua a fornire aggiornamenti e ha annunciato di voler aggiungere il supporto del PowerPC nel prossimo futuro. o Storm C Prodotto da Haage & Partner questo giovane compilatore e' nato due anni fa ed ha raggiunto in breve tempo un notevole livello qualitativo. Recentemente e' stato dotato del supporto per PowerPC e per pOS. Il compilatore supporta il C++ in modo nativo e compila l'ANSI C come un caso particolare del C++. Per facilitare il porting di applicazioni Amiga scritte con SAS/C lo Storm C supporta la maggior parte delle keyword specifiche per Amiga che permettono di effettuare chiamate con i parametri nei registri e gestire funzioni --callback--. o GCC Il progetto Geek Gadgets (un tempo chiamato ADE) coordinato da Fred Fishtra le applicazioni portate su Amiga e messe gratuitamente a disposizione di tutti gli sviluppatori annovera il compilatore C/C++ GNU. Il GCC e' un compilatore multipiattaforma sviluppato dalla Free Software Foundation, progettato per essere altamente portabile, è famoso sui sistemi derivati da UNIX al punto da essere considerato da tutti "IL" compilatore C di UNIX. Su Amiga si distingue da tutti gli altri compilatori per l'assenza totale di un ambiente integrato e di una interfaccia utente grafica. Pero', su un piano strettamente tecnico, il GCC e' tra i piu' completi compilatori esistenti: introduce un vasto numero di estensioni al linguaggio originale e supporta in modo esaustivo anche C++ e Objective C (che non e' disponibile in nessun altro compilatore per Amiga). o Aztec C Si tratta di un compilatore oramai non piu' sviluppato. Sviluppato da Manx, era il diretto concorrente del Lattice C, ed era basato su interi a 16bit, come del resto il Lattice C. Come il GCC questo compilatore permetteva di inserire assembler in linea nel codice C. Molte applicazioni famose per Amiga furono sviluppate con questo compilatore, tra cui il Cygnus ED, Mandel 2000 e il software di BBS Dialog Pro. o DICE Il compilatore C creato dal celebre Matt Dillon venne dapprima distribuito nel pubblico dominio e in seguito divenne un prodotto commerciale a basso costo. Recentemente Matt Dillon ha deciso di renderlo nuovamente pubblico, rilasciando anche sorgenti e documentazione completa (1). L'autore ha cosi' concesso a tutti di studiarne le caratteristiche di DICE ed eventualmente di sviluppare futuri aggiornamenti. Forse il tool più interessante tra quelli forniti con DICE era dmake, la piu' flessibile e completa tra tutte le utility make fornite a corredo dei compilatori per Amiga. o Maxon C Questo compilatore C/C++ non e' mai stato molto diffuso al di fuori della Germania. Maxon ne ha interrotto lo sviluppo due anni fa dopo il rilascio della versione 4.0PRO e corre voce che lo StormC sia stato sviluppato sulle basi di questo compilatore. I test da me condotti si riferiscono ai seguenti compilatori: StormC V2.0.23 SAS/C 6.58 GCC 2.7.2.1 (GeekGadgets snapshot 970928) --footnotes-- (1) I sorgenti della versione 3.20 sono disponibili su Aminet e all'URL http://www.obviously.com. Fasi della Compilazione ======================= Normalmente un compilatore C/C++ e' composto da cinque o sei stadi successivi che permettono di generare un eseguibile a partire da uno o piu' file di testo contenenti sorgenti in C o C++. I compilatori moderni tendono ad occultare o fondere assieme alcune di queste fasi per ragioni di efficienza. 1 - Preprocessore Il sorgente viene analizzato dal preprocessore C, che risolve le inclusioni dei file header e sostituisce le definizioni e le macro con i valori ad esse assegnati. Il preprocessore produce in uscita un sorgente C privo di costanti simboliche e dei blocchi che sono stati esclusi da #if e #ifdef. Il sorgente C preprocessato contiene inoltre i riferimenti ai file e ai numeri di linea originali, in modo che il compilatore possa riportare informazioni corrette nel segnalare gli errori. Nel GCC, il preprocessore e' un eseguibile distinto chiamato cpp (C PreProcessor) che puo' essere utilizzato per elaborare qualsiasi file di testo, come ad esempio un Makefile oppure uno script di shell. 2 - Frontend C++ Alcuni compilatori C++ (e' il caso del SAS/C) analizzano il sorgente con un frontend in grado comprendere la grammatica del C++ e di generare il codice ANSI C necessario per implementare quanto richiesto dal sorgente originale. L'output del frontend viene poi compilato dal compilatore C standard. Questo approccio e' generalmente piu' lento e spesso produce codice meno efficiente rispetto al supporto diretto del C++, come nel caso di StormC, GCC e della maggior parte dei compilatori moderni. Tra i frontend e' noto il CFront di AT&T, che forniva la prima implementazione in assoluto del linguaggio C++. 3 - Parse Questa fase viene spesso chiamata "fase 1" nei compilatori a due passi. Il compilatore analizza l'intero sorgente, controllandone la correttezza sintattica, e crea un albero contenente tutti i simboli e altri dati necessari alla compilazione. Nel SAS/C, questa fase e' racchiusa all'interno della libreria condivisa sc1.library. Se questa fase e' separata da quella successiva (generazione del codice), l'output consiste in un file binario contenente le cosiddette "quadruple". Questo pseudo-linguaggio e' costituito da una sequenza di istruzioni elementari ognuna delle quali contiene quattro parametri: [operatore, operando 1, operando 2, destinazione]. Il GCC usa invece un formato chiamato RTL (Register Transfer Language) per memorizzare il codice intermedio. In entrambi i casi, dato che il compilatore non ha ancora assegnato un indirizzo alle variabili e alle funzioni, gli operandi di queste meta istruzioni sono ancora espressi simbolicamente. Si tratta di qualcosa di molto simile al P-code del Pascal o al piu' noto byte-code del Java. Le quadruple e gli altri sistemi analoghi sono indipendenti dall'architettura del microprocessore per il quale verra' generato il codice e dal linguaggio che e' stato utilizzato per produrle. Questo approccio semplifica la creazione di compilatori modulari che supportano piu' linguaggi e producono codice per molti microprocessori diversi. Gli ottimizzatori globali dei compilatori operano principalmente su informazioni ricavate in questa fase al fine di ridurre il numero complessivo delle operazioni tenendo conto di vari fattori che ancora non dipendono dall'architettura del microprocessore. 4 - Generazione del codice La fase 2 della compilazione trasforma le quadruple in un sorgente assembler o direttamente in linguaggio macchina. Alcuni compilatori riesaminano il codice prodotto con un ottimizzatore specifico detto --peep-hole optimizer-- (ottimizzatore del buco di serratura). Questa tecnica e' in grado di individuare brevi sequenze di codice inefficienti e sostituirle con altre migliori, eventualmente sfruttando le caratteristiche specifiche del microprocessore per il quale viene compilato il codice, accorpando due o piu' istruzioni in una sola istruzione piu' complessa o ricorrendo a modi di indirizzamento piu' sofisticati. SAS/C e GCC hanno entrambi un peep-hole optimizer piuttosto evoluto. StormC non ne ha bisogno dato che il compilatore e' in grado di generare direttamente istruzioni che accorpano piu' funzioni elementari. 5 - Assemblatore Il GCC produce sempre un sorgente assembler che viene poi passato all'assemblatore di sistema (as). Questo approccio e' ovviamente piu' lento rispetto alla generazione diretta del codice macchina, ma non di molto: il tempo richiesto dall'assemblatore in genere e' trascurabile rispetto alle altre fasi della compilazione. Inoltre, la possibilita' di far rielaborare l'output del compilatore ad un assemblatore consente di inserire agevolmente istruzioni assembler in linea al codice C. Lo StormC prevede invece un output assembler commentato fra le opzioni utili per il debug e per l'ottimizzazione manuale del codice prodotto. 6 - Linker L'output delle fasi precedenti e' un file oggetto nel formato tipico del sistema operativo, che in genere e' indipendente dal particolare linguaggio e dallo specifico compilatore utilizzato. Nel caso di Amiga, questo formato viene chiamato "hunk format", composto da diversi sezioni di codice e dati di vario genere chiamati appunto "hunks". Questo formato e' molto simile a quello degli eseguibili veri e propri: manca soltanto l'hunk header e compaiono degli hunk aggiuntivi che servono al linker per unire insieme piu' moduli e formare un unico programma. Oggetti e librerie statiche contengono al loro interno i nomi dei riferimenti esterni e gli offset in cui questi simboli devono essere sostituiti con il loro indirizzo finale dopo il caricamento in memoria. Il GCC attualmente non genera direttamente oggetti in formato hunk, (ne esiste gia' una versione alpha che implementa questo formato, ma non e' ancora utilizzabile). Il formato in uso e' il classico --a.out--, molto diffuso nella maggior parte dei sistemi UNIX. L'uso del formato a.out rende di fatto il GCC incompatibile con tutti gli altri compilatori e linker per Amiga. Sebbene esistano delle utility di conversione come --hunk2aout--, di fatto la scelta del GCC impedisce il piu' delle volte al programmatore di usare dei tool di sviluppo al di fuori della suite GeekGadgets. Lo StormC possiede invece uno dei linker piu' flessibili tra quelli disponibili per Amiga. Insieme al PhxLnk, e' l'unico a produrre gli hunk di tipo reloc_32c. Altra caratteristica unica dello StormLink e' la possibilita' di individuare ed eliminare parti di codice identiche e di ottimizzare i riferimenti tra moduli quando e' possibile fare uso degli offset a 16bit al posto di un indirizzamento assoluto. Il GCC e' l'unico compilatore in cui ben quattro delle sei fasi della compilazione sono state rese esplicite. Cio' significa che sono presenti altrettanti eseguibili indipendenti tra loro. Mancano solamente i frontend C/C++, che sono integrati in un unico eseguibile insieme al backend che genera il codice per il sistema target. Del resto, frontend e backend sono del tutto disgiunti a livello logico ed e' dunque possibile ottenere una qualsiasi combinazione dei due ricompilando il compilatore stesso in una configurazione differente. Il programma di controllo "gcc" si limita ad esaminare gli argomenti sulla linea di comando e quindi eseguire le parti del compilatore che sono coinvolte nella compilazione, le quali comunicano tra loro tramite un pipe multiplo. In pratica, scrivere: gcc foobar.cpp omettendo le opzioni aggiuntive richieste dai comandi per funzionare correttamente, e' equivalente a: cpp a.out Tra tutti i compilatori C++ Amiga, il GCC e' l'unico a prevedere tutte le estensioni piu' recenti del linguaggio, permettendo dunque cosi' di scrivere programmi C++ che utilizzano la Standard Template Library (STL), la libreria orientata alla programmazione generica che dipende pesantemente dai template, e da altre estensioni piu' occulte introdotte nel C++ dal comitato di standardizzazione del linguaggio (2). Inoltre il compilatore viene distribuito con la libreria di classi libg++ che contiene un set molto esteso di classi di base. La complessita' delle operazioni compiute dal GCC per produrre un eseguibile partendo dal sorgente ne giustifica ampiamente la lentezza rispetto agli altri compilatori per Amiga. Il manuale del GCC contiene un interessante capitolo che descrive dettagliatamente tutti i passaggi della compilazione. Si tratta di una lettura molto istruttiva alla quale vi rimandiamo se desiderate approfondire l'argomento. --footnotes-- (2) vedi http://www.sgi.com/Technology/STL/. L'allocazione dei registri ========================== Una delle fasi piu' delicate della generazione del codice e' la scelta dei registri da usare per memorizzare le variabili e i risultati intermedi delle espressioni. Una scelta poco oculata da parte dell'ottimizzatore ha come inevitabilmente conseguenza un decadimento delle prestazioni del codice. Alcuni compilatori allocano i registri in modo statico per ciascuna funzione, producendo risultati mediocri nel caso di funzioni piu' complesse con molte variabili. Altri sono in grado di analizzare il flusso del programma per decidere quali variabili convenga spostare nei registri, e quale sia il momento piu' adatto per farlo. Per fortuna il 68000 ha un design piuttosto ortogonale rispetto agli altri CISC. Dispone infatti di un abbondante numero di registri general pourpose, tutti della stessa dimensione (32bit) e utilizzabili liberamente con la maggior parte delle istruzioni e dei modi di indirizzamento. I registri del 68000 si dividono in due gruppi: registri dati e registri indirizzi. Molte istruzioni possono operare indistintamente con qualsiasi registro, altre invece richiedono tassativamente un registro dati o uno indirizzi. Questo e' il solo vincolo di cui un compilatore per 68000 deve tener conto durante l'allocazione dei registri. Altri microprocessori piu' diffusi, per non fare nomi, soffrono invece di una penuria di registri aggravata dal fatto che quasi tutte le istruzioni operano soltanto su un unico registro (una antica tradizione che nasce con le prime ALU basate sul concetto di accumulatore). L'ambiente di sviluppo dello StormC prevede ben nove diversi livelli di ottimizzazione del codice, per ognuno dei quali viene fornita una descrizione sommaria del tipo di ottimizzazioni possono essere attivate. Questa ricchezza di opzioni potrebbe far pensare che la scelta dei registri verra' svolta in modo ottimale al livello di ottimizzazione massimo, cosa che di fatto non accade. Il backend 68000 dello StormC segue una politica di allocazione dei registri piuttosto ingenua, con frequenti spostamenti di dati da un registro all'altro e dai registri alla memoria. Ecco una tipica sequenza di istruzioni generate dallo StormC: if (result = foobar(param)) { ... } pea param ; mette param sullo stack bsr foobar ; chiama foobar() move.l d0,a3 ; sposta il risultato in A3 addq.w #4,sp ; ripristina lo stack pointer move.l a3,a0 ; sposta di nuovo il risultato in A0!! cmp.w #0,a0 ; controlla che sia diverso da 0 beq.s endif ; se e' 0, salta a endif move.l a3,a1 ; sposta per la terza volta il risultato!! ... Tutto questo poteva facilmente essere riassunto in: pea param ; mette param sullo stack bsr foobar ; chiama foobar() tst.l d0 ; controlla il risultato lea 4(sp),sp ; ripristina lo stack pointer beq.s endif ; se e' 0, salta a endif ... SAS/C e GCC usano invece degli algoritmi molto piu' sofisticati e in molti casi riducono al minimo il numero di spostamenti superflui. Gestione dello stack ==================== Ogni funzione che dichiara delle variabili locali ha bisogno di una certa porzione di stack in cui memorizzarle. Se il numero delle variabili e' ridotto e il compilatore e' abbastanza intelligente, e' possibile che tutte le variabili vengano mantenute nei registri. Negli altri casi, il compilatore deve far riferimento alle variabili con un offset rispetto allo stack pointer (SP). Purtroppo non e' sempre garantito che lo stack pointer mantenga un valore costante nel corso della funzione: qualsiasi inserimento successivo sullo stack sposta in avanti il puntatore e ciò costringe il compilatore a tenerne conto nei successivi accessi alle variabili. Per esempio, una variabile che si trovava all'offet 12 rispetto allo stack pointer, in seguito ad un push si troverebbe all'offset 16 (di norma ogni inserimento sullo stack e' lungo 4 byte). Tutto cio' introduce una certa complicazione che non tutti i compilatori sono in grado di gestire. Molti compilatori dedicano un registro indirizzi (tipicamente A5) a puntatore all'area delle variabili locali sullo stack (frame pointer), sottraendo in questo modo un altro registro all'ottimizzatore. Il problema puo' sembrare di poco conto, ma si deve considerare che i registri indirizzi sono in tutto 8 e che A7 e' lo stack pointer, A6 su Amiga e' usato per la base delle librerie dinamiche, mentre A4 e A5 sono rispettivamente il puntatore alla sezione dati near e il frame pointer. Visto che A0 e A1 sono registri scratch e sono spesso usati per il passaggio dei parametri nei registri, in questo scenario rimangono soltanto due registri liberi: A2 e A3. Il 68000 prevede due istruzioni di supporto per i linguaggi di alto livello che semplificano le operazioni di gestione del frame. L'istruzione LINK memorizza in un registro indirizzi il contenuto di SP e quindi lo sposta in avanti di un valore specificato dall'istruzione stessa, creando cosi' un'area sullo stack dedicata alle variabili locali. L'istruzione UNLK (unlink) esegue l'operazione inversa e serve a riposizionare lo stack al suo valore originale prima di uscire da una funzione. Sia lo StormC sia il GCC utilizzano LINK e UNLK come descritto, mentre il SAS/C dalla versione 6 e' in grado di calcolare dinamicamente l'offset delle variabili rispetto a SP e non usa piu' A5 come frame pointer. Il GCC riesce comunque a compensare questo svantaggio usando alcuni accorgimenti nella gestione dello stack. Nel C per convenzione il passaggio dei parametri alle funzioni avviene inserendoli sullo stack in ordine inverso (da destra verso sinistra) ed e' compito del programma chiamante rimuovere dallo stack tutti i parametri quando la funzione ritorna. Per fare un esempio: ; sprintf (str,"un %s ha %d zampe", animale, nzampe); move.l nzampe,-(sp) ; mette nzampe sullo stack pea animale ; mette animale sullo stack pea format ; mette la stringa costante sullo stack pea str ; mette str sullo stack bsr sprintf ; chiama sprintf() lea 16(sp),sp ; elimina i parametri dallo stack (16 bytes) E' piuttosto raro che il codice prodotto dal GCC debba togliere dallo stack i parametri passati alle funzioni in questo modo. Il GCC lascia che lo stack cresca sempre di piu' dopo ogni chiamata e ne ripristina il valore originale con UNLK quando la funzione principale termina (3). Questo e' uno dei motivi per cui i programmi compilati con il GCC richiedono in genere molto stack: su UNIX quando è necessario lo stack viene esteso automaticamente dal sistema operativo e il GCC se ne avvantaggia per poter produrre codice piu' efficiente. Il GCC per default insiste nell'usare LINK e UNLK anche nel prologo e nell'epilogo delle funzioni che non definiscono alcuna variabile locale. Non e' raro imbattersi in sequenze di questo tipo: foobar: link a5,#0 ; inutile move.l 8(a5),a0 ; preleva il primo parametro dallo stack ; (avrebbe potuto usare "move.l 4(sp),a0") move.l 12(a5),d0 ; preleva il secondo parametro dallo stack ; (avrebbe potuto usare "move.l 8(sp),d0") ... ; corpo della funzione unlk a5 ; inutile rts Questo comportamento viene mantenuto in tutti i livelli di ottimizzazione perche' garantisce che i debugger simbolici siano sempre in grado di accedere alle variabili locali, ma puo' essere facilmente soppresso con lo switch -fomit-frame-pointer, che sul 68000 ha un effetto benefico sulle prestazioni. --footnotes-- (3) L'opzione che controlla questa caratteristica e' -fdefer-pop. Il codice invariante ==================== I compilatori moderni sono in grado di individuare all'interno dei loop le istruzioni che non e' necessario ripetere ad ogni ciclo e che possono dunque essere spostare al di fuori del blocco senza alterare il funzionamento del programma. Un caso molto banale e' il seguente: for (i = 0; i < 1000; i++) { a = 10; printf ("i = %d a = %d\n", i, a); } Un ottimizzatore puo' spostare l'assegnazione alla variabile a al di fuori del ciclo. Ovviamente anche un programmatore mediocre potrebbe fare la stessa cosa in questo caso, ma spesso il codice invariante e' nascosto all'interno del codice generato dal compilatore stesso. La linea di codice che segue e' stata estratta da un programma reale e serve a copiare la stringa "name" in un buffer, spostando allo stesso tempo un indice e interrompendo il ciclo quando viene copiato un carattere nullo. Il valore iniziale di i non e' necessariamente zero. while (buf[i++] = *name++); In questa situazione lo StormC produce questo output: ; name: a2 ; buf: -$104(a5) ; i: d0 [1] loop: move.b (a2)+,d1 ; d1 = *name++ [2] move.l d0,d2 ; d2 = i !!! [3] addq.l #1,d0 ; i++ [4] lea -$104(a5),a0 ; a0 = buf !!! [5] move.b d1,0(a0,d2.l) ; *(buf + i) = d1 [6] bne.s loop ; while (d1 != 0) E' evidente che l'ottimizzatore dello StormC non e' stato in grado di spostare il codice invariante al di fuori del loop. Il ciclo si potrebbe riscrivere spostando la [4] fuori dal ciclo, eliminando la seconda copia di i e accorpando la [1] con la [5]: lea -$104(a5),a0 ; a0 = buf bra.s start ; salta all'inizio del ciclo loop: addq.l #1,d0 ; i++ start: move.b (a2)+,(a0,d0.l) ; buf[i] = *name++ bne.s loop ; while () Questa versione ha solamente tre istruzioni all'interno del ciclo contro le sei della precedente. Se poi il compilatore si accorgesse che il valore di i alla fine del ciclo non viene piu' utilizzato (4), il tutto potrebbe essere ottimizzato in: lea -$104(a5),a0 ; buf -> a0 lea 0(d0,a0),a0 ; a0 = a0 + i loop: move.b (a2)+,(a0)+ ; *buf++ = *name++ bne.s loop ; while() Il SAS/C se la cava appena meglio dello StormC: ; name: a5 ; buf: a0 ; i: d6 [1] loop: addq.l #1,d6 ; i++ [2] move.b (a5)+,d0 ; d0 = *name++ [3] lea 20(a7),a0 ; a0 = buf [4] move.b d0,-1(a0,d6.l) ; buf[i-1] = d0 [5] bne.s loop ; while (d0 != 0) In questo caso il SAS/C ha risparmiato una istruzione sfruttando la costante prevista dal modo di indirizzamento usato [4] per sottrarre 1 al valore di i gia' incrementato in [1]. L'ottimizzatore non si e' accorto dell'invarianza di [3] e ha fatto dunque in modo di ricaricarlo in a0 ad ogni iterazione. Per produrre questo codice e' stata attivata anche l'opzione OptimizerSchedule, una funzione del peep-hole optimizer che riordina le istruzioni per evitare gli stalli delle pipeline nel 68040 e nel 68060. Esaminando il codice prodotto dal SAS/C si nota che l'ottimizzatore non ha potuto evitare che la [4] dipendesse dal risultato dell'istruzione precedente. Questa sequenza costringerebbe infatti la doppia pipeline di un 68060 a bloccarsi in attesa del completamento della [3]. Il GCC produce invece questo codice quasi ottimo, con soltanto tre istruzioni all'interno del loop: ; name: a2 ; buf: 12(sp) ; i: d1 [1] lea 12(sp),a0 ; a0 = buf [2] lea 0(a0,d1.l),a0 ; a0 = a0 + i [3] loop: move.b (a2)+,d0 ; d0 = *name++ [4] move.b d0,(a0)+ ; *buf++ = d0 [5] bne.s loop ; while (d0 != 0)) Incredibilmente, il peep-hole optimizer del GCC non e' riuscito ad accorpare la [3] e la [4] in un'unica istruzione. Per il resto, il compilatore e' riuscito ad eliminare la variabile di iterazione mostrando un'astuzia sorprendente. --footnotes-- (4) eliminazione delle variabili di iterazione. Questa caratteristica e' presente sia nel GCC che nel SAS/C. Loop unrolling ============== L'impatto maggiore sull'efficienza di un programma lo si ottiene ottimizzando l'esecuzione dei loop che vengono ripetuti un gran numero di volte. Lo "srotolamento dei cicli" (loop unrolling) e' una delle tecniche di ottimizzazione piu' critiche. Insieme all'inlining delle chiamate a funzione che tratteremo successivamente e' una delle poche tecniche di ottimizzazione in cui vi e' un netto trade-off tra dimensioni del codice e velocita' di esecuzione. Srotolare eccessivamente un ciclo che viene eseguito un numero limitato di volte puo' anche non essere conveniente. Difatti, il codice del loop deve essere prelevato dalla memoria almeno una volta prima di riempire le linee della cache istruzioni. Questo overhead iniziale e' trascurabile nel caso di un loop che verra' ripetuto un gran numero di volte, ma diventa svantaggioso quando il numero delle iterazioni e' molto ridotto. Ad esempio, srotolare il loop di copia della funzione strcpy() porta dei vantaggi soltanto con stringhe molto lunghe, mentre e' svantaggioso quando si devono copiare stringhe di pochi caratteri. Nel 68020 la cache istruzioni contiene soltanto 256 byte, e tutti i loop di lunghezza superiore costringeranno la CPU a ricaricare dalla memoria tutte le istruzioni ad ogni iterazione successiva. Il 68010 non ha la cache, ma e' dotato di una coda di prefetch che e' in grado di riconoscere i loop piu' brevi, evitando cosi' di ricaricare dalla memoria le istruzioni. Un compilatore dovrebbe tenere conto di queste differenze nell'architettura dei diversi membri di una stessa famiglia di microprocessori e generare codice diverso a seconda dei casi. Gli ottimizzatori migliori sono quelli che possiedono una euristica in grado di stabilire con buona approssimazione quali siano i cicli che conviene srotolare. Ad esempio, con tutta probabilita' il loop piu' interno di una serie di cicli nidificati verra' eseguito un gran numero di volte ed e' quindi conveniente srotolarlo maggiormente. I microprocessori moderni possiedono architetture ad elevato grado di parallelismo, con una o piu' unita' di esecuzione ognuna delle quali costituita da una pipeline a piu' stadi. Il 68040 scompone ogni istruzione in sei stadi di esecuzione successivi. Il 68060 e' dotato di due pipeline superscalari identiche, ciascuna con sei stadi. Quando un'istruzione viene completata da una delle due pipeline, ve ne sono sempre altre cinque in fase di esecuzione sulla stessa pipeline e altre sei accodate alla pipeline gemella. La situazione diventa ancora piu' complessa nel caso del PPC604. Ci sono in totale sei unita' di esecuzione parallele: due unita' intere a singolo ciclo di clock, una unita' intera per istruzioni che richiedono piu' cicli di clock, una unita' floating point a tre stadi, una unita' per la gestione dei salti e una unita' per gli accessi alla memoria. Nei microprocessori ad elevato grado di parallelismo, l'esecuzione dei salti condizionali (branch) costituisce un grave problema. Infatti quando l'istruzione di branch ha raggiunto l'unita' di esecuzione, ormai le altre unita' di esecuzione stanno gia' elaboarandp le istruzioni successive. Il 68060 e tutti i modelli di PPC possiedono una logica di predizione dei salti che tenta di stabilire anticipatamente se il salto avverra' oppure no, eseguendo in modo speculativo le istruzioni sulla diramazione piu' probabile del salto. La valutazione viene fatta sulla base di considerazioni statistiche e in caso di errore costringe la CPU a scartare tutti i risultati prodotti dalle istruzioni eseguite in modo speculativo e ricaricare nuovamente le pipeline con le istruzioni della diramazione corretta. (5) L'idea alla base del loop unrolling consiste nel ridurre il numero di salti condizionali eseguiti dalla CPU ripetendo piu' volte il codice contenuto nel ciclo. Per esempio, un ciclo tipico dei programmi che calcolano l'insieme di Mandelbrot si presenta grossomodo cosi': for (iter = 0; iter < 256; iter++) { zi = zr*zi*2 + ci; zr = zr*zr - zi*zi + cr; } Se srotoliamo quattro volte questo loop, otteniamo questa versione funzionalmente equivalente: for (iter = 0; iter < 64; iter++) { zi = zr*zi*2 + ci; zr = zr*zr - zi*zi + cr; zi = zr*zi*2 + ci; zr = zr*zr - zi*zi + cr; zi = zr*zi*2 + ci; zr = zr*zr - zi*zi + cr; zi = zr*zi*2 + ci; zr = zr*zr - zi*zi + cr; } In questo caso la trasformazione e' semplice perche' il numero di iterazioni e' costante ed e' divisibile per 4. La maggior parte dei loop in un programma reale sono invece eseguiti un numero variabile di volte. Per ovviare al problema il GCC adotta alcune interessanti strategie, diverse a seconda dei casi. Prima di iniziare il loop viene calcolato il numero delle iterazioni in difetto per raggiungere il successivo multiplo del numero di srotolamenti effettuati. Questo numero si calcola piuttosto facilmente: iterazioni_da_saltare = ~(iterazioni - 1) % numero_di_srotolamenti; dove `~' e' il complemento bit a bit e `%' e' il modulo della divisione. Dal momento che il numero di ripetizioni e' sempre una potenza di 2, il modulo si riduce ad estrarre i bit meno significativi dal numero delle iterazioni con un semplice AND logico. Per fare un esempio, supponiamo che iter sia 101 e che il loop sia stato srotolato 8 volte. Il numero di iterazioni da saltare in questo caso sarebbe 3. --footnotes-- (5) La predizione dei salti, l'esecuzione fuori ordine delle istruzioni e l'interlock delle pipeline rendono molto complesse le unita' di controllo dei microprocessori, perche' devono essere in grado di eseguire il codice preesistente che non tiene conto della natura parallela della CPU. Alcuni microprocessori RISC (e' il caso dello SPARC) hanno risolto alla base questo problema, eliminando dall'unita' di esecuzione tutta la logica di bloccaggio e di predizione dei salti. La CPU non garantisce affatto un modello di esecuzione ordinato delle istruzioni e i salti vengono posticipati quanto basta per dar tempo alle pipeline di terminare le elaborazioni in corso. La fase di scheduling del compilatore deve tenere conto di questo design e riordinare le istruzioni che verranno eseguite in parallelo in modo che non vi sia dipendenza diretta tra di esse. Funzioni inline =============== L'inserimento di una breve funzione in linea al codice chiamante e' un'altra ottimizzazione che baratta un minor tempo di esecuzione con una maggiore dimensione del codice. Inserire in linea una funzione presenta alcuni evidenti vantaggi: - eliminazione delle istruzioni che servono al passaggio dei parametri - eliminazione delle istruzioni di chiamata e di ritorno - eliminazione del prologo e dell'epilogo della funzione In alcuni casi fortunati il codice generato inline puo' essere addirittura piu' breve del codice che avrebbe dovuto provvedere al passaggio dei parametri e a saltare alla funzione. Un altro vantaggio tuttaltro che trascurabile e' che il compilatore conosce a priori i parametri che vengono passati alla funzione e ha l'opportunita' di generare codice specializzato caso per caso, propagando le costanti anche all'interno della funzione. Per esempio: /* Calcola x elevato alla y */ int power(int x, int y) { int result = 1; while (y--) result *= x; return result; } ... printf ("n^3 = %d\n", power(n,3)); Se power() viene inserita inline, il compilatore puo' sostituire a y il valore costante 3, ottenendo cosi' una versione ottimizzata della funzione: printf ("n^3 = %d", n*n*n); Mantenendo le opzioni di default per l'inlining delle funzioni, il SAS/C giudica che power() sia troppo complessa per poter essere generata inline. Aumentando il valore del parametro "OptimizerComplexity", si ottinene finalmente l'inlining, che produce questo ottimo risultato: ; n: d0 move.l d0,(sp) ; salva n muls.l d0,d0 ; d0 = n * n move.l (sp),d1 ; d1 = n muls.l d1,d0 ; d0 = n * n * n move.l d0,-(sp) ; passa n a printf() pea msg(pc) ; e anche la stringa di formattazione bsr _tinyprintf ; chiama printf() Il GCC questa volta rimane una indietro di una lunghezza e perde l'occasione di propagare la costante 3 all'interno della funzione inline: ; n: d0 moveq #1,d2 ; result = 1 moveq #2,d1 ; contatore del ciclo (variabile y) loop: muls.l d0,d2 ; result *= x dbra d1,loop ; decrementa la parte bassa y e ripete clr.w d1 ; corregge la parte bassa di y subql #1,d1 ; decrementa la parte alta di y bcc.s loop ; ripete il ciclo fino a 0 move.l d2,-(sp) ; passa result a printf() pea msg ; e anche la stringa di formattazione bsr _printf ; chiama printf() Il GCC ha diligentemente generato per intero la funzione power() cosi' come si presentava nella sua forma generica e ha addirittura previsto la possibilita' che y fosse un numero maggiore di 65535, generando quindi il tipico loop "a due fasi" con dbra e subq. Lo StormC come il SAS/C preferisce non spostare inline la funzione power(). Dal momento che lo StormC non prevede opzioni che consentono di suggerire al compilatore i criteri da usare per decidere quali funzioni siano adatte ad essere spostate in linea, e' necessario modificare il sorgente dichiarando esplicitamente l'attributo "__inline" per la funzione power(). Il risultato che si ottiene in questo modo e' comunque del tutto analogo a quello del GCC: moveq #3,d1 ; y = 3 moveq #1,d2 ; result = 1 bra.s start ; inizia il ciclo loop: muls.l d0,d2 ; result *= x start: move.l d1,d3 ; salva y subq.l #1,d1 ; y-- tst.l d3 ; y == 0? bne.s loop ; while() move.l d2,-(sp) ; passa result a printf() move.l #msg,-(sp) ; e anche la stringa di formattazione bsr _printf ; chiama printf() Funzioni virtuali ================= Una classe in C++ non e' altro che una struttura che contiene delle variabili ed eventualmente un puntatore ad una tabella di salto per le funzioni virtuali. Il compilatore trasforma al momento della compilazione tutte le chiamate alle funzioni membro non virtuali in normali chiamate a funzione, aggiungendovi un parametro in piu': la variabile "this" che rappresenta l'istanza della classe sulla quale e' stata invocata la funzione membro. Usando questo puntatore la funzione ha accesso alle variabili membro. class FooBar { int foo(int x, int y); int bar(int x, int y); }; FooBar *fb = new FooBar; fb->foo(42,666); Un comune frontend C++ tradurrebbe la chiamata a foo() in questo modo: foo__FooBar (fb, 42, 666); Sia i frontend C++ che i compilatori C++ nativi creano dei nomi univoci come "foo__FooBar" per permettere al linker di distinguere tra funzioni membro appartenenti a classi diverse. I nomi cosi' modificati si dicono "decorati" (decorated). L'algoritmo di decorazione non e' standardizzato e quindi ogni compilatore ne utilizza uno proprio, rendendo cosi' incompatibili tra loro i moduli oggetto e le librerie statiche prodotte da compilatori diversi. Le funzioni virtuali sono implementate in modo diverso. Ogni classe che contiene una o piu' funzioni virtuali possiede anche una tavola di salto chiamata "vtable" che permette di chiamare le funzioni membro corrette anche senza conoscere la classe dell'oggetto. In molti compilatori, ogni entry della vtable contiene due valori: un puntatore alla funzione e una costante di aggiustamento per la variabile --this--. In fase di compilazione le funzioni virtuali di ogni classe vengono numerate progressivamente e le entry corrispondenti nella vtable sono riempite con un puntatore alla funzione corretta. Il costrutture della classe associa la vtable ad ogni oggetto istanziato usando un puntatore memorizzato all'interno dell'istanza stessa. Se nel caso precedente le funzioni membro foo() e bar() fossero state dichiarate di tipo virtual, il compilatore avrebbe generato qualcosa di simile a questo: fb->vtable[1].func(fb - fb->vtable[1].offset, 10, 3); fb->vtable[2].func(fb - fb->vtable[2].offset, 10, 3); Il GCC e' in grado di rilevare i casi in cui la chiamata ad una funzione virtuale puo' essere effetuata in modo diretto perche' si conosce la classe a cui l'oggetto appartiene. Nel caso di classi derivate, il compilatore genera istanze che contengono tutte le variabili membro della classe base, seguite dalle variabili membro della classe derivata. In C cio' equivale a definire strutture nidificate in questo modo: struct ClasseBase { [vtable] [variabili membro] }; struct ClasseDerivata { struct ClasseBase; [vtable] [variabili membro] }; Goto, buono o cattivo? ====================== Da quando si e' diffusa la programmazione strutturata, l'uso dei salti diretti che era cosi' diffuso in linguaggi come il BASIC e' stato condannato un po' da tutti. I programmatori si sono divisi fondamentalmente in due scuole di pensiero opposte: quella che sostiene che --goto-- non vada mai usato in nessun caso e quelli che ritengono che esista un gruppo piu' o meno circoscritto di situazioni in cui l'uso di --goto-- permette di ottenere un risultato piu' elegante e, sopratutto, piu' efficiente. Capita di frequente che gli adepti di queste due filosofie di vita si scontrino in interminabili discussioni in cui nessuna argomentazione dei primi potra' mai convincere i secondi a cambiare idea e viceversa. Probabilmente il motivo e' che le due parti parlano sempre lingue diverse. I primi ne fanno infatti una questione di chiarezza, leggibilita' e mantenibilita' del codice, mentre i secondi mettono davanti a tutto l'efficienza e la semplicita'. Lungi dal voler prendere parte in disquisizioni di carattere religioso, vorrei osservare che l'uso di --goto-- in un linguaggio come il C non e' necessariamente il modo migliore di aiutare un compilatore a generare codice migliore. Analizzando il comportamento tipico dei generatori di codice e' facile avvedersi che la presenza di un goto puo' dar luogo ad alcuni inconvenienti che limitano pesantemente la liberta' di azione dell'ottimizzatore. Innanzitutto, il flusso del programma diventa piu' ingarbugliato, e questo intralcia il compilatore nella propagazione delle costanti e nel loop unrolling. Per di piu' e' necessario che le variabili contenute nei registri e nello stack coincidano perfettamente tra il punto di partenza e quello di arrivo del salto, cosa che difficilmente si verifica nei casi tipici in cui si usa goto, come per esempio uscire da un gruppo di cicli nidificati. Nella migliore delle ipotesi il compilatore deve spesso rinunciare a mantenere alcune variabili nei registri per poter garantire la coerenza richiesta tra i due punti della funzione. Detto questo, sono certo che pochi programmatori avranno ancora voglia di usare --goto--. Sviluppi Futuri =============== Il progetto Experimental GNU Compiler System (in breve EGCS, che si pronincia "eggs", cioe' "uova") e' stato creato recentemente da un gruppo di contributors del compilatore GCC con l'intento di rivoluzionare le attuali tecniche di compilazione, pur sacrificando l'alto grado di maturita' e stabilita' propri del GCC. In passato i mantainers del progetto GCC si erano spesso rifiutati di integrare nei sorgenti ufficiali alcuni progetti innovativi sviluppati indipendentemente da vari gruppi di programmatori. La ragione e' che questi cambiamenti rischiavano di introddure delle incompatibilita' verso il basso e di destabilizzare il compilatore. Questa cautela e' giustificata perche' dalla robustezza del GCC dipende una grande quantita' di software GNU che gira attualmente su decine di sistemi operativi diversi. Tuttavia, molti progetti interessanti rischiavano per questo di essere esclusi per sempre dallo sviluppo del compilatore, tra cui anche il supporto per le piattaforme m68k-amigaos e powerpc-amigaos aggiunto dal gruppo GeekGadgets, un nuovo sistema di allocazione dinamica dei registri e la riscrittura completa del generatore di codice per ottimizzare al meglio il codice x86. Una politica troppo restrittiva nella gestione del repositorio dei sorgenti del GCC rischiava di produrre un gran numero di versioni personalizzate dello stesso compilatore, una cosa gia' accaduta troppe volte in passato nel mondo UNIX, con conseguenze sempre negative (vedasi il caso di OpenBSD, NetBSD, BSDI, FreeBSD, 4.4 BSD, etc). EGCS si e' distaccato dal filone principale del GCC ereditando tutti i sorgenti della versione 2.7.2.2. I cambiamenti apportati ai sorgenti di EGCS seguono una policy chiamata "bazar" che, a differenza della policy "chatedral" usata per il GCC, consente praticamente a chiunque di contribuire allo sviluppo con un minimo controllo da parte di un organo di coordinamento centrale. Fred Fish ha colto al volo l'occasione e ha aderito immediatamente allo sviluppo di EGCS, dopo aver tentato invano per mesi di sottoporre i sorgenti specifici per Amiga all'approvazione dei coordinatori del GCC. Presto dunque EGCS prendera' il posto del GCC nella distribuzione standard GeekGadgets. Settimanalmente viene distribuito un nuovo snapshot di EGCS (6) e, occasionalmente, viene rilasciata anche una versione stabile per l'utente finale (6). La lista dei contributors e' lunga e piena di nomi celebri. Si nota purtroppo la totale assenza di sviluppatori italiani, equesto la dice lunga sullo stato della ricerca nel nostro paese. --footnotes-- (6) Home page: http://www.cygnus.com/egcs Sito FTP: ftp.cygnus.com:/pub/egcs/ Esempi inclusi nel CD ===================== I sorgenti dimostrativi inclusi nel CD di IPISA possono essere ricompilati facilmente con StormC, SAS/C e GCC, usando i file progetto o i Makefile forniti. L'header "CompilerSpecific.h" contiene alcune macro che consentono di scrivere programmi che usano caratteristiche specifiche di Amiga in modo indipendente dal compilatore. "BoopsiStubs.h" propone delle macro che sostituiscono in modo piu' efficiente le corrispondenti funzioni contenute nella libreria statica amiga.lib. "Debug.h" fornisce delle macro che semplificano il controllo delle parti di codice che per vari motivi non possono essere analizzate con il debugger (per esempio i dispatcher dei gadget boopsi). Confrontando gli eseguibili prodotti dai compilatori si puo' verificare che il GCC non produce dei buoni risultati compilando codice costellato di chiamate a funzioni di libreria e passaggi di taglist. SAS/C e StormC si comportano entrambi abbastanza bene, con qualche punto a favore del primo. Le cose cambiano radicalmente quando si compilano programmi scritti usando funzioni ANSI o POSIX. Il GCC e' l'unico tra questi compilatori a fornire una libreria POSIX completa che consente di ricompilare su Amiga qualsiasi programma UNIX senza sostanziali modifiche ai sorgenti. Pregi e difetti del C ===================== Il C possiede strutture molto piu' vicine all'architettura fisica della macchina rispetto alla maggior parte degli altri linguaggi di alto livello (HLL). Si sarebbe portati a credere quindi che tanto piu' un linguaggio si avvicina alla struttura reale del microprocessore, maggiori sono le possibilita' di ottenere codice ottimizzato nella maggior parte dei casi. Questo in parte e' vero, ma non del tutto. Con l'avvento dei compilatori ottimizzanti, un linguaggio di alto livello si presta maggiormente ad essere ottimizzato quando i suoi costrutti sono in grado di spiegare esaurientemente al compilatore cio' che si intende fare e quali sono i vincoli da rispettare per ottenere un risultato corretto. Questa affermazione diventa chiara in un semplice caso come questo: void set_colors (struct RastPort *rp) { if (rp->BitMap->Depth > 1) SetAPen (rp, 2); if (rp->BitMap->Depth > 2) SetBPen (rp, 3); } Il compilatore non puo' prevedere al momento della compilazione se la funzione SetAPen() modifichera' o meno il valore dei campi BitMap e BitMap.Depth e quindi perde l'occasione di ottimizzare il successivo test riutilizzando il valore di Depth gia' calcolato in precedenza. Il programmatore puo' rendersi conto facilmente che questo non puo' avvenire, ma il compilatore non e' in grado di estrarre questa informazione leggendosi l'autodoc di SetAPen() e dunque deve rinunciare ad una semplice ottimizzazione come questa. In alcuni casi (non in questo) la keyword const permetterebbe di far sapere al compilatore che e' lecito aspettarsi che nessuno dei membri della struttura RastPort venga cambiato all'interno della funzione chiamata. Un altra situazione che ricorre piuttosto spesso e' la seguente: int *foo; void hello (int bar) { foo = &bar; printf ("Hello, world!\n"); if (bar) ... else ... } In questo caso il compilatore e' costretto a rileggere dalla memoria il valore della variabile esterna bar anche se potrebbe esserne rimasta una copia in un registro. Il motivo e' che printf() e' una funzione esterna di cui il compilatore non sa niente, pertanto non puo' escludere che printf() modifichi il valore di una variabile globale. Per risolvere in parte questo problema il GCC prevede una un'estensione non standard al linguaggio C che permette di dichiarare che una funzione non modifica il valore delle variabili globali (si aggiunge --__attribute__((const)--) al prototipo della funzione). In effetti nel caso di printf() non sarebbe lecito dire al compilatore che nessuna variabile globale verra' modificata, dal momento che printf() certamente utilizza una funzione di I/O per scrivere sullo standard output, modificando cosi' lo stato della variabile globale stdout. La possibilita' di estrarre l'indirizzo di qualsiasi variabile intralcia l'ottimizzatore in un gran numero di casi, impedendogli di spostare in un registro il valore della variabile. Vediamo questo caso: void foo (void) { int n; scanf ("%d", &n); /* qua si estrae l'indirizzo di n */ while (n--) do_something(); } In questa funzione il compilatore deve memorizzare il valore della variabile locale n sullo stack e rileggerlo dallo stack anche ad ogni iterazione del ciclo while, perche', una volta che scanf() ne ha ottenuto l'indirizzo, e' possibile che lo abbia memorizzato in una variabile globale rendendolo cosi' disponibile anche a do_something(), che potrebbe dunque alterarne il valore. Situazioni vincolanti per l'ottimizzatore come quelle appena descritte sono molto comuni in C, specialmente in programmi grossi e complessi. Inoltre, non avendo modo di sapere cosa intende fare il programmatore, il compilatore non puo' sapere quali sono i cicli verranno eseguiti piu' di frequente, quale sia l'esito piu' probabile di un if, e cosi' via. Il C++ e altri linguaggi orientati agli oggetti accentuano ancor piu' il problema dell'efficienza, perche' la necessita' di rendere piu' mantenibili i sorgenti grazie al paradigma OOP tende a frammentare maggiormente il codice rispetto al modello di programmazione tipico del C, percio' il compilatore perde molte occasioni di ottimizzare il codice. Un paradigma forse diametralmente opposto all'OOP e' la programmazione generica, un'invenzione tuttaltro che recente, ma che inizia a risquotere un discreto successo soltanto ora che ne esiste una implementazione adatta al C++. Ogni buon libro sulla programmazione orientata agli oggetti inizia mostrando che il mondo in fin dei conti e' fatto di oggetti che hanno la capacita' di fare certe cose. Per riutilizzare al massimo il codice in un programma bisogna individuare questi oggetti e creare delle interfacce ben definite (i metodi) per manipolare i dati che essi contengono. Il concetto di ereditarieta' nasce invece dall'osservazione che spesso un oggetto fa parte di gruppi piu' specializzati, che a loro volta discendono da gruppi meno specializzati. Per esempio, un cane da fiuto si distingue dagli altri cani perche' ha la capacita' di fiutare, ma come tutti i cani eredita dalla propria specie anche la capacita' di abbaiare. I cani inoltre appartengono alla classe piu' generica degli animali, che hanno tutti in comune la capacita' di mangiare e di dormire. Il modello object oriented e l'ereditarieta' sono particolarmente adatti a risolvere certi tipi di problemi. La gestione delle interfacce utente e' senz'altro una delle applicazioni in cui l'OOP ha piu' successo. Questo non implica affatto che l'OOP risolva in modo altrettanto elegante qualsiasi altro tipo di problema. Da quando esistono i computer, i programmatori perdono gran parte del loro tempo a riscrivere e debuggare algoritmi inventati venti anni fa, come ad esempio la ricerca di un elemento in un array e l'inserimento di un nodo in una lista. La programmazione generica affronta il problema della riusabilita' del codice da un punto di vista diverso da quello del C++. La gia' citata libreria standard di template (STL) e' una ricca collezione di algoritmi generici (ricerca, ordinamento, media...) che possono essere applicati su qualsiasi tipo di dato (intero, floating point, classe...), indipendentemente dal contenitore che raggruppa i dati (vettore, lista, albero...). Immaginiamo uno spazio tridimensionale in cui l'asse X elenca tutti i possibili algoritmi, l'asse Y i tipi di dati e l'asse Z tutti i contenitori. Tutte le versioni specializzate degli algoritmi sarebbero quindi collocate all'interno di un cubo. Trattandosi di templates, gli algoritmi STL vengono scritti una volta per tutte, lasciando al compilatore il compito meccanico di generare tutte le varianti che servono di volta in volta. Gli ottimizzatori dei compilatori moderni hanno ormai raggiunto un limite quasi invalicabile, che non puo' essere abbattuto senza modificare in modo sostanziale la struttura di base del linguaggio. Introdurre nuove keyword come const puo' risolvere solo in parte il problema dell'ottimizzazione del codice. Il vero nocciolo della questione e' che i linguaggi di programmazione odierni dicono al compilatore in modo imperativo cosa va fatto, non quale problema si intende risolvere. E' la differenza che c'e' tra lo scrivere un algoritmo di ordinamento e dire informalmente: "disponi tutti gli elementi dal piu' piccolo al piu' grande". Uno schiavo al quale viene detto di ordinare degli elementi potrebbe essere abbastanza intelligente da applicare un merge sort. Se invece gli si dice esplicitamente di eseguire un sort sequenziale, lo schiavo non ha alcuna possibilita' di scegliere. Fino a qualche anno fa i compilatori erano degli schiavi molto stupidi, percio' era meglio che i padroni (i programmatori) scegliessero al loro posto il modo migliore di fare le cose. Adesso i compilatori possono tener conto di una quantita' di fattori molto piu' vasta - assolutamente ingestible dal programmatore - e talvolta sono addirittura in grado di battere un buon programmatore assembler nell'individuare le strategie di ottimizzazione piu' efficaci per determinati problemi. Paradossalmente, ai fini della migliore ottimizzazione del codice oggi servirebbe un linguaggio di livello piu' alto del C, con delle primitive complesse come FIND e SORT, che permettano al compilatore di scegliere non soltanto le istruzioni da usare, ma anche l'algoritmo piu' efficace per risolvere un determinato problema di programmazione. Un buon punto di partenza per arrivare a questo a mio parere e' STL. Attualmente gli algoritmi generici di STL sono scritti in C++ e presentano dunque gli stessi problemi di efficienza che affliggono tutte le altre implementazioni. In futuro pero' e' possibile che i compilatori C++ inizino a prevedere delle versioni built-in degli algoritmi piu' comuni, allo stesso modo in cui oggi esistono compilatori che implementano versioni built-in delle funzioni piu' usate in C come strlen(), memcpy() e printf(). Bibliografia ============ Aho, Sethi and Ullman, "Compilers: Principles, Techniques, and Tools," Addison Wesley, 1986, ISBN 0-201-10088-6, the "dragon book". SAS Institute Inc., "SAS/C Development System User's Guide", Version 6.50, Cary, NC, SAS Institute Inc., 1993, ISBN 1-55544-584-5 "StormC & C++ Advanced Development System" Haage & Partner, 1996 "GCC 2.7.2 TeXInfo Manual" 1997, Free Software Foundation "PowerPC 604 RISC Microprocessor User's Manual", IBM Microelectronics, Motorola, 1994, MPR604UM/AD. "MC68060 User's Manual" Motorola, 1994, M68060UM/AD "MC68040 User's Manual" Motorola, 1990, M68040UM/AD Bernardo Innocenti Sysop di SystemShock BBS (2:332/125@fidonet, 39:102/205@amiganet)