C++
Optimalisatie in C ++

Lege basisklasse optimalisatie

Een object kan niet minder dan 1 byte bezetten, omdat dan de leden van een array van dit type hetzelfde adres hebben. Dus sizeof(T)>=1 geldt altijd. Het is ook waar dat een afgeleide klasse niet kleiner kan zijn dan een van de basisklassen. Wanneer de basisklasse echter leeg is, wordt de grootte niet noodzakelijkerwijs toegevoegd aan de afgeleide klasse:

class Base {};

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

In dit geval is het niet vereist om een byte voor Base binnen Derived toe te wijzen om een verschillend adres per type per object te hebben. Als optimalisatie van de lege basisklasse wordt uitgevoerd (en geen opvulling is vereist), dan wordt sizeof(Derived) == sizeof(int) , dat wil zeggen dat er geen extra toewijzing wordt gedaan voor de lege basis. Dit is ook mogelijk met meerdere basisklassen (in C ++ kunnen meerdere basen niet hetzelfde type hebben, dus daar ontstaan geen problemen).

Merk op dat dit alleen kan worden uitgevoerd als het eerste lid van Derived in type verschilt van een van de basisklassen. Dit omvat alle directe of indirecte gemeenschappelijke bases. Als het hetzelfde type is als een van de basen (of er is een gemeenschappelijke basis), is minstens één byte toewijzen vereist om ervoor te zorgen dat geen twee verschillende objecten van hetzelfde type hetzelfde adres hebben.

Inleiding tot prestaties

C en C ++ staan bekend als high-performance talen - grotendeels vanwege de grote hoeveelheid aanpassing van de code, waardoor een gebruiker prestaties kan specificeren door de keuze van de structuur.

Bij het optimaliseren is het belangrijk om relevante code te benchmarken en volledig te begrijpen hoe de code zal worden gebruikt.

Veelvoorkomende optimalisatiefouten zijn:

• Voortijdige optimalisatie: complexe code kan na optimalisatie slechter presteren, wat tijd en moeite verspilt. De eerste prioriteit moet zijn om correcte en onderhoudbare code te schrijven in plaats van geoptimaliseerde code.
• Optimalisatie voor de verkeerde use case: overhead toevoegen voor de 1% is misschien niet de vertraging waard voor de andere 99%
• Micro-optimalisatie: compilers doen dit zeer efficiënt en micro-optimalisatie kan zelfs het vermogen van de compilers om de code verder te optimaliseren beschadigen

Typische optimalisatiedoelen zijn:

• Om minder werk te doen
• Om efficiëntere algoritmen / structuren te gebruiken
• Om hardware beter te gebruiken

Geoptimaliseerde code kan negatieve bijwerkingen hebben, waaronder:

• Hoger geheugengebruik
• Complexe code - moeilijk te lezen of te onderhouden
• Gecompromitteerd API- en code-ontwerp

Optimaliseren door minder code uit te voeren

De meest eenvoudige manier om te optimaliseren is door minder code uit te voeren. Deze aanpak geeft meestal een vaste versnelling zonder de tijdcomplexiteit van de code te wijzigen.

Hoewel deze aanpak je een duidelijke versnelling geeft, levert dit alleen merkbare verbeteringen op als de code veel wordt genoemd.

Nutteloze code verwijderen

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 slechts eenmaal uitvoeren

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

Een vergelijkbare benadering van deze optimalisatie kan worden gebruikt om een stabiele unique versie te implementeren

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

Voorkomen van nutteloze herallocatie en kopiëren / verplaatsen

In het vorige voorbeeld hebben we opzoekingen in de std :: set al voorkomen, maar de std::vector bevat nog steeds een groeiend algoritme, waarin het zijn opslag opnieuw moet toewijzen. Dit kan worden voorkomen door eerst de juiste maat te reserveren.

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

Efficiënte containers gebruiken

Optimalisatie door de juiste gegevensstructuren op het juiste moment te gebruiken, kan de tijdcomplexiteit van de code veranderen.

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

Door een container te gebruiken die een andere implementatie gebruikt voor het opslaan van zijn elementen (hashcontainer in plaats van een boom), kunnen we onze implementatie transformeren naar complexiteit N. Als bijwerking zullen we de vergelijkingsoperator voor std :: string minder noemen, omdat deze hoeft alleen te worden opgeroepen als de ingevoegde string in dezelfde bucket moet eindigen.

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

Optimalisatie van kleine objecten

Optimalisatie van kleine objecten is een techniek die wordt gebruikt binnen gegevensstructuren op laag niveau, bijvoorbeeld de std::string (soms aangeduid als korte / kleine stringoptimalisatie). Het is bedoeld om stapelruimte als buffer te gebruiken in plaats van toegewezen geheugen voor het geval de inhoud klein genoeg is om in de gereserveerde ruimte te passen.

Door extra geheugenoverhead en extra berekeningen toe te voegen, probeert het een dure heap-toewijzing te voorkomen. De voordelen van deze techniek zijn afhankelijk van het gebruik en kunnen zelfs de prestaties nadelig beïnvloeden als ze onjuist worden gebruikt.

Voorbeeld

Een zeer naïeve manier om een string met deze optimalisatie te implementeren zou het volgende zijn:

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

Zoals u in de bovenstaande code kunt zien, is wat extra complexiteit toegevoegd om enkele new en delete te voorkomen. Bovendien heeft de klasse een grotere geheugenvoetafdruk die alleen in enkele gevallen kan worden gebruikt.

Vaak wordt getracht de bool waarde coderen _isAllocated binnen de aanwijzer _buffer met bitmanipulatie de grootte van een enkel geval verminderen (Intel 64 bit: Kan duceren met 8 bytes). Een optimalisatie die alleen mogelijk is als bekend is wat de uitlijningsregels van het platform zijn.

Wanneer te gebruiken?

Omdat deze optimalisatie veel complexiteit toevoegt, wordt het niet aanbevolen om deze optimalisatie voor elke klasse te gebruiken. Het komt vaak voor in veelgebruikte datastructuren op laag niveau. In gebruikelijke C ++ 11 standard library kan men gebruik vinden in std::basic_string<> en std::function<> .

Omdat deze optimalisatie alleen geheugentoewijzingen voorkomt wanneer de opgeslagen gegevens kleiner zijn dan de buffer, biedt het alleen voordelen als de klasse vaak wordt gebruikt met kleine gegevens.

Een laatste nadeel van deze optimalisatie is dat extra inspanning vereist is bij het verplaatsen van de buffer, waardoor de verplaatsing duurder wordt dan wanneer de buffer niet zou worden gebruikt. Dit is met name het geval wanneer de buffer een niet-POD-type bevat.