C++
Optimering i C ++

Tom basklassoptimering

Ett objekt kan inte uppta mindre än 1 byte, då medlemmarna i en grupp av denna typ skulle ha samma adress. Således har sizeof(T)>=1 alltid. Det är också sant att en härledd klass inte kan vara mindre än någon av dess basklasser. Men när basklassen är tom läggs inte nödvändigtvis dess storlek till den härledda klassen:

class Base {};

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

I det här fallet är det inte nödvändigt att tilldela en byte för Base inom Derived att ha en distinkt adress per typ per objekt. Om tom basklassoptimering utförs (och ingen utfyllning krävs) sizeof(Derived) == sizeof(int) , det vill säga ingen ytterligare tilldelning görs för den tomma basen. Detta är också möjligt med flera basklasser (i C ++ kan flera baser inte ha samma typ, så inga problem uppstår av det).

Observera att detta endast kan utföras om den första medlemmen i Derived skiljer sig i typ från någon av basklasserna. Detta inkluderar alla direkta eller indirekta gemensamma baser. Om det är samma typ som en av baserna (eller det finns en gemensam bas) krävs åtminstone tilldelning av en enda byte för att säkerställa att inga två distinkta objekt av samma typ har samma adress.

Introduktion till prestanda

C och C ++ är välkända som högpresterande språk - till stor del på grund av den stora mängden kodanpassning, vilket gör det möjligt för en användare att specificera prestanda genom val av struktur.

När du optimerar är det viktigt att jämföra relevant kod och helt förstå hur koden kommer att användas.

Vanliga optimeringsfel inkluderar:

• För tidig optimering: Komplex kod kan fungera sämre efter optimering, slösa tid och ansträngning. Första prioriteringen bör vara att skriva korrekt och underhållbar kod snarare än optimerad kod.
• Optimering för fel användning: Att lägga till omkostnader för 1% kanske inte är värt att avmattningen för de andra 99%
• Mikrooptimering: Kompilatorer gör detta mycket effektivt och mikrooptimering kan till och med skada kompilatorernas förmåga att ytterligare optimera koden

Typiska optimeringsmål är:

• Att göra mindre arbete
• För att använda effektivare algoritmer / strukturer
• För att bättre använda hårdvaran

Optimerad kod kan ha negativa biverkningar, inklusive:

• Högre minnesanvändning
• Komplex kod - att vara svår att läsa eller underhålla
• Kompromissad API och koddesign

Optimera genom att köra mindre kod

Det mest enkla sättet att optimera är genom att utföra mindre kod. Detta tillvägagångssätt ger vanligtvis en fast hastighet utan att ändra kodens komplexitet.

Även om det här tillvägagångssättet ger dig en tydlig speedup, kommer detta endast att uppvisa märkbara förbättringar när koden kallas mycket.

Tar bort värdelös kod

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

Gör kod bara en gång

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

En liknande strategi för denna optimering kan användas för att implementera en stabil version av 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;
}

Förhindrar värdelös omfördelning och kopiering / flyttning

I det föregående exemplet förhindrade vi redan uppslag i std :: set, men std::vector innehåller fortfarande en växande algoritm, där den måste omfördela sin lagring. Detta kan förhindras genom att först reservera för rätt storlek.

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

Använd effektiva behållare

Optimering genom att använda rätt datastrukturer i rätt tid kan ändra kodens komplexitet.

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

Genom att använda en behållare som använder en annan implementering för att lagra dess element (hashcontainer istället för träd), kan vi omvandla vår implementering till komplexitet N. Som en bieffekt kommer vi att kalla jämförelseoperatören för std :: sträng mindre, eftersom det måste bara ringas när den infogade strängen ska hamna i samma hink.

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

Lite objektoptimering

Optimering av små objekt är en teknik som används inom datastrukturer på låg nivå, till exempel std::string (kallas ibland kort / liten strängoptimering). Det är tänkt att använda stapelutrymme som buffert istället för tilldelat minne om innehållet är tillräckligt litet för att passa in i det reserverade utrymmet.

Genom att lägga till extra minneskostnader och extra beräkningar försöker det förhindra en dyr tilldelning av hög. Fördelarna med denna teknik är beroende av användningen och kan till och med skada prestanda om de används felaktigt.

Exempel

Ett mycket naivt sätt att implementera en sträng med denna optimering skulle följande:

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

Som du kan se i koden ovan har en viss extra komplexitet lagts till för att förhindra new och delete operationer. Dessutom har klassen ett större minnesfotavtryck som kanske inte används förutom i några fall.

Det försöks ofta att koda boolvärdet _isAllocated , inom pekaren _buffer med bitmanipulation för att minska storleken på en enda instans (intel 64 bit: Kan minska storleken med 8 byte). En optimering som bara är möjlig när det är känt vad plattformens justeringsregler är.

När ska man använda?

Eftersom denna optimering lägger till mycket komplexitet, rekommenderas det inte att använda denna optimering i varje klass. Det kommer ofta att uppstå i vanligt använda datastrukturer på låg nivå. I vanliga C ++ 11- standard library kan man hitta användningar i std::basic_string<> och std::function<> .

Eftersom denna optimering endast förhindrar minnesallokeringar när den lagrade datan är mindre än bufferten kommer det bara att ge fördelar om klassen ofta används med små data.

En sista nackdel med denna optimering är att extra ansträngning krävs när man flyttar bufferten, vilket gör flyttningen dyrare än när bufferten inte skulle användas. Detta gäller särskilt när bufferten innehåller en icke-POD-typ.