C++
Optimierung in C ++

Leere Basisklassenoptimierung

Ein Objekt darf nicht weniger als 1 Byte belegen, da dann die Mitglieder eines Arrays dieses Typs dieselbe Adresse hätten. Also gilt sizeof(T)>=1 immer. Es ist auch wahr , dass eine abgeleitete Klasse nicht als eine ihrer Basisklassen kleiner sein kann. Wenn die Basisklasse jedoch leer ist, wird ihre Größe nicht notwendigerweise zur abgeleiteten Klasse hinzugefügt:

class Base {};

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

In diesem Fall ist es nicht erforderlich, ein Byte für Base in Derived zuzuordnen, um pro Objekt und Objekt eine eindeutige Adresse zu erhalten. Wenn eine leere Basisklassenoptimierung durchgeführt wird (und keine Auffüllung erforderlich ist), dann sizeof(Derived) == sizeof(int) , sizeof(Derived) == sizeof(int) , es wird keine zusätzliche Zuordnung für die leere Basis vorgenommen. Dies ist auch mit mehreren Basisklassen möglich (in C ++ können nicht mehrere Basen denselben Typ haben, daher treten keine Probleme auf).

Beachten Sie, dass dies nur möglich ist, wenn der erste Member von Derived sich von den Basisklassen in seinem Typ unterscheidet. Dies schließt jegliche direkte oder indirekte Basis ein. Wenn es sich um denselben Typ handelt wie eine der Basen (oder es gibt eine gemeinsame Basis), muss mindestens ein Byte zugeordnet werden, um sicherzustellen, dass keine zwei verschiedenen Objekte desselben Typs dieselbe Adresse haben.

Einführung in die Leistung

C und C ++ sind allgemein als Hochleistungssprachen bekannt - hauptsächlich aufgrund der umfangreichen Anpassungen von Code, die es einem Benutzer ermöglichen, die Leistung durch die Wahl der Struktur festzulegen.

Bei der Optimierung ist es wichtig, den relevanten Code zu vergleichen und zu verstehen, wie der Code verwendet wird.

Häufige Optimierungsfehler sind:

• Vorzeitige Optimierung: Komplexer Code kann nach der Optimierung schlechter ablaufen, was Zeit und Mühe kostet. Die erste Priorität sollte das Schreiben von korrektem und wartungsfähigem Code anstelle von optimiertem Code sein.
• Optimierung für den falschen Anwendungsfall: Das Hinzufügen von Overhead für die 1% ist möglicherweise nicht die Verlangsamung für die anderen 99% wert.
• Mikrooptimierung: Compiler machen dies sehr effizient, und Mikrooptimierung kann sogar die Fähigkeit des Compilers beeinträchtigen, den Code weiter zu optimieren

Typische Optimierungsziele sind:

• Weniger arbeiten
• Effizientere Algorithmen / Strukturen verwenden
• Hardware besser nutzen

Optimierter Code kann negative Nebenwirkungen haben, einschließlich:

• Höhere Speicherauslastung
• Komplexer Code - schwer zu lesen oder zu warten
• Kompromissloses API- und Code-Design

Optimierung durch weniger Code ausführen

Der einfachste Ansatz zur Optimierung besteht darin, weniger Code auszuführen. Dieser Ansatz führt normalerweise zu einer festen Beschleunigung, ohne die zeitliche Komplexität des Codes zu ändern.

Auch wenn dieser Ansatz eine deutliche Beschleunigung bewirkt, führt dies nur zu spürbaren Verbesserungen, wenn der Code viel aufgerufen wird.

Nutzlosen Code entfernen

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

Code nur einmal machen

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

Ein ähnlicher Ansatz zu dieser Optimierung kann verwendet werden, um eine stabile Version von unique zu implementieren

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

Verhindern Sie unnötige Neuzuordnungen und Kopieren / Verschieben

Im vorherigen Beispiel haben wir bereits Lookups in std :: set verhindert, der std::vector enthält jedoch noch einen wachsenden Algorithmus, in dem er seinen Speicher neu zuordnen muss. Dies kann verhindert werden, indem zunächst die richtige Größe reserviert wird.

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

Effiziente Behälter verwenden

Durch die Optimierung der richtigen Datenstrukturen zum richtigen Zeitpunkt kann sich die zeitliche Komplexität des Codes ändern.

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

Durch die Verwendung eines Containers, der eine andere Implementierung zum Speichern seiner Elemente verwendet (Hash-Container statt Baum), können wir unsere Implementierung in Komplexität N umwandeln. Als Nebeneffekt rufen wir den Vergleichsoperator für std :: string less auf muss nur aufgerufen werden, wenn der eingefügte String im selben Bucket enden soll.

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

Kleinobjekt-Optimierung

Die Optimierung von kleinen Objekten ist eine Technik, die in Datenstrukturen niedriger Ebene verwendet wird, z. B. std::string (manchmal auch als kurze / kleine String-Optimierung bezeichnet). Es ist dazu gedacht, Stapelspeicher als Puffer zu verwenden, anstelle von zugewiesenem Speicher, falls der Inhalt klein genug ist, um in den reservierten Speicherplatz zu passen.

Durch das Hinzufügen von zusätzlichem Speicheraufwand und zusätzlichen Berechnungen wird versucht, eine teure Heapzuweisung zu verhindern. Die Vorteile dieser Technik hängen von der Verwendung ab und können bei falscher Verwendung sogar die Leistung beeinträchtigen.

Beispiel

Eine sehr naive Art, eine Zeichenfolge mit dieser Optimierung zu implementieren, wäre folgende:

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

Wie Sie im obigen Code sehen können, wurde etwas mehr Komplexität hinzugefügt, um einige new und delete zu verhindern. Darüber hinaus verfügt die Klasse über einen größeren Speicherbedarf, der möglicherweise nur in einigen Fällen verwendet wird.

Oft wird versucht , den Wert zu codieren bool _isAllocated innerhalb des Zeigers _buffer mit Bitmanipulation die Größe einer einzelnen Instanz (Intel - 64 - Bit: kann Größe reduzieren um 8 Byte) zu reduzieren. Eine Optimierung, die nur möglich ist, wenn die Ausrichtungsregeln der Plattform bekannt sind.

Wann verwenden?

Da diese Optimierung die Komplexität erhöht, wird nicht empfohlen, diese Optimierung für jede einzelne Klasse zu verwenden. Sie wird häufig in häufig verwendeten Datenstrukturen niedriger Ebene angetroffen. In gängigen C ++ 11- standard library finden Sie Verwendungen in std::basic_string<> und std::function<> .

Da diese Optimierung nur Speicherzuordnungen verhindert, wenn die gespeicherten Daten kleiner als der Puffer sind, bietet dies nur Vorteile, wenn die Klasse häufig mit kleinen Daten verwendet wird.

Ein letzter Nachteil dieser Optimierung besteht darin, dass beim Verschieben des Puffers ein zusätzlicher Aufwand erforderlich ist, was den Verschiebevorgang teurer macht, als wenn der Puffer nicht verwendet würde. Dies gilt insbesondere, wenn der Puffer einen Nicht-POD-Typ enthält.