Ottimizzare C++/Ciclo di vita dell’ottimizzazione

Indice del libro

La costruzione di un'applicazione efficiente dovrebbe procedere secondo il seguente processo di sviluppo:

  1. Progettazione (design). Dapprima, si progettano gli algoritmi e le strutture dati in modo tale che abbiano senso per la logica applicativa, e che siano ragionevolmente efficienti, ma senza occuparsi di ottimizzarle. Dove si deve definire una struttura dati di ampio utilizzo e per la quale non è ovvio quale sia l'implementazione ottimale (per esempio, non si sa scegliere tra un array e una lista collegata), si definisce una struttura astratta, la cui implementazione possa essere cambiata in fase di ottimizzazione.
  2. Codifica (coding). Poi si scrive il codice che implementa gli algoritmi progettati, seguendo linee-guida che permettano di evitare alcune operazioni inefficienti e di incapsulare le operazioni che probabilmente richiederanno ottimizzazioni.
  3. Collaudo funzionale (functional testing). Poi si collauda il software prodotto, in modo da aumentare la probabilità che non abbia difetti rilevanti.
  4. Ottimizzazione (tuning). Dopo aver completato lo sviluppo di un'applicazione o libreria funzionante correttamente, si passa alla fase di ottimizzazione, costituita dalle seguenti sotto-fasi:
    1. Collaudo prestazionale (performance testing). Si valuta quali comandi hanno prestazioni inadeguate, cioè si identificano i comandi che, elaborando dei dati tipici, richiedono più memoria o più tempo di quelli massimi specificati nei requisiti.
    2. Analisi delle prestazioni. Per ogni comando avente prestazioni inadeguate, si determina, usando un profiler, quali porzioni di codice costituiscono i cosiddetti colli di bottiglia per tale comando. Cioè si identificano le porzioni di codice nelle quali, tra l'inizio del comando e il suo completamento, viene trascorso più tempo e viene allocata più memoria.
    3. Ottimizzazione algoritmica. Nei colli di bottiglia, si applicano tecniche di ottimizzazione sostanzialmente indipendenti dal linguaggio di programmazione, e totalmente indipendenti dalla piattaforma. Sono le tecniche che si trovano nei testi di teoria degli algoritmi. In pratica, si cerca di ridurre il numero di istruzioni eseguite, e in particolare il numero delle chiamate a routine costose, oppure a trasformare le chiamate costose in chiamate equivalenti ma meno costose. Per esempio, si sceglie di implementare l'algoritmo di ordinamento quick sort invece dell'algoritmo selection sort. Se questa ottimizzazione rende il programma sufficientemente veloce, si termina l'ottimizzazione.
    4. Ottimizzazione indipendente dalla piattaforma. Nei colli di bottiglia, si adottano tecniche di ottimizzazione dipendenti dal linguaggio di programmazione e dalla sua libreria standard, ma indipendenti sia dalla piattaforma software che dalla piattaforma hardware. Per esempio, si usano operazioni intere invece di operazioni a virgola mobile, o si sceglie il tipo di contenitore più appropriato tra quelli disponibili nella libreria standard. Se questo rende il programma sufficientemente veloce, si termina l'ottimizzazione.
    5. Ottimizzazione dipendente dalla piattaforma software. Nei colli di bottiglia, si adottano tecniche di ottimizzazione dipendenti sia dal linguaggio di programmazione che dalla piattaforma software, ma indipendenti dalla piattaforma hardware. Per esempio, si sfruttano le opzioni di compilazione, le direttive pragma di compilazione, le estensioni al linguaggio offerte da un particolare compilatore, si usano librerie non-standard, o si chiama direttamente il sistema operativo. Se questo rende il programma sufficientemente veloce, si termina l’ottimizzazione.
    6. Ottimizzazione dipendente dalla piattaforma hardware. Nei colli di bottiglia si adottano tecniche di ottimizzazione dipendenti dalla piattaforma hardware, cioè o istruzioni macchina che esistono solo su una particolare famiglia di processori, o costrutti ad alto livello che, pur essendo eseguibili su qualunque processore, risultano vantaggiose solo su alcuni tipi di processore.

Questo processo di sviluppo segue due criteri:

  • Principio delle rese calanti. Le ottimizzazioni che danno grandi risultati con poco sforzo devono essere applicate per prime, in quanto così si minimizza il tempo necessario a raggiungere gli obiettivi prestazionali.
  • Principio della portabilità calante. È meglio applicare prima le ottimizzazioni applicabili su più piattaforme, in quanto rimangono applicabili anche cambiando piattaforma, e in quanto sono di più facile comprensione per altri programmatori.

