+ Rispondi al messaggio
Visualizzazione dei risultati da 1 a 6 su 6

[C] Ottimizzazione di semplici programmi

  1. #1
    jmimmo82 non è in linea Novello
    Salve a tutti.

    Dato il codice sorgente di un programma, la minimizzazione del tempo di esecuzione e del numero di istruzioni è una di quelle sfide che più mi affascinano.

    Volevo confrontarmi con voi per capire dove posso migliorare in tal senso.

    Parto da un programmino semplice che ho scritto in C il quale stampa una matrice NxN (le dimensioni non contano) i cui elementi sono tutti "zero" eccetto quelli che vanno a disegnare una Z (di Zorro ;P) con degli "uno".

    Questo è l'output su terminale:
    1 1 1 1 1 1 1 1 1 1
    0 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 1 0 0 0 0
    0 0 0 0 1 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 1 1 1 1 1 1


    Il programmino che ho scritto è il seguente:

    #include <stdio.h>
    
    #define N 10
    
    int main()
    {
        int i, j;
        for(i=0; i<N; i++)
        {
            for(j=0; j<N; j++)
                printf("%d ", (i==0 || i==N-1 || i+j==N-1)?1:0);
            
            printf("\n");
        } 
    
    return 0;
    }
    

    Secondo voi si può compattare ulteriormente?

  2. #2
    L'avatar di bottomap
    bottomap non è in linea Amanuense
    Ciao,

    A livello di codice direi di no, a meno di non modificare del tutto l'approccio. Forse potresti tirare fuori la prima e l'ultima riga, che sono costanti, da entrambi i cicli (ovviamente se in un'ottica più generale questo è fattibile), risparmiandoti 2*N confronti.

    Andrebbe valutato un poco, ma a parte la prima e l'ultima riga hai una sequenza binaria di potenze del due se guardi agli uni e agli zeri come bit...
    Passare dalla riga X alla X+1 è un'operazione di shift a sinistra, però è necessario del codice che poi scompatti e stampi il binario a schermo. Viste e considerate le operazioni di contorno, probabilmente la strada è peggiore di quella che hai scelto tu.

    Per quanto riguarda l'occupanzione di memoria invece, un'oggetto come quella matrice (qualora dovessi leggere i dati invece di generarli al volo) potrebbe essere compresso con qualche forma di codifica (anche RLE, visto che alla fine hai due simboli).

    Ciaociao
    Ultima modifica di bottomap; 22-12-2009 17:21 
    ℹ️ Leggi di più su bottomap ...

  3. #3
    Quote Originariamente inviato da jmimmo82 Visualizza il messaggio
    Dato il codice sorgente di un programma, la minimizzazione del tempo di esecuzione e del numero di istruzioni è una di quelle sfide che più mi affascinano.
    Vale la pena di rilevare che parlare di ottimizzazione in astratto ha, in generale, validità unicamente in campo algoritmico, e sempre in relazione ad una data architettura - un algoritmo seriamente ottimizzato per una PRAM non ha neppure vagamente lo stesso aspetto di un algoritmo per un quantum computer (es. l'algoritmo di Shor) o per una banale macchina Von Neumann.

    In altri casi, si deve necessariamente fare riferimento ad una precisa catena che comprende compilatore e accessori, e soprattutto una ben specifica piattaforma hardware, o al più una famiglia affine di processori monomarca per i quali un singolo compilatore possa generare codice decentemente ottimizzato dal medesimo sorgente.

    Detto questo, sulle moderne piattaforme wintel la minimizzazione del tempo di esecuzione molto spesso causa un aumento del numero di istruzioni Assembly necessarie e/o del footprint in memoria: a cominciare da banalità come il loop unrolling, le copie nascoste per evitare il cache stall e garantire la coerenza di cache, oppure le innumerevoli LUT nascoste utilizzate dai compilatori e relative librerie per velocizzare talune operazioni.

    Quanto appena esposto vuol suggerire anche che il conteggio delle istruzioni necessarie, qualora il target sia l'effettiva riduzione del footprint in memoria, va effettuato solo e unicamente a livello di immagine binaria, e per comodità di lettura a livello di assembly listing.

    Uno dei primi dogmi dell'ottimizzazione è che non esiste alcuna legge elementare e lineare di corrispondenza quantitativa diretta tra istruzioni C e codice macchina generato, in special modo con compilatori "ottimizzanti" e su piattaforme superscalari.

    Il secondo dogma è che l'ultima parola sulle prestazioni spetta unicamente alle misure, effettuate in condizioni e con modalità ripetibili secondo protocolli semplici ma da seguire in modo scrupoloso.


    Discorso diverso, e limitatamente valido, è invece quello di sfruttare la compattezza dei linguaggi di alto livello e realizzare un dato algoritmo utilizzando il minimo numero di LOC nel linguaggio prescelto: si tratta tuttavia di una attività con risvolti ludico-sportivi, a margine di competizioni ben più note come Obfuscated C o Underhanded C oppure altre manifestazioni competitive che impongono limiti al numero di linee di codice utilizzabili a livello di sorgente HLL, come ad esempio alcune versioni di CRobots.


    Una osservazione in merito all'esempio proposto: tra le (poche) operazioni compiute, l'I/O a video è certamente la più lenta.
    Una ottimizzazione (forse anche misurabile) delle prestazioni a runtime si avrebbe semplicemente eliminando la printf, la cui prestazioni in footprint e tempo di esecuzione sono in pratica tra le peggiori dell'intera libreria standard, e sostituendola con altri equivalenti che non facciano uso di stringhe di formato - al limite anche con una sprintf() per linea su un apposito buffer, seguita da puts().

    Altra possibile ottimizzazione, ammesso che l'optimizer del compilatore non vi abbia già provveduto risistemando il codice per la jump prediction unit (per questo occorre sempre riferirsi all'Assembly listing !) consiste nell'utilizzare esplicitamente una struttura di supporto: una lookup table o una bitmap come suggerito sopra dal nostro ottimo bottomap, con una banale addizione per generare il codice ASCII dal valore contenuto nella singola cella/bit.
    Ciò elimina l'intera struttura condizionale ed il relativo salto, ma oblitera anche il secondo salto (eseguito ad ogni iterazione) implicito nell'operatore ternario.


    La sezione A di questa bibliografia contiene alcuni utili riferimenti introduttivi per l'arte e la scienza dell'ottimizzazione.
    ℹ️ Leggi di più su M.A.W. 1968 ...

  4. #4
    jmimmo82 non è in linea Novello
    Vi ringrazio per le interessanti risposte
    Quote Originariamente inviato da bottomap Visualizza il messaggio
    A livello di codice direi di no, a meno di non modificare del tutto l'approccio. Forse potresti tirare fuori la prima e l'ultima riga, che sono costanti, da entrambi i cicli (ovviamente se in un'ottica più generale questo è fattibile), risparmiandoti 2*N confronti.
    Ho provato a seguire il tuo suggerimento. Però mi è stato necessario un for per inizializzare una stringa che fosse identica alla prima e all'ultima riga della matrice... Il programma funziona correttamente. Dopo di che ho provato a confrontare il tempo di esecuzione dei due programmi con il comando time (trovandomi in ambiente linux).
    Ho cambiato le dimensioni della costante simbolica N da 10 a 10.000.

    Il programma originale viene eseguito in circa 12 secondi.
    Il programma ritoccato viene eseguito in circa 11,8 secondi.

    Il miglioramento è esiguo, d'altronde la complessità è rimasta O(N^2)

    Andrebbe valutato un poco, ma a parte la prima e l'ultima riga hai una sequenza binaria di potenze del due se guardi agli uni e agli zeri come bit...
    Passare dalla riga X alla X+1 è un'operazione di shift a sinistra, però è necessario del codice che poi scompatti e stampi il binario a schermo. Viste e considerate le operazioni di contorno, probabilmente la strada è peggiore di quella che hai scelto tu.
    Avevo provato a fare qualcosa del genere. Mi generavo il decimale, vi effettuavo le operazioni per cambiarne il valore da una riga all'altra e poi dovendolo riconvertire in binario alla fine ci voleva più tempo rispetto al programma di origine.

  5. #5
    jmimmo82 non è in linea Novello
    Quote Originariamente inviato da M.A.W. 1968 Visualizza il messaggio
    Detto questo, sulle moderne piattaforme wintel la minimizzazione del tempo di esecuzione molto spesso causa un aumento del numero di istruzioni Assembly necessarie e/o del footprint in memoria: a cominciare da banalità come il loop unrolling, le copie nascoste per evitare il cache stall e garantire la coerenza di cache, oppure le innumerevoli LUT nascoste utilizzate dai compilatori e relative librerie per velocizzare talune operazioni.

    Quanto appena esposto vuol suggerire anche che il conteggio delle istruzioni necessarie, qualora il target sia l'effettiva riduzione del footprint in memoria, va effettuato solo e unicamente a livello di immagine binaria, e per comodità di lettura a livello di assembly listing.
    Quindi dici che l'importante è ridurre il footprint in memoria RAM. Ma allora, la vecchia storia del programmatore che è bravo perché implementa le funzionalità richieste con poche righe di codice deriva da quando si programmava in Assembly o in linguaggi di alto livello compilati per le medesime architetture di calcolatori?


    Una osservazione in merito all'esempio proposto: tra le (poche) operazioni compiute, l'I/O a video è certamente la più lenta.
    Una ottimizzazione (forse anche misurabile) delle prestazioni a runtime si avrebbe semplicemente eliminando la printf, la cui prestazioni in footprint e tempo di esecuzione sono in pratica tra le peggiori dell'intera libreria standard, e sostituendola con altri equivalenti che non facciano uso di stringhe di formato - al limite anche con una sprintf() per linea su un apposito buffer, seguita da puts().

    Altra possibile ottimizzazione, ammesso che l'optimizer del compilatore non vi abbia già provveduto risistemando il codice per la jump prediction unit (per questo occorre sempre riferirsi all'Assembly listing !) consiste nell'utilizzare esplicitamente una struttura di supporto: una lookup table o una bitmap come suggerito sopra dal nostro ottimo bottomap, con una banale addizione per generare il codice ASCII dal valore contenuto nella singola cella/bit.
    Ciò elimina l'intera struttura condizionale ed il relativo salto, ma oblitera anche il secondo salto (eseguito ad ogni iterazione) implicito nell'operatore ternario.
    Farò qualche prova.

    grazie
    ciao

  6. #6
    Il conteggio delle linee di codice effettive (LOC) nei linguaggi di alto livello HLL è una metrica elementare che riveste un'importanza decisamente ridotta dal punto di vista dell'ottimizzazione in prestazioni o in spazio. Esistono numerose altre metriche ingegneristiche relative agli HLL (es. Function Points, McCabe, Halstead, e naturalmente la solita orgia di acronimi della Chidamber & Kemerer...), e quasi nessuna ha risvolti immediati nel campo dell'ottimizzazione.

    Le solide ragioni per cui si parla ancor oggi di minimizzazione del footprint, in Assembly, come sinonimo quasi deterministico di "ottimizzazione" sono legate alle architetture x86 arcaiche ed alle notevoli sfide imposte negli anni Ottanta dal software di base (BIOS e SO). Tali problematiche oggi persistono nelle innumerevoli piattaforme embedded RISC, che sovente hanno a disposizione pochi kb per la program memory e spesso meno di un kb per la RAM dati ma possono anche contare su una ISA (architettura del set di istruzioni) ortogonale, ultraridotta e progettata con molto maggiore cognizione di causa rispetto ai primordiali tentativi dell'8086 - purtroppo rimasti a penalizzare anche le attuali generazioni di processori Intel a causa della retrocompatibilità.


    Viceversa, ottimizzare in un HLL significa sovente solo scegliere quegli idiomi, quelle strutture dati e quelle funzioni di libreria che indirettamente danno luogo al risultato desiderato, tramite misure e approssimazioni successive e sfruttando un ampio body of knowledge (esperienza ingegneristica collettiva) ed un idea non troppo vaga del funzionamento di compilatore, librerie (standard e di runtime), linker, loader, formato dell'eseguibile, interazione col SO, e numerosi altri dettagli.
    ℹ️ Leggi di più su M.A.W. 1968 ...

+ Rispondi al messaggio

Potrebbero interessarti anche ...

  1. Decodificare semplici operazioni
    Da systemgvp nel forum Delphi
    Risposte: 3
    Ultimo Post: 16-12-2016, 18:33
  2. Articolo: [VBA] Combinazioni Semplici e con Ripetizione
    Da MarcoGG nel forum Microsoft Word
    Risposte: 5
    Ultimo Post: 30-04-2010, 19:16
  3. 2 semplici domande
    Da Mauro T nel forum Visual Basic 6
    Risposte: 1
    Ultimo Post: 21-07-2008, 11:04
  4. Menù Programmi di WinXP:la lista dei programmi è parziale!
    Da elios81 nel forum Microsoft Windows
    Risposte: 2
    Ultimo Post: 06-12-2005, 22:42
  5. Semplici domande Newbie!
    Da Maphia nel forum Tutto Linux
    Risposte: 5
    Ultimo Post: 28-12-2004, 02:14