C++
Optimización en C ++

Optimización de clase base vacía

Un objeto no puede ocupar menos de 1 byte, ya que entonces los miembros de una matriz de este tipo tendrían la misma dirección. Por lo tanto, sizeof(T)>=1 siempre se cumple. También es cierto que una clase derivada no puede ser más pequeña que cualquiera de sus clases base. Sin embargo, cuando la clase base está vacía, su tamaño no necesariamente se agrega a la clase derivada:

class Base {};

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

En este caso, no es necesario asignar un byte para Base dentro de Derived para tener una dirección distinta por tipo por objeto. Si se realiza la optimización de la clase base vacía (y no se requiere relleno), entonces sizeof(Derived) == sizeof(int) , es decir, no se realiza ninguna asignación adicional para la base vacía. Esto también es posible con varias clases base (en C ++, las bases múltiples no pueden tener el mismo tipo, por lo que no surgen problemas).

Tenga en cuenta que esto solo se puede realizar si el primer miembro de Derived difiere en tipo de cualquiera de las clases base. Esto incluye cualquier base común directa o indirecta. Si es el mismo tipo que una de las bases (o hay una base común), se requiere al menos la asignación de un solo byte para garantizar que no haya dos objetos distintos del mismo tipo que tengan la misma dirección.

Introducción al rendimiento

C y C ++ son conocidos como lenguajes de alto rendimiento, en gran parte debido a la gran cantidad de personalización del código, lo que permite a un usuario especificar el rendimiento mediante la elección de la estructura.

Cuando se optimiza, es importante comparar el código relevante y comprender completamente cómo se utilizará el código.

Los errores comunes de optimización incluyen:

• Optimización prematura: el código complejo puede tener peores resultados después de la optimización, desperdiciando tiempo y esfuerzo. La primera prioridad debe ser escribir el código correcto y mantenible , en lugar del código optimizado.
• Optimización para el caso de uso incorrecto: agregar una sobrecarga para el 1% podría no valer la pena para el otro 99%
• Microoptimización: los compiladores hacen esto muy eficientemente y la microoptimización puede incluso afectar la capacidad de los compiladores para optimizar aún más el código.

Los objetivos típicos de optimización son:

• Hacer menos trabajo
• Usar algoritmos / estructuras más eficientes.
• Para hacer un mejor uso del hardware.

El código optimizado puede tener efectos secundarios negativos, que incluyen:

• Mayor uso de memoria
• Código complejo: ser difícil de leer o mantener
• API comprometida y diseño de código

Optimizando ejecutando menos código.

El enfoque más sencillo para optimizar es ejecutando menos código. Este enfoque generalmente proporciona una aceleración fija sin cambiar la complejidad de tiempo del código.

A pesar de que este enfoque le proporciona una clara aceleración, esto solo proporcionará mejoras notables cuando el código se llame mucho.

Eliminando código inútil

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

Haciendo código solo una vez

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

Se puede utilizar un enfoque similar a esta optimización para implementar una versión estable de dispositivos 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;
}

Evitar la reasignación inútil y copiar / mover

En el ejemplo anterior, ya evitamos las búsquedas en std :: set, sin embargo, std::vector todavía contiene un algoritmo creciente, en el que tendrá que reasignar su almacenamiento. Esto se puede prevenir reservando primero para el tamaño correcto.

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

Usando contenedores eficientes

La optimización mediante el uso de las estructuras de datos correctas en el momento adecuado puede cambiar la complejidad del tiempo del código.

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

Al usar un contenedor que usa una implementación diferente para almacenar sus elementos (hash container en lugar de tree), podemos transformar nuestra implementación en la complejidad N. Como efecto secundario, llamaremos al operador de comparación para std :: string less, ya que solo debe llamarse cuando la cadena insertada debe terminar en el mismo cubo.

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

Optimización de objetos pequeños

La optimización de objetos pequeños es una técnica que se utiliza en estructuras de datos de bajo nivel, por ejemplo, std::string (a veces denominada optimización de cadena pequeña / corta). Está destinado a usar el espacio de pila como un búfer en lugar de alguna memoria asignada en caso de que el contenido sea lo suficientemente pequeño como para caber dentro del espacio reservado.

Al agregar una sobrecarga de memoria adicional y cálculos adicionales, intenta evitar una asignación de pila costosa. Los beneficios de esta técnica dependen del uso y pueden incluso afectar el rendimiento si se usan incorrectamente.

Ejemplo

Una forma muy ingenua de implementar una cadena con esta optimización sería lo siguiente:

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

Como puede ver en el código anterior, se ha agregado cierta complejidad adicional para evitar algunas operaciones new y de delete . Además de esto, la clase tiene una huella de memoria mayor que no se puede usar, excepto en un par de casos.

A menudo se intenta codificar el valor bool _isAllocated , dentro del puntero _buffer con la manipulación de bits para reducir el tamaño de una instancia (Intel 64 bit: podría reducir el tamaño en 8 bytes). Una optimización que solo es posible cuando se conoce cuáles son las reglas de alineación de la plataforma.

¿Cuándo usar?

Como esta optimización agrega mucha complejidad, no se recomienda usar esta optimización en todas las clases. A menudo se encontrará en estructuras de datos de bajo nivel de uso común. En las implementaciones comunes de standard library C ++ 11 se pueden encontrar usos en std::basic_string<> y std::function<> .

Como esta optimización solo evita las asignaciones de memoria cuando los datos almacenados son más pequeños que el búfer, solo dará beneficios si la clase se usa a menudo con datos pequeños.

Un inconveniente final de esta optimización es que se requiere un esfuerzo adicional al mover el búfer, lo que hace que la operación de movimiento sea más costosa que cuando no se usaría el búfer. Esto es especialmente cierto cuando el búfer contiene un tipo que no es POD.