Compilatori vs. Uomo

[dsar]

• 

.

[cdimauro]

• 

programmazione amichevole

e assembly non vanno d'accordo.

Per il resto l'assembly è meglio non usarlo, come giustamente osservava dsar, se non in particolarissimi casi.

Oggi i compilatori fanno veramente un ottimo lavoro. Soltanto alcune volte ho sentito la necessità di riscrivere il codice prodotto in assembly, perché quello generato non mi soddisfaceva.

Ad esempio, ecco il codice generato dal compilatore (Visual Studio C++ 2008):

Codice: [Seleziona]

static int long_compare(PyLongObject *a, PyLongObject *b)
{   Py_ssize_t sign;
    Py_ssize_t i = Py_SIZE(a), j = Py_SIZE(b);
          push        ebx  
          mov         ebx,dword ptr [edx+8]
          push        ebp  
          push        esi  
          mov         esi,dword ptr [edi+8]
          mov         eax,ebx
    if (i != j)
          cmp         eax,esi
          je          @else
        sign = (FAST_MSD(a, i) < 0 ? -i : i) - (FAST_MSD(b, j) < 0 ? -j : j);
          cmp         dword ptr [edx+eax*4+8],0
          jge         @a_pos
          neg         eax  
@a_pos:
          cmp         dword ptr [edi+esi*4+8],0
          jge         @b_pos
          neg         esi  
@b_pos:
          sub         eax,esi
          mov         ecx,eax
          jmp         @compute_sign
    else {
e quello che ho riscritto a mano:

Codice: [Seleziona]

static int long_compare(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t sign;
    Py_ssize_t i = Py_SIZE(a), j = Py_SIZE(b);
          mov         eax,dword ptr [esi+8]
          mov         ecx,dword ptr [edi+8]
    if (i != j)
          cmp         eax,ecx
          je          @else
        sign = (FAST_MSD(a, i) < 0 ? -i : i) - (FAST_MSD(b, j) < 0 ? -j : j);
          cmp         dword ptr [esi+eax*4+8],0
          jge         @a_pos
          neg         eax  
@a_pos:
          cmp         dword ptr [edi+ecx*4+8],0
          jge         @b_pos
          neg         ecx  
@b_pos:
          sub eax,ecx          
          jmp @compute_sign
else {
Fanno parte di alcune slide che non ho incluso nella presentazione dei talk che ho tenuto al recente EuroPython, per alleggerire la discussione.

Come potete vedere l'allocazione e l'uso di registri manuali risulta migliore. Per il resto ci sono stati un paio di casi in cui sono rimasto sorpreso dalla qualità del codice prodotto, superiore alle mie soluzioni (non me lo sarei mai aspettato, anche se sono anni ormai che non scrivo codice assembly).

[cdimauro]

• 

Come potete vedere l'allocazione e l'uso di registri manuali risulta migliore.

Posso muovere una critica? :-) Mi permetto di farlo perché i compilatori sono il mio campo (anche se hobbistico).

Certamente, ci mancherebbe.

Ovviamente è corretto il codice di msvc 2008, prima di operare sui registri si fa sempre il backup sullo stack. Pushare e poppare dallo stack è un'operazione lenta, motivo per cui la chiamata di una procedura ha un certo overhead (tutti i registri vengono backuppati nello stack).
Considera che il compilatore ha sempre una variabile riservata per registro, viene assegnato con il liveness analysis (le variabili più utilizzate), ci sono alcuni casi in cui serve più velocità, quindi prende in prestito un registro da una variabile backuppandola nello stack, e dopo lo ripoppa nel registro.
Quindi non puoi fare un mov su un registro senza prima salvare il contenuto, dipende cosa avviene dopo quel pezzo di codice, l'eseguibile potrebbe avere comportamenti indeterministici.

In realtà alcuni registri (come eax, ecx, edx) sono liberi (e liberamente utilizzabili) già in partenza, per cui non è necessario farne il backup e si possono utilizzare immediatamente.

Mostro un esempio a riguardo:

Codice: [Seleziona]

static int long_compare(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t sign;
    if (Py_SIZE(a) != Py_SIZE(b)) {
          mov         edx,dword ptr [ebx+8]
          mov         eax,dword ptr [esi+8]
          push        ebp  
          push        edi  
          cmp         edx,eax
          je          @else
        sign = Py_SIZE(a) - Py_SIZE(b);
          sub         edx,eax
          mov         ecx,edx
          jmp         @compute_sign
    }
    else {
Questa funzione è quella usata correntemente da CPython (quelle precedenti riguardano la nuova implementazione che ho proposto) e il codice è quello generato dal solito VS 2008.

Come vedi eax ed edx vengono utilizzati immediatamente senza farne il backup; successivamente il compilatore fa il push di ebp ed edi perché probabilmente gli serviranno dopo, anche se io avrei aspettato il risultato del confronto, perché nel caso comune & semplice si deve soltanto calcolare il segno (-1, 0 o 1) e restituirne il valore (quindi ebp ed edi non vengono utilizzati).

Quest'esempio mostra, a mio avviso, come l'algoritmo di register allocation potrebbe essere ulteriormente migliorato da Microsoft (magari l'avranno già fatto nella 2010, ma io sono costretto a usare la 2008 finché gli sviluppatori di Python non decideranno di aggiornare il progetto) procedendo al backup (e successivo restore) dei registri soltanto nel ramo dell'else (quello più complicato).

Se vuoi fare in modo che il compilatore usi direttamente i registri dovresti fare una funzione inline (o macro, se è in C). Se le variabili che compari vengono usate abbastanza spesso ovviamente in quel punto te le ritrovi già nei registri e il compilatore fa il folding del codice (essendo inline/macro).

Purtroppo quello è codice C (CPython non utilizza C++) per cui non si può utilizzare l'inline (che, comunque, ormai un compilatore può benissimo ignorare perché può decidere che non ne vale la pena; d'altra parte è soltanto un'indicazione).

Inoltre, anche se funzione è definita come static, viene comunque referenziata all'esterno di quel modulo tramite una tabella pubblica che ne contiene un puntatore (in pratica si simula la programmazione a oggetti), per cui comunque il compilatore sarebbe costretto a evitare l'inline e a generarne una copia.

[Z80Fan]

• 

Mi inserisco un attimo in questa interessante discussione.

e assembly non vanno d'accordo.

Ovviamente parlavo di "programmazione amichevole" per un programmatore Assembly, non di "programmazione amichevole" in generale.
Poi sappiamo tutti che non c'è nulla di amichevole nell'x86 ma quello è un altro discorso! :mrgreen:

Inoltre, anche se funzione è definita come static, viene comunque referenziata all'esterno di quel modulo tramite una tabella pubblica che ne contiene un puntatore (in pratica si simula la programmazione a oggetti), per cui comunque il compilatore sarebbe costretto a evitare l'inline e a generarne una copia.

Una volta, giocando con l'output di GCC (v. 4+) ho notato che piccole funzioni venivano messe inline, ma veniva cmq generata una copia a se stante; non era stato specificato nulla di particolare nel codice, solo -O2 (o O3 non ricordo) alla linea di comando.

[TheKaneB]

• 

Mi inserisco un attimo in questa interessante discussione.

e assembly non vanno d'accordo.

Ovviamente parlavo di "programmazione amichevole" per un programmatore Assembly, non di "programmazione amichevole" in generale.
Poi sappiamo tutti che non c'è nulla di amichevole nell'x86 ma quello è un altro discorso! :mrgreen:

Inoltre, anche se funzione è definita come static, viene comunque referenziata all'esterno di quel modulo tramite una tabella pubblica che ne contiene un puntatore (in pratica si simula la programmazione a oggetti), per cui comunque il compilatore sarebbe costretto a evitare l'inline e a generarne una copia.

Una volta, giocando con l'output di GCC (v. 4+) ho notato che piccole funzioni venivano messe inline, ma veniva cmq generata una copia a se stante; non era stato specificato nulla di particolare nel codice, solo -O2 (o O3 non ricordo) alla linea di comando.

La copia della funzione verrebbe comunque strippata in fase di linking, a meno che tu non usi un puntatore a quella funzione (quindi il puntatore a funzione deve spuntare da qualche parte del codice come RValue).

[cdimauro]

• 

Ho trovato un po' di tempo per tornare su quest'interessante thread.

In realtà alcuni registri (come eax, ecx, edx) sono liberi (e liberamente utilizzabili) già in partenza, per cui non è necessario farne il backup e si possono utilizzare immediatamente.

Sì, diciamo che lo standard x86 calling convention riserva 5 registri e 3 sono di uso libero, ma in genere il compilatore cerca sempre di ottimizzare là dove può, considera che oggi si raggiunge il register saturation (soprattutto in x86 dove i registri sono troppo pochi e non bastano mai).
Non sapevo che oggi venisse ancora rispettato il calling convention tradizionale (i tempi sono cambiati). In ogni caso GCC ed ICC saturano tutti i registri.
Per esempio vengono utilizzati anche quelli di ritorno (eax, edx) se la procedura è una funzione, non vengono lasciati inutilizzati fino alla fine.

La calling convention dipende dal s.o. (e dal compilatore), per cui i risultati possono essere molto diversi. Quello che ho analizzato riguarda Windows e VisualStudio in particolare, che ne lasciano liberi soltanto 3.

Hai provato a giocare un po' con le ottimizzazioni di msvc? Tipo con /O2 o /Ox ? Se riuscissi ad ottenere lo stesso risultato è sempre meglio di scrivere codice assembly ;-)

No, non ho provato perché volevo confrontare i risultati con la normale compilazione di CPython.

Dubito che VS possa fare di meglio, ma appena avrò un po' di tempo controllerò il codice che VS tira fuori attivando quelle opzioni di compilazione.

Il problema dei registri è sempre stato stressante in x86, fortunatamente in x86_64 lo è molto meno.

AMD ha fatto un ottimo lavoro.

Quest'esempio mostra, a mio avviso, come l'algoritmo di register allocation potrebbe essere ulteriormente migliorato da Microsoft (magari l'avranno già fatto nella 2010, ma io sono costretto a usare la 2008 finché gli sviluppatori di Python non decideranno di aggiornare il progetto) procedendo al backup (e successivo restore) dei registri soltanto nel ramo dell'else (quello più complicato).

Sottolineo che è un problema di msvc :-) Non del codice generato da un compilatore in generale.

Sì sì. Io ho messo chiaro fin dall'inizio che ho usato VS.

Il register allocation va spesso in spilling (supera il numero di registri della macchina e molte variabili vengono messe in stack). Mi chiedo come abbia potuto utilizzare registri occupati al posto dei registri liberi, avranno una strategia diversa di allocazione. Bisognerebbe vedere il calling convention di msvc (mi pare di vedere da un codice generato che quei tre li riserva per le costanti, scelta discutibile).

EAX, ECX e EDX sono liberi. Tutti gli altri devono essere preservati.

Comunque da quel che ho visto li usa per qualunque dato.

Purtroppo quello è codice C (CPython non utilizza C++) per cui non si può utilizzare l'inline (che, comunque, ormai un compilatore può benissimo ignorare perché può decidere che non ne vale la pena; d'altra parte è soltanto un'indicazione).

Inoltre, anche se funzione è definita come static, viene comunque referenziata all'esterno di quel modulo tramite una tabella pubblica che ne contiene un puntatore (in pratica si simula la programmazione a oggetti), per cui comunque il compilatore sarebbe costretto a evitare l'inline e a generarne una copia.

Una method table molto sporca :-) ma è l'unico modo per un encapsulation strong in C.

Esattamente. Non c'è altra via purtroppo.

Io sono contrario all'inlining, perché è un reserved word che non cambia il meaning del codice ma solo il tipo di generazione. Tuttavia spesso è difficile per il compilatore scegliere cosa foldare oppure no, la soluzione sarebbe non foldare e basta (perdendo i vantaggi di alcuni casi).

Dipende anche da come sarà usato il codice. Per lo scopo di cui sopra è impossibile ricorrere all'inlining.

Comunque io non l'ho mai usato e preferisco delegare al compilatore se farlo o meno, se ne avesse la possibilità.

Mi inserisco un attimo in questa interessante discussione.

e assembly non vanno d'accordo.

Ovviamente parlavo di "programmazione amichevole" per un programmatore Assembly, non di "programmazione amichevole" in generale.
Poi sappiamo tutti che non c'è nulla di amichevole nell'x86 ma quello è un altro discorso! :mrgreen:

Non te lo lascerei dire. Preferisco lavorare con x86 che con tanti RISC.

[rebraist]

• 

mi sto eccitando a leggere.. :geek:  :geek:  :geek:
giuro :geek:  :geek:

[cdimauro]

• 

La calling convention dipende dal s.o. (e dal compilatore), per cui i risultati possono essere molto diversi. Quello che ho analizzato riguarda Windows e VisualStudio in particolare, che ne lasciano liberi soltanto 3.

Secondo me usare uno schema fisso per il calling convention è molto limitativo, c'è molto spazio per l'ottimizzazione.

Purtroppo quando devi definire le ABI di un s.o. (o anche di un virtual machine che espone un'interfaccia pubblica) sei costretto a fissare la calling convention.

Come nel caso citato. CPython espone delle ben precise API pubbliche, perché si tratta sostanzialmente di una DLL/so/dynlib che può tranquillamente essere richiamata dall'interno di applicazioni scritte in altri linguaggi, oppure è possibile scrivere delle estensioni per la VM (sempre con linguaggi diversi, e non necessariamente C/C++).

Per esempio quei linguaggi che supportano un vero passaggio per riferimento possono sfruttare il by value/result (al posto del by reference, più lento) per le variabili scalari. O il by result (i parametri out delle procedure). Questo richiede uso di registri (non pochi).
Ho letto da qualche parte (non ricordo dove) che provieni dal Pascal. Molti compilatori per i parametri VAR usano il by value/result.

Sì, anche se ho cominciato con BASIC (e linguaggio macchina), mi sono "posizionato" nell'area "Pascal & derivati", e tutt'oggi non mi piace lavorare coi linguaggi C-like (anche se, per una sorta di legge del contrappasso, sono costretto a lavorarci spesso ).

Per il resto concordo, ma purtroppo un'architettura come x86 ha veramente pochi registri (difatti la mia preferita rimane quella 68K :ugeek:).

Dubito che VS possa fare di meglio, ma appena avrò un po' di tempo controllerò il codice che VS tira fuori attivando quelle opzioni di compilazione.

E' molto probabile che in codice non (o poco) ottimizzato usi un calling convention più rilassato.

Purtroppo non può farlo. Vedi sopra.

Non te lo lascerei dire. Preferisco lavorare con x86 che con tanti RISC.

Intendi: lavorare con macchine di quel tipo o produrre codice assembly?
Se bisogna scrivere codice assembly a mano ovviamente una piattaforma CISC ti aiuta parecchio, produrre codice RISC è molto più semplice (e facile da ottimizzare) per un compilatore.

La seconda che hai detto.

[AmigaCori]

• 

...
Per il resto concordo, ma purtroppo un'architettura come x86 ha veramente pochi registri (difatti la mia preferita rimane quella 68K :ugeek:).
...

Premessa: capisco si e no il 5% di quello che scrivete  :lol:  e non voglio avviare una guerra sacro vs. x86, pero' ragionavo leggendo il passaggio su citato.

Il 68k ha piu' registri di un x86? quindi per un compilatore e' piu' semplice o magari ha piu' flessibilita' nel creare codice migliore su un 68k che su un x86?  :?:

[cdimauro]

• 

Dipende sempre da chi ha scritto il compilatore.

Comunque il 68000 ha 8 registri dati (tutti utilizzabili per conservare dati, appunto) e 8 registri indirizzi (l'ultimo, però, è riservato per lo stack pointer).

Quindi i registri sono specializzati, e questo è un problema per un codegen perché gli complica la vita, ma giocandoseli opportunamente si fanno grandi cose.

Non è un caso che su Amiga molti :ugeek: programmavano in assembly anche applicazioni dotate di GUI e addirittura comandi per AmigaDOS.

[cdimauro]

• 

Purtroppo quando devi definire le ABI di un s.o. (o anche di un virtual machine che espone un'interfaccia pubblica) sei costretto a fissare la calling convention.

Piccola digressione filosofica, a causa della compatibilità con il legacy code si rimpiangono tante scelte passate sulle ABI. Su C++0x non stanno risolvendo problemi fondamentali a causa della compatibilità con il legacy code. Vedere problemi come fragile base class problem nel 2011 è anacronistico.

C++ è cominciato male, con questa fissazione della retrocompatibilità col C, e continua a peggiorare.

Peccato che D rimanga nella sua nicchia.

Tornando on topic:
Considera che questo è prettamente un lavoro del linker e si può fare tantissimo. Credo che non lo facciano per pigrizia, e soprattutto perché tutti gli sviluppatori dei linker dovrebbero mettersi d'accordo. Considera che il compilatore quando genera codice per l'interfaccia esposta, non sa nulla sul calling convention. Genera una sorta di calling convention thunk (che viene calcolato dopo in linking time, un po' come avviene per il relocation). Nei casi classici il linker sceglie tra _stdcall, _fastcall, etc, in base a ciò che è stato specificato. Quindi uno schema dinamico non è impossibile, semplicemente gli scoccia farlo.

Dovrebbero mettersi d'accordo tutti (quelli che sviluppano compilatori), però. Questo è il motivo per cui in genere chi produce il s.o. fissa anche la calling convention e, quindi, l'ABI.

Diciamo che non c'è il coraggio di cambiare quanto già stabilmente fissato, e d'altra parte non gli do tutti i torti perché sono passati parecchi anni e ormai hanno preso parecchio piede i linguaggi managed, che non hanno di questi problemi.

Insomma, con .NET che si espande sempre più, non vedo convenienza nello stravolgimento dell'ABI attuale per MS.

Ovviamente ti prendo un caso reale:
Su Ada (ero un adaista fanatico, uno di quelli che credeva di cambiare il mondo, thekaneb può confermartelo) il passaggio dei parametri è totalmente indipendente dalla piattaforma (IN, INOUT, OUT). In un certo senso il passaggio per valore o riferimento è dipendente dalla piattaforma, mi pare che ora anche C# supporti pure questa notazione.

Sì, hai esattamente le stesse possibilità (e nomenclatura) che offre Ada nello specificare in che modo avviene il passaggio dei parametri.

Per esempio un array di 32 booleani (che entra in un solo registro) sceglie il compilatore come passarlo, non il programmatore.
Ada da molta priorità al by value/result tramite registri nel multithreading per motivi di safety, si evita l'aliasing dovuto al by reference. Immagina due procedure concorrenti, in cui una variabile viene passata by reference e ci lavorano sopra, il programma va in race condition.
Credo che il meccanismo di passaggio (indipendente dal linguaggio o dalla piattaforma) sia molto più importante del passaggio su stack o registri.

Ada mi piace da quando l'ho conosciuto (fine anni '80), ma non ero a conoscenza di questi dettagli di basso livello. Molto interessante.

Il 68k ha piu' registri di un x86? quindi per un compilatore e' piu' semplice o magari ha piu' flessibilita' nel creare codice migliore su un 68k che su un x86?

Non ho mai programmato su m68k, ho solo letto i reference manual. Come architettura la reputo superiore, Intel ha molto puntato sulla compatibilità dei vecchi 80x86, che non erano molto comodi né per i linguaggi di alto livello né per programmarci a mano (rispetto ad un m68k).

Come disse un computer scientist (oggi sono in vena di quote): x86 is like an oxcart in an highway (x86 è come un carro trainato da buoi in un'autostrada).

ROFL :lol:

[cdimauro]

• 

Ada mi piace da quando l'ho conosciuto (fine anni '80), ma non ero a conoscenza di questi dettagli di basso livello. Molto interessante.

Non ti facevo così vecchio

Sono passato da qualche mese agli anta. :cry:

Ada era il mio linguaggio preferito e l'ho usato per un bel po' di tempo, ora però me ne sono allontanato parecchio. Da quando Tucker Taft ha potere decisionale nel design di Ada, sta diventando un casino. Ada 2012 non mi piace per nulla, troppo complesso.

E' anche uno dei due motivi principali per cui non mi piace C++: è un linguaggio troppo complesso che richiede parecchio tempo per essere padroneggiato in tutti gli aspetti.

L'altro, ovviamente, è la sintassi.

Tuttavia Ada continua ad avere caratteristiche uniche rispetto ad altri linguaggi, come il rigorosissimo conformismo agli standard (il reference manual per i compiler writer è di 1300 pagine). Avevo sviluppato un'applicazione non molto complessa ma sufficientemente grande. Potevo compilarlo con GNAT, ObjectAda e PowerAda, compilava e funzionava benissimo in tutti e tre. Questo in altri linguaggi non succede, c'è sempre qualche differenza nell'implementazione.

Hum. Nemmeno col Pascal standard, Modula-2/3, Oberon?

Inoltre gnat possiede ottimi tool di profiling e di static checking, molti bug potevano essere rilevati in compile time (utilissimo!).

Vero. Ma io ormai sono votato ai linguaggi dinamici (Python, ovviamente) e preferisco lo unit testing (che ritengo ormai indispensabile in un buon progetto).

Grazie allo UT le differenze fra linguaggi statici e dinamici vengono sostanzialmente eliminate.

Tornando alle caratteristiche low-level di Ada, anche l'operatore new era molto platform independent, tu non sapevi se allocava su stack oppure heap, lo decideva il compilatore. C'erano anche qui molti casi di ottimizzazione (ovviamente tu potevi forzare lo storage allocator per usare l'heap).

Immagino che lo decidesse in base allo scoping e all'uso delle variabili all'interno delle procedure/funzioni. Al momento non mi viene in mente nessun altro modo per decidere in che modo cambiare la strategia d'allocazione.

Comunque ho cambiato filosofia, è molto meglio un linguaggio più snello e semplice

Idem. Con Python ho trovato sia questo che una notevole leggibilità e manutenibilità. Oltre al piacere di programmare.