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

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica
Riga 1: 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.
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.


* [[Ottimizzare C++/Tecniche generali di ottimizzazione/Input/Output|Input/Output]]
== Input/Output ==
* [[Ottimizzare C++/Tecniche generali di ottimizzazione/Caching|Caching]]

* [[Ottimizzare C++/Tecniche generali di ottimizzazione/Ordinamento|Ordinamento]]
=== Chiamate di sistema ===
* [[Ottimizzare C++/Tecniche generali di ottimizzazione/Altre tecniche|Altre tecniche]]
'''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.

=== Formato binario ===
'''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.

=== Memory-mapped-file ===
'''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 un memory-mapped-file, se il tuo sistema operativo fornisce tale strumento.'''

Quando si deve accedere a gran parte di un file binario in modo non-sequenziale, ci sono due tecniche alternative standard:
* Aprire il file senza leggerne il contenuto; e ogni volta che si deve leggere un dato, saltare al punto di interesse usando una operazione di posizionamento nel file (''seek''), e leggere il dato usando un'operazione di lettura.
* Allocare un buffer grande quanto tutto il file, aprire il file, leggere tutto il contenuto del file nel buffer, chiudere il file; e ogni volta che si deve leggere un dato, cercarlo nel buffer.

Rispetto alla prima tecnica, usando i memory-mapped-file, ogni operazione di posizionamento viene sostituita da una semplice assegnazione a un puntatore, e ogni operazione di lettura da file viene sostituita da una semplice copia da memoria a memoria. Anche supponendo che i dati siano già nella disk cache, entrambe le operazioni effettuate con i memory-mapped-files sono notevolmente più veloci delle operazioni effettuate sui file, in quanto queste ultime comportano altrettante chiamate di libreria, le quali a loro volta effettuano chiamate di sistema.

Rispetto alla tecnica di precaricare in memoria l'intero file, usando i memory-mapped-file, si hanno i seguenti vantaggi:
* Usando le primitive di lettura di file, i dati vengono normalmente 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.
* Leggendo tutto il file, il programma si blocca per un tempo significativo per leggere il file, mentre usando un memory-mapped-file tale tempo viene distribuito nel corso dell'elaborazione, man mano che si accede alle varie parti del file.
* Se in alcune esecuzioni serve solo una piccola parte del file, il memory-mapped-file carica in memoria solo quelle parti.
* 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.
* 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à.

Ecco una classe che incapsula le primitive di accesso in sola lettura a un file tramite memory-mapped-file, utilizzabile sia nei sistemi operativi di tipo Posix (come Unix, Linux, e Mac OS X), sia in ambiente Microsoft Windows.

'''File "memory_file.hpp":'''

<source lang=cpp>
#ifndef MEMORY_FILE_HPP
#define MEMORY_FILE_HPP

/*
Wrapper di memory-mapped file per sola lettura.
Gestisce solo file che possono essere interamente caricati
nello spazio di indirizzamento del processo.
Il costruttore apre il file, il distruttore lo chiude.
La funzione "data" rende un puntatore all'inizio del file,
se il file e' stato aperto con successo, altrimenti rende 0.
La funzione "length" rende la lunghezza in byte del file,
se il file e' stato aperto con successo,
altrimenti rende 0.
*/

class InputMemoryFile {
public:
InputMemoryFile(const char *pathname);
~InputMemoryFile();
const void* data() const { return data_; }
unsigned long length() const { return length_; }
private:
void* data_;
unsigned long length_;
#if defined(__unix__)
int file_handle_;
#elif defined(_WIN32)
typedef void * HANDLE;
HANDLE file_handle_;
HANDLE file_mapping_handle_;
#else
#error Solo i sistemi Posix o Windows possono usare i memory-mapped files.
#endif
};
#endif
</source>

'''File "memory_file.cpp":'''

<source lang=cpp>
#include "memory_file.hpp"
#if defined(__unix__)
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#elif defined(_WIN32)
#include <windows.h>
#endif

