C++
Optymalizacja w C ++

Optymalizacja pustej klasy podstawowej

Obiekt nie może zajmować mniej niż 1 bajt, ponieważ wówczas elementy tablicy tego typu miałyby ten sam adres. Zatem sizeof(T)>=1 zawsze obowiązuje. Prawdą jest również to, że klasa pochodna nie może być mniejsza niż żadna z jej klas podstawowych. Jednak gdy klasa podstawowa jest pusta, jej rozmiar niekoniecznie jest dodawany do klasy pochodnej:

class Base {};

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

W tym przypadku nie jest konieczne przydzielanie bajtu dla Base w Derived aby mieć odrębny adres dla typu dla obiektu. Jeśli przeprowadzana jest optymalizacja pustej klasy bazowej (i nie jest wymagane wypełnianie), to sizeof(Derived) == sizeof(int) , to znaczy, że dla pustej bazy nie jest wykonywana dodatkowa alokacja. Jest to możliwe również w przypadku wielu klas bazowych (w C ++ wiele baz nie może mieć tego samego typu, więc nie wynikają z tego żadne problemy).

Zauważ, że można tego dokonać tylko wtedy, gdy pierwszy element Derived różni się typem od dowolnej klasy podstawowej. Obejmuje to wszelkie bezpośrednie lub pośrednie wspólne bazy. Jeśli jest tego samego typu co jedna z baz (lub istnieje wspólna baza), wymagane jest przynajmniej przydzielenie jednego bajtu, aby upewnić się, że żadne dwa różne obiekty tego samego typu nie mają tego samego adresu.

Wprowadzenie do wydajności

C i C ++ są dobrze znane jako języki o wysokiej wydajności - głównie ze względu na dużą liczbę dostosowań kodu, umożliwiając użytkownikowi określenie wydajności poprzez wybór struktury.

Podczas optymalizacji ważne jest, aby przeprowadzić test porównawczy odpowiedniego kodu i całkowicie zrozumieć, w jaki sposób kod zostanie wykorzystany.

Typowe błędy optymalizacji obejmują:

• Przedwczesna optymalizacja: złożony kod może działać gorzej po optymalizacji, marnowaniu czasu i wysiłku. Pierwszym priorytetem powinno być pisanie poprawnego i łatwego do utrzymania kodu, a nie kodu zoptymalizowanego.
• Optymalizacja dla niewłaściwego przypadku użycia: dodanie kosztów ogólnych dla 1% może nie być warte spowolnienia dla pozostałych 99%
• Mikrooptymalizacja: kompilatory wykonują to bardzo skutecznie, a mikrooptymalizacja może nawet zaszkodzić zdolności kompilatorów do dalszej optymalizacji kodu

Typowe cele optymalizacji to:

• Aby wykonać mniej pracy
• Aby użyć wydajniejszych algorytmów / struktur
• Aby lepiej wykorzystać sprzęt

Zoptymalizowany kod może mieć negatywne skutki uboczne, w tym:

• Wyższe zużycie pamięci
• Skomplikowany kod jest trudny do odczytania lub utrzymania
• Kompromisowy interfejs API i projekt kodu

Optymalizacja poprzez wykonanie mniej kodu

Najprostszym podejściem do optymalizacji jest wykonanie mniejszej ilości kodu. Takie podejście zazwyczaj zapewnia stałe przyspieszenie bez zmiany złożoności czasowej kodu.

Chociaż takie podejście zapewnia wyraźne przyspieszenie, da to zauważalną poprawę tylko wtedy, gdy kod jest często wywoływany.

Usuwanie niepotrzebnego kodu

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

Robię kod tylko raz

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

Podobne podejście do tej optymalizacji można zastosować do wdrożenia stabilnej wersji 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;
}

Zapobieganie bezużytecznemu ponownemu przydzielaniu i kopiowaniu / przenoszeniu

W poprzednim przykładzie już zapobiegaliśmy przeszukiwaniu zestawu std :: set, jednak std::vector nadal zawiera rosnący algorytm, w którym będzie musiał ponownie przydzielić pamięć. Można temu zapobiec, rezerwując najpierw odpowiedni rozmiar.

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

Używanie wydajnych pojemników

Optymalizacja przy użyciu odpowiednich struktur danych we właściwym czasie może zmienić złożoność czasową kodu.

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

Używając kontenera, który wykorzystuje inną implementację do przechowywania swoich elementów (kontener hash zamiast drzewa), możemy przekształcić naszą implementację w złożoność N. Jako efekt uboczny wywołamy operator porównania dla std :: string mniej, ponieważ musi być wywołany tylko wtedy, gdy wstawiony łańcuch powinien skończyć w tym samym wiadrze.

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

Optymalizacja małych obiektów

Optymalizacja małych obiektów jest techniką stosowaną w strukturach danych niskiego poziomu, na przykład std::string (czasami określany jako Optymalizacja krótkiego / małego łańcucha). Ma to na celu wykorzystanie przestrzeni stosu jako bufora zamiast pewnej przydzielonej pamięci w przypadku, gdy zawartość jest wystarczająco mała, aby zmieścić się w zarezerwowanym miejscu.

Dodając dodatkowy narzut pamięci i dodatkowe obliczenia, stara się zapobiec drogiej alokacji sterty. Korzyści z tej techniki zależą od użycia, a nawet mogą pogorszyć wydajność, jeśli zostaną niewłaściwie użyte.

Przykład

Bardzo naiwny sposób implementacji łańcucha przy tej optymalizacji wyglądałby następująco:

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

Jak widać w powyższym kodzie, dodano dodatkową złożoność, aby zapobiec niektórym new operacjom delete i delete . Ponadto klasa ma większy obszar pamięci, który może nie być używany z wyjątkiem kilku przypadków.

Często próbuje się zakodować wartość bool _isAllocated , w ramach wskaźnika _buffer z manipulacją bitami w celu zmniejszenia rozmiaru pojedynczej instancji (intel 64 bit: Mógł zmniejszyć rozmiar o 8 bajtów). Optymalizacja możliwa tylko wtedy, gdy wiadomo, jakie są reguły wyrównania platformy.

Kiedy użyć?

Ponieważ ta optymalizacja powoduje wiele komplikacji, nie zaleca się korzystania z tej optymalizacji w każdej klasie. Często spotyka się go w często używanych strukturach danych niskiego poziomu. W typowych implementacjach standard library C ++ 11 można znaleźć zastosowania w std::basic_string<> i std::function<> .

Ponieważ ta optymalizacja zapobiega alokacji pamięci tylko wtedy, gdy przechowywane dane są mniejsze niż bufor, przyniesie to korzyści tylko wtedy, gdy klasa jest często używana z małymi danymi.

Ostatnią wadą tej optymalizacji jest to, że wymagany jest dodatkowy wysiłek podczas przenoszenia bufora, co powoduje, że operacja przenoszenia jest droższa niż wtedy, gdy bufor nie byłby używany. Jest to szczególnie prawdziwe, gdy bufor zawiera typ inny niż POD.