C++
Оптимизация в C ++

Пустая оптимизация базового класса

Объект не может занимать менее 1 байт, так как тогда члены массива этого типа будут иметь один и тот же адрес. Таким образом, sizeof(T)>=1 всегда выполняется. Верно также, что производный класс не может быть меньше любого из его базовых классов. Однако, когда базовый класс пуст, его размер необязательно добавляется к производному классу:

class Base {};

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

В этом случае не требуется выделять байт для Base Derived чтобы иметь отдельный адрес для каждого типа объекта. Если выполняется пустая оптимизация базового класса (и не требуется заполнить), тогда sizeof(Derived) == sizeof(int) , то есть никакого дополнительного распределения для пустой базы не выполняется. Это возможно и с несколькими базовыми классами (в C ++ несколько баз не могут иметь один и тот же тип, поэтому из этого не возникает никаких проблем).

Обратите внимание, что это может быть выполнено только в том случае, если первый член Derived отличается по типу от любого из базовых классов. Сюда входят любые прямые или косвенные общие основания. Если это тот же тип, что и один из оснований (или общая база), требуется хотя бы выделение одного байта, чтобы гарантировать, что два разных объекта одного и того же типа не имеют одинакового адреса.

Введение в производительность

C и C ++ хорошо известны как высокопроизводительные языки - во многом из-за большого количества настроек кода, позволяя пользователю указывать производительность по выбору структуры.

При оптимизации важно провести оценку соответствующего кода и полностью понять, как будет использоваться код.

Общие ошибки оптимизации включают:

• Преждевременная оптимизация: сложный код может ухудшиться после оптимизации, тратя время и силы. Первым приоритетом должно быть написание правильного и поддерживаемого кода, а не оптимизированный код.
• Оптимизация для неправильного варианта использования: добавление накладных расходов для 1% может не стоить замедления для других 99%
• Микро-оптимизация: компиляторы делают это очень эффективно, и микро-оптимизация может даже повредить компиляторам возможность дальнейшей оптимизации кода

Типичными целями оптимизации являются:

• Делать меньше работы
• Использовать более эффективные алгоритмы / структуры
• Чтобы лучше использовать аппаратное обеспечение

Оптимизированный код может иметь отрицательные побочные эффекты, в том числе:

• Использование более высокой памяти
• Сложный код - трудно читать или поддерживать
• Компромисс API и дизайн кода

Оптимизация путем выполнения меньшего количества кода

Самый простой подход к оптимизации - это сокращение кода. Этот подход обычно дает фиксированное ускорение без изменения временной сложности кода.

Несмотря на то, что этот подход дает вам четкое ускорение, это только даст заметные улучшения, когда код называется много.

Удаление бесполезного кода

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

Выполнение кода только один раз

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

Аналогичный подход к этой оптимизации может быть использован для реализации стабильной версии 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;
}

Предотвращение бесполезного перераспределения и копирования / перемещения

В предыдущем примере мы уже предотвратили поиск в std :: set, однако std::vector все еще содержит растущий алгоритм, в котором он должен будет перераспределить его хранилище. Этого можно предотвратить, предварительно зарезервировав нужный размер.

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

Использование эффективных контейнеров

Оптимизация с использованием правильных структур данных в нужное время может изменить временную сложность кода.

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

Используя контейнер, который использует другую реализацию для хранения своих элементов (хэш-контейнер вместо дерева), мы можем преобразовать нашу реализацию в сложность N. В качестве побочного эффекта мы будем называть оператор сравнения для std :: string less, поскольку он нужно только вызывать, когда вставленная строка должна заканчиваться в том же ведре.

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

Оптимизация малых объектов

Оптимизация небольших объектов - это метод, который используется в структурах данных низкого уровня, например std::string (иногда называемый Short / Small String Optimization). Он предназначен для использования пространства стека в качестве буфера вместо некоторой выделенной памяти, если контент достаточно мал, чтобы вместиться в зарезервированное пространство.

Добавляя дополнительные накладные расходы памяти и дополнительные вычисления, он пытается предотвратить дорогостоящее распределение кучи. Преимущества этого метода зависят от использования и могут даже повредить производительность при неправильном использовании.

пример

Очень наивный способ реализации строки с этой оптимизацией:

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

Как вы можете видеть в приведенном выше коде, добавлена ​​дополнительная сложность, чтобы предотвратить некоторые new операции и delete . Кроме того, класс имеет больший объем памяти, который может не использоваться, за исключением нескольких случаев.

Часто он пытается кодировать значение bool _isAllocated в указателе _buffer с помощью бит-манипуляции для уменьшения размера одного экземпляра (бит 64-разрядной версии: может уменьшить размер на 8 байт). Оптимизация, которая возможна только тогда, когда известно, какие правила выравнивания платформы.

Когда использовать?

Поскольку эта оптимизация добавляет много сложности, не рекомендуется использовать эту оптимизацию для каждого отдельного класса. Это часто встречается в часто используемых структурах данных низкого уровня. В обычных реализациях standard library C ++ 11 можно найти std::basic_string<> использования в std::basic_string<> и std::function<> .

Поскольку эта оптимизация только предотвращает выделение памяти, когда хранящиеся данные меньше, чем буфер, это даст только преимущества, если класс часто используется с небольшими данными.

Конечным недостатком этой оптимизации является то, что при перемещении буфера требуется дополнительное усилие, что делает операцию перемещения более дорогой, чем когда буфер не будет использоваться. Это особенно верно, когда буфер содержит не-POD-тип.