InputMemoryFile::InputMemoryFile(const char *pathname):
data_(0),
length_(0),
#if defined(__unix__)
file_handle_(-1)
{
file_handle_ = open(pathname, O_RDONLY);
if (file_handle_ == -1) return;
struct stat sbuf;
if (fstat(file_handle_, &sbuf) == -1) return;
data_ = mmap(0, sbuf.st_size, PROT_READ, MAP_SHARED, file_handle_, 0);
if (data_ == MAP_FAILED) data_ = 0;
else length_ = sbuf.st_size;
#elif defined(_WIN32)
file_handle_(INVALID_HANDLE_VALUE),
file_mapping_handle_(INVALID_HANDLE_VALUE)
{
file_handle_ = ::CreateFile(pathname, GENERIC_READ,
FILE_SHARE_READ, 0, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
if (file_handle_ == INVALID_HANDLE_VALUE) return;
file_mapping_handle_ = ::CreateFileMapping(
file_handle_, 0, PAGE_READONLY, 0, 0, 0);
if (file_mapping_handle_ == INVALID_HANDLE_VALUE) return;
data_ = ::MapViewOfFile(
file_mapping_handle_, FILE_MAP_READ, 0, 0, 0);
if (data_) length_ = ::GetFileSize(file_handle_, 0);
#endif
}

InputMemoryFile::~InputMemoryFile() {
#if defined(__unix__)
munmap(data_, length_);
close(file_handle_);
#elif defined(_WIN32)
::UnmapViewOfFile(data_);
::CloseHandle(file_mapping_handle_);
::CloseHandle(file_handle_);
#endif
}
</source>

'''File "memory_file_test.cpp":'''

<source lang=cpp>
include "memory_file.hpp"
#include <iostream>
#include <iterator>

int main() {
// Scrive su console il contenuto del file sorgente.
InputMemoryFile imf("memory_file_test.cpp");
if (imf.data())
copy((const char*)imf.data(),
(const char*)imf.data() + imf.length(),
std::ostream_iterator<char>(std::cout));
else std::cerr << "Impossibile aprire il file";
}
</source>

== Caching ==

Le tecniche di ''caching'' (in inglese chiamate anche tecniche di ''memoization'') si basano sul principio che se una funzione pura (cioè una funzione matematica) deve essere calcolata più volte per lo stesso argomento, e se tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che si esegue la funzione, e recuperando il valore salvato le volte successive.

=== ''Look-up table'' ===

'''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 devi calcolare il valore della funzione per un dato valore del dominio, preleva l'elemento corrispondente di tale array.'''

L'accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Pertanto, se la look-up table non è grande, quasi sicuramente è più veloce della funzione che si deve calcolare.

Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, conviene usare la seguente funzione:

<source lang=cpp>
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];
}
</source>

Se la funzione da calcolare è piuttosto lenta, e si ha a disposizione molta memoria, può essere opportuno usare una look-up table anche se risulta piuttosto grande. Tuttavia, raramente è opportuno definire una look-up table più grande di un megabyte.

=== Caching a un posto ===

'''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:
<source lang=cpp>
double f(double x, double y) {
return sqrt(x * x + y * y);
}
</source>

può convenire scrivere:

<source lang=cpp>
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;
}
</source>

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

Ovviamente, invece di migliorare le prestazioni, questa soluzione le peggiora nel caso in cui la funzione è chiamata con argomenti variabili molto spesso, oppure se il confronto tra gli argomenti nuovi e quelli vecchi richiede più tempo del calcolo della funzione stessa.

Nota 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.

Nota anche che nell'esempio si assume che la funzione valga zero quando gli argomenti sono entrambi zero. In caso contrario, si dovrebbe adottare un'altra soluzione, come una delle seguenti:
* Inizializzare la variabile ''result'' al valore corrispondente ad argomenti tutti a valore zero.
* Inizializzare le variabili ''prev_x'' e ''prev_y'' a valori non validi come argomenti.
* Aggiungere un flag che indica se le variabili statiche hanno valori validi, e controllare tale flag.

=== Caching a N posti ===

'''Se devi calcolare spesso una funzione avente un dominio limitato, usa una mappa (o dizionario) 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 della cache a singolo posto appena vista. Ecco un esempio, riferito alla stessa funzione di sopra:

