Ottimizzare C++/Tecniche generali di ottimizzazione: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Nuova pagina: In questa sezione vengono proposte alcune tecniche di ottimizzazione algoritmica di ampia utilizzabilità, e sostanzialmente indipendenti sia dal linguaggio di programmazione, che dall...
(Nessuna differenza)

Versione delle 09:41, 11 mag 2008

In questa sezione vengono proposte alcune tecniche di ottimizzazione algoritmica di ampia utilizzabilità, e sostanzialmente indipendenti sia dal linguaggio di programmazione, che dalla piattaforma software e hardware. 4.1. Input/Output 4.1.1. Per eseguire operazioni di input/output, invece di usare le primitive del linguaggio, usa direttamente le chiamate al sistema operativo.

Le primitive di I/O dei linguaggi di programmazione sono pensate soprattutto tenendo conto della comodità d’uso invece che le prestazioni, in quanto solitamente per tale codice il collo di bottiglia non è il processore, ma la periferica. Tuttavia, a volte si vuole ottimizzare anche il codice eseguito per effettuare operazioni di I/O. Inoltre, nel caso del C++, la libreria degli stream è particolarmente inefficiente. Le chiamate al sistema operativo garantiscono la massima efficienza, a costo di rinunciare alla portabilità ad altri sistemi operativi, e di dover gestire manualmente la formattazione, la bufferizzazione, e gli errori. 4.1.2. Invece di memorizzare i dati su file in modalità testuale, memorizzali in formato binario.

I numeri in formato binario occupano mediamente meno spazio, e quindi richiedono meno tempo per essere letti da disco e scritti su disco, ma, soprattutto, scrivendo e leggendo i dati nello stesso formato che hanno in memoria non c’è bisogno di nessuna conversione da o verso il formato testuale. 4.1.3. Eccetto che in una sezione critica di un sistema real-time, se devi accedere a gran parte di un file binario in modo non-sequenziale, invece di accedervi ripetutamente con operazioni di seek oppure di caricarlo tutto in un buffer dell’applicazione, usa i Memory Mapped File, se il sistema operativo fornisce tale strumento.

Mentre le operazioni di posizionamento (seek) richiedono un certo tempo, con i memory mapped file tali operazioni diventano semplici assegnazioni a un puntatore.

Per quanto riguarda il caricamento in memoria di un intero file per elaborazioni successive, usando le primitive di lettura di file i dati vengono letti prima nella cache del disco e poi nella memoria del processo, mentre con i memory mapped file si accede direttamente al buffer caricato dal disco, risparmiando così sia un’operazione di copia che lo spazio di memoria per la cache del disco. Analoga situazione si ha per la scrittura su disco.

Inoltre, se più processi devono caricare in memoria lo stesso file, lo spazio di memoria viene allocato per ogni processo, mentre usando i memory mapped file il sistema operativo tiene in memoria una sola copia dei dati, condivisa da tutti i processi.

Infine, in condizioni di scarsità di memoria, il sistema operativo scrive nell'area di swap del disco anche la memoria del processo che non è stata modificata, mentre si limita a scartare le pagine non modificate del memory mapped file, senza scriverle sul disco.

Tuttavia, l’uso di memory mapped file non è appropriato in una porzione critica di un sistema real-time, in quanto l'accesso a tali dati ha una latenza fortemente variabile a seconda che il dato acceduto sia in cache o su disco.

A rigore, questa è una tecnica dipendente dalla piattaforma, in quanto la funzionalità dei memory mapped files non esiste in tutti i sistemi operativi. Tuttavia, dato che tale funzionalità esiste in tutti i principali sistemi operativi dotati di memoria virtuale, questa tecnica si può considerare di ampia applicabilità. 4.2. Caching

Le tecniche di caching si basano sul principio che se una funzione pura (o funzione matematica) deve essere calcolata più volte per un dato argomento, e tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che si esegue la funzione, e ritornando il valore salvato le volte successive. 4.2.1. Se devi calcolare spesso una funzione avente come dominio un piccolo intervallo di numeri interi, pre-calcola (in fase di sviluppo del software o in fase di inizializzazione dell’applicazione) tutti i valori della funzione per ogni valore del dominio e ponili in un array statico, detto “lookup-table”. Quando dovrai calcolare il valore della funzione per un dato valore del dominio, preleva l’elemento corrispondente dell’array.

L’accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, si può usare la seguente funzione:

double sqrt10(int i) {

   static double lookup_table[] = {
       0, 1, sqrt(2.), sqrt(3.), 2,
       sqrt(5.), sqrt(6.), sqrt(7.), sqrt(8.), 3,
   };
   assert(0 <= i && i < 10);
   return lookup_table[i];

}

