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

Contenuto cancellato Contenuto aggiunto
Ramac (discussione | contributi)
m ha spostato C++ ottimizzato/Tecniche generali di ottimizzazione a Ottimizzare C++/Tecniche generali di ottimizzazione: correggo il titolo
Nessun oggetto della modifica
Riga 1:
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.
 
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.
Line 20 ⟶ 24:
 
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òpuoi 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 notiNota 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 notiNota 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.
Line 98 ⟶ 105:
 
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).
 
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.
Line 111 ⟶ 121:
 
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.
Line 118 ⟶ 129:
 
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 [[Implementazioni_di_algoritmi/Counting_sort|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.