<source lang=cpp>
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 = 0;
static int last_written_i = 0;
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;
}
</source>

Anche per questo caso valgono le considerazioni riguardanti le variabili statiche, fatte al punto precedente ("Caching a un posto").

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, un albero di ricerca o una hashtable sarebbero più efficienti.

La ricerca nella cache parte sempre dall'ultimo elemento letto, in quanto solitamente è il più probabile. La scrittura nella cache di un elemento non presente sovrascrive l'elemento successivo all'ultimo elemento scritto, cioè si sostituisce l'elemento meno recentemente ''scritto'. Si avrebbe un algoritmo migliore sostituendo l'elemento meno recentemente ''letto'', ma ciò richiederebbe che si prendesse nota dell'ordine di accesso.

== Altre tecniche ==

=== Lettere maiuscole e minuscole ===

'''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 case-insensitive tra stringhe richiede più tempo del confronto case-sensitive.

=== Query con cursore ===

'''In una classe, invece di definire una funzione che restituisce al chiamante una collezione di dati (detto anche ''snapshot''), definisci una funzione che restituisce un iteratore di uscita (detto anche ''cursore'' o ''dynaset''), con il quale si possono generare i dati richiesti.'''

Questa tecnica è particolarmente utile per interrogazioni su database (o ''query''), ma è applicabile anche a strutture dati gestite internamente dall'applicazione.

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.
Nel mondo dei database, tale collezione si chiama ''snapshot''.
Questa tecnica è però inefficiente, perché ognuna delle suddette tre operazioni richiede molto tempo, e potrebbe richiede molta memoria.
Inoltre, ha il difetto che, finché non sono stati estratti tutti i dati, non si può procedere a elaborare quelli già estratti.

Ecco una tecnica equivalente ma più efficiente.
La funzione di interrogazione rende un iteratore di uscita (o ''output iterator'').
Nel mondo dei database, tale iteratore si chiama ''cursore'' o ''dynaset''.
Il chiamante usa tale iteratore per estrarre, uno alla volta i dati filtrati.

Nota 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.

=== Ricerca binaria ===

'''Se devi fare molte ricerche in una collezione che viene variata raramente o mai, invece di usare un albero di ricerca o una hashtable, puoi migliorare la velocità se poni i dati in un array, ordini l'array, e usi la ricerca binaria.'''

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

Se la modifica consiste in pochissimi inserimenti o modifiche o eliminazioni di elementi, conviene effettuare uno scorrimento dell'array ad ogni operazione.

Se invece la modifica è più massiccia, conviene ricreare tutto l'array.

=== Countingsort ===

'''Per ordinare un insieme di dati in base a una chiave intera avente 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.
In alcuni casi è 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 <math>a_n < a_{n + 1} + 256*256*256. </math>

=== Il contenitore ''slist'' ===

'''Se per una lista ti basta usare 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 contenitore di tipo ''slist'' (o, in C++0x, ''forward_list'').'''

Mentre il contenitore ''std::list'' è implementato da una lista a collegamento doppio (o bidirezionale o ''doubly-linked list''), il contenitore ''slist'', è implementato da una lista a collegamento singolo (o unidirezionale o ''singly-linked list'').

Tale contenitore, 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.

=== Partizionamento ===

'''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) invece di O(N log(N)).

=== Partizionamento e ordinamento stabili ===

'''Se devi partizionare o ordinare una sequenza per cui non è richiesto di mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile.'''

In STL c'è l'algoritmo di partizionamento ''stable_partition'', che è leggermente più lento dell'algoritmo ''partition''; e c'è l'algoritmo di ordinamento ''stable_sort'', che è leggermente più lento dell'algoritmo ''sort''.

=== Partizionamento d'ordine ===

'''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) invece di O(N log(N)).

=== Statistica d'ordine ===

'''Se devi solo ordinare i primi N elementi di una sequenza, usa un algoritmo di statistica d'ordine, invece di un algoritmo di ordinamento.'''

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


[[Categoria:Ottimizzare C++|Tecniche generali di ottimizzazione]]
[[Categoria:Ottimizzare C++|Tecniche generali di ottimizzazione]]

Versione delle 23:00, 22 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.