4.2.2. Se devi calcolare spesso una funzione con gli stessi argomenti, salva in variabili statiche gli argomenti e il risultato. Quando devi calcolare la funzione, confronta i nuovi argomenti con quelli vecchi. Se coincidono, rendi il risultato memorizzato, altrimenti calcola il risultato e memorizza nelle variabili statiche gli argomenti e il risultato.

Per esempio, invece di scrivere:

double f(double x, double y) {

   return sqrt(x * x + y * y);

}

si può scrivere:

double f(double x, double y) {

   static double prev_x = 0;
   static double prev_y = 0;
   static double result = 0;
   if (x == prev_x && y == prev_y) {
       return result;
   }
   prev_x = x;
   prev_y = y;
   result = sqrt(x * x + y * y);
   return result;

}

Si noti che, per avere un vantaggio prestazionale, non è necessario che la funzione sia chiamata con gli stessi parametri per tutta l’esecuzione del programma. È sufficiente che sia chiamata alcune volte con gli stessi parametri, poi altre volte con altri parametri, e così via. In tale caso, il calcolo viene effettuato solo al cambiamento dei parametri.

Ovviamente, questa soluzione peggiora le prestazioni, invece di migliorarle, nel caso in cui la funzione è chiamata con parametri variabili spesso, o se il confronto tra i parametri nuovi e quelli vecchi richiede più tempo del calcolo della funzione.

Questo algoritmo è detto anche "caching a un posto", in quanto si memorizza solo una coppia argomento-risultato. 4.2.3. Se devi calcolare spesso una funzione avente un dominio limitato, usa una mappa inizialmente vuota. Quando devi calcolare la funzione, cerca l’argomento nella mappa. Se lo trovi, rendi il valore associato, altrimenti calcola il risultato e inserisci nella mappa la coppia argomento-risultato.

In alcuni casi, la funzione viene chiamata con parametri variabili, ma appartenenti a un insieme molto limitato. In tale caso si può implementare una cache a più posti, invece di una cache a un singolo posto, come quella appena vista. Ecco un esempio, riferito alla stessa funzione di sopra:

double f(double x, double y) {

   static const int n_buckets = 8; // Dovrebbe essere una potenza di 2
   static struct {
       double x; double y; double result;
   } cache[n_buckets];
   static int last_read_i;
   static int last_written_i;
   int i = last_read_i;
   do {
       if (cache[i].x == x && cache[i].y == y) {
           return cache[i].result;
       }
       i = (i + 1) % n_buckets;
   } while (i != last_read_i);
   last_read_i = last_written_i = (last_written_i + 1) % n_buckets;
   cache[last_written_i].x = x;
   cache[last_written_i].y = y;
   cache[last_written_i].result = sqrt(x * x + y * y);
   return cache[last_written_i].result;

}

Si noti che l’uso di variabili statiche rende la routine non più thread-safe. Se questa routine deve poter essere chiamata contemporaneamente da più thread, è necessario sostituire le variabili statiche con variabili distinte per ogni thread.

Si noti anche che negli esempi si assumeva che la funzione valesse 0 per i parametri di input entrambi zero. In caso contrario, si dovrebbe, o inizializzare il campo result al valore appropriato, o aggiungere un flag che indica se tale campo ha un valore valido e controllare tale flag, o usare un valore inammissibile per il campo result come indicatore del fatto che non contiene un valore valido.

Per cache piccole, nel caso sopra di 8 elementi, l’algoritmo più efficiente è la scansione sequenziale su un array. Tuttavia, se si volesse fare una cache di dimensioni maggiori, sarebbero più efficienti un albero di ricerca o una hashtable.

Si noti infine, che la ricerca parte sempre dall’ultimo elemento letto, che solitamente è il più probabile, e la scrittura in cache di un elemento non presente sovrascrive l’elemento successivo all’ultimo elemento scritto, cioè si sostituisce l’elemento meno recentemente scritto. Un algoritmo migliore sarebbe sostituire l’elemento meno recentemente letto, ma richiederebbe che si prenda nota dei tempi di accesso.

Questo algoritmo è detto anche "caching a N posti". 4.3. Altre tecniche 4.3.1. Prima di confrontare una stringa con una serie di altre stringhe, trasforma tutte le stringhe in lettere maiuscole (o in minuscole), ed esegui il confronto distinguendo tra minuscole e maiuscole (case-sensitive).

Il confronto tra stringhe case-insensitive costa di più del confronto case-sensitive. 4.3.2. In una classe, invece di definire una funzione che restituisce al chiamante una collezione di dati, definisci una funzione che restituisce un iteratore di uscita, con il quale si possono generare i dati richiesti.

