C++
Optimisation en C ++

Optimisation de la classe de base vide

Un objet ne peut pas occuper moins de 1 octet, car les membres d'un tableau de ce type auraient la même adresse. Ainsi sizeof(T)>=1 tient toujours. Il est également vrai qu'une classe dérivée ne peut être inférieure à aucune de ses classes de base. Cependant, lorsque la classe de base est vide, sa taille n'est pas nécessairement ajoutée à la classe dérivée:

class Base {};

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

Dans ce cas, il n'est pas nécessaire d'allouer un octet à Base dans Derived pour avoir une adresse distincte par type et par objet. Si l'optimisation de la classe de base vide est effectuée (et qu'aucun remplissage n'est requis), alors sizeof(Derived) == sizeof(int) , c'est-à-dire qu'aucune allocation supplémentaire n'est effectuée pour la base vide. Cela est également possible avec plusieurs classes de base (en C ++, plusieurs bases ne peuvent pas avoir le même type, donc aucun problème ne se pose).

Notez que cela ne peut être effectué que si le premier membre de Derived diffère de type de l'une des classes de base. Cela inclut toute base commune directe ou indirecte. Si c'est le même type que l'une des bases (ou s'il y a une base commune), il faut au moins attribuer un seul octet pour s'assurer que deux objets distincts du même type n'ont pas la même adresse.

Introduction à la performance

C et C ++ sont bien connus en tant que langages haute performance - en grande partie en raison de la grande quantité de personnalisation du code, permettant à un utilisateur de spécifier les performances par choix de la structure.

Lors de l'optimisation, il est important d'évaluer le code pertinent et de comprendre complètement comment le code sera utilisé.

Les erreurs d'optimisation courantes incluent:

• Optimisation prématurée: le code complexe peut être moins performant après optimisation, perte de temps et d'effort. La première priorité devrait être d'écrire du code correct et maintenable , plutôt que du code optimisé.
• Optimisation pour le cas d'utilisation incorrect: l' ajout de frais généraux pour le 1% ne vaut peut-être pas le ralentissement pour les autres 99%
• Micro-optimisation: les compilateurs le font très efficacement et la micro-optimisation peut même nuire à la capacité des compilateurs à optimiser davantage le code

Les objectifs d'optimisation typiques sont:

• Faire moins de travail
• Utiliser des algorithmes / structures plus efficaces
• Pour mieux utiliser le matériel

Le code optimisé peut avoir des effets secondaires négatifs, notamment:

• Utilisation de mémoire supérieure
• Code complexe - difficile à lire ou à maintenir
• API et conception de code compromises

Optimiser en exécutant moins de code

L'approche la plus simple de l'optimisation consiste à exécuter moins de code. Cette approche donne généralement une accélération fixe sans changer la complexité temporelle du code.

Même si cette approche vous donne une accélération claire, cela ne vous apportera que des améliorations notables lorsque le code est appelé beaucoup.

Supprimer le code inutile

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

Faire du code une seule fois

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

Une approche similaire à cette optimisation peut être utilisé pour mettre en œuvre une version stable de 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;
}

Prévenir les réaffectations inutiles et la copie / déplacement

Dans l'exemple précédent, nous avons déjà empêché les recherches dans le std :: set, cependant le std::vector contient toujours un algorithme croissant, dans lequel il devra réallouer son stockage. Cela peut être évité en réservant d'abord pour la bonne taille.

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

Utiliser des conteneurs efficaces

Optimiser en utilisant les bonnes structures de données au bon moment peut modifier la complexité temporelle du code.

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

En utilisant un conteneur qui utilise une implémentation différente pour stocker ses éléments (conteneur de hachage au lieu de l'arbre), nous pouvons transformer notre implémentation en complexité N. En tant qu'effet secondaire, nous appellerons l'opérateur de comparaison pour std :: string less, car ne doit être appelé que lorsque la chaîne insérée doit se retrouver dans le même compartiment.

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

Optimisation des petits objets

L'optimisation des petits objets est une technique utilisée dans les structures de données de bas niveau, par exemple la std::string (parfois appelée optimisation de chaîne courte / petite). Il est destiné à utiliser l'espace de pile comme tampon au lieu de la mémoire allouée au cas où le contenu serait suffisamment petit pour tenir dans l'espace réservé.

En ajoutant des surcharges de mémoire et des calculs supplémentaires, il essaie d'empêcher une allocation de segment de mémoire coûteuse. Les avantages de cette technique dépendent de l'utilisation et peuvent même nuire à la performance s'ils sont utilisés de manière incorrecte.

Exemple

Une manière très naïve d'implémenter une chaîne avec cette optimisation serait la suivante:

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

Comme vous pouvez le voir dans le code ci-dessus, une complexité supplémentaire a été ajoutée afin d'empêcher certaines opérations new et de delete . En plus de cela, la classe a une empreinte mémoire plus grande qui pourrait ne pas être utilisée sauf dans quelques cas.

On essaie souvent de coder la valeur bool _isAllocated , dans le pointeur _buffer avec manipulation des bits pour réduire la taille d'une seule instance (intel 64 bit: peut réduire la taille de 8 octets). Une optimisation qui n'est possible que lorsque ses règles d'alignement sont connues.

Quand utiliser?

Comme cette optimisation ajoute beaucoup de complexité, il n'est pas recommandé d'utiliser cette optimisation sur chaque classe. Cela se rencontrera souvent dans les structures de données de bas niveau couramment utilisées. Dans les implémentations de standard library C ++ 11 courantes, on peut trouver des utilisations dans std::basic_string<> et std::function<> .

Comme cette optimisation n'empêche que les allocations de mémoire lorsque les données stockées sont plus petites que le tampon, cela ne donnera des avantages que si la classe est souvent utilisée avec de petites données.

Un dernier inconvénient de cette optimisation est que des efforts supplémentaires sont nécessaires lors du déplacement du tampon, ce qui rend l'opération de déplacement plus coûteuse que lorsque le tampon ne serait pas utilisé. Cela est particulièrement vrai lorsque le tampon contient un type non-POD.