Nei rari casi di software che dovrà funzionare con più compilatori e su più sistemi operativi ma su un solo tipo di processore, le fasi 4.5 e 4.6 dovrebbero essere invertite.

Questa sequenza di fasi non va affatto interpretata come una sequenza a senso unico, cioè tale per cui una volta raggiunta una fase non si torna più alla fase precedente. In realtà ogni fase può avere successo o fallire. Se ha successo, si passa alla fase successiva, se fallisce si torna alla fase precedente.

Inoltre, un collaudo parziale delle prestazioni deve essere eseguito dopo ogni tentativo di ottimizzazione, per verificare se il tentativo risulta utile, e, in caso affermativo, per verificare se risulta risolutivo, cioè se sono necessarie altre ottimizzazioni.

Infine, dopo aver completato la fase di ottimizzazione, si devono ripetere sia il collaudo funzionale che il collaudo prestazionale completo, per garantire che la nuova versione ottimizzata del software non sia peggiorata né per la correttezza né per le prestazioni complessive.

Questo testo approfondisce solo tre delle fasi citate:

  • La fase 2, limitatamente all'uso del linguaggio C++, nel capitolo "Scrivere codice efficiente".
  • Alcune tecniche generali relative alla fase 4.3, con esempi in C++, nel capitolo "Tecniche generali di ottimizzazione".
  • La fase 4.4, limitatamente all'uso del linguaggio C++, nel capitolo "Ottimizzazione del codice".

Notazioni terminologiche

modifica

Per oggetto si intende una regione allocata di memoria. In particolare, un dato associato a una variabile di un tipo fondamentale (come bool, double, unsigned long, o un puntatore) è un oggetto, così come lo è la struttura dati associata a un'istanza di una classe. A ogni variabile è associato un oggetto, la cui lunghezza si ottiene con l'operatore del C++ sizeof, ma un oggetto potrebbe non avere nessuna variabile associata a esso, oppure più variabili associate a esso. Per esempio, un puntatore è un oggetto, ma può puntare a un altro oggetto; tale oggetto puntato non è associato a nessuna variabile. D'altra parte, nel seguente codice, sia la variabile a che la variabile b sono associate allo stesso oggetto:

int a;
int& b = a;

Gli array, le strutture, e le istanze di classi sono oggetti che, se non sono vuoti, contengono sotto-oggetti. Perciò, tali oggetti verranno chiamati oggetti composti (sinonimo di oggetti compositi o oggetti aggregati).

Diciamo che un oggetto possiede un altro oggetto se la deallocazione del primo oggetto comporta la deallocazione del secondo. Per esempio, un oggetto vector non vuoto tipicamente contiene un puntatore a un buffer contenente gli elementi; la distruzione del vector comporta la distruzione di tale buffer, e quindi diciamo che questo buffer è posseduto dall'oggetto vector.

Alcune ottimizzazioni risultano utili solo per brevi sequenze di dati, altre per sequenze più lunghe. In seguito, si userà la seguente classificazione per le dimensioni degli oggetti:

  • Piccolissimo: Non oltre 8 byte. Sta in uno o due registri a 32 bit o in un registro a 64 bit.
  • Piccolo: Oltre 8 byte, ma non oltre 64 byte. Non sta in un registro del processore, ma sta in una linea della cache dei dati del processore, e può essere interamente indirizzato da istruzioni macchina molto compatte tramite uno scostamento rispetto all'indirizzo iniziale.
  • Medio: Oltre 64 byte, ma non oltre 4096 byte. Non sta in una linea della cache dei dati del processore, e non può essere interamente indirizzato da istruzioni macchina compatte, ma sta nella cache dei dati di primo livello del processore, sta in una pagina di memoria virtuale, e sta in un cluster della memoria di massa.
  • Grande: Oltre 4096 byte. Non sta nella cache dei dati di primo livello del processore, non sta in una sola pagina di memoria virtuale, e non sta in un solo cluster della memoria di massa.

Per esempio, un array di double è considerato piccolissimo solo se contiene esattamente un elemento, piccolo se ha da 2 a 8 elementi, medio se ne ha da 9 a 512, grande se ne ha più di 512.

Dato che ci sono architetture hardware molto variabili, i numeri suddetti sono solo indicativi. Tuttavia, tali numeri sono abbastanza realistici, e possono essere considerati seriamente come criteri per sviluppare del software che copra le principali architetture in modo piuttosto efficiente.