Supponiamo di avere una collezione (o un insieme di collezioni) incapsulati in una classe. Tale classe espone uno o più metodi per estrarre (o filtrare) da tale collezione un sottoinsieme. Un modo di ottenere ciò è costruire una nuova collezione, copiarci i dati estratti, e restituire tale collezione al chiamante. Questa tecnica è però inefficiente, perché ognuna delle suddette operazioni è costosa.

Ecco una tecnica equivalente ma più efficiente. La funzione rende un iteratore di ingresso (input iterator). Il chiamante usa tale iteratore per estrarre, uno alla volta i dati filtrati.

Si noti che questa soluzione non è del tutto equivalente, in quanto se durante l’uso dell’iteratore la collezione viene modificata da un’altra chiamata all’oggetto che incapsula la collezione, eventualmente proveniente da un altro thread, può succedere che l’iteratore sia invalidato, o anche solo che l’insieme filtrato non corrisponda ai criteri impostati. Pertanto questa tecnica è da usare solo se si ha la certezza che la collezione sottostante non viene modificata da nessuno, se non tramite l’iteratore stesso, durante tutta la vita dell'iteratore.

Questa tecnica è indipendente dal linguaggio di programmazione, in quanto il concetto di iteratore è un design pattern, implementabile in qualsiasi linguaggio. 4.3.3. Per cercare numerose volte in una collezione che viene variata raramente o mai, invece di usare un albero di ricerca o una hashtable, può essere più efficiente porre i dati in un array, ordinare l'array, e usare la ricerca binaria.

Se l'array viene saltuariamente modificato, l'algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.

Se la modifica consiste in un singolo inserimento o modifica o eliminazione di un elemento, conviene effettuare degli scorrimenti nell'array.

Se invece la modifica è più massiccia, conviene ricreare tutto l'array. 4.3.4. Per ordinare un insieme di dati aventi un range limitato, usa l’algoritmo countingsort.

L’algoritmo countingsort ha complessità O(N+M), dove N è il numero di elementi da ordinare e M è il range delle chiavi di ordinamento, cioè la differenza tra la chiave massima e la chiave minima. Nel caso in cui si vogliano ordinare N elementi la cui chiave è un numero intero appartenente a un intervallo di non oltre 2 * N valori, questo algoritmo può essere notevolmente più veloce di quicksort. A volte è più veloce anche per range più grandi, fino a 50 * N.

Questo algoritmo può essere usato anche per un ordinamento parziale; per esempio, se la chiave è un intero compreso tra zero e un miliardo, si può ordinare solamente in base al byte più significativo della chiave, così da ottenere un ordine tale per cui per ogni n vale la formula a[n] < a[n + 1] + 256*256*256. 4.3.5. Se per una lista ti basta l’iteratore in avanti, inserire gli elementi solo all’inizio o dopo l’elemento corrente, e non ti serve sapere quanti elementi ci sono nella lista, usa un oggetto “slist” (o in C++0x, “forward_list”).

La “slist”, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.

Infatti, tipicamente, l’intestazione di un oggetto “std::list” contiene un puntatore alla cima, un puntatore al fondo della lista, e il contatore del numero di elementi, mentre l’intestazione di un oggetto “slist” contiene solo un puntatore alla cima della lista. Inoltre, tipicamente, ogni nodo di un oggetto “std::list” contiene un puntatore all’elemento precedente e un puntatore all’elemento successivo, mentre ogni nodo di un oggetto “slist” contiene solo un puntatore all’elemento successivo. Infine, ogni inserimento di un elemento da un oggetto “std::list” deve aggiornare quattro puntatori e un contatore, mentre ogni inserimento da un oggetto “slist” deve aggiornare solo due puntatori. 4.3.6. Se devi solo dividere una sequenza in due gruppi in base a un criterio, usa un algoritmo di partizionamento, invece di uno di ordinamento.

In STL c'è l'algoritmo partition, che è più veloce dell'algoritmo sort, in quanto ha complessità O(N). 4.3.7. Se non devi mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile.

In STL c'è l'algoritmo stable_partition, che è leggermente più lento dell'algoritmo partition, e c'è l'algoritmo stable_sort, che è leggermente più lento dell'algoritmo sort. 4.3.8. Se devi solo individuare i primi N elementi di una sequenza, o l'N-esimo elemento di una sequenza, usa un algoritmo di partizionamento d'ordine, invece di un ordinamento.

In STL c'è l'algoritmo nth_element, che, pur essendo è leggermente più lento dell'algoritmo stable_partition, è notevolmente più veloce dell'algoritmo sort, in quanto ha complessità O(N). 4.3.9. Se devi solo ordinare i primi N elementi di una sequenza, usa un algoritmo di statistica d'ordine, invece di un ordinamento.

In STL ci sono gli algoritmi partial_sort e partial_sort_copy, che, pur essendo più lenti di dell'algoritmo nth_element, sono tanto più veloci dell'algoritmo sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.