Ottimizzare C++/Tecniche generali di ottimizzazione

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.

Input/Output

Chiamate di sistema

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":

#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

File "memory_file.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
}

File "memory_file_test.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";
}

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:

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];
}

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:

double f(double x, double y) {
    return sqrt(x * x + y * y);
}

può convenire 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;
}

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:

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;
}

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

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.

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.

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.

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

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.

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

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.

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

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.