C++
Ottimizzazione in C ++

Ottimizzazione della classe base vuota

Un oggetto non può occupare meno di 1 byte, in quanto i membri di un array di questo tipo avrebbero lo stesso indirizzo. Quindi sizeof(T)>=1 sempre valido. È anche vero che una classe derivata non può essere più piccola di nessuna delle sue classi base. Tuttavia, quando la classe base è vuota, la sua dimensione non è necessariamente aggiunta alla classe derivata:

class Base {};

class Derived : public Base
{
public:
    int i;
};

In questo caso, non è necessario allocare un byte per Base in Derived per avere un indirizzo distinto per tipo per oggetto. Se viene eseguita l'ottimizzazione della classe base vuota (e non è richiesto alcun riempimento), quindi sizeof(Derived) == sizeof(int) , cioè, non viene eseguita alcuna allocazione aggiuntiva per la base vuota. Questo è possibile anche con più classi di base (in C ++, le basi multiple non possono avere lo stesso tipo, quindi non ci sono problemi da ciò).

Si noti che questo può essere eseguito solo se il primo membro di Derived differisce nel tipo da una qualsiasi delle classi di base. Questo include qualsiasi base comune diretta o indiretta. Se è lo stesso tipo di una delle basi (o c'è una base comune), è necessario allocare almeno un singolo byte per garantire che non ci siano due oggetti distinti dello stesso tipo con lo stesso indirizzo.

Introduzione alle prestazioni

C e C ++ sono noti come linguaggi ad alte prestazioni, in gran parte a causa della notevole quantità di personalizzazione del codice, che consente all'utente di specificare le prestazioni in base alla scelta della struttura.

Quando si ottimizza, è importante fare un benchmark del codice rilevante e capire completamente come verrà utilizzato il codice.

Gli errori di ottimizzazione comuni includono:

• Ottimizzazione prematura: il codice complesso può peggiorare dopo l'ottimizzazione, sprecando tempo e fatica. La prima priorità dovrebbe essere quella di scrivere codice corretto e gestibile , piuttosto che codice ottimizzato.
• Ottimizzazione per il caso d'uso sbagliato: l' aggiunta di spese generali per l'1% potrebbe non valere il rallentamento per l'altro 99%
• Micro-ottimizzazione: i compilatori lo fanno in modo molto efficiente e la micro-ottimizzazione può anche danneggiare la capacità dei compilatori di ottimizzare ulteriormente il codice

Gli obiettivi di ottimizzazione tipici sono:

• Per fare meno lavoro
• Utilizzare algoritmi / strutture più efficienti
• Per fare un uso migliore dell'hardware

Il codice ottimizzato può avere effetti collaterali negativi, tra cui:

• Maggiore utilizzo della memoria
• Il codice complesso è difficile da leggere o mantenere
• API compromessa e progettazione del codice

Ottimizzazione eseguendo meno codice

L'approccio più diretto all'ottimizzazione consiste nell'eseguire meno codice. Questo approccio di solito dà una velocità fissa senza modificare la complessità temporale del codice.

Anche se questo approccio ti dà una chiara accelerazione, questo darà solo notevoli miglioramenti quando il codice è chiamato molto.

Rimozione del codice inutile

void func(const A *a); // Some random function

// useless memory allocation + deallocation for the instance
auto a1 = std::make_unique<A>();
func(a1.get()); 

// making use of a stack object prevents 
auto a2 = A{};
func(&a2);

Fare codice solo una volta

std::map<std::string, std::unique_ptr<A>> lookup;
// Slow insertion/lookup
// Within this function, we will traverse twice through the map lookup an element
// and even a thirth time when it wasn't in
const A *lazyLookupSlow(const std::string &key) {
    if (lookup.find(key) != lookup.cend())
        lookup.emplace_back(key, std::make_unique<A>());
    return lookup[key].get();
}

// Within this function, we will have the same noticeable effect as the slow variant while going at double speed as we only traverse once through the code
const A *lazyLookupSlow(const std::string &key) {
    auto &value = lookup[key];
    if (!value)
        value = std::make_unique<A>();
    return value.get();
}

Un approccio simile a questa ottimizzazione può essere utilizzato per implementare una versione stabile di unique

std::vector<std::string> stableUnique(const std::vector<std::string> &v) {
    std::vector<std::string> result;
    std::set<std::string> checkUnique;
    for (const auto &s : v) {
        // As insert returns if the insertion was successful, we can deduce if the element was already in or not
        // This prevents an insertion, which will traverse through the map for every unique element
        // As a result we can almost gain 50% if v would not contain any duplicates
        if (checkUnique.insert(s).second)
            result.push_back(s);
    }
    return result;
}

Prevenire la ridistribuzione, la copia / lo spostamento inutili

Nell'esempio precedente, abbiamo già impedito le ricerche in std :: set, tuttavia il file std::vector contiene ancora un algoritmo in crescita, nel quale dovrà riallocare la sua memoria. Questo può essere evitato prenotando per la giusta dimensione.

std::vector<std::string> stableUnique(const std::vector<std::string> &v) {
    std::vector<std::string> result;
    // By reserving 'result', we can ensure that no copying or moving will be done in the vector
    // as it will have capacity for the maximum number of elements we will be inserting
    // If we make the assumption that no allocation occurs for size zero
    // and allocating a large block of memory takes the same time as a small block of memory
    // this will never slow down the program
    // Side note: Compilers can even predict this and remove the checks the growing from the generated code
    result.reserve(v.size());
    std::set<std::string> checkUnique;
    for (const auto &s : v) {
        // See example above
        if (checkUnique.insert(s).second)
            result.push_back(s);
    }
    return result;
}

Usare contenitori efficienti

L'ottimizzazione utilizzando le giuste strutture di dati al momento giusto può modificare la complessità temporale del codice.

// This variant of stableUnique contains a complexity of N log(N)
// N > number of elements in v
// log(N) > insert complexity of std::set
std::vector<std::string> stableUnique(const std::vector<std::string> &v) {
    std::vector<std::string> result;
    std::set<std::string> checkUnique;
    for (const auto &s : v) {
        // See Optimizing by executing less code
        if (checkUnique.insert(s).second)
            result.push_back(s);
    }
    return result;
}

Utilizzando un contenitore che utilizza un'implementazione diversa per la memorizzazione dei suoi elementi (contenitore hash anziché albero), possiamo trasformare la nostra implementazione in complessità N. Come effetto collaterale, chiameremo l'operatore di confronto per std :: string less, poiché deve essere chiamato solo quando la stringa inserita deve finire nello stesso bucket.

// This variant of stableUnique contains a complexity of N
// N > number of elements in v
// 1 > insert complexity of std::unordered_set
std::vector<std::string> stableUnique(const std::vector<std::string> &v) {
    std::vector<std::string> result;
    std::unordered_set<std::string> checkUnique;
    for (const auto &s : v) {
        // See Optimizing by executing less code
        if (checkUnique.insert(s).second)
            result.push_back(s);
    }
    return result;
}

Ottimizzazione di piccoli oggetti

L'ottimizzazione degli oggetti piccoli è una tecnica che viene utilizzata all'interno di strutture di dati di basso livello, ad esempio la std::string (talvolta denominata Ottimizzazione stringa corta / piccola). È pensato per utilizzare lo spazio di stack come buffer invece di una memoria allocata nel caso in cui il contenuto sia abbastanza piccolo da adattarsi allo spazio riservato.

Aggiungendo overhead di memoria extra e calcoli extra, si tenta di evitare una costosa allocazione dell'heap. I vantaggi di questa tecnica dipendono dall'utilizzo e possono anche danneggiare le prestazioni se utilizzate in modo errato.

Esempio

Un modo molto ingenuo per implementare una stringa con questa ottimizzazione sarebbe il seguente:

#include <cstring>

class string final
{
    constexpr static auto SMALL_BUFFER_SIZE = 16;

    bool _isAllocated{false};                       ///< Remember if we allocated memory
    char *_buffer{nullptr};                         ///< Pointer to the buffer we are using
    char _smallBuffer[SMALL_BUFFER_SIZE]= {'\0'};   ///< Stack space used for SMALL OBJECT OPTIMIZATION

public:
    ~string()
    {
        if (_isAllocated)
            delete [] _buffer;
    }        

    explicit string(const char *cStyleString)
    {
        auto stringSize = std::strlen(cStyleString);
        _isAllocated = (stringSize > SMALL_BUFFER_SIZE);
        if (_isAllocated)
            _buffer = new char[stringSize];
        else
            _buffer = &_smallBuffer[0];
        std::strcpy(_buffer, &cStyleString[0]);
    }

    string(string &&rhs)
       : _isAllocated(rhs._isAllocated)
       , _buffer(rhs._buffer)
       , _smallBuffer(rhs._smallBuffer) //< Not needed if allocated
    {
        if (_isAllocated)
        {
           // Prevent double deletion of the memory
           rhs._buffer = nullptr;
        }
        else
        {
            // Copy over data
            std::strcpy(_smallBuffer, rhs._smallBuffer);
            _buffer = &_smallBuffer[0];
        }
    }
    // Other methods, including other constructors, copy constructor,
    // assignment operators have been omitted for readability
};

Come puoi vedere nel codice qui sopra, è stata aggiunta una maggiore complessità per evitare alcune operazioni new e di delete . Inoltre, la classe ha un'impronta di memoria più ampia che potrebbe non essere utilizzata, tranne in un paio di casi.

Spesso si tenta di codificare il valore bool _isAllocated , all'interno del pointer _buffer con la manipolazione del bit per ridurre la dimensione di una singola istanza (intel 64 bit: potrebbe ridurre le dimensioni di 8 byte). Un'ottimizzazione che è possibile solo quando è noto quali sono le regole di allineamento della piattaforma.

Quando usare?

Poiché questa ottimizzazione aggiunge molta complessità, non è consigliabile utilizzare questa ottimizzazione su ogni singola classe. Si incontrerà spesso in strutture di dati di basso livello di uso comune. Nelle comuni implementazioni di standard library C ++ 11 si possono trovare usi in std::basic_string<> e std::function<> .

Poiché questa ottimizzazione impedisce solo allocazioni di memoria quando i dati memorizzati sono più piccoli del buffer, darà benefici solo se la classe viene spesso utilizzata con dati di piccole dimensioni.

Un ultimo svantaggio di questa ottimizzazione è che è necessario uno sforzo supplementare quando si sposta il buffer, rendendo l'operazione di spostamento più costosa rispetto a quando il buffer non verrebbe utilizzato. Questo è particolarmente vero quando il buffer contiene un tipo non POD.